Enhanced exact solution methods for the Team Orienteering Problem

M. Keshtkaran, K. Ziarati, A. Bettinelli, D. Vigo

Research output: Contribution to JournalArticleAcademicpeer-review

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.
Original languageEnglish
Pages (from-to)591-601
JournalInternational Journal of Production Research
Volume54
Issue number2
Early online date6 Jul 2015
DOIs
Publication statusPublished - 2016

Fingerprint

Dive into the research topics of 'Enhanced exact solution methods for the Team Orienteering Problem'. Together they form a unique fingerprint.

Cite this