Restricted dynamic programming based neighborhoods for the hop‐constrained minimum spanning tree problem

Restricted dynamic programming based neighborhoods for the hop‐constrained minimum spanning tree problem

0.00 Avg rating0 Votes
Article ID: iaor20111346
Volume: 17
Issue: 1
Start Page Number: 23
End Page Number: 37
Publication Date: Feb 2011
Journal: Journal of Heuristics
Authors: , ,
Keywords: graphs, programming: dynamic
Abstract:

In this paper we develop, study and test new neighborhood structures for the Hop‐constrained Minimum Spanning Tree Problem (HMSTP). These neighborhoods are defined by restricted versions of a new dynamic programming formulation for the problem and provide a systematic way of searching neighborhood structures based on node‐level exchanges. We have also developed several local search methods that are based on the new neighborhoods. Computational experiments for a set of benchmark instances with up to 80 nodes show that the more elaborate methods produce in a quite fast way, heuristic solutions that are, for all cases, within 2% of the optimum.

Reviews

Required fields are marked *. Your email address will not be published.