[Home ] [Archive]    
:: Main :: About :: Current Issue :: Archive :: Search :: Submit :: Registration ::
:: 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:   (5221 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]   (3170 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



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.04 seconds with 30 queries by YEKTAWEB 4241