电动车-无人机协同配送模式下带时间窗的车辆路径优化问题

doi:10.16381/j.cnki.issn1003-207x.2023.0447

Abstract

Abstract:

With national efforts to achieve carbon neutrality goals， electric vehicles have gradually become the preferred choice for logistics enterprises. However， electric vehicles require planning additional charging routes during delivery， which results in high logistics costs. To reduce the logistics cost of the electric vehicle delivery system， integration of drones is considered into the existing delivery system， and the vehicle routing problem with time windows is investigated under the collaborative delivery mode of electric vehicle-drone. The primary goal is to determine the optimal routes for both electric vehicles and drones to minimize total costs while satisfying the customer's time window requirements. During the delivery process in this mode， electric vehicles may require recharging at charging stations due to their limited battery capacity， when drones are loaded with batteries and goods， launched from， and recovered to the depot. To solve this problem， a mixed-integer programming-based mathematical optimization model is constructed. Then， an extended adaptive large neighborhood search algorithm （EALNS） is proposed， which integrates a construction heuristic algorithm to quickly obtain the initial feasible solution. In the algorithm， new insertion criterion and removal criterion of charging station are incorporated to satisfy the battery capacity constraint， and a shortest path removal operator is designed to accelerate the algorithmic convergence. Finally， simulation experiments are conducted to demonstrate the effectiveness of the proposed model and algorithm. The experimental results show that：（1） Compared with the Gurobi solver and ALNS algorithm， the EALNS algorithm obtains a better solution with a shorter running time in solving the proposed model；（2） Compared to existing delivery systems， integrating drones into the delivery systems can yield cost savings ranging from 1.07% to 19.50%， with an average saving of 5.97%； and （3） The changes in model parameters affect the cost of the solution. Specifically， the costs of the solution decrease as the load capacity and flight duration of drones increase， or as the load capacity and battery capacity of electric vehicles increase. Furthermore， as the customer's time window constraints are tightened， the cost of the solution increases. In conclusion， a new variant of the electric vehicle routing problem with time windows is presented， verifying that integrating drones into electric vehicle delivery systems can significantly reduce logistics costs， and the proposed EALNS algorithm is effective in solving this problem.

Key words: time windows, electric vehicle-drone, collaborative delivery, routing problem, adaptive large neighborhood search algorithm

CLC Number:

U492.2

Shuai Zhang, Siliang Liu, Wenyu Zhang. Vehicle Routing Problems with Time Windows under the Collaborative Delivery Mode of Electric Vehicle-drone[J]. Chinese Journal of Management Science, 2025, 33(4): 131-141.

Figures/Tables 12

符号	定义
节点、集合
$V$	顾客节点集合
$0$	作为出发地的仓库节点
$N + 1$	作为返回地的仓库节点
$S$	充电站节点集合
$S'$	虚拟充电站节点集合
$S 0'$	虚拟充电站、出发地仓库节点集合， $S 0' = S' ⋃ {0}$
$V 0$	顾客、出发地仓库节点集合， $V 0 = V ⋃ {0}$
$V'$	顾客、虚拟充电站节点集合， $V' = V ⋃ S'$
$V 0'$	顾客、虚拟充电站、出发地仓库节点集合， $V 0' = V ⋃ S' ⋃ {0}$
$V N + 1'$	顾客、虚拟充电站、返回地仓库节点集合， $V N + 1' = V ⋃ S' ∪ {N + 1}$
$V 0, N + 1'$	顾客、虚拟充电站、出发地和返回地仓库节点集合， $V 0, N + 1' = V ⋃ S' ⋃ {0} ⋃ {N + 1}$
参数
$C 0$	每辆电动车的派遣成本
$C 1$	电动车每单位距离的行驶成本
$C 2$	无人机每单位距离的行驶成本
$Q 1$	电动车的载货容量
$Q 2$	无人机的载货容量
$B$	电动车的电池容量
$F$	无人机飞行续航时间
$q i$	节点i的商品需求量
$t u i$	电动车/无人机在节点i卸下商品的所需时间
$[s i, e i]$	节点i的时间窗，其中 $s i$ 为时间窗的开始时间， $e i$ 为时间窗的结束时间
$h g +$	电动车的电池充电系数
$h g -$	电动车的电池耗电系数
$t i j 1$	电动车从节点i到节点j的行驶时间
$t i j 2$	无人机从节点i到节点j的行驶时间
$d i j$	节点i到节点j的距离
$l i$	节点i的配送标记， $l i = 1$ 表示节点i可由电动车或无人机配送， $l i = 0$ 表示为节点i只能由电动车配送
决策变量
$x i j$	0-1变量，若电动车从节点i到节点j，则 $x i j = 1$
$y i$	0-1变量，若无人机从仓库到节点i后返回仓库，则 $y i = 1$
$r b i$	连续变量，电动车到达节点i时剩余电池容量
$r q i$	连续变量，电动车到达节点i时剩余载货容量
$t a i$	连续变量，电动车到达节点i的时间

