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.

A branch-and-cut algorithm for the Team Orienteering Problem / N. Bianchessi, R. Mansini, M.G. Speranza. - In: INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH. - ISSN 0969-6016. - 25:2(2018), pp. 627-635. [10.1111/itor.12422]

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

N. Bianchessi
;
2018

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.
Team Orienteering Problem; two-index mathematical formulation; branch-and-cut algorithm
Settore MAT/09 - Ricerca Operativa
Settore INF/01 - Informatica
2018
Article (author)
File in questo prodotto:
File Dimensione Formato  
bc_top_reviewed.pdf

Open Access dal 29/07/2020

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 233.74 kB
Formato Adobe PDF
233.74 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/609523
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 53
  • ???jsp.display-item.citation.isi??? 47
social impact