Two-phase heuristic for vehicle routing problem with drones in multi-trip and multi-drop mode

doi:10.23919/JSEE.2025.000091

Abstract

Abstract:

As commercial drone delivery becomes increasingly popular, the extension of the vehicle routing problem with drones (VRPD) is emerging as an optimization problem of interests. This paper studies a variant of VRPD in multi-trip and multi-drop (VRP-mmD). The problem aims at making schedules for the trucks and drones such that the total travel time is minimized. This paper formulate the problem with a mixed integer programming model and propose a two-phase algorithm, i.e., a parallel route construction heuristic (PRCH) for the first phase and an adaptive neighbor searching heuristic (ANSH) for the second phase. The PRCH generates an initial solution by concurrently assigning as many nodes as possible to the truck–drone pair to progressively reduce the waiting time at the rendezvous node in the first phase. Then the ANSH improves the initial solution by adaptively exploring the neighborhoods in the second phase. Numerical tests on some benchmark data are conducted to verify the performance of the algorithm. The results show that the proposed algorithm can found better solutions than some state-of-the-art methods for all instances. Moreover, an extensive analysis highlights the stability of the proposed algorithm.

Key words: vehicle routing problem with drones (VRPD), mixed integer program, parallel route construction heuristic (PRCH), adaptive neighbor searching heuristic (ANSH)

Huawei MA, Xiaoxuan HU, Waiming ZHU. Two-phase heuristic for vehicle routing problem with drones in multi-trip and multi-drop mode[J]. Journal of Systems Engineering and Electronics, 2025, 36(4): 1024-1036.

Figures/Tables 11

Fig 1

Table 1

Table 2

Table 3

Fig 2

Fig 3

Table 4

Table 5

Table 6

Comparison of the results between PRCH and DTRC in VRP-smD mode"