References 21

1	任璇，黄辉，于少伟，等. 车辆与无人机组合配送研究综述［J］. 控制与决策， 2021， 36（10）： 2313-2327.
	Ren X， Huang H， Yu S W， et al. Review on vehicle-UAV combined delivery problem［J］. Control and Decision， 2021， 36（10）： 2313-2327.
2	郭戈，张振琳. 电动车辆路径优化研究与进展［J］. 控制与决策， 2018， 33（10）： 1729-1739.
	Guo G， Zhang Z L. Status and development of electric vehicle routing optimization ［J］. Control and Decision， 2018， 33（10）： 1729-1739.
3	张歆悦，靳鹏，胡笑旋，等. 时间依赖型多配送中心带时间窗的开放式车辆路径问题研究［J］. 中国管理科学， 2024， 32（1）： 146-157.
	Zhang X Y， Jin P， Hu X X， et al. Research on the time-dependent multi-depot open vehicle routing problem with time windows［J］. Chinese Journal of Managent Science， 2024， 32（1）： 146-157.
4	Schneider M， Stenger A， Goeke D. The electric vehicle-routing problem with time windows and recharging stations［J］. Transportation Science， 2014， 48（4）： 500-520.
5	Keskin M， Laporte G， Çatay B. Electric vehicle routing problem with time-dependent waiting times at recharging stations［J］. Computers & Operations Research， 2019， 107： 77-94.
6	黄建华，刘方翔. 动态负载下电动汽车充电策略及路径优化问题［J］. 计算机集成制造系统， 2023， 29（11）：3909-3921.
	Huang J H， Liu F X. Charging strategy and routing optimization of electric vehicles under dynamic load［J］. Computer Integrated Manufacturing Systems， 2023， 29（11）：3909-3921.
7	Taş D. Electric vehicle routing with flexible time windows： A column generation solution approach［J］. Transportation Letters， 2021， 13（2）： 97-103.
8	Sadati M E H， Akbari V， Çatay B. Electric vehicle routing problem with flexible deliveries［J］. International Journal of Production Research， 2022， 60（13）： 4268-4294.
9	Murray C C， Chu A G. The flying sidekick traveling salesman problem： Optimization of drone-assisted parcel delivery［J］. Transportation Research Part C： Emerging Technologies， 2015， 54： 86-109.
10	Agatz N， Bouman P， Schmidt M. Optimization approaches for the traveling salesman problem with drone［J］. Transportation Science， 2018， 52（4）： 965-981.
11	吴廷映，陶新月，孟婷. “卡车+无人机”模式下带时间窗的取送货车辆路径问题［J］. 计算机集成制造系统， 2023， 29（7）： 2440-2448.
	Wu T Y， Tao X Y， Meng T. Pickup and delivery problem with time windows in the mode of “Truck+Drone”［J］. Computer Integrated Manufacturing Systems， 2023， 29（7）： 2440-2448.
12	Zhang S， Liu S L， Xu W B， et al. A novel multi-objective optimization model for the vehicle routing problem with drone delivery and dynamic flight endurance［J］. Computers & Industrial Engineering， 2022， 173： 108679.
13	颜瑞，陈立双，朱晓宁，等. 考虑区域限制的卡车搭载无人机车辆路径问题研究［J］. 中国管理科学， 2022， 30（5）： 144-155.
	Yan R， Chen L S， Zhu X N， et al. Research on vehicle routing problem with truck and drone considering regiona restriction［J］. Chinese Journal of Managent Science， 2022， 30（5）： 144-155.
14	高佳静，镇璐. 多卡车多机器人联合配送系统路径问题研究［J］. 中国管理科学， 2023， 31（3）： 48-57.
	Gao J J， Zhen L. Research on routing problem for joint delivery system based on multiple trucks and robots［J］. Chinese Journal of Managent Science， 2023， 31（3）： 48-57.
