Enhanced exact solution methods for the Team Orienteering Problem
- 6 July 2015
- journal article
- Published by Taylor & Francis in International Journal of Production Research
- Vol. 54 (2) , 591-601
Abstract
The Team Orienteering Problem (TOP) is one of the most investigated problems in the family of vehicle routing problems with profits. In this paper, we propose a Branch-and-Price approach to find proven optimal solutions to TOP. The pricing sub-problem is solved by a bounded bidirectional dynamic programming algorithm with decremental state space relaxation featuring a two-phase dominance rule relaxation. The new method is able to close 17 previously unsolved benchmark instances. In addition, we propose a Branch-and-Cut-and-Price approach using subset-row inequalities and show the effectiveness of these cuts in solving TOPKeywords
This publication has 18 references indexed in Scilit:
- A survey on algorithmic approaches for solving tourist trip design problemsJournal of Heuristics, 2014
- An effective PSO-inspired algorithm for the team orienteering problemEuropean Journal of Operational Research, 2013
- A Branch-and-Cut Algorithm for Solving the Team Orienteering Problem2013
- A memetic algorithm for the team orienteering problem4OR, 2009
- Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time WindowsOperations Research, 2008
- Metaheuristics for the team orienteering problemJournal of Heuristics, 2006
- An exact algorithm for team orienteering problems4OR, 2006
- An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problemsNetworks, 2004
- An optimal solution procedure for the multiple tour maximum collection problem using column generationComputers & Operations Research, 1999
- The team orienteering problemEuropean Journal of Operational Research, 1996