IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v322y2023i1d10.1007_s10479-022-04883-1.html
   My bibliography  Save this article

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

Author

Listed:
  • Bismark Singh

    (Friedrich-Alexander-Universität Erlangen-Nürnberg
    Friedrich-Alexander-Universität Erlangen-Nürnberg)

  • Lena Oberfichtner

    (Fraunhofer Institute for Machine Tools and Forming Technology IWU)

  • Sergey Ivliev

    (Perm State University)

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.

Suggested Citation

  • Bismark Singh & Lena Oberfichtner & Sergey Ivliev, 2023. "Heuristics for a cash-collection routing problem with a cluster-first route-second approach," Annals of Operations Research, Springer, vol. 322(1), pages 413-440, March.
  • Handle: RePEc:spr:annopr:v:322:y:2023:i:1:d:10.1007_s10479-022-04883-1
    DOI: 10.1007/s10479-022-04883-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-022-04883-1
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10479-022-04883-1?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Gilbert Laporte, 2010. "The Traveling Salesman Problem, the Vehicle Routing Problem, and Their Impact on Combinatorial Optimization," International Journal of Strategic Decision Sciences (IJSDS), IGI Global, vol. 1(2), pages 82-92, April.
    2. Robert Tibshirani & Guenther Walther & Trevor Hastie, 2001. "Estimating the number of clusters in a data set via the gap statistic," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 63(2), pages 411-423.
    3. Baniasadi, Pouya & Foumani, Mehdi & Smith-Miles, Kate & Ejov, Vladimir, 2020. "A transformation technique for the clustered generalized traveling salesman problem with applications to logistics," European Journal of Operational Research, Elsevier, vol. 285(2), pages 444-457.
    4. B. Bullnheimer & R.F. Hartl & C. Strauss, 1999. "An improved Ant System algorithm for theVehicle Routing Problem," Annals of Operations Research, Springer, vol. 89(0), pages 319-328, January.
    5. G. A. Croes, 1958. "A Method for Solving Traveling-Salesman Problems," Operations Research, INFORMS, vol. 6(6), pages 791-812, December.
    6. Bektas, Tolga, 2006. "The multiple traveling salesman problem: an overview of formulations and solution procedures," Omega, Elsevier, vol. 34(3), pages 209-219, June.
    7. M. Bellmore & G. L. Nemhauser, 1968. "The Traveling Salesman Problem: A Survey," Operations Research, INFORMS, vol. 16(3), pages 538-558, June.
    8. Jon Jouis Bentley, 1992. "Fast Algorithms for Geometric Traveling Salesman Problems," INFORMS Journal on Computing, INFORMS, vol. 4(4), pages 387-411, November.
    9. Selim Çetiner & Canan Sepil & Haldun Süral, 2010. "Hubbing and routing in postal delivery systems," Annals of Operations Research, Springer, vol. 181(1), pages 109-124, December.
    10. Joseph A. Svestka & Vaughn E. Huckfeldt, 1973. "Computational Experience with an M-Salesman Traveling Salesman Algorithm," Management Science, INFORMS, vol. 19(7), pages 790-799, March.
    11. Snyder, Lawrence V. & Daskin, Mark S., 2006. "A random-key genetic algorithm for the generalized traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 174(1), pages 38-53, October.
    12. Varese, Federico, 2001. "The Russian Mafia: Private Protection in a New Market Economy," OUP Catalogue, Oxford University Press, number 9780198297369.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Scianna, Marco, 2024. "The AddACO: A bio-inspired modified version of the ant colony optimization algorithm to solve travel salesman problems," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 218(C), pages 357-382.
    2. Kusum Deep & Hadush Mebrahtu & Atulya K. Nagar, 2018. "Novel GA for metropolitan stations of Indian railways when modelled as a TSP," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 9(3), pages 639-645, June.
    3. Luc Muyldermans & Patrick Beullens & Dirk Cattrysse & Dirk Van Oudheusden, 2005. "Exploring Variants of 2-Opt and 3-Opt for the General Routing Problem," Operations Research, INFORMS, vol. 53(6), pages 982-995, December.
    4. Gang Du & Xi Liang & Chuanwang Sun, 2017. "Scheduling Optimization of Home Health Care Service Considering Patients’ Priorities and Time Windows," Sustainability, MDPI, vol. 9(2), pages 1-22, February.
    5. G Babin & S Deneault & G Laporte, 2007. "Improvements to the Or-opt heuristic for the symmetric travelling salesman problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(3), pages 402-407, March.
    6. Jean Bertrand Gauthier & Stefan Irnich, 2020. "Inter-Depot Moves and Dynamic-Radius Search for Multi-Depot Vehicle Routing Problems," Working Papers 2004, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    7. Jeanette Schmidt & Stefan Irnich, 2020. "New Neighborhoods and an Iterated Local Search Algorithm for the Generalized Traveling Salesman Problem," Working Papers 2020, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    8. Chris Walshaw, 2002. "A Multilevel Approach to the Travelling Salesman Problem," Operations Research, INFORMS, vol. 50(5), pages 862-877, October.
    9. Yuan, Shuai & Skinner, Bradley & Huang, Shoudong & Liu, Dikai, 2013. "A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms," European Journal of Operational Research, Elsevier, vol. 228(1), pages 72-82.
    10. Luca Maria Gambardella & Marco Dorigo, 2000. "An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem," INFORMS Journal on Computing, INFORMS, vol. 12(3), pages 237-255, August.
    11. CASTRO, Marco & SÖRENSEN, Kenneth & VANSTEENWEGEN, Pieter & GOOS, Peter, 2012. "A simple GRASP+VND for the travelling salesperson problem with hotel selection," Working Papers 2012024, University of Antwerp, Faculty of Business and Economics.
    12. Pop, Petrică C. & Cosma, Ovidiu & Sabo, Cosmin & Sitar, Corina Pop, 2024. "A comprehensive survey on the generalized traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 314(3), pages 819-835.
    13. Muren, & Wu, Jianjun & Zhou, Li & Du, Zhiping & Lv, Ying, 2019. "Mixed steepest descent algorithm for the traveling salesman problem and application in air logistics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 126(C), pages 87-102.
    14. William Cook & André Rohe, 1999. "Computing Minimum-Weight Perfect Matchings," INFORMS Journal on Computing, INFORMS, vol. 11(2), pages 138-148, May.
    15. N. A. Arellano-Arriaga & J. Molina & S. E. Schaeffer & A. M. Álvarez-Socarrás & I. A. Martínez-Salazar, 2019. "A bi-objective study of the minimum latency problem," Journal of Heuristics, Springer, vol. 25(3), pages 431-454, June.
    16. Li Zhu & Yeming Gong & Yishui Xu & Jun Gu, 2019. "Emergency relief routing models for injured victims considering equity and priority," Annals of Operations Research, Springer, vol. 283(1), pages 1573-1606, December.
    17. CASTRO, Marco & SÖRENSEN, Kenneth & GOOS, Peter & VANSTEENWEGEN, Pieter, 2014. "The multiple travelling salesperson problem with hotel selection," Working Papers 2014030, University of Antwerp, Faculty of Business and Economics.
    18. Wang, Congke & Liu, Yankui & Yang, Guoqing, 2023. "Adaptive distributionally robust hub location and routing problem with a third-party logistics strategy," Socio-Economic Planning Sciences, Elsevier, vol. 87(PA).
    19. Shengbin Wang & Weizhen Rao & Yuan Hong, 2020. "A distance matrix based algorithm for solving the traveling salesman problem," Operational Research, Springer, vol. 20(3), pages 1505-1542, September.
    20. Marc Francke & Alex Van de Minne, 2021. "Modeling unobserved heterogeneity in hedonic price models," Real Estate Economics, American Real Estate and Urban Economics Association, vol. 49(4), pages 1315-1339, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:annopr:v:322:y:2023:i:1:d:10.1007_s10479-022-04883-1. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.