15	Ham A M. Integrated scheduling of m-truck， m-drone， and m-depot constrained by time-window， drop-pickup， and m-visit using constraint programming［J］. Transportation Research Part C： Emerging Technologies， 2018， 91： 1-14.
16	Nguyen M A， Dang G T H， Hà M H， et al. The min-cost parallel drone scheduling vehicle routing problem［J］. European Journal of Operational Research， 2022， 299（3）： 910-930.
17	Kyriakakis N A， Stamadianos T， Marinaki M， et al. The electric vehicle routing problem with drones： An energy minimization approach for aerial deliveries［J］. Cleaner Logistics and Supply Chain， 2022，4： 100041.
18	Mara S T W， Sarker R， Essam D， et al. Solving electric vehicle-drone routing problem using memetic algorithm［J］. Swarm and Evolutionary Computation， 2023， 79： 101295.
19	Jia Y H， Mei Y， Zhang M J. Confidence-based ant colony optimization for capacitated electric vehicle routing problem with comparison of different encoding schemes［J］. IEEE Transactions on Evolutionary Computation， 2022， 26（6）： 1394-1408.
20	Ropke S， Pisinger D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows［J］. Transportation Science， 2006， 40（4）： 455-472.
21	Solomon M M. Algorithms for the vehicle routing and scheduling problems with time window constraints［J］. Operations Research， 1987， 35（2）： 254-265.

文献来源	问题特征				求解算法
文献来源	时间窗	协同	载机平台	参与配送	求解算法
Schneider等^[4]	√	×	×	电动车	改进型变邻域搜索混合算法
Murray和Chu^[9]	√	√	燃油车/仓库	燃油车&无人机	FSTSP/PDSTSP启发式算法
Zhang等^[12]	×	√	燃油车	燃油车&无人机	改进型二代非支配排序遗传算法
Nguyen等^[16]	√	√	仓库	燃油车&无人机	Ruin-Recreate算法
Kyriakakis等^[17]	×	√	电动车	无人机	蚁群-变邻域搜索混合算法
Mara等^[18]	×	√	电动车	电动车&无人机	改进型模因算法
本文	√	√	仓库	电动车&无人机	拓展型自适应大邻域搜索算法

小规模算例	Gurobi		构造启发式算法			拓展型ALNS算法
小规模算例	结果	求解时间(s)	平均结果	求解时间(s)	Gap₁（%）	平均结果	求解时间(s)	Gap₂（%）
c'101-10-5	2597.00	94.44	2621.60	0.04	0.94	2597.00	29.55	0.00
c'104-10-5	1821.79	1800.00	1902.80	0.01	4.26	1821.79	22.38	0.00
c'202-10-5	1391.60	1155.56	1813.77	0.01	23.28	1391.60	46.87	0.00
c'205-10-5	1203.87	1.94	1281.12	0.01	6.03	1203.87	21.67	0.00
r'102-10-5	2247.57	15.18	2808.22	0.01	19.96	2247.57	19.68	0.00
r'103-10-5	1588.29	1800.00	1588.29	0.01	0.00	1588.29	18.51	0.00
r'201-10-5	1223.90	76.28	1245.99	0.03	1.77	1223.90	33.53	0.00
r'203-10-5	1154.64	1800.00	1709.87	0.02	32.47	1154.64	57.59	0.00
rc'102-10-5	3236.68	9.45	3821.39	0.01	15.30	3236.68	19.48	0.00
rc'108-10-5	2537.78	1245.27	2847.85	0.02	10.89	2537.78	24.27	0.00
rc'201-10-5	1622.50	17.53	2198.19	0.02	26.19	1622.50	35.00	0.00
rc'205-10-5	1971.73	82.66	2401.61	0.02	17.90	1971.73	30.29	0.00
c'103-15-5	2653.28	1800.00	2640.57	0.05	-0.48	2623.14	88.37	-1.14
c'106-15-5	1819.53	16.84	2429.24	0.02	25.10	1819.53	56.63	0.00
c'202-15-5	2139.79	1800.00	2303.25	0.04	7.10	2139.79	97.38	0.00
c'208-15-5	1354.16	427.65	1472.82	0.04	8.06	1354.16	78.38	0.00
r'102-15-5	3217.10	1800.00	4440.68	0.04	27.55	3227.86	57.76	0.33
r'105-15-5	2489.84	1800.00	3100.90	0.03	19.71	2489.84	53.26	0.00
r'202-15-5	2074.01	1800.00	2557.28	0.10	18.90	2074.01	133.84	0.00
r'209-15-5	1439.71	1800.00	1972.48	0.13	27.01	1439.71	140.68	0.00
rc'103-15-5	3176.28	1800.00	3320.36	0.02	4.34	3176.28	46.57	0.00
rc'108-15-5	2635.07	1800.00	3543.97	0.05	25.65	2596.64	63.35	-1.46
rc'202-15-5	2183.16	1800.00	2614.13	0.09	16.49	2183.16	121.08	0.00
rc'204-15-5	1656.44	1800.00	1879.70	0.09	11.885	1624.06	258.38	-1.95
平均值	2059.82	1105.95	2438.17	0.04	15.52	2056.06	64.77	-0.18

