Iranian Journal of Operations Research
مجله انجمن ایرانی تحقیق در عملیات
IJOR
Basic Sciences
http://iors.ir/journal
0
user
2008-1189
10.29252/iors
en
jalali
1393
12
1
gregorian
2015
3
1
6
1
online
1
fulltext
fa
A Metaheuristic Algorithm for the Minimum Routing Cost Spanning Tree Problem
Discrete Optimization
Discrete Optimization
پژوهشی
Original
<p>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.</p>
Graph, Spanning Tree, Routing Cost, Metaheuristic.
65
78
http://iors.ir/journal/browse.php?a_code=A-10-538-1&slc_lang=fa&sid=1
Sattar
Sattari
ستار
ستاری
s.sattari@aut.ac.ir
`00031947532846001524`

00031947532846001524
Yes
Amirkabir University
دانشگاه صنعتی امیرکبیر
Didehvar
دیده ور
didehvar@aut.ac.ir.
`00031947532846001525`

00031947532846001525
No
Amirkabir University
دانشگاه صنعتی امیرکبیر