The team orienteering problem with overlaps: An application in cash logistics

Christos Orlis, Nicola Bianchessi, Roberto Roberti, Wout Dullaert

Research output: Contribution to JournalArticleAcademicpeer-review

20 Downloads (Pure)

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.

Original languageEnglish
Pages (from-to)470-487
Number of pages18
JournalTransportation Science
Volume54
Issue number2
Early online date4 Mar 2020
DOIs
Publication statusPublished - Mar 2020

Keywords

  • Cash distribution
  • Column generation
  • Metaheuristic
  • Routing with profits
  • Team orienteering

Fingerprint Dive into the research topics of 'The team orienteering problem with overlaps: An application in cash logistics'. Together they form a unique fingerprint.

Cite this