大规模算例	拓展型ALNS算法				原始ALNS算法
大规模算例	最好结果	最差结果	平均结果	求解时间(s)	最好结果	最差结果	平均结果	求解时间(s)
c'101-50-21	4026.94	4175.90	4074.62	1733.34	4032.22	4633.50	4331.44	1810.12
c'104-50-21	3445.51	3968.39	3647.74	2337.22	3700.17	4163.13	3918.14	2212.08
c'202-50-21	2186.31	2332.52	2246.10	3471.77	2204.61	2774.92	2400.59	3510.34
c'205-50-21	2179.71	2312.07	2213.34	3373.58	2186.29	2481.25	2387.98	3632.94
r'102-50-21	7853.29	8775.69	8222.46	1437.06	7915.18	8568.89	8224.19	2008.88
r'103-50-21	6410.88	7151.83	6785.54	1643.21	6387.14	7664.78	6874.59	2130.63
r'201-50-21	3575.30	3695.09	3632.72	3268.21	3585.84	3878.04	3674.69	2512.29
r'203-50-21	2636.83	3023.25	2808.07	3784.78	2705.28	3165.94	2838.17	3530.82
rc'102-50-21	6822.06	8085.07	7608.92	1518.09	7343.42	8047.72	7691.07	1986.68
rc'108-50-21	4982.78	5876.91	5585.97	1819.73	4996.45	6548.56	5603.96	2288.80
rc'201-50-21	4151.51	4848.81	4422.21	3540.07	4232.24	4843.93	4493.76	2660.32
rc'205-50-21	3143.20	3727.59	3439.14	4056.24	3221.38	3921.27	3608.49	3676.23
c'103-75-21	5975.25	6595.09	6284.27	5638.79	6442.85	7264.70	6767.96	6659.92
c'208-75-21	2945.13	3561.68	3182.93	13658.89	3281.87	3985.13	3521.66	12331.50
r'102-75-21	11088.43	11801.42	11461.22	4163.39	10974.41	11731.95	11517.31	5831.83
r'209-75-21	3433.44	3721.12	3537.16	14956.28	3390.15	4062.27	3854.47	12420.52
rc'103-75-21	8382.04	9712.31	9070.71	4554.43	9045.72	10066.35	9444.52	6338.62
rc'204-75-21	3316.06	4159.33	3646.66	18842.94	3690.78	4147.93	3838.15	13677.38

算例	EVRPTW-D模型	基准模型	成本节省比（%）
c'101-50-21	4403.83	4074.62	7.48
c'104-50-21	4154.12	3647.74	12.19
c'202-50-21	2679.77	2246.10	16.18
c'205-50-21	2749.42	2213.34	19.50
r'102-50-21	8464.87	8222.46	2.86
r'103-50-21	7008.55	6785.54	3.18
r'201-50-21	4031.61	3632.72	9.89
r'203-50-21	2984.04	2808.07	5.90
rc'102-50-21	7821.50	7608.92	2.72
rc'108-50-21	5757.45	5585.97	2.98
rc'201-50-21	4470.19	4422.21	1.07
rc'205-50-21	3632.78	3439.14	5.33
c'103-75-21	6651.91	6284.27	5.53
c'208-75-21	3490.21	3182.93	8.80
r'102-75-21	11802.24	11461.22	2.89
r'209-75-21	4054.40	3537.16	12.76
rc'103-75-21	9572.20	9070.71	5.24
rc'204-75-21	3969.89	3646.66	8.14
平均值	5427.72	5103.88	5.97

