Abstract
The vehicle routing problem with backhauls (VRPB) allows to integrate inbound and outbound routes, which is an efficient strategy to reduce routing costs and also to reduce the environmental and social impacts of transportation. In this paper, we analyze the VRPB literature with a sustainability perspective, which covers environmental and social objectives, collaborative networks and reverse logistics. First, to better understand and analyze the VRPB literature, all related works are characterized according to a common taxonomy provided for routing problems. This taxonomy is extended to differentiate between economic, environmental and social objectives. After identification of all VRPB papers that include sustainability issues, these are analyzed and discussed in more detail. The analysis reveals that research on VRPBs with sustainability concerns is recent and relatively scarce and the most popular aspects investigated are the minimization of fuel consumption and \(\hbox {CO}_{2}\) emissions. Future research lines driven by sustainability concerns are suggested for the VRPB as a promoter of green logistics.
Similar content being viewed by others
References
Adulyasak Y, Jaillet P (2016) Models and algorithms for stochastic and robust vehicle routing with deadlines. Transp Sci 50(2):608–626. https://doi.org/10.1287/trsc.2014.0581
Anbuudayasankar S, Ganesh K, Koh SL, Ducq Y (2012) Modified savings heuristics and genetic algorithm for bi-objective vehicle routing problem with forced backhauls. Expert Syst Appl 39(3):2296–2305. https://doi.org/10.1016/j.eswa.2011.08.009. http://www.sciencedirect.com/science/article/pii/S0957417411011201
Angelelli E, Mansini R (2002) The vehicle routing problem with time windows and simultaneous pick-up and delivery. In: Klose A, Speranza MG, Van Wassenhove LN (eds) Quantitative approaches to distribution logistics and supply chain management. Springer, Heidelberg, pp 249–267
Anily S (1996) The vehicle-routing problem with delivery and back-haul options. Nav Res Logist 43:415–434
Ashtineh H, Pishvaee MS (2019) Alternative fuel vehicle-routing problem: a life cycle analysis of transportation fuels. J Clean Prod 219:166–182. https://doi.org/10.1016/j.jclepro.2019.01.343. http://www.sciencedirect.com/science/article/pii/S0959652619303798
Audy JF, Lehoux N, D’Amours S, Rönnqvist M (2012) A framework for an efficient implementation of logistics collaborations. Int Trans Oper Res 19(5):633–657. https://doi.org/10.1111/j.1475-3995.2010.00799.x
Averbakh I (2001) On the complexity of a class of combinatorial optimization problems with uncertainty. Math Program 90(2):263–272. https://doi.org/10.1007/PL00011424
Bailey E, Unnikrishnan A, Lin DY (2011) Models for minimizing backhaul costs through freight collaboration. Transp Res Rec J Transp Res Board 2224(1):51–60. https://doi.org/10.3141/2224-07
Baldacci R, Bartolini E, Laporte G (2010) Some applications of the generalized vehicle routing problem. J Oper Res Soc 61(7):1072–1077. https://doi.org/10.1057/jors.2009.51
Bektaş T, Laporte G, (2011) The pollution-routing problem. Transp Res Part B Methodol 45(8):1232–1250. https://doi.org/10.1016/j.trb.2011.02.004. https://linkinghub.elsevier.com/retrieve/pii/S019126151100018X
Belloso J, Juan AA, Faulin J, Serrano A (2015) Using multi-start biased randomization of heuristics to solve the vehicle routing problem with clustered backhauls. Lecture Notes Manag Sci 7:15–20
Belloso J, Juan AA, Faulin J (2017a) An iterative biased-randomized heuristic for the fleet size and mix vehicle-routing problem with backhauls. Int Trans Oper Res 26(1):289–301. https://doi.org/10.1111/itor.12379
Belloso J, Juan AA, Martinez E, Faulin J (2017b) A biased-randomized metaheuristic for the vehicle routing problem with clustered and mixed backhauls. Networks 69(3):241–255. https://doi.org/10.1002/net.21734
Belmecheri F, Prins C, Yalaoui F, Amodeo L (2013) Particle swarm optimization algorithm for a vehicle routing problem with heterogeneous fleet, mixed backhauls, and time windows. J Intell Manuf 24(4):775–789. https://doi.org/10.1007/s10845-012-0627-8
Berghida M, Boukra A (2016) Quantum inspired algorithm for a VRP with heterogeneous fleet mixed backhauls and time windows. Int J Appl Metaheuristic Comput 7(4):18–38. https://doi.org/10.4018/IJAMC.2016100102
Bianchessi N, Righini G (2007) Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery. Comput Oper Res 34(2):578–594. https://doi.org/10.1016/j.cor.2005.03.014. http://www.sciencedirect.com/science/article/pii/S0305054805001097(reverse Logistics)
Bortfeldt A, Hahn T, Männel D, Mönch L (2015) Hybrid algorithms for the vehicle routing problem with clustered backhauls and 3D loading constraints. Eur J Oper Res 243(1):82–96. https://doi.org/10.1016/j.ejor.2014.12.001. https://linkinghub.elsevier.com/retrieve/pii/S0377221714009837
Braekers K, Ramaekers K, Van Nieuwenhuyse I (2016) The vehicle routing problem: state of the art classification and review. Comput Ind Eng 99:300–313. https://doi.org/10.1016/j.cie.2015.12.007. https://linkinghub.elsevier.com/retrieve/pii/S0360835215004775
Brandão J (2006) A new tabu search algorithm for the vehicle routing problem with backhauls. Eur J Oper Res 173(2):540–555. https://doi.org/10.1016/j.ejor.2005.01.042. http://linkinghub.elsevier.com/retrieve/pii/S0377221705001918
Brandão J (2016) A deterministic iterated local search algorithm for the vehicle routing problem with backhauls. TOP 24(2):445–465. https://doi.org/10.1007/s11750-015-0404-x
Bruglieri M, Mancini S, Pisacane O (2019) The green vehicle routing problem with capacitated alternative fuel stations. Comput Oper Res 112:104759. https://doi.org/10.1016/j.cor.2019.07.017. http://www.sciencedirect.com/science/article/pii/S0305054819301935
Caceres-Cruz J, Arias P, Guimarans D, Riera D, Juan AA (2014) Rich vehicle routing problem. ACM Comput Surv 47(2):1–28. https://doi.org/10.1145/2666003
Casco DO, Golden BL, Wasil EA (1988) Vehicle routing with backhauls: models, algorithms, and case studies. In: Golden B, Assad AA (eds) Vehicle routing: methods and studies, 16th edn. North-Holland, Amsterdam, pp 127–147
Çatay B (2010) A new saving-based ant algorithm for the vehicle routing problem with simultaneous pickup and delivery. Expert Syst Appl 37(10):6809–6817. https://doi.org/10.1016/j.eswa.2010.03.045. http://www.sciencedirect.com/science/article/pii/S0957417410002265
Catherine Early (2011) Delivering greener logistics. https://transform.iema.net/article/delivering-greener-logistics
Chardy M, Klopfenstein O (2012) Handling uncertainties in vehicle routing problems through data preprocessing. Transp Res Part E Logist Transp Rev 48(3):667–683. https://doi.org/10.1016/j.tre.2011.12.001. https://linkinghub.elsevier.com/retrieve/pii/S1366554511001438
Chávez JJS, Escobar JW, Echeverri MG (2016) A multi-objective pareto ant colony algorithm for the multi-depot vehicle routing problem with backhauls. Int J Ind Eng Comput 7(1):35–48. https://doi.org/10.5267/j.ijiec.2015.8.003. http://www.growingscience.com/ijiec/Vol7/IJIEC_2015_31.pdf
Chen JF, Wu TH (2006) Vehicle routing problem with simultaneous deliveries and pickups. J Oper Res Soc 57(5):579–587. https://doi.org/10.1057/palgrave.jors.2602028
Chen L, Gendreau M, Hà MH, Langevin A (2016) A robust optimization approach for the road network daily maintenance routing problem with uncertain service time. Transp Res Part E Logist Transp Rev 85:40–51. https://doi.org/10.1016/j.tre.2015.11.006. https://linkinghub.elsevier.com/retrieve/pii/S1366554515002094
Cheung RK, Hang DD (2003) Multi-attribute label matching algorithms for vehicle routing problems with time windows and backhauls. IIE Trans 35(3):191–205. https://doi.org/10.1080/07408170304371
Cho YJ, Wang SD (2005) A threshold accepting meta-heuristic for the vehicle routing problem with backhauls and time windows. J East Asia Soc Transp Stud 6:3022–3037
Clarke G, Wright JW (1964) Scheduling of vehicles from a central depot to a number of delivery points. Oper Res 12(4):568–581. https://doi.org/10.1287/opre.12.4.568
Crispim J, Brandão J (2005) Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls. J Oper Res Soc 56:1296–1302. https://doi.org/10.1057/palgrave.jors.2601935
Cuervo DP, 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(2):454–464. https://doi.org/10.1016/j.ejor.2014.02.011. http://linkinghub.elsevier.com/retrieve/pii/S037722171400126X
Davis LB, Sengul I, Ivy JS, Brock LG, Miles L (2014) Scheduling food bank collections and deliveries to ensure food safety and improve access. Socio Econ Plan Sci 48(3):175–188. https://doi.org/10.1016/j.seps.2014.04.001. https://linkinghub.elsevier.com/retrieve/pii/S0038012114000172
Deif I, Bodin L (1984) Extension of the Clarke and Wright algorithm for solving the vehicle routing problem with backhauling. In: Kidder A (ed) Proceedings of the Babson College conference on software uses in transportation and logistic management, Babson Park, MA, pp 75–96
Dell’Amico M, Righini G, Salani M (2006) A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection. Transp Sci 40(2):235–247. https://doi.org/10.1287/trsc.1050.0118
Demir E, Bektaş T, Laporte G (2014) The bi-objective pollution-routing problem. Eur J Oper Res 232(3):464–478. https://doi.org/10.1016/j.ejor.2013.08.002. https://linkinghub.elsevier.com/retrieve/pii/S0377221713006486
Demir E, Huang Y, Scholts S, Van Woensel T (2015) A selected review on the negative externalities of the freight transportation: modeling and pricing. Transp Res Part E Logist Transp Rev 77:95–114. https://doi.org/10.1016/j.tre.2015.02.020. https://linkinghub.elsevier.com/retrieve/pii/S1366554515000605
Derigs U, Metz A (1992) A matching-based approach for solving a delivery/pick-up vehicle routing problem with time constraints. Oper Res Spektrum 14(2):91–106. https://doi.org/10.1007/BF01720353
Dethloff J (2001) Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up. OR Spektrum 23(1):79–96. https://doi.org/10.1007/PL00013346
Dethloff J (2002) Relation between vehicle routing problems: an insertion heuristic for the vehicle routing problem with simultaneous delivery and pick-up applied to the vehicle routing problem with backhauls. J Oper Res Soc 53(1):115–118. https://doi.org/10.1057/palgrave.jors.2601263
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. https://doi.org/10.1016/j.ejor.2016.05.002. https://linkinghub.elsevier.com/retrieve/pii/S0957417415001682 https://linkinghub.elsevier.com/retrieve/pii/S0377221716303046
Dueck G, Scheuer T (1990) Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing. J Comput Phys 90(1):161–175. https://doi.org/10.1016/0021-9991(90)90201-B
Duhamel C, Potvin JY, Rousseau JM (1997) A tabu search heuristic for the vehicle routing problem with backhauls and time windows. Transp Sci 31(1):49–59. https://doi.org/10.1287/trsc.31.1.49
Eguia I, Racero J, Molina JC, Guerrero F (2013) Environmental issues in vehicle routing problems. Springer, Berlin, pp 215–241. https://doi.org/10.1007/978-3-642-32081-1_10
Eksioglu B, Vural AV, Reisman A (2009) The vehicle routing problem: a taxonomic review. Comput Ind Eng 57(4):1472–1483. https://doi.org/10.1016/j.cie.2009.05.009. https://linkinghub.elsevier.com/retrieve/pii/S0360835209001405. arXiv:1011.1669v3
Erdoğan S, Miller-Hooks E (2012) A green vehicle routing problem. Transp Res Part E Logist Transp Rev 48(1):100–114. https://doi.org/10.1016/j.tre.2011.08.001. https://linkinghub.elsevier.com/retrieve/pii/S1366554511001062
Evangelista P, Colicchia C, Creazza A (2017) Is environmental sustainability a strategic priority for logistics service providers? J Environ Manag 198:353–362. https://doi.org/10.1016/j.jenvman.2017.04.096. https://linkinghub.elsevier.com/retrieve/pii/S0301479717304541
Fischetti M, Toth P (1992) An additive bounding procedure for the asymmetric travelling salesman problem. Math Program 53(1):173–197. https://doi.org/10.1007/BF01585701
Fisher ML, Jaikumar R (1981) A generalized assignment heuristic for vehicle routing. Networks 11(2):109–124. https://doi.org/10.1002/net.3230110205
Gajpal Y, Abad P (2009) Multi-ant colony system (MACS) for a vehicle routing problem with backhauls. Eur J Oper Res 196(1):102–117. https://doi.org/10.1016/j.ejor.2008.02.025. https://linkinghub.elsevier.com/retrieve/pii/S0377221708002300
Ganesh K, Narendran T (2007) CLOVES: A cluster-and-search heuristic to solve the vehicle routing problem with delivery and pick-up. Eur J Oper Res 178(3):699–717. https://doi.org/10.1016/j.ejor.2006.01.037. http://linkinghub.elsevier.com/retrieve/pii/S0377221706001214
Gansterer M, Hartl RF (2018) Collaborative vehicle routing: a survey. Eur J Oper Res 268(1):1–12. https://doi.org/10.1016/j.ejor.2017.10.023. https://linkinghub.elsevier.com/retrieve/pii/S0377221717309360. arXiv:1706.05254
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. https://doi.org/10.1016/j.cie.2014.12.029. https://linkinghub.elsevier.com/retrieve/pii/S0360835214004586
Gélinas S, Desrochers M, Desrosiers J, Solomon MM (1995) A new branching strategy for time constrained routing problems with application to backhauling. Ann Oper Res 61(1):91–109. https://doi.org/10.1007/BF02098283
Ghaziri H, Osman IH (2003) A neural network algorithm for the traveling salesman problem with backhauls. Comput Ind Eng 44(2):267–281. https://doi.org/10.1016/S0360-8352(02)00179-1
Ghaziri H, Osman IH (2006) Self-organizing feature maps for the vehicle routing problem with backhauls. J Sched 9(2):97–114. https://doi.org/10.1007/s10951-006-6774-z
Goetschalckx M, Jacobs-Blecha C (1989) The vehicle routing problem with backhauls. Eur J Oper Res 42(1):39–51. https://doi.org/10.1016/0377-2217(89)90057-X
Golden BL, Raghavan S, Wasil EA (2008) The vehicle routing problem: latest advances and new challenges. Operations research/computer science interfaces series, vol 43. Springer, New York
Granada-Echeverri M, Toro EM, Santa JJ (2019) A mixed integer linear programming formulation for the vehicle routing problem with backhauls. Int J Ind Eng Comput 10:295–308. https://doi.org/10.5267/j.ijiec.2018.6.003. http://www.growingscience.com/ijiec/Vol10/IJIEC_2018_12.pdf
Gribkovskaia I, Halskau Myklebost K (2001) Models for pick-up and deliveries from depots with lasso solutions. In: Stefansson G, Tilanus B (eds) Proceedings of the 13th annual conference on logistics research NOFOMA 2001, Chalmers University of Technology, Göteborg, pp 279–293
Gribkovskaia I, Laporte G, Shyshou A (2008) The single vehicle routing problem with deliveries and selective pickups. Comput Oper Res 35(9):2908–2924. https://doi.org/10.1016/j.cor.2007.01.007. https://linkinghub.elsevier.com/retrieve/pii/S0305054807000111
Grossmann IE, Apap RM, Calfa BA, García-Herreros P, Zhang Q (2016) Recent advances in mathematical programming techniques for the optimization of process systems under uncertainty. Comput Chem Eng 91:3–14. https://doi.org/10.1016/j.compchemeng.2016.03.002. https://linkinghub.elsevier.com/retrieve/pii/S0098135416300540
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. https://doi.org/10.1016/j.ejor.2010.02.037. https://linkinghub.elsevier.com/retrieve/pii/S0377221710001700
Han J, Lee C, Park S (2014) A robust scenario approach for the vehicle routing problem with uncertain travel times. Transp Sci 48(3):373–390. https://doi.org/10.1287/trsc.2013.0476
Hertz A, Widmer M (2003) Guidelines for the use of meta-heuristics in combinatorial optimization. Eur J Oper Res 151(2):247–252. https://doi.org/10.1016/S0377-2217(02)00823-8
Hoff A, Gribkovskaia I, Laporte G, Løkketangen A (2009) Lasso solution strategies for the vehicle routing problem with pickups and deliveries. Eur J Oper Res 192(3):755–766. https://doi.org/10.1016/j.ejor.2007.10.021. https://linkinghub.elsevier.com/retrieve/pii/S0377221707010235
Juan AA, Faulin J, Pérez-Bernabeu E, Jozefowiez N (2014) Horizontal cooperation in vehicle routing problems with backhauling and environmental criteria. Proced Soc Behav Sci 111:1133–1141. https://doi.org/10.1016/j.sbspro.2014.01.148. http://linkinghub.elsevier.com/retrieve/pii/S1877042814001499
Kara Kara BY, Yetis MK (2007) Energy minimizing vehicle routing problem. In: Combinatorial optimization and applications. Springer, Berlin, pp 62–71. https://doi.org/10.1007/978-3-540-73556-4_9. http://www.mendeley.com/research/lecture-notes-computer-science-2/
Katoh N, Yano T (2006) An approximation algorithm for the pickup and delivery vehicle routing problem on trees. Discrete Appl Math 154(16):2335–2349. https://doi.org/10.1016/j.dam.2006.04.028. http://www.sciencedirect.com/science/article/pii/S0166218X06001892(discrete Algorithms and Optimization, in Honor of Professor Toshihide Ibaraki at His Retirement from Kyoto University)
Koç Ç, Laporte G (2018) Vehicle routing with backhauls: review and research perspectives. Comput Oper Res 91:79–91. https://doi.org/10.1016/j.cor.2017.11.003. https://linkinghub.elsevier.com/retrieve/pii/S0305054817302794
Kontoravdis G, Bard JF (1995) A grasp for the vehicle routing problem with time windows. ORSA J Comput 7(1):10–23. https://doi.org/10.1287/ijoc.7.1.10
Küçükoğlu Öztürk N (2014) A differential evolution approach for the vehicle routing problem with backhauls and time windows. J Adv Transp 48(8):942–956. https://doi.org/10.1002/atr.1237
Küçükoğlu, Ö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. https://doi.org/10.1016/j.cie.2014.10.014. https://linkinghub.elsevier.com/retrieve/pii/S0360835214003453
Kumar R, Unnikrishnan A, Waller ST (2011) Capacitated-vehicle routing problem with backhauls on trees. Transp Res Rec J Transp Res Board 2263(1):92–102. https://doi.org/10.3141/2263-11
Labbé M, Laporte G, Mercure H (1991) Capacitated vehicle routing on trees. Oper Res 39(4):616–622. https://doi.org/10.1287/opre.39.4.616
Lai M, Crainic TG, Di Francesco M, Zuddas P (2013) An heuristic search for the routing of heterogeneous trucks with single and double container loads. Transp Res Part E Logist Transp Rev 56:108–118. https://doi.org/10.1016/j.tre.2013.06.001. https://linkinghub.elsevier.com/retrieve/pii/S1366554513001154
Lai M, Battarra M, Di Francesco M, Zuddas P (2015) An adaptive guidance meta-heuristic for the vehicle routing problem with splits and clustered backhauls. J Oper Res Soc 66(7):1222–1235. https://doi.org/10.1057/jors.2014.123
Lee C, Lee K, Park S (2012) Robust vehicle routing problem with deadlines and travel time/demand uncertainty. J Oper Res Soc 63(9):1294–1306. https://doi.org/10.1057/jors.2011.136
Li X, Tian P, Leung SC (2010) Vehicle routing problems with time windows and stochastic travel and service times: models and algorithm. Int J Prod Econ 125(1):137–145. https://doi.org/10.1016/j.ijpe.2010.01.013. https://linkinghub.elsevier.com/retrieve/pii/S092552731000023X
Lin C, Choy K, Ho G, Chung S, Lam H (2014) Survey of green vehicle routing problem: past and future trends. Expert Syst Appl 41(4):1118–1138. https://doi.org/10.1016/j.eswa.2013.07.107. https://linkinghub.elsevier.com/retrieve/pii/S095741741300609X
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. https://doi.org/10.1016/j.trc.2017.01.005
Liu SC, Chung CH (2009) A heuristic method for the vehicle routing problem with backhauls and inventory. J Intell Manuf 20(1):29–42. https://doi.org/10.1007/s10845-008-0101-9
Lu EHC, Yang YW (2019) A hybrid route planning approach for logistics with pickup and delivery. Expert Syst Appl 118:482–492. https://doi.org/10.1016/j.eswa.2018.10.031
Mancini S (2016) A real-life multi depot multi period vehicle routing problem with a heterogeneous fleet: formulation and adaptive large neighborhood search based matheuristic. Transp Res Part C Emerg Technol 70:100–112. https://doi.org/10.1016/j.trc.2015.06.016. https://linkinghub.elsevier.com/retrieve/pii/S0968090X15002314
Min H (1989) The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transp Res Part A Gen 23(5):377–386. https://doi.org/10.1016/0191-2607(89)90085-X
Mingozzi A, Giorgi S, Baldacci R (1999) An exact method for the vehicle routing problem with backhauls. Transp Sci 33(3):315–329. https://doi.org/10.1287/trsc.33.3.315
Montané FAT, Galvão RD (2006) A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Comput Oper Res 33(3):595–619. https://doi.org/10.1016/j.cor.2004.07.009. http://www.sciencedirect.com/science/article/pii/S0305054804001741
Mosheiov G (1994) The travelling salesman problem with pick-up and delivery. Eur J Oper Res 79(2):299–310. https://doi.org/10.1016/0377-2217(94)90360-3
Mosheiov G (1998) Vehicle routing with pick-up and delivery: tour-partitioning heuristics. Comput Ind Eng 34(3):669–684. https://doi.org/10.1016/S0360-8352(97)00275-1
Naderipour M, Alinaghian M (2016) Measurement, evaluation and minimization of CO2, NOx, and CO emissions in the open time dependent vehicle routing problem. Measurement 90:443–452. https://doi.org/10.1016/j.measurement.2016.04.043. http://www.sciencedirect.com/science/article/pii/S0263224116301105
Nagy G, Salhi S (2005) Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries. Eur J Oper Res 162(1):126–141. https://doi.org/10.1016/j.ejor.2002.11.003. http://www.sciencedirect.com/science/article/pii/S0377221703008361(logistics: From Theory to Application)
Nagy G, Wassan NA, Speranza MG, Archetti C (2013) The vehicle routing problem with divisible deliveries and pickups. Transp Sci 49(2):271–294. https://doi.org/10.1287/trsc.2013.0501
Nguyen PK, Crainic TG, Toulouse M (2016) Multi-trip pickup and delivery problem with time windows and synchronization. Ann Oper Res 253(2):899–934. https://doi.org/10.1007/s10479-015-2001-7
Nikolakopoulos A (2015) A metaheuristic reconstruction algorithm for solving bi-level vehicle routing problems with backhauls for army rapid fielding. In: Zeimpekis V, Kaimakamis G, Daras NJ (eds) Military logistics. Operations research/computer science interfaces series, vol 56, Springer International Publishing, pp 141–157. https://doi.org/10.1007/978-3-319-12075-1_8. http://link.springer.com/10.1007/978-3-319-12075-1
Oberhofer P, Dieplinger M (2014) Sustainability in the transport and logistics sector: lacking environmental measures. Bus Strategy Environ 23(4):236–253. https://doi.org/10.1002/bse.1769
Oesterle J, Bauernhansl T (2016) Exact method for the vehicle routing problem with mixed linehaul and backhaul customers, heterogeneous fleet, time window and manufacturing capacity. Proced CIRP 41:573–578. https://doi.org/10.1016/j.procir.2015.12.040. https://linkinghub.elsevier.com/retrieve/pii/S2212827115011191
Osman IH, Wassan NA (2002) A reactive tabu search meta-heuristic for the vehicle routing problem with back-hauls. J Sched 5(4):263–285. https://doi.org/10.1002/jos.122
Paraphantakul C, Miller-Hooks E, Opasanon S (2012) Scheduling deliveries with backhauls in Thailand’s cement industry. Transp Res Rec 2269(1):73–82. https://doi.org/10.3141/2269-09. arXiv:1011.1669v3
Parragh SN, Doerner KF, Hartl RF (2008a) A survey on pickup and delivery problems, part I: transportation between customers and depot. J Betriebswirtschaft 58(1):21–51. https://doi.org/10.1007/s11301-008-0033-7
Parragh SN, Doerner KF, Hartl RF (2008b) A survey on pickup and delivery problems, part II: transportation between pickup and delivery locations. J Betriebswirtschaft 58:81–117. https://doi.org/10.1007/s11301-008-0036-4
Potvin JY, Duhamel C, Guertin F (1996) A genetic algorithm for vehicle routing with backhauling. Appl Intell 6(4):345–355. https://doi.org/10.1007/BF00132738
Pradenas L, Oportus B, Parada V (2013) Mitigation of greenhouse gas emissions in vehicle routing problems with backhauling. Expert Syst Appl 40(8):2985–2991. https://doi.org/10.1016/j.eswa.2012.12.014. https://linkinghub.elsevier.com/retrieve/pii/S0957417412012559
Privé J, Renaud J, Boctor F, Laporte G (2006) Solving a vehicle-routing problem arising in soft-drink distribution. J Oper Res Soc 57(9):1045–1052. https://doi.org/10.1057/palgrave.jors.2602087
Rahimi M, Baboli A, Rekik Y (2016) Sustainable inventory routing problem for perishable products by considering reverse logistic. IFAC Pap Online 49(12):949–954. https://doi.org/10.1016/j.ifacol.2016.07.898. https://linkinghub.elsevier.com/retrieve/pii/S2405896316311843
Ramos TRP, Gomes MI, Barbosa-Póvoa AP (2014) Planning a sustainable reverse logistics system: balancing costs with environmental and social concerns. Omega 48:60–74. https://doi.org/10.1016/j.omega.2013.11.006. https://linkinghub.elsevier.com/retrieve/pii/S0305048313001175(NIHMS150003)
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. https://doi.org/10.1016/j.ejor.2017.10.029
Reimann M, Ulrich H (2006) Comparing backhauling strategies in vehicle routing using ant colony optimization. Cent Eur J Oper Res 14(2):105–123. https://doi.org/10.1007/s10100-006-0163-8
Reimann M, Doerner K, Hartl RF (2002) Insertion based ants for vehicle routing problems with backhauls and time windows. In: Dorigo M, Di Caro G, Sampels M (eds) Ant Algorithms. Springer, Heidelberg, pp 135–148
Ritzinger U, Puchinger J, Hartl RF (2016) A survey on dynamic and stochastic vehicle routing problems. Int J Prod Res 54(1):215–231. https://doi.org/10.1080/00207543.2015.1043403
Ropke S, Pisinger D (2006) A unified heuristic for a large class of vehicle routing problems with backhauls. Eur J Oper Res 171(3):750–775. https://doi.org/10.1016/j.ejor.2004.09.004. http://linkinghub.elsevier.com/retrieve/pii/S0377221704005831
Salhi S, Nagy G (1999) A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling. J Oper Res Soc 50(10):1034–1042. https://doi.org/10.1057/palgrave.jors.2600808
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. https://doi.org/10.1016/j.tre.2013.05.005. https://linkinghub.elsevier.com/retrieve/pii/S1366554513001142
Saremi A, Elmekkawy TY, Wang GG (2007) Tuning the parameters of a memetic algorithm to solve vehicle routing problem with backhauls using design of experiments. Int J Oper Res 4(4):206–219
Seuring S, Müller M, Westhaus M, Morana R (2005) Conducting a literature review–the example of sustainability in supply chains. Research methodologies in supply chain management. Physica-Verlag, Heidelberg, pp 91–106. https://doi.org/10.1007/3-7908-1636-1_7
Shapley LS (1953) A value for n-person games. Ann Math Stud 28:307–318. https://www.cambridge.org/core/product/identifier/CBO9780511528446A008/type/book_part
Smith DS (2017) Tesco food waste case study. https://www.dssmith.com/recycling/insights/case-studies/tesco-food-waste-case-study
Sofge D, Schultz A, De Jong K (2002) Evolutionary computational approaches to solving the multiple traveling salesman problem using a neighborhood attractor schema. In: Cagnoni S, Gottlieb J, Hart E, Middendorf M, Raidl GR (eds) Applications of evolutionary computing, vol 2279. Springer, Berlin, pp 153–162
Soleimani H, Chaharlang Y, Ghaderi H (2018) Collection and distribution of returned-remanufactured products in a vehicle routing problem with pickup and delivery considering sustainable and green criteria. J Clean Prod 172:960–970. https://doi.org/10.1016/j.jclepro.2017.10.124
Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper Res 35(2):254–265. https://doi.org/10.1287/opre.35.2.254
Subramanian A, Drummond L, Bentes C, Ochi L, Farias R (2010) A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery. Comput Oper Res 37(11):1899–1911. https://doi.org/10.1016/j.cor.2009.10.011. http://www.sciencedirect.com/science/article/pii/S0305054809002779(metaheuristics for Logistics and Vehicle Routing)
Subramanian A, Uchoa E, Pessoa AA, Ochi LS (2011) Branch-and-cut with lazy separation for the vehicle routing problem with simultaneous pickup and delivery. Oper Res Lett 39(5):338–341. https://doi.org/10.1016/j.orl.2011.06.012. http://www.sciencedirect.com/science/article/pii/S0167637711000666
Subramanian A, Uchoa E, Pessoa AA, Ochi LS (2012) Branch-cut-and-price for the vehicle routing problem with simultaneous pickup and delivery. Optim Lett 7(7):1569–1581. https://doi.org/10.1007/s11590-012-0570-9
Subramanian A, Uchoa E, Ochi LS (2013) A hybrid algorithm for a class of vehicle routing problems. Comput Oper Res 40(10):2519–2531. https://doi.org/10.1016/j.cor.2013.01.013. http://www.sciencedirect.com/science/article/pii/S030505481300021X
Süral H, Bookbinder JH (2003) The single-vehicle routing problem with unrestricted backhauls. Networks 41(3):127–136. https://doi.org/10.1002/net.10067
Tarantilis CD, Anagnostopoulou AK, Repoussis PP (2013) Adaptive path relinking for vehicle routing and scheduling problems with product returns. Transp Sci 47(3):356–379. https://doi.org/10.1287/trsc.1120.0439
Tavakkoli-Moghaddam R, Saremi A, Ziaee M (2006) A memetic algorithm for a vehicle routing problem with backhauls. Appl Math Comput 181(2):1049–1060. https://doi.org/10.1016/j.amc.2006.01.059. http://linkinghub.elsevier.com/retrieve/pii/S0096300306001883
Thangiah SR, Potvin JY, Sun T (1996) Heuristic approaches to vehicle routing with backhauls and time windows. Comput Oper Res 23(11):1043–1057. https://doi.org/10.1016/0305-0548(96)00018-4
Toth P, Vigo D (1996) A heuristic algorithm for the vehicle routing problem with backhauls. In: Bianco L, Toth P (eds) Advanced methods in transportation analysis. Springer, Heidelberg, pp 585–608
Toth P, Vigo D (1997) An exact algorithm for the vehicle routing problem with backhauls. Transp Sci 31(4):372–385. https://doi.org/10.1287/trsc.31.4.372
Toth P, Vigo D (1999) A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls. Eur J Oper Res 113(3):528–543. https://doi.org/10.1016/S0377-2217(98)00086-1
Toth P, Vigo D (2002a) 8. VRP with backhauls. In: Toth P, Vigo D (eds) The vehicle routing problem. SIAM, Philadelphia, vol 9, pp 195–224. https://doi.org/10.1137/1.9780898718515.ch8
Toth P, Vigo D (2002b) The vehicle routing problem. SIAM monographs on discrete mathematics and applications, Philadelphia: Society for Industrial and Applied Mathematics, DOI 10(1137/1):9780898718515
Toth P, Vigo D (eds) (2014) Vehicle routing: problems, methods, and applications, 2nd edition. No. 18 in MOS-SIAM Series on Optimization, SIAM, Philadelphia
Turkensteen M, Hasle G (2017) Combining pickups and deliveries in vehicle routing—an assessment of carbon emission effects. Transp Res Part C Emerg Technol 80:117–132. https://doi.org/10.1016/j.trc.2017.04.006. https://linkinghub.elsevier.com/retrieve/pii/S0968090X17301122
Tütüncü GY (2010) An interactive GRAMPS algorithm for the heterogeneous fixed fleet vehicle routing problem with and without backhauls. Eur J Oper Res 201(2):593–600. https://doi.org/10.1016/j.ejor.2009.03.044. https://linkinghub.elsevier.com/retrieve/pii/S0377221709001957
Tütüncü GY, Carreto C, Baker B (2009) A visual interactive approach to classical and mixed vehicle routing problems with backhauls. Omega 37(1):138–154. https://doi.org/10.1016/j.omega.2006.11.001. https://linkinghub.elsevier.com/retrieve/pii/S0305048306001356
Ubeda S, Arcelus F, Faulin J (2011) Green logistics at Eroski: a case study. Int J Prod Econ 131(1):44–51. https://doi.org/10.1016/j.ijpe.2010.04.041. https://linkinghub.elsevier.com/retrieve/pii/S092552731000174X
Vidal T, Crainic TG, Gendreau M, Prins C (2014) A unified solution framework for multi-attribute vehicle routing problems. Eur J Oper Res 234(3):658–673. https://doi.org/10.1016/j.ejor.2013.09.045. https://linkinghub.elsevier.com/retrieve/pii/S037722171300800X
Wade A, Salhi S (2002) An investigation into a new class of vehicle routing problem with backhauls. Omega 30(6):479–487. https://doi.org/10.1016/S0305-0483(02)00056-7. http://kar.kent.ac.uk/5274/
Wade A, Salhi S (2004) An ant system algorithm for the mixed vehicle routing problem with backhauls. Springer, Boston, pp 699–719. https://doi.org/10.1007/978-1-4757-4137-7_33
Wang Z, Wang Z (2009) A novel two-phase heuristic method for vehicle routing problem with backhauls. Comput Math Appl 57(11–12):1923–1928. https://doi.org/10.1016/j.camwa.2008.10.045. https://linkinghub.elsevier.com/retrieve/pii/S0898122108005312
Wassan N (2007) Reactive tabu adaptive memory programming search for the vehicle routing problem with backhauls. J Oper Res Soc 58(12):1630–1641. https://doi.org/10.1057/palgrave.jors.2602313
Wassan N, Wassan N, Nagy G, Salhi S (2017) The multiple trip vehicle routing problem with backhauls: formulation and a two-level variable neighbourhood search. Comput Oper Res 78:454–467. https://doi.org/10.1016/j.cor.2015.12.017. https://linkinghub.elsevier.com/retrieve/pii/S0305054815003032
Wassan NA, Nagy G, Ahmadi S (2008a) A heuristic method for the vehicle routing problem with mixed deliveries and pickups. J Sched 11(2):149–161. https://doi.org/10.1007/s10951-008-0055-y
Wassan NA, Wassan AH, Nagy G (2008b) A reactive tabu search algorithm for the vehicle routing problem with simultaneous pickups and deliveries. J Comb Optim 15(4):368–386. https://doi.org/10.1007/s10878-007-9090-4
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. https://doi.org/10.1016/j.asoc.2016.05.011. http://linkinghub.elsevier.com/retrieve/pii/S1568494616302125
Yalcın GD, Erginel N (2015) Fuzzy multi-objective programming algorithm for vehicle routing problems with backhauls. Expert Syst Appl 42(13):5632–5644. https://doi.org/10.1016/j.eswa.2015.02.060. https://linkinghub.elsevier.com/retrieve/pii/S0957417415001682
Yano CA, Chan TJ, Richter LK, Cutler T, Murty KG, McGettigan D (1987) Vehicle routing at quality stores. Interfaces 17(2):52–63. http://www.jstor.org/stable/25060942
Yu M, Qi X (2014) A vehicle routing problem with multiple overlapped batches. Transp Res Part E Logist Transp Rev 61:40–55. https://doi.org/10.1016/j.tre.2013.10.004. https://linkinghub.elsevier.com/retrieve/pii/S1366554513001701
Zachariadis EE, Kiranoudis CT (2012) An effective local search approach for the vehicle routing problem with backhauls. Expert Syst Appl 39(3):3174–3184. https://doi.org/10.1016/j.eswa.2011.09.004. https://linkinghub.elsevier.com/retrieve/pii/S0957417411013133
Zachariadis EE, Tarantilis CD, Kiranoudis CT (2009) A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service. Expert Syst Appl 36(2, Part 1):1070–1081. https://doi.org/10.1016/j.eswa.2007.11.005. http://www.sciencedirect.com/science/article/pii/S095741740700526X
Zachariadis EE, Tarantilis CD, Kiranoudis CT (2010) An adaptive memory methodology for the vehicle routing problem with simultaneous pick-ups and deliveries. Eur J Oper Res 202(2):401–411. https://doi.org/10.1016/j.ejor.2009.05.015. http://www.sciencedirect.com/science/article/pii/S0377221709003476
Zachariadis EE, Tarantilis CD, Kiranoudis CT (2015) Vehicle routing strategies for pick-up and delivery service under two dimensional loading constraints. Oper Res 17(1):115–143. https://doi.org/10.1007/s12351-015-0218-5
Zhong Y, Cole MH (2005) A vehicle routing problem with backhauls and time windows: a guided local search solution. Transp Res Part E Logist Transp Rev 41(2):131–144. https://doi.org/10.1016/j.tre.2003.12.003. http://linkinghub.elsevier.com/retrieve/pii/S136655450400016X
Zhu Z, Chu F, Sun L (2010) The capacitated plant location problem with customers and suppliers matching. Transp Res Part E Logist Transp Rev 46(3):469–480. https://doi.org/10.1016/j.tre.2009.09.002. https://linkinghub.elsevier.com/retrieve/pii/S1366554509001227
Acknowledgements
This work is financed by the ERDF—European Regional Development Fund through the Operational Programme for Competitiveness and Internationalisation—COMPETE 2020 Programme and by National Funds through the Portuguese funding agency, FCT—Fundação para a Ciência e a Tecnologia within project POCI-01-0145-FEDER-016733 (Easyflow).
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendices
Appendix A Classification of VRPB works
Appendix B Benchmark instances
Appendix C: Cases studies and applications of VRPB and variants
Rights and permissions
About this article
Cite this article
Santos, M.J., Amorim, P., Marques, A. et al. The vehicle routing problem with backhauls towards a sustainability perspective: a review. TOP 28, 358–401 (2020). https://doi.org/10.1007/s11750-019-00534-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-019-00534-0