Published Online:https://doi.org/10.1287/trsc.2019.0923

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.

INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.