Skip to main content
SpringerLink
Log in

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

  • Original Paper
  • Published:
TOP Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  • Al Chami Z, El Flity H, Manier H, Manier MA (2018) A new metaheuristic to solve a selective pickup and delivery problem. In: 2018 4th international conference on logistics operations management (GOL), IEEE, pp 1–5

  • Arab R, Ghaderi S, Tavakkoli-Moghaddam R (2018) Bi-objective inventory routing problem with backhauls under transportation risks: two meta-heuristics. Transportation Letters, pp 1–17

  • Assis LP, Maravilha AL, Vivas A, Campelo F, Ramírez JA (2013) Multiobjective vehicle routing problem with fixed delivery and optional collections. Optimiz Lett 7(7):1419–1431

    Google Scholar 

  • Belloso J, Juan AA, Martinez E, Faulin J (2017) A biased-randomized metaheuristic for the vehicle routing problem with clustered and mixed backhauls. Networks 69(3):241–255

    Google Scholar 

  • Belloso J, Juan AA, Faulin J (2019) An iterative biased-randomized heuristic for the fleet size and mix vehicle-routing problem with backhauls. Int Trans Oper Res 26(1):289–301

    Google Scholar 

  • Berbeglia G, Cordeau JF, Gribkovskaia I, Laporte G (2007) Static pickup and delivery problems: a classification scheme and survey. Top 15(1):1–31

    Google Scholar 

  • Brandão J (2016) A deterministic iterated local search algorithm for the vehicle routing problem with backhauls. Top 24(2):445–465

    Google Scholar 

  • Bruck BP, Iori M (2017) Non-elementary formulations for single vehicle routing problems with pickups and deliveries. Oper Res 65(6):1597–1614

    Google Scholar 

  • Caceres-Cruz J, Arias P, Guimarans D, Riera D, Juan AA (2014) Rich vehicle routing problem: survey. ACM Comput Surv (CSUR) 47(2):1–28

    Google Scholar 

  • Calvet L, Juan AA, Serrat C, Ries J (2016) A statistical learning based approach for parameter fine-tuning of metaheuristics. SORT-Stat. Oper. Res. Trans. 1(1):201–224

    Google Scholar 

  • Christofides N, Eilon S (1969) An algorithm for the vehicle-dispatching problem. J Oper Res Soc 20(3):309–318

    Google Scholar 

  • Deif I, Bodin L (1984) Extension of the Clarke and Wright algorithm for solving the vehicle routing problem with backhauling. In: Proceedings of the Babson conference on software uses in transportation and logistics management, Babson Park, MA, pp 75–96

  • Del Ser J, Torre-Bastida AI, Lana I, Bilbao MN, Perfecto C (2017) Nature-inspired heuristics for the multiple-vehicle selective pickup and delivery problem under maximum profit and incentive fairness criteria. In: 2017 IEEE Congress on Evolutionary Computation (CEC), IEEE, pp 480–487

  • Dominguez O, Guimarans D, Juan AA, de la Nuez I (2016) A biased-randomised large neighbourhood search for the two-dimensional vehicle routing problem with backhauls. Eur J Oper Res 255(2):442–462

    Google Scholar 

  • Elia V, Gnoni MG (2015) Designing an effective closed loop system for pallet management. Int J Prod Econ 170:730–740

    Google Scholar 

  • Falcon R, Li X, Nayak A, Stojmenovic I (2010) The one-commodity traveling salesman problem with selective pickup and delivery: An ant colony approach. In: IEEE congress on evolutionary computation, IEEE, pp 1–8

  • Fan X, Gong Y, Xu X, Zou B (2019) Optimal decisions in reducing loss rate of returnable transport items. J Clean Prod 214:1050–1060

    Google Scholar 

  • Ferone D, Gruler A, Festa P, Juan AA (2019) Enhancing and extending the classical grasp framework with biased randomisation and simulation. J Oper Res Soc 70(8):1362–1375

    Google Scholar 

  • García-Nájera A, Bullinaria JA, Gutiérrez-Andrade MA (2015) An evolutionary approach for multi-objective vehicle routing problems with backhauls. Comput Ind Eng 81:90–108

    Google Scholar 

  • Gavish B, Graves SC (1978) The travelling salesman problem and related problems (Working Paper). Tech. rep., Massachusetts Institute of Technology, Operations Research Center

  • Glock CH (2017) Decision support models for managing returnable transport items in supply chains: A systematic literature review. Int J Prod Econ 183:561–569

    Google Scholar 

  • Goetschalckx M, Jacobs-Blecha C (1989) The vehicle routing problem with backhauls. Eur J Oper Res 42(1):39–51

    Google Scholar 

  • Gonzalez-Neira EM, Ferone D, Hatami S, Juan AA (2017) A biased-randomized simheuristic for the distributed assembly permutation flowshop problem with stochastic processing times. Simul Model Pract Theory 79:23–36

    Google Scholar 

  • Govindan K, Soleimani H (2017) A review of reverse logistics and closed-loop supply chains: a journal of cleaner production focus. J Clean Prod 142:371–384

    Google Scholar 

  • Grasas A, Juan AA, Faulin J, de Armas J, Ramalhinho H (2017) Biased randomization of heuristics using skewed probability distributions: a survey and some applications. Comput Ind Eng 110:216–228

    Google Scholar 

  • Gribkovskaia I, Laporte G, Shyshou A (2008) The single vehicle routing problem with deliveries and selective pickups. Comput Oper Res 35(9):2908–2924

    Google Scholar 

  • Gruler A, Panadero J, de Armas J, Moreno JA, Juan AA (2018) Combining variable neighborhood search with simulation for the inventory routing problem with stochastic demands and stock-outs. Comput Ind Eng 123:278–288

    Google Scholar 

  • Gruler A, Panadero J, de Armas J, Moreno JA, Juan AA (2020) A variable neighborhood search simheuristic for the multiperiod inventory routing problem with stochastic demands. Int Trans Oper Res 27(1):314–335

    Google Scholar 

  • Gutiérrez-Jarpa G, Desaulniers G, Laporte G, Marianov V (2010) A branch-and-price algorithm for the vehicle routing problem with deliveries, selective pickups and time windows. Eur J Oper Res 206(2):341–349

    Google Scholar 

  • Hellström D, Johansson O (2010) The impact of control strategies on the management of returnable transport items. Transp Res Part E Logist Transp Rev 46(6):1128–1139

    Google Scholar 

  • Ilic A, Ng JW, Bowman P, Staake T (2009) The value of rfid for rti management. Electron Mark 19(2–3):125–135

    Google Scholar 

  • ISO (2016) ISO/IEC 19762:2016. Information technology—Automatic identification and data capture (AIDC) techniques—Harmonized vocabulary

  • Jacobs-Blecha C, Goetschalckx M (1992) The vehicle routing problem with backhauls: properties and solution algorithms. Natl Transp Res Board 13

  • Kim T, Glock CH, Kwon Y (2014) A closed-loop supply chain for deteriorating products under stochastic container return times. Omega 43:30–40

    Google Scholar 

  • Koç Ç, Laporte G (2018) Vehicle routing with backhauls: Review and research perspectives. Comput Oper Res 91:79–91

    Google Scholar 

  • Kroon L, Vrijens G (1995) Returnable containers: an example of reverse logistics. Int J Phys Distrib Logist Manag 25(2):56–68

    Google Scholar 

  • Küçükoğlu I, Öztürk N (2015) An advanced hybrid meta-heuristic algorithm for the vehicle routing problem with backhauls and time windows. Comput Ind Eng 86:60–68

    Google Scholar 

  • Lin S, Bard JF, Jarrah AI, Zhang X, Novoa LJ (2017) Route design for last-in, first-out deliveries with backhauling. Transp Res Part C Emerg Technol 76:90–117

    Google Scholar 

  • Lourenço HR, Martin OC, Stützle T (2010) Iterated local search: framework and applications. In: Handbook of metaheuristics, Springer, pp 363–397

  • Mahmoudi M, Parviziomran I (2020) Reusable packaging in supply chains: A review of environmental and economic impacts, logistics system designs, and operations management. Int J Prod Econ:107730

  • Martins LC, Hirsch P, Juan A (2020) Agile optimization of a two-echelon vehicle routing problem with pick-up and delivery. Int Trans Oper Res

  • Mason A, Shaw A, Al-Shamma’a A (2012) Peer-to-peer inventory management of returnable transport items: a design science approach. Comput Ind 63(3):265–274

    Google Scholar 

  • Öncan T, Altınel K, Laporte G (2009) A comparative analysis of several asymmetric traveling salesman problem formulations. Comput Oper Res 36(3):637–654

    Google Scholar 

  • Panadero J, Currie C, Juan AA, Bayliss C (2020) Maximizing reward from a team of surveillance drones under uncertainty conditions: a simheuristic approach

  • Parragh SN, Doerner KF, Hartl RF (2008) A survey on pickup and delivery problems. J für Betriebswirtschaft 58(1):21–51

    Google Scholar 

  • Reil S, Bortfeldt A, Mönch L (2018) Heuristics for vehicle routing problems with backhauls, time windows, and 3D loading constraints. Eur J Oper Res 266(3):877–894

    Google Scholar 

  • Ruiz R, Stützle T (2007) A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. Eur J Oper Res 177(3):2033–2049

    Google Scholar 

  • Soysal M (2016) Closed-loop inventory routing problem for returnable transport items. Transp Res Part D Transp Environ 48:31–45

    Google Scholar 

  • Ting CK, Liao XL (2013) The selective pickup and delivery problem: formulation and a memetic algorithm. Int J Prod Econ 141(1):199–211

    Google Scholar 

  • Ting CK, Liao XL, Huang YH, Liaw RT (2017) Multi-vehicle selective pickup and delivery using metaheuristic algorithms. Inf Sci 406:146–169

    Google Scholar 

  • Tordecilla-Madera R, Roa AP, Escobar JW, Buriticá NC (2018) A mathematical model for collecting and distributing perishable products by considering costs minimisation and \({CO}_2\) emissions. Int J Serv Oper Manag 31(2):207–234

    Google Scholar 

  • Toth P, Vigo D (1997) An exact algorithm for the vehicle routing problem with backhauls. Transp Sci 31(4):372–385

    Google Scholar 

  • Wassan N (2007) Reactive tabu adaptive memory programming search for the vehicle routing problem with backhauls. J Oper Res Soc 58(12):1630–1641

    Google Scholar 

  • Wu W, Tian Y, Jin T (2016) A label based ant colony algorithm for heterogeneous vehicle routing with mixed backhaul. Appl Soft Comput 47:224–234

    Google Scholar 

  • Zachariadis EE, Kiranoudis CT (2012) An effective local search approach for the vehicle routing problem with backhauls. Expert Syst Appl 39(3):3174–3184

    Google Scholar 

