A branch‐and‐cut algorithm for the Team Orienteering Problem. (17th May 2017)

• Record Type: Journal Article
• Authors: Bianchessi, Nicola; Mansini, Renata; Speranza, M. Grazia
• Is Part Of: International transactions in operational research. Volume 25:Number 2(2018)
• Page Start: 627
• Page End: 635
• Publication Date: 2017-05-17
• Subjects: Team Orienteering Problem -- two‐index mathematical formulation -- branch‐and‐cut algorithm; Operations research -- Periodicals; 003
• DOI: 10.1111/itor.12422
• Languages: English
• ISSNs: 0969-6016

Abstract

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.