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.

Key words： vehicle routing; multidepot; time windows; tabu search; split delivery

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.

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