Enhanced solution representations for vehicle routing problems with split deliveries

Abstract

In this study, we investigate a forest-based solution representation for split delivery vehicle routing problems (SDVRPs), which have several practical applications and are among the most difficult vehicle routing problems. The new solution representation fully reflects the nature of split delivery, and can help reduce the search space when used in heuristic algorithms. Based on the forest structure, we devise three neighborhood search operators. To highlight the effectiveness of this solution representation, we integrate these operators into a standard tabu search framework. We conduct extensive experiments on three main SDVRPs addressed in the literature: The basic SDVRP, the multidepot SDVRP, and the SDVRP with time windows. The experimental results show that the new forest-based solution representation is particularly effective in designing and implementing neighborhood operators, and that our new approach outperforms state-of-the-art algorithms on standard datasets.

Graphical abstract

Keywords

vehicle routing / multidepot / time windows / tabu search / split delivery

References

[1] AhujaR KMagnantiT LOrlinJ B (1993). Network Flows: Theory, Algorithms, and Applications. Englewood Cliffs, NJ: Prentice Hall

[2] Aleman, R E Hill, R R (2010). A tabu search with vocabulary building approach for the vehicle routing problem with split demands. International Journal of Metaheuristics, 1( 1): 55–80

[3] Aleman, R E Zhang, X Hill, R R (2010). An adaptive memory algorithm for the split delivery vehicle routing problem. Journal of Heuristics, 16( 3): 441–473

[4] Archetti, C Bianchessi, N Speranza, M G (2011a). A column generation approach for the split delivery vehicle routing problem. Networks: An International Journal, 58( 4): 241–254

[5] Archetti, C Bianchessi, N Speranza, M G (2014). Branch-and-cut algorithms for the split delivery vehicle routing problem. European Journal of Operational Research, 238( 3): 685–698

[6] Archetti, C Bouchard, M Desaulniers, G (2011b). Enhanced branch and price and cut for vehicle routing with split deliveries and time windows. Transportation Science, 45( 3): 285–298

[7] ArchettiCSperanzaM G (2008). The split delivery vehicle routing problem: A survey. In: Golden B, Raghavan S, Wasil E, eds. The Vehicle Routing Problem: Latest Advances and New Challenges. New York, NY: Springer, 103–122

[8] Archetti, C Speranza, M G Hertz, A (2006). A tabu search algorithm for the split delivery vehicle routing problem. Transportation Science, 40( 1): 64–73

[9] Archetti, C Speranza, M G Savelsbergh, M W (2008). An optimization-based heuristic for the split delivery vehicle routing problem. Transportation Science, 42( 1): 22–31

[10] Azad, A S Islam, M Chakraborty, S (2017). A heuristic initialized stochastic memetic algorithm for MDPVRP with interdependent depot operations. IEEE Transactions on Cybernetics, 47( 12): 4302–4315

[11] Baldacci, R Mingozzi, A Roberti, R (2012). Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints. European Journal of Operational Research, 218( 1): 1–6

[12] Belenguer, J M Martinez, M C Mota, E (2000). A lower bound for the split delivery vehicle routing problem. Operations Research, 48( 5): 801–810

[13] Berbotto, L García, S Nogales, F J (2014). A randomized granular tabu search heuristic for the split delivery vehicle routing problem. Annals of Operations Research, 222( 1): 153–173

[14] Bianchessi, N Irnich, S (2019). Branch-and-cut for the split delivery vehicle routing problem with time windows. Transportation Science, 53( 2): 442–462

[15] Bortfeldt, A Yi, J (2020). The split delivery vehicle routing problem with three-dimensional loading constraints. European Journal of Operational Research, 282( 2): 545–558

[16] Chen, P Golden, B Wang, X Wasil, E (2017). A novel approach to solve the split delivery vehicle routing problem. International Transactions in Operational Research, 24( 1–2): 27–41

[17] Chen, S Golden, B Wasil, E (2007). The split delivery vehicle routing problem: Applications, algorithms, test problems, and computational results. Networks: An International Journal, 49( 4): 318–329

[18] Christofides, N Eilon, S (1969). An algorithm for the vehicle-dispatching problem. Journal of the Operational Research Society, 20( 3): 309–318

[19] Cordeau, J F Gendreau, M Laporte, G (1997). A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks: An International Journal, 30( 2): 105–119

[20] Derigs, U Li, B Vogel, U (2010). Local search-based metaheuristics for the split delivery vehicle routing problem. Journal of the Operational Research Society, 61( 9): 1356–1364

[21] Desaulniers, G (2010). Branch-and-price-and-cut for the split-delivery vehicle routing problem with time windows. Operations Research, 58( 1): 179–192

[22] Dror, M Trudeau, P (1989). Savings by split delivery routing. Transportation Science, 23( 2): 141–145

[23] Gendreau, M Hertz, A Laporte, G (1994). A tabu search heuristic for the vehicle routing problem. Management Science, 40( 10): 1276–1290

[24] Gillett, B E Johnson, J G (1976). Multi-terminal vehicle-dispatch algorithm. Omega, 4( 6): 711–718