Instance	Q	q	DTRC		PRCH
Instance	Q	q	Best	Average time/s	Best	Average objective	Average time/s	Best gap/%	Average gap/%
A-n32-k5	100	35	783	0.68	746	752	0.15	−4.73	−4.02
A-n33-k5	100	35	646	0.79	606	621	0.13	−6.20	−3.88
A-n33-k6	100	35	701	0.69	661	676	0.13	−5.69	−3.61
A-n34-k5	100	35	752	0.86	737	755	0.15	−2.06	0.34
A-n36-k5	100	35	759	1.11	784	794	0.15	3.30	4.62
A-n37-k5	100	35	661	1.25	619	635	0.14	−6.33	−3.86
A-n37-k6	100	35	914	1.01	895	903	0.14	−2.03	−1.22
A-n38-k5	100	35	721	1.03	696	714	0.14	−3.45	−0.97
A-n39-k5	100	35	833	2.35	788	808	0.15	−5.41	−2.98
A-n39-k6	100	35	849	1.12	763	783	0.15	−10.12	−7.76
A-n44-k6	100	35	914	1.78	896	909	0.16	−1.96	−0.54
A-n45-k6	100	35	943	0.92	926	936	0.16	−1.82	−0.69
A-n46-k7	100	35	905	1.27	913	920	0.16	0.93	1.71
A-n48-k7	100	35	1075	1.34	1065	1090	0.17	−0.97	1.36
A-n53-k7	100	35	1000	1.02	994	1030	0.18	−0.56	3.01
A-n54-k7	100	35	1143	1.58	1160	1188	0.19	1.50	3.96
A-n55-k9	100	35	1057	1.53	1021	1055	0.19	−3.39	−0.15
A-n62-k8	100	35	1287	3.32	1329	1350	0.21	3.26	4.89
A-n63-k10	100	35	1305	2.26	1242	1314	0.22	−4.82	0.70
A-n65-k9	100	35	1180	2.96	1165	1199	0.22	−1.25	1.61
A-n69-k9	100	35	1078	2.40	1197	1219	0.24	11.01	13.04
B-n31-k5	100	35	672	0.72	582	585	0.13	−13.32	−13.00
B-n34-k5	100	35	769	0.87	664	694	0.13	−13.65	−9.77
B-n35-k5	100	35	954	0.71	767	774	0.13	−19.60	−18.88
B-n38-k6	100	35	803	1.11	644	655	0.14	−19.75	−18.46
B-n39-k5	100	35	548	0.97	534	538	0.14	−2.54	−1.76
B-n41-k6	100	35	875	0.82	778	785	0.15	−11.07	−10.33
E-n51-k5	160	50	502	2.86	522	538	0.17	3.95	7.21
E-n76-k7	220	55	650	3.87	727	745	0.27	11.86	14.63
E-n76-k8	180	45	684	3.65	796	812	0.27	16.41	18.71
E-n76-k10	140	40	827	3.06	886	897	0.27	7.18	8.42
E-n76-k14	100	35	1019	1.94	1010	1027	0.28	−0.90	0.83
P-n16-k8	35	20	469	0.37	430	447	0.11	−8.32	−4.69
P-n19-k2	160	40	221	0.65	205	205	0.11	−7.16	−7.16
P-n20-k2	160	40	216	0.54	216	216	0.11	−0.21	−0.21
P-n21-k2	160	40	203	0.77	223	223	0.11	9.68	9.68
P-n22-k2	160	40	208	0.76	218	218	0.11	4.97	4.97
P-n23-k8	40	20	527	0.48	496	503	0.12	−5.88	−4.55
P-n40-k5	140	40	456	1.56	446	458	0.15	−2.13	0.48
P-n45-k5	150	40	495	1.06	525	531	0.16	6.15	7.18
P-n50-k7	150	40	555	0.98	588	597	0.17	5.97	7.48
P-n50-k8	120	40	604	1.08	593	621	0.17	−1.77	2.80
P-n50-k10	100	35	705	1.45	671	685	0.18	−4.79	−2.79
P-n55-k7	170	45	579	1.68	576	601	0.19	−0.43	3.72
P-n55-k10	115	40	695	1.71	661	682	0.19	−4.83	−1.88
P-n55-k15	70	38	937	1.33	847	869	0.19	−9.65	−7.24
P-n60-k10	120	40	735	1.89	745	762	0.21	1.30	3.71
P-n60-k15	80	30	968	1.62	886	908	0.22	−8.45	−6.22
P-n65-k10	130	40	803	2.07	812	837	0.23	1.07	4.19
P-n70-k10	135	40	832	2.36	877	893	0.25	5.41	7.30
Average			−	1.48	−	−	0.17	−2.03	0.00

Table 6

Table 7

Comparison of the results between ANSH and LNS in VRP-smD mode"

