IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v244y2015i2p457-470.html
   My bibliography  Save this article

Metaheuristics for the risk-constrained cash-in-transit vehicle routing problem

Author

Listed:
  • Talarico, Luca
  • Sörensen, Kenneth
  • Springael, Johan

Abstract

This paper proposes a variant of the well-known capacitated vehicle routing problem that models the routing of vehicles in the cash-in-transit industry by introducing a risk constraint. In the Risk-constrained Cash-in-Transit Vehicle Routing Problem (RCTVRP), the risk of being robbed, which is assumed to be proportional both to the amount of cash being carried and the time or the distance covered by the vehicle carrying the cash, is limited by a risk threshold. A library containing two sets of instances for the RCTVRP, some with known optimal solution, is generated. A mathematical formulation is developed and small instances of the problem are solved by using IBM CPLEX. Four constructive heuristics as well as a local search block composed of six local search operators are developed and combined using two different metaheuristic structures: a multistart heuristic and a perturb-and-improve structure. In a statistical experiment, the best parameter settings for each component are determined, and the resulting heuristic configurations are compared in their best possible setting. The resulting metaheuristics are able to obtain solutions of excellent quality in very limited computing times.

Suggested Citation

  • Talarico, Luca & Sörensen, Kenneth & Springael, Johan, 2015. "Metaheuristics for the risk-constrained cash-in-transit vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 244(2), pages 457-470.
    • Handle: RePEc:eee:ejores:v:244:y:2015:i:2:p:457-470
    DOI: 10.1016/j.ejor.2015.01.040
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221715000600
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2015.01.040?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. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms," Transportation Science, INFORMS, vol. 39(1), pages 104-118, February.
    2. G. Clarke & J. W. Wright, 1964. "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operations Research, INFORMS, vol. 12(4), pages 568-581, August.
    3. S. Lin & B. W. Kernighan, 1973. "An Effective Heuristic Algorithm for the Traveling-Salesman Problem," Operations Research, INFORMS, vol. 21(2), pages 498-516, April.
    4. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part II: Metaheuristics," Transportation Science, INFORMS, vol. 39(1), pages 119-139, February.
    5. Lucio Bianco & Massimiliano Caramia & Stefano Giordani & Veronica Piccialli, 2013. "Operations Research Models for Global Route Planning in Hazardous Material Transportation," International Series in Operations Research & Management Science, in: Rajan Batta & Changhyun Kwon (ed.), Handbook of OR/MS Models in Hazardous Materials Transportation, edition 127, pages 49-101, Springer.
    6. Helsgaun, Keld, 2000. "An effective implementation of the Lin-Kernighan traveling salesman heuristic," European Journal of Operational Research, Elsevier, vol. 126(1), pages 106-130, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Tikani, Hamid & Setak, Mostafa & Demir, Emrah, 2021. "A risk-constrained time-dependent cash-in-transit routing problem in multigraph under uncertainty," European Journal of Operational Research, Elsevier, vol. 293(2), pages 703-730.
    2. Soriano, Adria & Vidal, Thibaut & Gansterer, Margaretha & Doerner, Karl, 2020. "The vehicle routing problem with arrival time diversification on a multigraph," European Journal of Operational Research, Elsevier, vol. 286(2), pages 564-575.
    3. Anita Agárdi & László Kovács & Tamás Bányai, 2022. "Mathematical Model for the Generalized VRP Model," Sustainability, MDPI, vol. 14(18), pages 1-22, September.
    4. Hoogeboom, Maaike & Dullaert, Wout, 2019. "Vehicle routing with arrival time diversification," European Journal of Operational Research, Elsevier, vol. 275(1), pages 93-107.
    5. Hughes, Michael S. & Lunday, Brian J. & Weir, Jeffrey D. & Hopkinson, Kenneth M., 2021. "The multiple shortest path problem with path deconfliction," European Journal of Operational Research, Elsevier, vol. 292(3), pages 818-829.
    6. Vidal, Thibaut & Laporte, Gilbert & Matl, Piotr, 2020. "A concise guide to existing and emerging vehicle routing problem variants," European Journal of Operational Research, Elsevier, vol. 286(2), pages 401-416.
    7. Allahyari, Somayeh & Yaghoubi, Saeed & Van Woensel, Tom, 2021. "A novel risk perspective on location-routing planning: An application in cash transportation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 150(C).
    8. Kian, Ramez & Erdoğan, Güneş & de Leeuw, Sander & Sibel Salman, F. & Sabet, Ehsan & Kara, Bahar Y. & Demir, Muhittin H., 2022. "Logistics planning of cash transfer to Syrian refugees in Turkey," European Journal of Operational Research, Elsevier, vol. 296(3), pages 1007-1024.
    9. Zandieh, Fatemeh & Ghannadpour, Seyed Farid & Mazdeh, Mohammad Mahdavi, 2024. "New integrated routing and surveillance model with drones and charging station considerations," European Journal of Operational Research, Elsevier, vol. 313(2), pages 527-547.
    10. Xianlong Ge & Yuanzhi Jin & Long Zhang, 2023. "Genetic-based algorithms for cash-in-transit multi depot vehicle routing problems: economic and environmental optimization," Environment, Development and Sustainability: A Multidisciplinary Approach to the Theory and Practice of Sustainable Development, Springer, vol. 25(1), pages 557-586, January.

    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. Michael Schneider & Michael Drexl, 2017. "A survey of the standard location-routing problem," Annals of Operations Research, Springer, vol. 259(1), pages 389-414, December.
    2. Wang, Zheng, 2018. "Delivering meals for multiple suppliers: Exclusive or sharing logistics service," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 118(C), pages 496-512.
    3. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    4. Theys, Christophe & Bräysy, Olli & Dullaert, Wout & Raa, Birger, 2010. "Using a TSP heuristic for routing order pickers in warehouses," European Journal of Operational Research, Elsevier, vol. 200(3), pages 755-763, February.
    5. Hideki Hashimoto & Mutsunori Yagiura & Shinji Imahori & Toshihide Ibaraki, 2013. "Recent progress of local search in handling the time window constraints of the vehicle routing problem," Annals of Operations Research, Springer, vol. 204(1), pages 171-187, April.
    6. Chiang, Wen-Chyuan & Russell, Robert & Xu, Xiaojing & Zepeda, David, 2009. "A simulation/metaheuristic approach to newspaper production and distribution supply chain problems," International Journal of Production Economics, Elsevier, vol. 121(2), pages 752-767, October.
    7. Qi, Mingyao & Lin, Wei-Hua & Li, Nan & Miao, Lixin, 2012. "A spatiotemporal partitioning approach for large-scale vehicle routing problems with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 248-257.
    8. Jeffrey W. Ohlmann & Michael J. Fry & Barrett W. Thomas, 2008. "Route Design for Lean Production Systems," Transportation Science, INFORMS, vol. 42(3), pages 352-370, August.
    9. Hiermann, Gerhard & Puchinger, Jakob & Ropke, Stefan & Hartl, Richard F., 2016. "The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations," European Journal of Operational Research, Elsevier, vol. 252(3), pages 995-1018.
    10. Xiaopan Chen & Yunfeng Kong & Lanxue Dang & Yane Hou & Xinyue Ye, 2015. "Exact and Metaheuristic Approaches for a Bi-Objective School Bus Scheduling Problem," PLOS ONE, Public Library of Science, vol. 10(7), pages 1-20, July.
    11. ARNOLD, Florian & SÖRENSEN, Kenneth, 2017. "A simple, deterministic, and efficient knowledge-driven heuristic for the vehicle routing problem," Working Papers 2017012, University of Antwerp, Faculty of Business and Economics.
    12. Loske, Dominic & Klumpp, Matthias, 2021. "Human-AI collaboration in route planning: An empirical efficiency-based analysis in retail logistics," International Journal of Production Economics, Elsevier, vol. 241(C).
    13. Gahm, Christian & Brabänder, Christian & Tuma, Axel, 2017. "Vehicle routing with private fleet, multiple common carriers offering volume discounts, and rental options," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 97(C), pages 192-216.
    14. Drexl, M. & Schneider, M., 2014. "A Survey of the Standard Location-Routing Problem," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 65940, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    15. Olli Bräysy & Wout Dullaert & Geir Hasle & David Mester & Michel Gendreau, 2008. "An Effective Multirestart Deterministic Annealing Metaheuristic for the Fleet Size and Mix Vehicle-Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 42(3), pages 371-386, August.
    16. Tobias Harks & Felix G König & Jannik Matuschke, 2013. "Approximation Algorithms for Capacitated Location Routing," Transportation Science, INFORMS, vol. 47(1), pages 3-22, February.
    17. Kritikos, Manolis N. & Ioannou, George, 2010. "The balanced cargo vehicle routing problem with time windows," International Journal of Production Economics, Elsevier, vol. 123(1), pages 42-51, January.
    18. Brandstätter, Christian & Reimann, Marc, 2018. "The Line-haul Feeder Vehicle Routing Problem: Mathematical model formulation and heuristic approaches," European Journal of Operational Research, Elsevier, vol. 270(1), pages 157-170.
    19. Bergmann, Felix M. & Wagner, Stephan M. & Winkenbach, Matthias, 2020. "Integrating first-mile pickup and last-mile delivery on shared vehicle routes for efficient urban e-commerce distribution," Transportation Research Part B: Methodological, Elsevier, vol. 131(C), pages 26-62.
    20. Liyang Xiao & Mahjoub Dridi & Amir Hajjam El Hassani & Hongying Fei & Wanlong Lin, 2018. "An Improved Cuckoo Search for a Patient Transportation Problem with Consideration of Reducing Transport Emissions," Sustainability, MDPI, vol. 10(3), pages 1-19, March.

    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:eee:ejores:v:244:y:2015:i:2:p:457-470. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.