[Home ] [Archive]    
:: Main :: About :: Current Issue :: Archive :: Search :: Submit :: Registration ::
Main Menu
Home::
Journal Information::
Articles archive::
Submission Instruction::
Registration::
Submit article::
Site Facilities::
Contact us::
::
Google Scholar

Citation Indices from GS

AllSince 2019
Citations85353571
h-index127
i10-index136

Search in website

Advanced Search
Receive site information
Enter your Email in the following box to receive the site news and information.
:: Volume 6, Issue 1 (3-2015) ::
IJOR 2015, 6(1): 65-78 Back to browse issues page
A Metaheuristic Algorithm for the Minimum Routing Cost Spanning Tree Problem
Sattar Sattari , Didehvar
Amirkabir University , s.sattari@aut.ac.ir
Abstract:   (13292 Views)

The routing cost of a spanning tree in a weighted and connected graph is defined as the total length of paths between all pairs of vertices. The objective of the minimum routing cost spanning tree problem is to find a spanning tree such that its routing cost is minimum. This is an NP-Hard problem that we present a GRASP with path-relinking metaheuristic algorithm for it. GRASP is a multi-start algorithm that in each iteration constructs a randomized greedy solution and applies local search to it. Path-relinking stores elite solutions and to find better solutions explores the paths between different solutions. Experimental results show the performance of our algorithm on many benchmark problems compared to the other algorithms.

Keywords: Graph, Spanning Tree, Routing Cost, Metaheuristic.
Full-Text [PDF 488 kb]   (16695 Downloads)    
Type of Study: Original | Subject: Discrete Optimization
Received: 2017/03/27 | Accepted: 2017/03/27 | Published: 2017/03/27
Send email to the article author

Add your comments about this article
Your username or Email:

CAPTCHA


XML     Print



Rights and permissions
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Volume 6, Issue 1 (3-2015) Back to browse issues page
مجله انجمن ایرانی تحقیق در عملیات Iranian Journal of Operations Research
Persian site map - English site map - Created in 0.05 seconds with 38 queries by YEKTAWEB 4645