Abstract
The vehicle routing problem with backhauls is a variant of the classical capacitated vehicle routing problem. The difference is that it contains two distinct sets of customers: those who receive goods from the depot, who are called linehauls, and those who send goods to the depot, who are referred to as backhauls. In this paper, we describe a new deterministic iterated local search algorithm, which is tested using a large number of benchmark problems chosen from the literature. These computational tests have proven that this algorithm competes with the best known algorithms in terms of the quality of the solutions and at the same time, it is simpler and faster.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Battarra M, Cordeau J-F, Iori M (2014) Pickup-and-delivery problems for goods transportation. In: Toth P, Vigo D (eds) Vehicle routing: problems, methods, and applications. MOS/SIAM series on optimization, 2nd edn, pp 161–192
Berbeglia G, Cordeau J-F, Gribkovskaia I, Laporte G (2007) Static pickup and delivery problems: a classification scheme and survey. TOP 15:1–31
Brandão J (2006) A new tabu search algorithm for the vehicle routing problem with backhauls. Eur J Oper Res 173:540–555
Casco D, Golden B, Wasil E (1988) Vehicle routing with backhauls: models, algorithms and case studies. In: Golden B, Assad A (eds) Vehicle routing: methods and studies, Elsevier, New York, pp 127–147
Clarke G, Wright JW (1964) Scheduling of vehicles from a central depot to a number of delivery points. Oper Res 12:568–581
Cuervo P, Goos P, Sörensen K, Arráiz E (2014) An iterated local search algorithm for the vehicle routing problem with backhauls. Eur J Oper Res 237:454–464
Deif I, Bodin L (1984) Extension of the Clarke and Wright algorithm for solving the vehicle routing with backhauling. In: Kidder A (ed) Proceedings of the Babson conference on software uses in transportation and logistics management, Babson Park, pp 75–96
Dongarra J (2006) Performance of various computers using standard linear equations software. In: Report CS-89-85, University of Tennessee
Dongarra J (2014) Performance of various computers using standard linear equations software. In: Report CS-89-85, University of Tennessee
Gajpal Y, Abad P (2009) Multi-ant colony system (MACS) for a vehicle routing problem with backhauls. Eur J Oper Res 196:102–107
Goetschalckx M, Jacobs-Blecha C (1989) The vehicle routing problem with backhauls. Eur J Oper Res 42:39–51
Goetschalckx M, Jacobs-Blecha C (1993) The vehicle routing problem with backhauls: properties and solution algorithms. In: Technical report MHRC-TR.88-13, Georgia Institute of Technology
Hoff A, Andersson H, Christiansen M, Hasle G, Løkketangen A (2010) Industrial aspects and literature survey: fleet composition and routing. Comput Oper Res 37:2041–2061
Irnich S, Schneider M, Vigo D (2014) Four variants of the vehicle routing problem. In: Toth P, Vigo D (eds) Vehicle routing: problems, methods, and applications. MOS/SIAM series on optimization, 2nd edn, pp 241–272
Lenstra J, Rinnoy Kan A (1981) Complexity of vehicle routing and scheduling problems. Networks 11:221–227
Lourenço H, Martin O, Stützle T (2003) Iterated local search. In: Kochenberger G, Glover F (eds) Handbook of metaheuristics. Kluwer, New York, pp 321–353
Mingozzi A, Giorgi S, Baldacci R (1999) An exact method for the vehicle routing problem with backhauls. Transp Sci 33:315–329
Osman I, Wassan N (2002) A reactive tabu search meta-heuristic for the vehicle routing problem with back-hauls. J Sched 5:263–285
Parragh S, Doerner M, Hartl R (2008) A survey on pickup and delivery problems—Part I: Transportation between customers and depot. J Betr 58:21–51
Reimann M, Doerner M, Hartl R (2002) Insertion based ants for vehicle routing problems with backhauls and time windows. In: Dorigo et al (eds) Ant algorithms. Lecture notes in computer science, vol 2463. Springer, Berlin, pp 135–147
Ropke S, Pisinger D (2006) A unified heuristic for a large class of vehicle routing problems with backhauls. Eur J Oper Res 171:750–775
Salhi S, Wassan N, Hajarat M (2013) The fleet size and mix vehicle routing problem with backhauls: formulation and set partitioning-based heuristics. Transp Res Part E Logist Transp Rev 56:22–35
Thangiah R, Potvin J, Sun T (1996) Heuristic approaches to vehicle routing with backhauls and time windows. Comput Oper Res 23:1043–1057
Toth P, Vigo D (1997) An exact algorithm for the vehicle routing problem with backhauls. Transp Sci 31:372–385
Toth P, Vigo D (1999) A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls. Eur J Oper Res 113:528–543
Toth P, Vigo D (2002) VRP with backhauls. In: Toth P, Vigo D (eds) The vehicle routing problem. SIAM monographs on discrete mathematics and applications, vol 9. SIAM, Philadelphia, pp 195–224
Vidal T, Crainic T, Gendreau M, Prins C (2014) A unified solution framework for multi-attribute vehicle routing problems. Eur J Oper Res 234:658–673
Wassan N (2007) Reactive tabu adaptive memory programming search for the vehicle routing problem with backhauls. J Oper Res Soc 58:1630–1641
Waters C (1990) Expert systems for vehicle scheduling. J Oper Res Soc 41:505–515
Zachariadis E, Kiranoudis C (2012) An effective local search approach for the vehicle routing problem with backhauls. Expert Syst Appl 39:3174–3184
Acknowledgments
This research was partially supported by the Fundação para a Ciência e Tecnologia, under project no. PTDC/EGE-GES/104092/2008. This support is gratefully acknowledged. We also thank the anonymous referees for their valuable comments.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Brandão, J. A deterministic iterated local search algorithm for the vehicle routing problem with backhauls. TOP 24, 445–465 (2016). https://doi.org/10.1007/s11750-015-0404-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-015-0404-x