IDEAS home Printed from https://ideas.repec.org/a/spr/topjnl/v29y2021i2d10.1007_s11750-020-00558-x.html
   My bibliography  Save this article

A biased-randomized iterated local search for the vehicle routing problem with optional backhauls

Author

Listed:
  • Julio C. Londoño

    (Universidad del Valle)

  • Rafael D. Tordecilla

    (Universitat Oberta de Catalunya
    Universidad de La Sabana)

  • Leandro do C. Martins

    (Universitat Oberta de Catalunya)

  • Angel A. Juan

    (Universitat Oberta de Catalunya)

Abstract

The vehicle routing problem with backhauls integrates decisions on product delivery with decisions on the collection of returnable items. In this paper, we analyze a scenario in which collection of items is optional—but subject to a penalty cost. Both transportation costs and penalties associated with non-collecting decisions are considered. A mixed-integer linear model is proposed and solved for small instances. Also, a metaheuristic algorithm combining biased randomization techniques with iterated local search is introduced for larger instances. Our approach yields cost savings and is competitive when compared to other state-of-the-art approaches.

Suggested Citation

  • Julio C. Londoño & Rafael D. Tordecilla & Leandro do C. Martins & Angel A. Juan, 2021. "A biased-randomized iterated local search for the vehicle routing problem with optional backhauls," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(2), pages 387-416, July.
    • Handle: RePEc:spr:topjnl:v:29:y:2021:i:2:d:10.1007_s11750-020-00558-x
    DOI: 10.1007/s11750-020-00558-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11750-020-00558-x
    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/s11750-020-00558-x?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. Gutiérrez-Jarpa, Gabriel & Desaulniers, Guy & Laporte, Gilbert & Marianov, Vladimir, 2010. "A branch-and-price algorithm for the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows," European Journal of Operational Research, Elsevier, vol. 206(2), pages 341-349, October.
    2. Rafael Tordecilla-Madera & Andrés Polo Roa & John Willmer Escobar & Nicolas Clavijo Buriticá, 2018. "A mathematical model for collecting and distributing perishable products by considering costs minimisation and CO 2 emissions," International Journal of Services and Operations Management, Inderscience Enterprises Ltd, vol. 31(2), pages 207-234.
    3. Dominguez, Oscar & Guimarans, Daniel & Juan, Angel A. & de la Nuez, Ignacio, 2016. "A Biased-Randomised Large Neighbourhood Search for the two-dimensional Vehicle Routing Problem with Backhauls," European Journal of Operational Research, Elsevier, vol. 255(2), pages 442-462.
    4. Goetschalckx, Marc & Jacobs-Blecha, Charlotte, 1989. "The vehicle routing problem with backhauls," European Journal of Operational Research, Elsevier, vol. 42(1), pages 39-51, September.
    5. Gerardo Berbeglia & Jean-François Cordeau & Irina Gribkovskaia & Gilbert Laporte, 2007. "Rejoinder on: Static pickup and delivery problems: a classification scheme and survey," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 15(1), pages 45-47, July.
    6. Reil, Sebastian & Bortfeldt, Andreas & Mönch, Lars, 2018. "Heuristics for vehicle routing problems with backhauls, time windows, and 3D loading constraints," European Journal of Operational Research, Elsevier, vol. 266(3), pages 877-894.
    7. Hellström, Daniel & Johansson, Ola, 2010. "The impact of control strategies on the management of returnable transport items," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 46(6), pages 1128-1139, November.
    8. Glock, Christoph H., 2017. "Decision support models for managing returnable transport items in supply chains: A systematic literature review," International Journal of Production Economics, Elsevier, vol. 183(PB), pages 561-569.
    9. Kim, Taebok & Glock, Christoph H. & Kwon, Yongjang, 2014. "A closed-loop supply chain for deteriorating products under stochastic container return times," Omega, Elsevier, vol. 43(C), pages 30-40.
    10. Ruiz, Ruben & Stutzle, Thomas, 2007. "A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem," European Journal of Operational Research, Elsevier, vol. 177(3), pages 2033-2049, March.
    11. Henriette Koch & Andreas Bortfeldt & Gerhard Wäscher, 2018. "A hybrid algorithm for the vehicle routing problem with backhauls, time windows and three-dimensional loading constraints," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(4), pages 1029-1075, October.
    12. Bruno P. Bruck & Manuel Iori, 2017. "Non-Elementary Formulations for Single Vehicle Routing Problems with Pickups and Deliveries," Operations Research, INFORMS, vol. 65(6), pages 1597-1614, December.
    13. Ting, Chuan-Kang & Liao, Xin-Lan, 2013. "The selective pickup and delivery problem: Formulation and a memetic algorithm," International Journal of Production Economics, Elsevier, vol. 141(1), pages 199-211.
    14. Gerardo Berbeglia & Jean-François Cordeau & Irina Gribkovskaia & Gilbert Laporte, 2007. "Static pickup and delivery problems: a classification scheme and survey," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 15(1), pages 1-31, July.
    15. Helena R. Lourenço & Olivier C. Martin & Thomas Stützle, 2010. "Iterated Local Search: Framework and Applications," International Series in Operations Research & Management Science, in: Michel Gendreau & Jean-Yves Potvin (ed.), Handbook of Metaheuristics, chapter 0, pages 363-397, Springer.
    16. Mahmoudi, Monirehalsadat & Parviziomran, Irandokht, 2020. "Reusable packaging in supply chains: A review of environmental and economic impacts, logistics system designs, and operations management," International Journal of Production Economics, Elsevier, vol. 228(C).
    17. Xiangxiang Fan & Yeming Gong & Xianhao Xu & Bipan Zou, 2019. "Optimal decisions in reducing loss rate of returnable transport items," Post-Print hal-02312287, HAL.
    18. Elia, Valerio & Gnoni, Maria Grazia, 2015. "Designing an effective closed loop system for pallet management," International Journal of Production Economics, Elsevier, vol. 170(PC), pages 730-740.
    19. F. Errico & G. Desaulniers & M. Gendreau & W. Rei & L.-M. Rousseau, 2018. "The vehicle routing problem with hard time windows and stochastic service times," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 7(3), pages 223-251, September.
    20. Daniele Ferone & Aljoscha Gruler & Paola Festa & Angel A. Juan, 2019. "Enhancing and extending the classical GRASP framework with biased randomisation and simulation," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 70(8), pages 1362-1375, August.
    21. Paolo Toth & Daniele Vigo, 1997. "An Exact Algorithm for the Vehicle Routing Problem with Backhauls," Transportation Science, INFORMS, vol. 31(4), pages 372-385, November.
    22. Glock, C. H., 2017. "Decision support models for managing returnable transport items in supply chains: A systematic literature review," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 79485, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    23. N Wassan, 2007. "Reactive tabu adaptive memory programming search for the vehicle routing problem with backhauls," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(12), pages 1630-1641, December.
    24. Kim, T. & Glock, C. H. & Kwon, Y., 2014. "A closed-loop supply chain for deteriorating products under stochastic container return times," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 62024, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    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. David Raba & Rafael D. Tordecilla & Pedro Copado & Angel A. Juan & Daniel Mount, 2022. "A Digital Twin for Decision Making on Livestock Feeding," Interfaces, INFORMS, vol. 52(3), pages 267-282, May.

    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. Maria João Santos & Pedro Amorim & Alexandra Marques & Ana Carvalho & Ana Póvoa, 2020. "The vehicle routing problem with backhauls towards a sustainability perspective: a review," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(2), pages 358-401, July.
    2. Mahmoudi, Monirehalsadat & Parviziomran, Irandokht, 2020. "Reusable packaging in supply chains: A review of environmental and economic impacts, logistics system designs, and operations management," International Journal of Production Economics, Elsevier, vol. 228(C).
    3. Phuong Khanh Nguyen & Teodor Gabriel Crainic & Michel Toulouse, 2017. "Multi-trip pickup and delivery problem with time windows and synchronization," Annals of Operations Research, Springer, vol. 253(2), pages 899-934, June.
    4. José Brandão, 2016. "A deterministic iterated local search algorithm for the vehicle routing problem with backhauls," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 24(2), pages 445-465, July.
    5. Qin, Hu & Moriakin, Anton & Xu, Gangyan & Li, Jiliu, 2024. "The generator distribution problem for base stations during emergency power outage: A branch-and-price-and-cut approach," European Journal of Operational Research, Elsevier, vol. 318(3), pages 752-767.
    6. Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
    7. Tanksale, Ajinkya N. & Das, Debabrata & Verma, Priyanka & Tiwari, Manoj Kumar, 2021. "Unpacking the role of primary packaging material in designing green supply chains: An integrated approach," International Journal of Production Economics, Elsevier, vol. 236(C).
    8. Meherishi, Lavanya & Narayana, Sushmita A. & Ranjani, K.S., 2021. "Integrated product and packaging decisions with secondary packaging returns and protective packaging management," European Journal of Operational Research, Elsevier, vol. 292(3), pages 930-952.
    9. 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.
    10. Qiu, Xiaoqiu & Feuerriegel, Stefan & Neumann, Dirk, 2017. "Making the most of fleets: A profit-maximizing multi-vehicle pickup and delivery selection problem," European Journal of Operational Research, Elsevier, vol. 259(1), pages 155-168.
    11. Ting, Chuan-Kang & Liao, Xin-Lan, 2013. "The selective pickup and delivery problem: Formulation and a memetic algorithm," International Journal of Production Economics, Elsevier, vol. 141(1), pages 199-211.
    12. Fatima Ezzahra Achamrah & Fouad Riane & Evren Sahin & Sabine Limbourg, 2022. "An Artificial-Immune-System-Based Algorithm Enhanced with Deep Reinforcement Learning for Solving Returnable Transport Item Problems," Sustainability, MDPI, vol. 14(10), pages 1-29, May.
    13. Iassinovskaia, Galina & Limbourg, Sabine & Riane, Fouad, 2017. "The inventory-routing problem of returnable transport items with time windows and simultaneous pickup and delivery in closed-loop supply chains," International Journal of Production Economics, Elsevier, vol. 183(PB), pages 570-582.
    14. Biswajit Sarkar & Mehran Ullah & Seok-Beom Choi, 2019. "Joint Inventory and Pricing Policy for an Online to Offline Closed-Loop Supply Chain Model with Random Defective Rate and Returnable Transport Items," Mathematics, MDPI, vol. 7(6), pages 1-20, June.
    15. Liu, Guoquan & Li, Lei & Chen, Jianghang & Ma, Fei, 2020. "Inventory sharing strategy and optimization for reusable transport items," International Journal of Production Economics, Elsevier, vol. 228(C).
    16. Gutiérrez-Jarpa, Gabriel & Desaulniers, Guy & Laporte, Gilbert & Marianov, Vladimir, 2010. "A branch-and-price algorithm for the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows," European Journal of Operational Research, Elsevier, vol. 206(2), pages 341-349, October.
    17. Sebastjan Škerlič & Robert Muha, 2020. "A Model for Managing Packaging in the Product Life Cycle in the Automotive Industry," Sustainability, MDPI, vol. 12(22), pages 1-19, November.
    18. Xiang Song & Dylan Jones & Nasrin Asgari & Tim Pigden, 2020. "Multi-objective vehicle routing and loading with time window constraints: a real-life application," Annals of Operations Research, Springer, vol. 291(1), pages 799-825, August.
    19. Dominguez, Oscar & Guimarans, Daniel & Juan, Angel A. & de la Nuez, Ignacio, 2016. "A Biased-Randomised Large Neighbourhood Search for the two-dimensional Vehicle Routing Problem with Backhauls," European Journal of Operational Research, Elsevier, vol. 255(2), pages 442-462.
    20. Paul Buijs & Jose Alejandro Lopez Alvarez & Marjolein Veenstra & Kees Jan Roodbergen, 2016. "Improved Collaborative Transport Planning at Dutch Logistics Service Provider Fritom," Interfaces, INFORMS, vol. 46(2), pages 119-132, April.

    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:topjnl:v:29:y:2021:i:2:d:10.1007_s11750-020-00558-x. 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.