Instance	Q	q	LNS		ANSH
Instance	Q	q	Best	Average time/s	Best	Average objective	Average time/s	Best gap/%	Average gap/%
A-n32-k5	100	35	699	68.36	689	706	6.12	−1.49	1.00
A-n33-k5	100	35	561	68.36	546	595	6.39	−2.65	6.10
A-n33-k6	100	35	634	63.53	632	662	4.97	−0.34	4.35
A-n34-k5	100	35	648	66.14	653	681	7.48	0.75	5.04
A-n36-k5	100	35	669	68.63	758	763	8.36	13.28	14.06
A-n37-k5	100	35	516	68.40	552	584	9.29	6.88	13.23
A-n37-k6	100	35	837	66.45	792	820	6.25	−5.39	−2.07
A-n38-k5	100	35	636	70.57	632	657	7.61	−0.56	3.31
A-n39-k5	100	35	698	66.38	681	693	7.29	−2.50	−0.65
A-n39-k6	100	35	692	76.10	686	733	6.92	−0.88	5.92
A-n44-k6	100	35	825	72.64	804	826	7.26	−2.58	0.11
A-n45-k6	100	35	846	85.52	855	892	7.14	1.04	5.46
A-n46-k7	100	35	810	90.40	780	832	6.17	−3.71	2.71
A-n48-k7	100	35	973	73.54	909	969	7.48	−6.61	−0.41
A-n53-k7	100	35	952	95.63	915	942	9.33	−3.89	−1.00
A-n54-k7	100	35	1057	93.10	1021	1057	8.12	−3.37	0.05
A-n55-k9	100	35	981	94.46	895	949	6.48	−8.81	−3.22
A-n62-k8	100	35	1241	118.51	1100	1155	7.55	−11.36	−6.91
A-n63-k10	100	35	1267	93.83	1143	1171	6.74	−9.77	−7.60
A-n65-k9	100	35	1080	145.90	1098	1132	6.71	1.63	4.83
A-n69-k9	100	35	1079	152.80	1039	1080	8.92	−3.70	0.13
B-n31-k5	100	35	653	66.35	556	572	7.84	−14.85	−12.38
B-n34-k5	100	35	748	69.87	678	698	7.13	−9.32	−6.74
B-n35-k5	100	35	896	67.05	747	750	8.84	−16.60	−16.24
B-n38-k6	100	35	723	69.44	634	665	6.72	−12.32	−8.08
B-n39-k5	100	35	497	75.09	530	534	6.70	6.55	7.42
B-n41-k6	100	35	813	82.07	762	770	6.89	−6.21	−5.30
E-n51-k5	160	50	452	94.20	451	467	9.00	−0.29	3.28
E-n76-k7	220	55	622	150.79	525	573	1.06	−15.53	−7.90
E-n76-k8	180	45	664	233.76	532	583	8.80	−19.91	−12.23
E-n76-k10	140	40	795	289.56	756	808	7.04	−4.94	1.62
E-n76-k14	100	35	1008	160.27	890	922	5.26	−11.73	−8.48
P-n16-k8	35	20	444	60.24	403	410	2.55	−9.23	−7.66
P-n19-k2	160	40	165	60.67	146	180	4.78	−11.33	8.93
P-n20-k2	160	40	166	60.88	139	158	3.48	−16.03	−5.05
P-n21-k2	160	40	161	61.77	150	165	2.22	−6.83	2.48
P-n22-k2	160	40	163	61.84	186	195	1.67	14.11	19.63
P-n23-k8	40	20	512	61.24	488	497	2.72	−4.69	−2.93
P-n40-k5	140	40	379	81.46	397	413	7.16	4.65	8.92
P-n45-k5	150	40	426	80.29	400	418	7.44	−6.02	−1.86
P-n50-k7	150	40	502	91.90	477	495	5.66	−4.94	−1.38
P-n50-k8	120	40	578	73.33	520	566	5.37	−9.99	−2.00
P-n50-k10	100	35	665	81.98	606	618	4.83	−8.90	−7.04
P-n55-k7	170	45	512	96.21	445	479	7.41	−13.00	−6.54
P-n55-k10	115	40	654	92.65	579	611	5.65	−11.41	−6.54
P-n55-k15	70	38	919	77.16	786	798	4.25	−14.52	−13.19
P-n60-k10	120	40	714	99.47	669	692	5.45	−6.37	−3.15
P-n60-k15	80	30	946	83.28	831	850	4.70	−12.20	−10.10
P-n65-k10	130	40	730	128.82	729	749	5.76	−0.18	2.58
P-n70-k10	135	40	783	138.90	765	783	6.48	−2.24	−0.05
Average			−	93.00	−	−	6.31	−5.37	−0.91

Table 7

Table 8

References 31

