Heuristics for a cash-collection routing problem with a cluster-first route-second approach

Singh B, Oberfichtner L, Ivliev S (2022)

Publication Type: Journal article

Publication year: 2022

Journal

Annals of Operations Research Springer Verlag (Germany)

DOI: 10.1007/s10479-022-04883-1

Abstract

Motivated by a routing problem faced by banks to enhance their encashment services in the city of Perm, Russia, we solve versions of the traveling salesman problem (TSP) with clustering. To minimize the risk of theft, suppliers seek to operate multiple vehicles and determine an efficient routing; and, a single vehicle serves a set of locations that forms a cluster. This need to form independent clusters—served by distinct vehicles—allows the use of the so-called cluster-first route-second approach. We are especially interested in the use of heuristics that are easily implementable and understandable by practitioners and require only the use of open-source solvers. To this end, we provide a short survey of 13 such heuristics for solving the TSP, five for clustering the set of locations, and three to determine an optimal number of clusters—all using data from Perm. To demonstrate the practicality and efficiency of the heuristics, we further compare our heuristic solutions against the optimal tours. We then provide statistical guarantees on the quality of our solution. All of our anonymized code is publicly available allowing extensions by practitioners, and serves as a decision-analytic framework for both clustering data and solving a TSP.

Authors with CRIS profile

Bismark Singh Lehrstuhl für Analytics & Mixed-Integer Optimization

Involved external institutions

Perm State National Research University / Пермский государственный национальный исследовательский университет RU Russian Federation (RU) Fraunhofer-Institut für Werkzeugmaschinen und Umformtechnik (IWU) DE Germany (DE)

How to cite

APA:

Singh, B., Oberfichtner, L., & Ivliev, S. (2022). Heuristics for a cash-collection routing problem with a cluster-first route-second approach. Annals of Operations Research. https://dx.doi.org/10.1007/s10479-022-04883-1

MLA:

Singh, Bismark, Lena Oberfichtner, and Sergey Ivliev. "Heuristics for a cash-collection routing problem with a cluster-first route-second approach." Annals of Operations Research (2022).

BibTeX: Download