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 TOP.
Enhanced exact solution methods for the Team Orienteering Problem / Keshtkaran, M.; Ziarati, K.; Bettinelli, A.; Vigo, D.. - In: INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH. - ISSN 0020-7543. - STAMPA. - 54:2(2016), pp. 591-601. [10.1080/00207543.2015.1058982]
Enhanced exact solution methods for the Team Orienteering Problem
BETTINELLI, ANDREA;VIGO, DANIELE
2016
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 TOP.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
