A branch-and-cut algorithm for the Team Orienteering Problem

Nicola Bianchessi, Renata Mansini, M. Grazia Speranza

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

The Team Orienteering Problem aims at maximizing the total amount of profit collected by a fleet of vehicles while not exceeding a predefined travel time limit on each vehicle. In the last years, several exact methods based on different mathematical formulations were proposed. In this paper, we present a new two-index formulation with a polynomial number of variables and constraints. This compact formulation, reinforced by connectivity constraints, was solved by means of a branch-and-cut algorithm. The total number of instances solved to optimality is 327 of 387 benchmark instances, 26 more than any previous method. Moreover, 24 not previously solved instances were closed to optimality.

Original languageEnglish
Pages (from-to)627-635
Number of pages9
JournalInternational Transactions in Operational Research
Volume25
Issue number2
DOIs
Publication statusPublished - 1 Mar 2018
Externally publishedYes

Keywords

  • branch-and-cut algorithm
  • Team Orienteering Problem
  • two-index mathematical formulation

Fingerprint Dive into the research topics of 'A branch-and-cut algorithm for the Team Orienteering Problem'. Together they form a unique fingerprint.

Cite this