[25] Glover, F (1989). Tabu search—Part I. ORSA Journal on Computing, 1( 3): 190–206

[26] Glover, F (1990). Tabu search—Part II. ORSA Journal on Computing, 2( 1): 4–32

[27] Gulczynski, D Golden, B Wasil, E (2011). The multi-depot split delivery vehicle routing problem: An integer programming-based heuristic, new test problems, and computational results. Computers & Industrial Engineering, 61( 3): 794–804

[28] GulczynskiD J (2010). Integer Programming-based Heuristics for Vehicle Routing Problems. Dissertation for the Doctoral Degree. College Park, MD: University of Maryland

[29] Han, A F W Chu, Y C (2016). A multi-start heuristic approach for the split-delivery vehicle routing problem with minimum delivery amounts. Transportation Research Part E: Logistics and Transportation Review, 88: 11–31

[30] Ho, S C Haugland, D (2004). A tabu search heuristic for the vehicle routing problem with time windows and split deliveries. Computers & Operations Research, 31( 12): 1947–1964

[31] Jin, M Liu, K Bowden, R O (2007). A two-stage algorithm with valid inequalities for the split delivery vehicle routing problem. International Journal of Production Economics, 105( 1): 228–242

[32] Jin, M Liu, K Eksioglu, B (2008). A column generation approach for the split delivery vehicle routing problem. Operations Research Letters, 36( 2): 265–270

[33] Lee, C G Epelman, M A White, III C C Bozer, Y A (2006). A shortest path approach to the multiple-vehicle routing problem with split pick-ups. Transportation Research Part B: Methodological, 40( 4): 265–284

[34] Li, J Qin, H Baldacci, R Zhu, W (2020). Branch-and-price-and-cut for the synchronized vehicle routing problem with split delivery, proportional service time and multiple time windows. Transportation Research Part E: Logistics and Transportation Review, 140: 101955

[35] Luo, Z Qin, H Zhu, W Lim, A (2017). Branch and price and cut for the split-delivery vehicle routing problem with time windows and linear weight-related cost. Transportation Science, 51( 2): 668–687

[36] MotaECamposVCorberánÁ (2007). A new metaheuristic for the vehicle routing problem with split demands. In: Proceedings of 7th European Conference on Evolutionary Computation in Combinatorial Optimization. Valencia: Springer, 121–129

[37] Munari, P Savelsbergh, M (2022). Compact formulations for split delivery routing problems. Transportation Science, 56( 4): 1022–1043

[38] Ozbaygin, G Karasan, O Yaman, H (2018). New exact solution approaches for the split delivery vehicle routing problem. EURO Journal on Computational Optimization, 6( 1): 85–115

[39] Penna, P H V Subramanian, A Ochi, L S (2013). An iterated local search heuristic for the heterogeneous fleet vehicle routing problem. Journal of Heuristics, 19( 2): 201–232

[40] Potvin, J Y Kervahut, T Garcia, B L Rousseau, J M (1996). The vehicle routing problem with time windows part I: Tabu search. INFORMS Journal on Computing, 8( 2): 158–164

[41] Qin, H Su, X Ren, T Luo, Z (2021). A review on the electric vehicle routing problems: Variants and algorithms. Frontiers of Engineering Management, 8( 3): 370–389

[42] Ray, S Soeanu, A Berger, J Debbabi, M (2014). The multi-depot split-delivery vehicle routing problem: Model and solution algorithm. Knowledge-Based Systems, 71: 238–265

[43] Salani, M Vacca, I (2011). Branch and price for the vehicle routing problem with discrete split deliveries and time windows. European Journal of Operational Research, 213( 3): 470–477

[44] Shi, J Zhang, J Wang, K Fang, X (2018). Particle swarm optimization for split delivery vehicle routing problem. Asia-Pacific Journal of Operational Research, 35( 2): 1840006

[45] Silva, M M Subramanian, A Ochi, L S (2015). An iterated local search heuristic for the split delivery vehicle routing problem. Computers & Operations Research, 53: 234–249

[46] Solomon, M M (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35( 2): 254–265

[47] TothPVigoD (2014). Vehicle Routing: Problems, Methods, and Applications. 2nd ed. Philadelphia, PA: Society for Industrial and Applied Mathematics, 241–271

[48] Wei, L Zhang, Z Lim, A (2014). An adaptive variable neighborhood search for a heterogeneous fleet vehicle routing problem with three-dimensional loading constraints. IEEE Computational Intelligence Magazine, 9( 4): 18–30

[49] Yamada, T Kataoka, S Watanabe, K (2002). Heuristic and exact algorithms for the disjunctively constrained knapsack problem. Information Processing Society of Japan Journal, 43( 9): 2864–2870

[50] ZhangZHeHLuoZQinHGuoS (2015). An efficient forest-based tabu search algorithm for the split-delivery vehicle routing problem. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence. Austin, TX: AAAI Press, 3432–3438

Competing Interests

The authors declare that they have no competing interests.

Electronic Supplementary Material

Supplementary material is available in the online version of this article at https://doi.org/10.1007/s42524-023-0259-z and is accessible for authorized users.

RIGHTS & PERMISSIONS

2023 Higher Education Press