fa 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 دانشگاه صنعتی امیرکبیر