1	YAMAN H, KARASAN O E, KARA B Y Release time scheduling and hub location for next-day delivery. Operations Research, 2012, 60 (4): 906- 917. doi: 10.1287/opre.1120.1065
2	RAMOS T R P, VIGO D A new hybrid distribution paradigm: integrating drones in medicines delivery. Expert Systems with Applications, 2023, 234, 120992. doi: 10.1016/j.eswa.2023.120992
3	CHEN X, ULMER M W, THOMAS B W Deep Q-learning for same-day delivery with vehicles and drones. European Journal of Operational Research, 2022, 298 (3): 939- 952. doi: 10.1016/j.ejor.2021.06.021
4	MBIADOU SALEU R G, DEROUSSI L, FEILLET D, et al An iterative two-step heuristic for the parallel drone scheduling traveling salesman problem. Networks, 2018, 72 (4): 459- 474. doi: 10.1002/net.21846
5	NGUYEN M A, DANG G T H, HA M H, et al The min-cost parallel drone scheduling vehicle routing problem. European Journal of Operational Research, 2022, 299 (3): 910- 930. doi: 10.1016/j.ejor.2021.07.008
6	MBIADOU SALEU R G, DEROUSSI L, FEILLET D, et al The parallel drone scheduling problem with multiple drones and vehicles. European Journal of Operational Research, 2022, 300 (2): 571- 589. doi: 10.1016/j.ejor.2021.08.014
7	BOGYRBAYEVA A, YOON T, KO H, et al A deep reinforcement learning approach for solving the traveling salesman problem with drone. Transportation Research Part C: Emerging Technologies, 2023, 148, 103981. doi: 10.1016/j.trc.2022.103981
8	TINIC G O, KARASAN O E, KARA B Y, et al Exact solution approaches for the minimum total cost traveling salesman problem with multiple drones. Transportation Research Part B: Methodological, 2023, 168, 81- 123. doi: 10.1016/j.trb.2022.12.007
9	YIN Y Q, LI D W, WANG D J, et al A branch-and-price-and-cut algorithm for the truck-based drone delivery routing problem with time windows. European Journal of Operational Research, 2023, 309 (3): 1125- 1144. doi: 10.1016/j.ejor.2023.02.030
10	XIA Y, ZENG W J, ZHANG C R, et al A branch-and-price-and-cut algorithm for the vehicle routing problem with load-dependent drones. Transportation Research Part B: Methodological, 2023, 171, 80- 110. doi: 10.1016/j.trb.2023.03.003
11	MURRAY C C, CHU A G The flying sidekick traveling salesman problem: optimization of drone-assisted parcel delivery. Transportation Research Part C: Emerging Technologies, 2015, 54, 86- 109. doi: 10.1016/j.trc.2015.03.005
12	MARINELLI M, CAGGIANI L, OTTOMANELLI M, et al En route truck–drone parcel delivery for optimal vehicle routing strategies. IET Intelligent Transport Systems, 2018, 12 (4): 253- 261. doi: 10.1049/iet-its.2017.0227
13	KITJACHAROENCHAI P, VENTRESCA M, MOSHREF-JAVADI M, et al Multiple traveling salesman problem with drones: mathematical model and heuristic approach. Computers & Industrial Engineering, 2019, 129, 14- 30.
14	VÁSQUEZ S A, ANGULO G, KLAPP M A An exact solution method for the TSP with drone based on decomposition. Computers & Operations Research, 2021, 127, 105127.
15	IBROŞKA B, OZPEYNIRCI S, OZPEYNIRCI O Multiple traveling salesperson problem with drones: general variable neighborhood search approach. Computers & Operations Research, 2023, 160, 106390.
16	HA Q M, DEVILLE Y, PHAM Q D, et al On the min-cost traveling salesman problem with drone. Transportation Research Part C: Emerging Technologies, 2018, 86, 597- 621. doi: 10.1016/j.trc.2017.11.015
17	DE FREITAS J C, PENNA P H V A variable neighborhood search for flying sidekick traveling salesman problem. International Transactions in Operational Research, 2020, 27 (1): 267- 290. doi: 10.1111/itor.12671
18	HA Q M, DEVILLE Y, PHAM Q D, et al A hybrid genetic algorithm for the traveling salesman problem with drone. Journal of Heuristics, 2020, 26 (2): 219- 247. doi: 10.1007/s10732-019-09431-y
19	GUNAY-SEZER N S, CAKMAK E, BULKAN S A hybrid metaheuristic solution method to traveling salesman problem with drone. Systems, 2023, 11 (5): 259. doi: 10.3390/systems11050259
20	EL-ADLE A M, GHONIEM A, HAOUARI M A variable neighborhood search for parcel delivery by vehicle with drone cycles. Computers & Operations Research, 2023, 159, 106319.
21	ZHOU H, QIN H, CHENG C, et al An exact algorithm for the two-echelon vehicle routing problem with drones. Transportation Research Part B: Methodological, 2023, 168, 124- 150. doi: 10.1016/j.trb.2023.01.002
22	KUO R J, EDBERT E, ZULVIA F E, et al Applying NSGA-II to vehicle routing problem with drones considering makespan and carbon emission. Expert Systems with Applications, 2023, 221, 119777. doi: 10.1016/j.eswa.2023.119777
23	KITJACHAROENCHAI P, MIN B C, LEE S Two echelon vehicle routing problem with drones in last mile delivery. International Journal of Production Economics, 2020, 225, 107598. doi: 10.1016/j.ijpe.2019.107598
24	GU R X, POON M, LUO Z H, et al A hierarchical solution evaluation method and a hybrid algorithm for the vehicle routing problem with drones and multiple visits. Transportation Research Part C: Emerging Technologies, 2022, 141, 103733. doi: 10.1016/j.trc.2022.103733
25	LU Y C, YANG J, YANG C A humanitarian vehicle routing problem synchronized with drones in time-varying weather conditions. Computers & Industrial Engineering, 2023, 184, 109563.
26	YIN Y Q, YANG Y J, YU Y, et al Robust vehicle routing with drones under uncertain demands and truck travel times in humanitarian logistics. Transportation Research Part B: Methodological, 2023, 174, 102781. doi: 10.1016/j.trb.2023.102781
27	ZENG F, CHEN Z, CLARKE J P, et al Nested vehicle routing problem: optimizing drone-truck surveillance operations. Transportation Research Part C: Emerging Technologies, 2022, 139, 103645. doi: 10.1016/j.trc.2022.103645
28	JIANG J, DAI Y, YANG F, et al A multi-visit flexible-docking vehicle routing problem with drones for simultaneous pickup and delivery services. European Journal of Operational Research, 2024, 312 (1): 125- 137. doi: 10.1016/j.ejor.2023.06.021
29	REN X, FROGER A, JABALI O, et al A competitive heuristic algorithm for vehicle routing problems with drones. European Journal of Operational Research, 2024, 318 (2): 469- 485. doi: 10.1016/j.ejor.2024.05.031
30	AMINE MASMOUDI M, MANCINI S, BALDACCI R, et al Vehicle routing problems with drones equipped with multi-package payload compartments. Transportation Research Part E: Logistics and Transportation Review, 2022, 164, 102757. doi: 10.1016/j.tre.2022.102757
31	EUCHI J, SADOK A Hybrid genetic-sweep algorithm to solve the vehicle routing problem with drones. Physical Communication, 2021, 44, 101236. doi: 10.1016/j.phycom.2020.101236

