Fast heuristics for the Steiner tree problem with revenues,budget and hop constraints |
| |
| Authors: | Alysson M Costa Jean-François Cordeau Gilbert Laporte |
| |
| Institution: | 1. Instituto de Ciências Matemáticas e de Computação, Universidade de São Paulo, CP 668, São Carlos 13560-970, São Paulo, Brazil;2. Centre for Research on Transportation and Canada Research Chair in Distribution Management, HEC Montréal, 3000 chemin de la Côte-Sainte-Catherine, Montréal, Canada, H3T 2A7;3. Centre for Research on Transportation and Canada Research Chair in Logistics and Transportation, HEC Montréal, 3000 chemin de la Côte-Sainte-Catherine, Montréal, Canada, H3T 2A7 |
| |
| Abstract: | This article describes and compares three heuristics for a variant of the Steiner tree problem with revenues, which includes budget and hop constraints. First, a greedy method which obtains good approximations in short computational times is proposed. This initial solution is then improved by means of a destroy-and-repair method or a tabu search algorithm. Computational results compare the three methods in terms of accuracy and speed. |
| |
| Keywords: | Prize collecting Network design Steiner tree problem Budget Hop constraints Heuristics Tabu search |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
