Enhanced exact solution methods for the Team Orienteering Problem |
| |
| Authors: | Morteza Keshtkaran Koorush Ziarati Andrea Bettinelli Daniele Vigo |
| |
| Affiliation: | 1. Department of Electrical and Computer Engineering, Shiraz University, Shiraz, Iran.;2. Department of Electrical, Electronic, and Information Engineering, University of Bologna, Bologna, Italy. |
| |
| 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. |
| |
| Keywords: | Logistics Team Orienteering Problem Vehicle Routing Problem Column Generation Branch-and-Cut-and-Price |
|
|