Parameter	Definition
$V$	Set of the nodes, $N = \{ 0,1,\cdots ,n\} $, $0$ represent the depot
${V_L}$	Set of the nodes from which a drone may depart
${V_R}$	Set of the nodes at which a drone may be retrieved
${V_C}$	Set of the customers, ${V_C} = V\backslash \{ 0\} $
$V'$	Set of the customers excludes the departing and retrieving nodes of drones, $V' = {V_C}\backslash ({V_L} \cup {V_R})$
$S$	Subset of $V$
$K$	Set of trucks and drones, indexed by $k$
${P_k}$	Set of the drone’s trips on the truck $k$, indexed by $p$
${d_i}$	Weight of the package delivered to customer $i$
$Q$	Maximum load capacity of each truck
$q$	Maximum load capacity of each drone
$\bar D $	Maximum flying duration of each drone in one trip
${\eta _{ik}}$	Time for the drone on truck $k$ arriving at node $i$
${t_{ik}}$	Time for truck $k$ arriving at node $i$
${\lambda _{ik}}$	Waiting time for truck $k$ at node $i$, equals $\max \{ {\eta _{ik}} - {t_{ik}},0\} $ if node $i$ is a retrieving node, and zero otherwise
$ \tau _{ij}^k $	Time for truck $k$ to travel from node $i$ to node $j$
$ \text{π} _{ij}^k $	Time for the drone on truck $k$ to travel from node $i$ to node $j$
${\text{M}}$	A sufficiently large positive constant
$ x_{ij}^k $	Binary, equals one if truck $k$ travels from node $i$ to node $j$, and zero otherwise
$ y_{ij}^{kp} $	Binary, equals one if the drone on truck $k$ travels from node $i$ to node $j$ in trip, and zero otherwise

