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.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.