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 (see Butt and Cavalier (1994), Archetti, Speranza, and Vigo (2014)). Motivated by a real-life Automated Teller Machine (ATM) 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), in which the total gathered profit can be strictly lower than the sum of the individual collected profits. We present exact algorithms based on column generation. An extensive computational analysis shows that the designed algorithms can efficiently solve synthetic and real-life TOPO instances. Moreover, the proposed algorithms are competitive with the best exact solution methods from the literature for the TOP. In particular, the algorithms can find the optimal solution for 371 out of the 387 benchmark TOP instances introduced by Chao, Golden, and Wasil (1996), 33 of which are closed for the first time.
The Team Orienteering Problem with Overlaps / C. Orlis, N. Bianchessi, W. Dullaert, R. Roberti. ((Intervento presentato al convegno International Conference on Optimization and Decision Science, XLIX Annual Meeting of AIRO - Italian Operations Research Society - ODS 2019 tenutosi a Genova nel 2019.
The Team Orienteering Problem with Overlaps
N. Bianchessi;
2019
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 (see Butt and Cavalier (1994), Archetti, Speranza, and Vigo (2014)). Motivated by a real-life Automated Teller Machine (ATM) 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), in which the total gathered profit can be strictly lower than the sum of the individual collected profits. We present exact algorithms based on column generation. An extensive computational analysis shows that the designed algorithms can efficiently solve synthetic and real-life TOPO instances. Moreover, the proposed algorithms are competitive with the best exact solution methods from the literature for the TOP. In particular, the algorithms can find the optimal solution for 371 out of the 387 benchmark TOP instances introduced by Chao, Golden, and Wasil (1996), 33 of which are closed for the first time.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.