Parameter	Definition
$ {R_T} $	The truck route set
${R_D}$	The drone trip set
${R_k}$	The node set of truck route $k$
${R_{k'}}$	The node set of drone trip $k'$
$\tilde V$	The set of unvisited customers
$j/\mu $	The current node in ${R_k}$/${R_{k'}}$
${L_{jh}}$	The distance between node $j$ and node $h$

Parameter	Definition
$\varepsilon $	The current solution
$ \varepsilon' $	The neighborhood solution
$\varepsilon^* $	The best solution
$\gamma $	The selected neighborhood structure
${w_\gamma }$	The index of neighborhood $ \gamma $
$t$	The current temperature
${T_s}$	The initial temperature
$\varphi $	A number between 0 and 1
$\rho $	Increment number in $[{\rho _1},{\rho _2},0]$
$r$	The random number between 0 and 1
${{\varTheta }}$	The solutions set
$ {{\varOmega }} $	The neighborhood structure set
$ f(\cdot) $	The objective function value

Instance	n	ANSH		PRCH
Instance	n	Average time/s	Average RV	Average time/s	Average RV
M-n101-K10	100	13.28	0.0216	2.43	0.0076
M-n151-k12	150	19.27	0.0173	2.88	0.0063
M-n200-k16	240	16.37	0.0441	3.13	0.0098
Golden_17	300	18.36	0.0280	3.39	0.0117
Golden_18	360	17.21	0.0263	4.94	0.0067
Golden_19	385	20.59	0.0215	5.47	0.0094
Tai385	420	19.37	0.0348	6.92	0.0089
Golden_20	468	24.63	0.0143	10.06	0.0048
Li_21	560	32.14	0.0275	15.18	0.0116
Li_25	626	35.92	0.0228	17.64	0.0138
Li_28	700	40.74	0.0349	23.16	0.0113
Li_29	836	40.24	0.0463	37.68	0.0122
Li_30	935	45.38	0.0380	44.95	0.0138
Li_31	978	60.51	0.0284	46.44	0.0177
Li_32	1000	65.71	0.0282	47.95	0.0216
Average		18.15	0.0289	31.31	0.0112

[1]	Zhishuo LIU, Yi’nan CHENG, Yanhua LI, Danyang SHEN. Modeling optimal air traffic rights resource allocation [J]. Journal of Systems Engineering and Electronics, 2025, 36(3): 778-790.
[2]	Naikang YU, Bin QIAN, Rong HU, Yuwang CHEN, Ling WANG. Solving open vehicle problem with time window by hybrid column generation algorithm [J]. Journal of Systems Engineering and Electronics, 2022, 33(4): 997-1009.