The team orienteering problem (TOP) aims at finding a set of routes subject to maximum route duration constraints that maximize the total collected profit from a set of customers. Motivated by a real-life automated teller machine cash replenishment problem that seeks for routes maximizing the number of bank account holders having access to cash withdrawal, we investigate a generalization of the TOP that we call the team orienteering problem with overlaps (TOPO). For this problem, the sum of individual profits may overestimate the real profit. We present exact solution methods based on column generation and a metaheuristic based on large neighborhood search to solve the TOPO. An extensive computational analysis shows that the proposed solution methods can efficiently solve synthetic and real-life TOPO instances. Moreover, the proposed methods are competitive with the best algorithms from the literature for the TOP. In particular, the exact methods can find the optimal solution of 371 of the 387 benchmark TOP instances, 33 of which are closed for the first time.
The Team Orienteering Problem with Overlaps : An Application in Cash Logistics / C. Orlis, N. Bianchessi, R. Roberti, W. Dullaert. - In: TRANSPORTATION SCIENCE. - ISSN 0041-1655. - 54:2(2020 Mar), pp. 470-487. [10.1287/trsc.2019.0923]
The Team Orienteering Problem with Overlaps : An Application in Cash Logistics
N. BianchessiCo-primo
;
2020
Abstract
The team orienteering problem (TOP) aims at finding a set of routes subject to maximum route duration constraints that maximize the total collected profit from a set of customers. Motivated by a real-life automated teller machine cash replenishment problem that seeks for routes maximizing the number of bank account holders having access to cash withdrawal, we investigate a generalization of the TOP that we call the team orienteering problem with overlaps (TOPO). For this problem, the sum of individual profits may overestimate the real profit. We present exact solution methods based on column generation and a metaheuristic based on large neighborhood search to solve the TOPO. An extensive computational analysis shows that the proposed solution methods can efficiently solve synthetic and real-life TOPO instances. Moreover, the proposed methods are competitive with the best algorithms from the literature for the TOP. In particular, the exact methods can find the optimal solution of 371 of the 387 benchmark TOP instances, 33 of which are closed for the first time.File | Dimensione | Formato | |
---|---|---|---|
topo-POSTPRINT.pdf
accesso aperto
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
473.63 kB
Formato
Adobe PDF
|
473.63 kB | Adobe PDF | Visualizza/Apri |
trsc.2019.0923.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
818.34 kB
Formato
Adobe PDF
|
818.34 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.