Restricted dynamic programming based neighborhoods for the hop-constrained minimum spanning tree problem |
| |
Authors: | Luis Gouveia Ana Paias Dushyant Sharma |
| |
Institution: | 1.Faculdade de Ciências, Departamento de Estatística e Investiga??o Operacional, Centro de Investiga??o Operacional,Universidade de Lisboa,Lisbon,Portugal;2.Department of Industrial and Operations Engineering,University of Michigan,Ann Arbor,USA |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|