The Team Orienteering Problem with Overlaps

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.