Download references

Acknowledgments

This work has been partially supported by COLCIENCIAS - Colombia, the School of Industrial Engineering of Universidad del Valle, the IoF2020, the AGAUR (2018-LLAV-00017), and the Erasmus+ Program (2018-1-ES01-KA103-049767). We also acknowledge the support of the doctoral programs at the Universitat Oberta de Catalunya and the Universidad de La Sabana.

Author information

Authors and Affiliations

  1. Faculty of Engineering, Universidad del Valle, Cali, Colombia

    Julio C. Londoño

  2. IN3-Computer Science Department, Universitat Oberta de Catalunya, 08860, Castelldefels, Spain

    Rafael D. Tordecilla, Leandro do C. Martins & Angel A. Juan

  3. Faculty of Engineering, Universidad de La Sabana, Km 7 Autopista norte de Bogota, D.C., Chia, Colombia

    Rafael D. Tordecilla

Authors
  1. Julio C. Londoño
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Rafael D. Tordecilla
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Leandro do C. Martins
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Angel A. Juan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Rafael D. Tordecilla.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Londoño, J.C., Tordecilla, R.D., Martins, L.d.C. et al. A biased-randomized iterated local search for the vehicle routing problem with optional backhauls. TOP 29, 387–416 (2021). https://doi.org/10.1007/s11750-020-00558-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-020-00558-x

Keywords

Mathematics Subject Classification

Search

Navigation