Enhanced solution representations for vehicle routing problems with split deliveries

doi:10.1007/s42524-023-0259-z

Front. Eng

2023, Vol. 10

Issue (3) : 483-498 https://doi.org/10.1007/s42524-023-0259-z

RESEARCH ARTICLE

Enhanced solution representations for vehicle routing problems with split deliveries

Wenbin ZHU¹, Zhuoran AO², Roberto BALDACCI³, Hu QIN⁴(

), Zizhen ZHANG⁵

¹. School of Business Administration, South China University of Technology, Guangzhou 510640, China
². Thrust of Intelligent Transportation, The Hong Kong University of Science and Technology (Guangzhou), Guangzhou 511466, China
³. College of Science and Engineering (CSE), Hamad Bin Khalifa University (HBKU), Doha 5825, Qatar
⁴. School of Management, Huazhong University of Science and Technology, Wuhan 430074, China
⁵. School of Data and Computer Science, Sun Yat-sen University, Guangzhou 510275, China

Download: PDF(2058 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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.

Keywords vehicle routing multidepot time windows tabu search split delivery

Corresponding Author(s): Hu QIN

About author:

^* These authors contributed equally to this work.

Just Accepted Date: 27 June 2023 Online First Date: 03 August 2023 Issue Date: 29 August 2023

Cite this article:

Wenbin ZHU,Zhuoran AO,Roberto BALDACCI, et al. Enhanced solution representations for vehicle routing problems with split deliveries[J]. Front. Eng, 2023, 10(3): 483-498.

URL:

https://academic.hep.com.cn/fem/EN/10.1007/s42524-023-0259-z
https://academic.hep.com.cn/fem/EN/Y2023/V10/I3/483

Fig.1 An example SDVRP instance. Three customers are represented by circles with demands

d 1 = 5

d 2 = 8

and

d 3 = 5

. The traveling distance between two vertices is marked beside the corresponding edge. The number in parentheses is the quantity delivered by the corresponding vehicle.

Fig.2 An example MDSDVRP instance. Four customers are represented by circles with demands

d 1 = 5

d 2 = 8

and

d 3 = d 4 = 5

. The traveling distance between two vertices is marked beside the corresponding edge. The number in parentheses is the quantity delivered by the corresponding vehicle.

Fig.3 An example SDVRPTW instance. Three customers are represented by circles with demands

d 1 = 5

d 2 = 8

and

d 3 = 5

. The traveling distance and time (in square brackets) between two vertices are marked beside the corresponding edge. The number in parentheses is the quantity delivered by the corresponding vehicle. The numbers in square brackets

[e, l, s]

are the ready time, due time and service time of a customer, respectively.

Fig.4 An example to illustrate Properties 1 and 2.

Fig.5 An example of solution involving six delivery patterns.

Fig.6 Flow network for the solution of Fig. 5.

Fig.7 Graph

G (S)

corresponding to the solution S shown in Fig. 5.

Fig.8 Example of where a customer node is connected with a set of route nodes.

Fig.9 Computing the maximum residual capacity, the maximum supporting capacity and the maximum available capacity.

Fig.10 An example of external relocate operation.

Fig.11 Examples of internal relocate operation.

Fig.12 An example of external exchange operation.

Fig.13 Examples of internal exchange operation.

Fig.14 An example of the split operator.

Description	Parameter	Values
Range of the tabu tenure	$[ξ l, ξ u]$	$[0.05 n, 0.1 n]$
Range of k in multiple-k-split	$[k l, k u]$	$[3, 5]$
Number of nonimproved steps	$η$	20000
Number of perturbations	$ρ$	10
Time limit	$τ$	400 s

Tab.1 Parameter settings of algorithm FTS

Tab.2 Summary results on the SDVRP

Tab.3 Summary results on the impacts of 3 operators

Tab.4 Summary results on the MDSDVRP

Tab.5 Summary results on the SDVRPTW

1	R K AhujaT L MagnantiJ B (1993) Orlin. Network Flows: Theory, Algorithms, and Applications. Englewood Cliffs, NJ: Prentice Hall
2	R E Aleman, R R Hill, (2010). A tabu search with vocabulary building approach for the vehicle routing problem with split demands. International Journal of Metaheuristics, 1( 1): 55–80 https://doi.org/10.1504/IJMHEUR.2010.033123
3	R E Aleman, X Zhang, R R Hill, (2010). An adaptive memory algorithm for the split delivery vehicle routing problem. Journal of Heuristics, 16( 3): 441–473 https://doi.org/10.1007/s10732-008-9101-3
4	C Archetti, N Bianchessi, M G Speranza, (2011a). A column generation approach for the split delivery vehicle routing problem. Networks: An International Journal, 58( 4): 241–254 https://doi.org/10.1002/net.20467
5	C Archetti, N Bianchessi, M G Speranza, (2014). Branch-and-cut algorithms for the split delivery vehicle routing problem. European Journal of Operational Research, 238( 3): 685–698 https://doi.org/10.1016/j.ejor.2014.04.026
6	C Archetti, M Bouchard, G Desaulniers, (2011b). Enhanced branch and price and cut for vehicle routing with split deliveries and time windows. Transportation Science, 45( 3): 285–298 https://doi.org/10.1287/trsc.1100.0363
7	C ArchettiM G (2008) Speranza. 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	C Archetti, M G Speranza, A Hertz, (2006). A tabu search algorithm for the split delivery vehicle routing problem. Transportation Science, 40( 1): 64–73 https://doi.org/10.1287/trsc.1040.0103
9	C Archetti, M G Speranza, M W Savelsbergh, (2008). An optimization-based heuristic for the split delivery vehicle routing problem. Transportation Science, 42( 1): 22–31 https://doi.org/10.1287/trsc.1070.0204
10	A S Azad, M Islam, S Chakraborty, (2017). A heuristic initialized stochastic memetic algorithm for MDPVRP with interdependent depot operations. IEEE Transactions on Cybernetics, 47( 12): 4302–4315 https://doi.org/10.1109/TCYB.2016.2607220
11	R Baldacci, A Mingozzi, R Roberti, (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 https://doi.org/10.1016/j.ejor.2011.07.037
12	J M Belenguer, M C Martinez, E Mota, (2000). A lower bound for the split delivery vehicle routing problem. Operations Research, 48( 5): 801–810 https://doi.org/10.1287/opre.48.5.801.12407
13	L Berbotto, S García, F J Nogales, (2014). A randomized granular tabu search heuristic for the split delivery vehicle routing problem. Annals of Operations Research, 222( 1): 153–173 https://doi.org/10.1007/s10479-012-1282-3
14	N Bianchessi, S Irnich, (2019). Branch-and-cut for the split delivery vehicle routing problem with time windows. Transportation Science, 53( 2): 442–462 https://doi.org/10.1287/trsc.2018.0825
15	A Bortfeldt, J Yi, (2020). The split delivery vehicle routing problem with three-dimensional loading constraints. European Journal of Operational Research, 282( 2): 545–558 https://doi.org/10.1016/j.ejor.2019.09.024
16	P Chen, B Golden, X Wang, E Wasil, (2017). A novel approach to solve the split delivery vehicle routing problem. International Transactions in Operational Research, 24( 1–2): 27–41 https://doi.org/10.1111/itor.12250
17	S Chen, B Golden, E Wasil, (2007). The split delivery vehicle routing problem: Applications, algorithms, test problems, and computational results. Networks: An International Journal, 49( 4): 318–329 https://doi.org/10.1002/net.20181
18	N Christofides, S Eilon, (1969). An algorithm for the vehicle-dispatching problem. Journal of the Operational Research Society, 20( 3): 309–318 https://doi.org/10.1057/jors.1969.75
19	J F Cordeau, M Gendreau, G Laporte, (1997). A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks: An International Journal, 30( 2): 105–119 https://doi.org/10.1002/(SICI)1097-0037(199709)30:2<105::AID-NET5>3.0.CO;2-G
20	U Derigs, B Li, U Vogel, (2010). Local search-based metaheuristics for the split delivery vehicle routing problem. Journal of the Operational Research Society, 61( 9): 1356–1364 https://doi.org/10.1057/jors.2009.100
21	G Desaulniers, (2010). Branch-and-price-and-cut for the split-delivery vehicle routing problem with time windows. Operations Research, 58( 1): 179–192 https://doi.org/10.1287/opre.1090.0713
22	M Dror, P Trudeau, (1989). Savings by split delivery routing. Transportation Science, 23( 2): 141–145 https://doi.org/10.1287/trsc.23.2.141
23	M Gendreau, A Hertz, G Laporte, (1994). A tabu search heuristic for the vehicle routing problem. Management Science, 40( 10): 1276–1290 https://doi.org/10.1287/mnsc.40.10.1276
24	B E Gillett, J G Johnson, (1976). Multi-terminal vehicle-dispatch algorithm. Omega, 4( 6): 711–718 https://doi.org/10.1016/0305-0483(76)90097-9
25	F Glover, (1989). Tabu search—Part I. ORSA Journal on Computing, 1( 3): 190–206 https://doi.org/10.1287/ijoc.1.3.190
26	F Glover, (1990). Tabu search—Part II. ORSA Journal on Computing, 2( 1): 4–32 https://doi.org/10.1287/ijoc.2.1.4
27	D Gulczynski, B Golden, E Wasil, (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 https://doi.org/10.1016/j.cie.2011.05.012
28	D J (2010) Gulczynski. Integer Programming-based Heuristics for Vehicle Routing Problems. Dissertation for the Doctoral Degree. College Park, MD: University of Maryland
29	A F W Han, Y C Chu, (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 https://doi.org/10.1016/j.tre.2016.01.014
30	S C Ho, D Haugland, (2004). A tabu search heuristic for the vehicle routing problem with time windows and split deliveries. Computers & Operations Research, 31( 12): 1947–1964 https://doi.org/10.1016/S0305-0548(03)00155-2
31	M Jin, K Liu, R O Bowden, (2007). A two-stage algorithm with valid inequalities for the split delivery vehicle routing problem. International Journal of Production Economics, 105( 1): 228–242 https://doi.org/10.1016/j.ijpe.2006.04.014
32	M Jin, K Liu, B Eksioglu, (2008). A column generation approach for the split delivery vehicle routing problem. Operations Research Letters, 36( 2): 265–270 https://doi.org/10.1016/j.orl.2007.05.012
33	C G Lee, M A Epelman, III C C White, Y A Bozer, (2006). A shortest path approach to the multiple-vehicle routing problem with split pick-ups. Transportation Research Part B: Methodological, 40( 4): 265–284 https://doi.org/10.1016/j.trb.2004.11.004
34	J Li, H Qin, R Baldacci, W Zhu, (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 https://doi.org/10.1016/j.tre.2020.101955
35	Z Luo, H Qin, W Zhu, A Lim, (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 https://doi.org/10.1287/trsc.2015.0666
36	E MotaV CamposÁ (2007) Corberán. 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	P Munari, M Savelsbergh, (2022). Compact formulations for split delivery routing problems. Transportation Science, 56( 4): 1022–1043 https://doi.org/10.1287/trsc.2021.1106
38	G Ozbaygin, O Karasan, H Yaman, (2018). New exact solution approaches for the split delivery vehicle routing problem. EURO Journal on Computational Optimization, 6( 1): 85–115 https://doi.org/10.1007/s13675-017-0089-z
39	P H V Penna, A Subramanian, L S Ochi, (2013). An iterated local search heuristic for the heterogeneous fleet vehicle routing problem. Journal of Heuristics, 19( 2): 201–232 https://doi.org/10.1007/s10732-011-9186-y
40	J Y Potvin, T Kervahut, B L Garcia, J M Rousseau, (1996). The vehicle routing problem with time windows part I: Tabu search. INFORMS Journal on Computing, 8( 2): 158–164 https://doi.org/10.1287/ijoc.8.2.158
41	H Qin, X Su, T Ren, Z Luo, (2021). A review on the electric vehicle routing problems: Variants and algorithms. Frontiers of Engineering Management, 8( 3): 370–389 https://doi.org/10.1007/s42524-021-0157-1
42	S Ray, A Soeanu, J Berger, M Debbabi, (2014). The multi-depot split-delivery vehicle routing problem: Model and solution algorithm. Knowledge-Based Systems, 71: 238–265 https://doi.org/10.1016/j.knosys.2014.08.006
43	M Salani, I Vacca, (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 https://doi.org/10.1016/j.ejor.2011.03.023
44	J Shi, J Zhang, K Wang, X Fang, (2018). Particle swarm optimization for split delivery vehicle routing problem. Asia-Pacific Journal of Operational Research, 35( 2): 1840006 https://doi.org/10.1142/S0217595918400067
45	M M Silva, A Subramanian, L S Ochi, (2015). An iterated local search heuristic for the split delivery vehicle routing problem. Computers & Operations Research, 53: 234–249 https://doi.org/10.1016/j.cor.2014.08.005
46	M M Solomon, (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35( 2): 254–265 https://doi.org/10.1287/opre.35.2.254
47	P TothD (2014) Vigo. Vehicle Routing: Problems, Methods, and Applications. 2nd ed. Philadelphia, PA: Society for Industrial and Applied Mathematics, 241–271
48	L Wei, Z Zhang, A Lim, (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 https://doi.org/10.1109/MCI.2014.2350933
49	T Yamada, S Kataoka, K Watanabe, (2002). Heuristic and exact algorithms for the disjunctively constrained knapsack problem. Information Processing Society of Japan Journal, 43( 9): 2864–2870
50	Z ZhangH HeZ LuoH QinS (2015) Guo. 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

[1]

FEM-22043-OF-HQ_suppl_1

Download

[1]	Fred GLOVER, Saïd HANAFI, Oualid GUEMRI, Igor CREVITS. A simple multi-wave algorithm for the uncapacitated facility location problem[J]. Front. Eng, 2018, 5(4): 451-465.
[2]	Han-peng Zhang, Yi Liao, Hui-xia Luo. Two-echelon Emergency Response Problem and Simulation Considering Secondary Disasters[J]. Front. Eng, 2014, 1(3): 318-321.

Viewed

Full text

Abstract

Cited

Shared

Discussed