Abstract
There are numerous practical vehicle routing applications in which vehicles have to stop at certain facilities along their routes to be able to continue their service. At these stops, the vehicles replenish or unload their cargo or they stop to refuel. In this paper, we study the vehicle routing problem with intermediate stops (VRPIS), which considers stopping requirements at intermediate facilities. Service times occur at these stops and may depend on the load level or fuel level on arrival. This is incorporated into the routing model to respect route duration constraints. We develop an adaptive variable neighborhood search (AVNS) to solve the VRPIS. The adaptive mechanism guides the shaking step of the AVNS by favoring the route and vertex selection methods according to their success within the search. The performance of the AVNS is demonstrated on test instances for VRPIS variants available in the literature. Furthermore, we conduct tests on newly generated instances of the electric vehicle routing problem with recharging facilities, which can also be modeled as VRPIS variant. In this problem, battery electric vehicles need to recharge their battery en route at respective recharging facilities.
Similar content being viewed by others
References
Amaya A, Langevin A, Trépanier M (2007) The capacitated arc routing problem with refill points. Oper Res Lett 35(1):45–53
Angelelli E, Speranza MG (2002) The periodic vehicle routing problem with intermediate facilities. Eur J Oper Res 137:233–247
Archetti C, Speranza MG, Vigo D (2013) Vehicle routing problems with profits. Tech. Rep. WPDEM 2013/3, Department of Economics and Management, University of Brescia
Bard J, Huang L, Dror M, Jaillet P (1998) A branch and cut algorithm for the VRP with satellite facilities. IIE Trans 30(9):821–834
Barnes J, Wiley V, Moore J, Ryer D (2004) Solving the aerial fleet refueling problem using group theoretic tabu search. Math Comput Model 39(6–8):617–640
Beliën J, Boeck LD, Ackere JV (2014) Municipal solid waste collection and management problems: A literature review. Trans Sci 48(1):78–102
Benjamin A, Beasley J (2010) Metaheuristics for the waste collection vehicle routing problem with time windows, driver rest period and multiple disposal facilities. Comput Oper Res 37(12):2270–2280
Christofides N, Eilon S (1969) An algorithm for the vehicle-dispatching problem. Oper Res Quart 20(3):309–318
Clarke G, Wright JW (1964) Scheduling of vehicles from a central depot to a number of delivery points. Oper Res 12(4):568–581
Coene S, Arnout A, Spieksma FCR (2010) On a periodic vehicle routing problem. J Oper Res Soc 61:1719–1728
Conrad RG, Figliozzi MA (2011) The recharging vehicle routing problem. In: Doolen T, Aken EV (eds) Proceedings Industrial Engineering Research Conference
Cordeau JF, Gendreau M, Laporte G (1997) A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks 30(2):105–119
Crainic TG, Ricciardi N, Storchi G (2009) Models for evaluating and planning city logistics systems. Transp Sci 43(4):432–454
Crevier B, Cordeau JF, Laporte G (2007) The multi-depot vehicle routing problem with inter-depot routes. Eur J Oper Res 176:756–773
Erdoğan S, Miller-Hooks E (2012) A green vehicle routing problem. Transp Res Part E Logist Transp Rev 48(1):100–114
Golden BL, Wasil EA, Kelly JP, Chao IM (1998) The impact of metaheuristics on solving the vehicle routing problem: Algorithms, problem sets and computational results. In: Crainic T, Laporte G (eds) Fleet management and logistics. Kluwer, Boston, pp 33–56
Hansen P, Mladenović N (2001) Variable neighborhood search: principles and applications. Eur J Oper Res 130(3):449–467
Hemmelmayr V, Doerner K, Hartl R, Rath S (2013) A heuristic solution method for node routing based solid waste collection problems. J Heuristics 19(2):129–156
Hemmelmayr VC, Doerner KF, Hartl RF (2009) A variable neighborhood search heuristic for periodic routing problems. Eur J Oper Res 195(3):791–802
Kim BI, Kim S, Sahoo S (2006) Waste collection vehicle routing problem with time windows. Comput Oper Res 33:3624–3642
Lin S (1965) Computer solutions to the traveling-salesman problem. Bell Syst Techn J 44(10):2245–2269
Mester D, Bräysy O (2007) Active-guided evolution strategies for large-scale capacitated vehicle routing problems. Comput Oper Res 34(10):2964–2975
Or I (1976) Traveling salesman-type problems and their relation to the logistics of regional blood banking. Ph.D. thesis, Department of Industrial Engineering and Management Sciences, Northwestern University Evanston, USA
Perrier N, Langevin A, Campbell JF (2007) A survey of models and algorithms for winter road maintenance. Part IV: Vehicle routing and fleet sizing for plowing and snow disposal. Comput Oper Res 34(1):258–294
Pisinger D, Ropke S (2007) A general heuristic for vehicle routing problems. Comput Oper Res 34(8):2403–2435
Prescott-Gagnon E, Desaulniers G, Rousseau LM (2012) Heuristics for an oil delivery vehicle routing problem, forthcoming in Flexible Services and Manufacturing Journal
Raviv T, Kaspi M (2012) The locomotive fleet fueling problem. Oper Res Lett 40(1):39–45
Rochat Y, Taillard E (1995) Probabilistic diversification and intensification in local search for vehicle routing. J Heuristics 1(1):147–167
Ropke S, Pisinger D (2006) An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp Sci 40(4):455–472
Salazar-Aguilar MA, Langevin A, Laporte G (2013) The synchronized arc and node routing problem: application to road marking. Comput Oper Res 40(7):1708–1715
Savelsbergh M (1992) The vehicle routing problem with time windows: minimizing route duration. ORSA J Comput 4(2):146–154
Schneider M, Stenger A, Goeke D (2014) The electric vehicle routing problem with time windows and recharging stations. Transp Sci Artic Adv. doi:10.1287/trsc.2013.0490
Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper Res 35(2):254–265
Stenger A, Schneider M, Goeke D (2013a) The prize-collecting vehicle routing problem with single and multiple depots and non-linear cost. EURO J Transp Logis 2(1–2):57–87
Stenger A, Vigo D, Enz S, Schwind M (2013b) An adaptive variable neighborhood search algorithm for a vehicle routing problem arising in small package shipping. Transp Sci 47(1):64–80
Tarantilis CD, Zachariadis EE, Kiranoudis CT (2008) A hybrid guided local search for the vehicle-routing problem with intermediate replenishment facilities. INFORMS J Comput 20(1):154–168
Thompson PM, Orlin JB (1989) Theory of cyclic transfers. Working Paper, MIT, Operations Research Center, Cambridge, USA
Vidal T, Crainic TG, Gendreau M, Lahrichi N, Rei W (2012) A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Oper Res 60(3):611–624
Wang YW, Lin CC (2013) Locating multiple types of recharging stations for battery-powered electric vehicle transport. Transp Res Part E Logis Transp Rev 58:76–87
Author information
Authors and Affiliations
Corresponding author
Appendix: Influence of problem-specific components
Appendix: Influence of problem-specific components
Table 12 shows a comparison of our AVNS to an AVNS without the problem-specific components addressing intermediate stops (denoted as \(\text {AVNS-without}\)) on the VRPIRF instances of Crevier et al. (2007). For each instance, we report the instance name and the BKS. Moreover, we provide the average solution found in the ten runs (\(L^\mathrm{{avg}}\)), the gap of the average solution to the BKS (\(\Delta ^\mathrm{{avg}}\)) and the average runtime in minutes (\(t^\mathrm{{avg}}\)) for both methods. Finally, averages of the runtimes and the gaps to the BKS over the complete set of instances are given at the end of the table. Results show that adding the problem-specific components clearly improves the solution quality while notably reducing runtimes.
Rights and permissions
About this article
Cite this article
Schneider, M., Stenger, A. & Hof, J. An adaptive VNS algorithm for vehicle routing problems with intermediate stops. OR Spectrum 37, 353–387 (2015). https://doi.org/10.1007/s00291-014-0376-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00291-014-0376-5