[1]	Guiqin Xue, Xianlong Ge. Study on Two-stage Dynamic Vehicle Scheduling Optimization Considering the Proactive Category [J]. Chinese Journal of Management Science, 2024, 32(12): 164-172.
[2]	Xinyue Zhang,Peng Jin,Xiaoxuan Hu,Moning Zhu. Research on the Time-dependent Multi-depot Open Vehicle Routing Problem with Time Windows [J]. Chinese Journal of Management Science, 2024, 32(1): 146-157.
[3]	HE Pei-yang, LI Kun-peng, TIAN Qian-nan. The Integrated Production and Transportation Scheduling Problem Based on 3D Printing Technology [J]. Chinese Journal of Management Science, 2023, 31(4): 239-249.
[4]	Xian-cheng ZHOU,Tao-ying JIANG,Cai-hong HE,Li WANG,Yang LV. Green Vehicle Routing Model and Its Solution Algorithm in Cold-chain Logistics Distribution [J]. Chinese Journal of Management Science, 2023, 31(12): 203-214.
[5]	TANG Zhao-ping, QIN Jin, SUN Jian-ping. Robust Optimization for Railway Emergency Location-Routing Based on Non-probabilistic Reliability [J]. Chinese Journal of Management Science, 2022, 30(9): 206-216.
[6]	GE Xian-long, WEN Peng-zhe, XUE Gui-qin. Two-echelon Dynamic Vehicle Routing Problem with Request Forecasting [J]. Chinese Journal of Management Science, 2022, 30(8): 210-220.
[7]	LI Yang, FAN Hou-ming, ZHANG Xiao-nan. A Periodic Optimization Model and Solution for Capacitated Vehicle Routing Problem with Dynamic Requests [J]. Chinese Journal of Management Science, 2022, 30(8): 254-266.
[8]	YAN Rui, CHEN Li-shuang, ZHU Xiao-ning, TIAN Hao-tong, WEN Ya, ZHANG Qun. Research on Vehicle Routing Problem with Truck and Drone Considering Regional Restriction [J]. Chinese Journal of Management Science, 2022, 30(5): 144-155.
[9]	XU Bao-guang, CHANG Jia-xin, GAO Min-gang. Research on Routing Problems about Road Information Collection Considering Mixed Mapping Method [J]. Chinese Journal of Management Science, 2022, 30(4): 218-227.
[10]	LIU Ming, XU Xi-fen, NING Jing, CAO Jie. Modeling and Optimizing Method for Rebalancing the Dock-less Bicycles based on Order Data Analysis [J]. Chinese Journal of Management Science, 2022, 30(4): 275-286.
[11]	GUO Fang, HUANG Zhi-hong, HUANG Wei-lai, YANG Chao. Optimal Planning of the Electric Vehicle Routing and Battery Charging Problem with Self-pickup and Door-to-door Delivery Service [J]. Chinese Journal of Management Science, 2022, 30(2): 264-275.
[12]	TANG Hui-ling, TANG Heng-shu, ZHU Xing-liang. Research on Low-carbon Vehicle Routing Problem Based on Modified Ant Colony Algorithm [J]. Chinese Journal of Management Science, 2021, 29(7): 118-127.
[13]	GUO Dong-wei, DING Gen-hong, LIU Wei. Improved Multi-Strategy Grouping Genetic Algorithm for the Pickup and Delivery Problem with Time Windows [J]. Chinese Journal of Management Science, 2020, 28(7): 204-211.
[14]	GUO Fang, YANG Jun, YANG Chao. Study on Heterogeneous Electric Vehicle Routing and Batterycharging Problem with the Consideration of Differentiated Service Cost [J]. Chinese Journal of Management Science, 2019, 27(8): 118-128.
[15]	FANG Wen-ting, AI Shi-zhong, WANG Qing, FAN Jun-bo. Research on Cold Chain Logistics Distribution Path Optimization Based on Hybrid Ant Colony Algorithm [J]. Chinese Journal of Management Science, 2019, 27(11): 107-115.

Vehicle Routing Problems with Time Windows under the Collaborative Delivery Mode of Electric Vehicle-drone

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 21

Related Articles 15

Metrics

Comments

Recommended 0