Article ID: | iaor20111346 |
Volume: | 17 |
Issue: | 1 |
Start Page Number: | 23 |
End Page Number: | 37 |
Publication Date: | Feb 2011 |
Journal: | Journal of Heuristics |
Authors: | Paias Ana, Gouveia Luis, Sharma Dushyant |
Keywords: | graphs, programming: dynamic |
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.