面向防疫物资分区配送车机协同路径规划问题

doi:10.16182/j.issn1004731x.joss.23-1022

摘要/Abstract

摘要：

针对目前防疫物资车机协同配送中没有满足疫区无接触配送需求的问题，提出车机协同分区配送问题。以最短配送时间作为优化目标，建立线性规划模型，并提出一种两阶段启发式算法，其中第一阶段通过贪婪算法生成初始解，第二阶段设计了一种混合遗传算法（tabu search algorithm with genetic algorithm，TSGA），将禁忌搜索算法思想与遗传算法相结合进行求解，通过引入禁忌表与节点交换算子和节点变异算子，改进了染色体方式，提升了算法的求解性能。实验结果表明，TSGA与基于遗传思想的自适应算法以及混合禁忌模拟退火算法对比，其解质量与求解时间均优。综上，该两阶段算法能够有效解决VRPD-ZD问题，提升防疫物资车机协同配送效率。

关键词: 车机协同, 分区配送, 防疫物资配送, 两阶段启发式算法, 遗传算法

Abstract:

To address the shortcomings of current contactless delivery methods in the collaborative distribution of epidemic prevention supplies, we introduce a specialized model called the vehicle routing problem with drones considering zoned distribution (VRPD-ZD). In order to solve the problem, a linear programming model is established with the shortest delivery time as the optimization objective, and a two-stage heuristic algorithm is proposed. The initial solution is generated by greedy algorithm in the first stage. In the second stage, we develop a Tabu search algorithm with genetic algorithm (TSGA) hybrid. This enhanced algorithm integrates a taboo list and employs advanced chromosome encoding techniques to improve performance. The experimental results show that TSGA compares favourably with the adaptive algorithm based on genetic method (AAGM) as well as the simulated-annealing-based two-phase optimization (SATO) in terms of solution quality and solution time. This two-stage algorithm can effectively solve the VRPD-ZD problem and can improve the efficiency of cooperative vehicle-machine distribution of epidemic prevention materials.

Key words: truck-drone cooperation, zoned distribution, distribution of epidemic prevention supplies, two stage heuristic algorithm, genetic algorithm

中图分类号:

U116

马华伟,闫伯英 . 面向防疫物资分区配送车机协同路径规划问题[J]. 系统仿真学报, 2025, 37(1): 234-244.

Ma Huawei,Yan Boying . Vehicle Routing Problem with Drones Considering Zoned Distribution of Epidemic Prevention Materials[J]. Journal of System Simulation, 2025, 37(1): 234-244.

图/表 13

图1

表1

符号及定义

符号类型	符号	含义
集合	$G$	定义问题的有向图
	$V$	节点集合
	$A$	所有弧集合
	$V 0$	仓库节点集合，包括出发点0(s)与返回点0(r)
	$V C$	顾客节点集合
	$K T$	={1,2,…,K}，车辆集合
	$K D$	={1,2,…,K}，无人机集合
	$V T$	车辆服务节点集合
	$V D$	无人机服务节点集合
	$V L$	无人机起飞节点集合
	$V R$	无人机降落节点集合
	$R k'$	无人机k′架次集合
	$V N T$	封控区内节点集合
	$D i$	服务节点i需求量
参数	$Q$	车辆最大载重
	$M$	能调用车辆最大数目
	$q$	无人机最大载重
	$B$	无人机最大续航
	$Γ i, j k$	车辆k经过弧(i,j)的运行时间
	$τ i, j k'$	无人机k'经过弧(i,j)的运行时间
	$T i k$	车辆k到达节点i的累计运行时间
决策变量	$t i k'$	无人机k'到达节点i的累计运行时间
	$v i k$	如果车辆k服务点i，则为1，否则为0
	$d i k'$	如果无人机k′服务点i，则为1，否则为0
	$x i, j k$	如果车辆k从点i行驶到点j，则为1，否则为0
	$y i, j p, k'$	如果无人机k'的第p个架次中从点i行驶到点j，则为1，否则为0，其中，p∈R $k'$
	$G k$	k型货车在给定路线下返回车辆段的时间，以及完成其服务路线后的总行驶时间

表1

图2

图3

图4

图5

图6

图7

图8

图9

图10

表2

表3

参考文献 26

1	Tăbușcă Alexandru, Gabriel Eugen Garais. IoT and the Flying Answer to COVID-19[J]. Journal of Information Systems & Operations Management, 2020, 14(1): 162-173.
2	北京日报. 疫情期间, 京东无人配送"科技抗疫"[EB/OL]. (2020-04-13) [2023-07-15]. .
3	Wu Guohua, Mao Ni, Luo Qizhang, et al. Collaborative Truck-drone Routing for Contactless Parcel Delivery During the Epidemic[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(12): 25077-25091.
4	Macrina Giusy, Luigi di Puglia Pugliese, Guerriero Francesca, et al. Drone-aided Routing: A Literature Review[J]. Transportation Research Part C: Emerging Technologies, 2020, 120: 102762.
5	和媛媛, 姜盼松, 温禄兴, 等. 权衡公平-经济-效率的多品种防疫物资配送策略[J]. 工业工程与管理, 2021, 26(6): 146-153.
	He Yuanyuan, Jiang Pansong, Wen Luxing, et al. Distribution Strategy of Multiple Epidemic Prevention Materials Weighing Fairness, Economy and Efficiency[J]. Industrial Engineering and Management, 2021, 26(6): 146-153.
6	何婷, 侯汉平, 杨建亮. 疫情背景下生鲜电商企业车辆路径优化研究[J]. 中国安全生产科学技术, 2020, 16(7): 183-188.
	He Ting, Hou Hanping, Yang Jianliang. Research on Vehicle Route Optimization of Fresh E-commerce Enterprises Under Background of Epidemic Situation[J]. Journal of Safety Science and Technology, 2020, 16(7): 183-188.
7	Lu Yichen, Yang Chao, Yang Jun. A Multi-objective Humanitarian Pickup and Delivery Vehicle Routing Problem with Drones[J]. Annals of Operations Research, 2022, 319(1): 291-353.
8	Shi Yuhe, Lin Yun, Li Bo, et al. A Bi-objective Optimization Model for the Medical Supplies' Simultaneous Pickup and Delivery with Drones[J]. Computers & Industrial Engineering, 2022, 171: 108389.
9	Barnawi Ahmed, Chhikara Prateek, Tekchandani Rajkumar, et al. A CNN-based Scheme for COVID-19 Detection with Emergency Services Provisions Using an Optimal Path Planning[J]. Multimedia Systems, 2023, 29(3): 1683-1697.
10	杨双鹏, 郭秀萍, 高娇娇. 无接触式"卡车+无人机"联合配送问题研究[J]. 工业工程与管理, 2022, 27(1): 184-194.
	Yang Shuangpeng, Guo Xiuping, Gao Jiaojiao. Research on Contactless "Truck+Drone" Joint Distribution Problem[J]. Industrial Engineering and Management, 2022, 27(1): 184-194.
11	刘长石, 吴张, 周愉峰, 等. 疫区应急物资供应的卡车-无人机动态协同配送路径优化[J]. 系统科学与数学, 2022, 42(11): 3027-3043.
	Liu Changshi, Wu Zhang, Zhou Yufeng, et al. The Optimization of Dynamic and Cooperative Truck-drone Distribution Routes for Emergency Supplies Delivery in Pandemic Areas[J]. Journal of Systems Science and Mathematical Sciences, 2022, 42(11): 3027-3043.
12	蒋丽, 梁昌勇, 臧晓宁. 卡车与无人机协同的无接触式配送问题的双层启发式算法[J/OL]. 中国管理科学. (2022-11-27) [2023-06-24]. .
	Jiang Li, Liang Changyong, Zang Xiaoning. A Bilevel Heuristic for the Contactless Delivery Problem Coordinated with Trucks and Drones[J/OL]. Chinese Journal of Management Science. (2022-11-27) [2023-06-24]. .
13	季金华, 刘亚君, 别一鸣, 等. 基于无人机与卡车协作的封控社区生活物资配送方法[J]. 交通运输系统工程与信息, 2022, 22(5): 264-272.
	Ji Jinhua, Liu Yajun, Bie Yiming, et al. Delivery Method of Living Goods in Controlled Communities Based on Cooperation Between Drones and Truck[J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(5): 264-272.
14	Wang Xingyin, Poikonen S, Golden B. The Vehicle Routing Problem with Drones: Several Worst-case Results[J]. Optimization Letters, 2017, 11(4): 679-697.
15	Daknama Rami, Kraus Elisabeth. Vehicle Routing with Drones[EB/OL]. (2017-05-18) [2023-07-15]. .
16	Wang Zheng, Sheu J B. Vehicle Routing Problem with Drones[J]. Transportation Research Part B: Methodological, 2019, 122: 350-364.
17	Schermer Daniel, Moeini Mahdi, Wendt Oliver. A Hybrid VNS/Tabu Search Algorithm for Solving the Vehicle Routing Problem with Drones and en Route Operations[J]. Computers & Operations Research, 2019, 109: 134-158.
18	Sacramento David, Pisinger David, Ropke Stefan. An Adaptive Large Neighborhood Search Metaheuristic for the Vehicle Routing Problem with Drones[J]. Transportation Research Part C: Emerging Technologies, 2019, 102: 289-315.
19	Kitjacharoenchai P, Min B C, Lee S. Two Echelon Vehicle Routing Problem with Drones in Last Mile Delivery[J]. International Journal of Production Economics, 2020, 225: 107598.
20	彭勇, 黎元钧. 考虑疫情影响的卡车无人机协同配送路径优化[J]. 中国公路学报, 2020, 33(11): 73-82.
	Peng Yong, Li Yuanjun. Optimization of Truck-drone Collaborative Distribution Route Considering Impact of Epidemic[J]. China Journal of Highway and Transport, 2020, 33(11): 73-82.
21	Jeong H Y, Duk Song Byung, Lee S. Truck-drone Hybrid Delivery Routing: Payload-energy Dependency and No-fly Zones[J]. International Journal of Production Economics, 2019, 214: 220-233.
22	颜瑞, 陈立双, 朱晓宁, 等. 考虑区域限制的卡车搭载无人机车辆路径问题研究[J]. 中国管理科学, 2022, 30(5): 144-155.
	Yan Rui, Chen Lishuang, Zhu Xiaoning, et al. Research on Vehicle Routing Problem with Truck and Drone Considering Regional Restriction[J]. Chinese Journal of Management Science, 2022, 30(5): 144-155.
23	Lin Shen. Computer Solutions of the Traveling Salesman Problem[J]. The Bell System Technical Journal, 1965, 44(10): 2245-2269.
24	Solomon M M. Benchmarking Problems[EB/OL]. (2005-03-24) [2023-06-15]. .
25	马华伟, 马凯, 郭君. 考虑多投递的带无人机车辆路径规划问题研究[J]. 计算机工程, 2022, 48(8): 299-305.
	Ma Huawei, Ma Kai, Guo Jun. Research on Vehicle Routing Problem with Drones Considering Multi-delivery[J]. Computer Engineering, 2022, 48(8): 299-305.
26	Hong Fangyu, Wu Guohua, Luo Qizhang, et al. Logistics in the Sky: A Two-phase Optimization Approach for the Drone Package Pickup and Delivery System[J]. IEEE Transactions on Intelligent Transportation Systems, 2023, 24(9): 9175-9190.

算例	TSGA		GAP/%	CPLEX
算例	最好解	时间/s	GAP/%	最好解	时间/s
平均值		3.26			2 530.52
c10-n1	27.17	1.14	1.30	26.82	3.57
c20-n2	141.34	2.96	0.21	141.05	212.86
c30-n3	242.56	3.50	0.17	242.18	6 120.24
c50-n5	510.78	3.94
r10-n1	125.90	2.08	1.05	151.31	5.19
r20-n2	270.03	4.23	0.11	269.72	314.51
r30-n3	395.16	4.29	0.07	394.87	8 320.38
r50-n5	651.29	4.80
rc10-n1	102.41	2.11	0.12	102.29	7.24
rc20-n2	250.54	3.01	0.63	248.97	170.56
rc30-n3	627.67	3.29	0.08	627.15	7 620.16
rc50-n5	947.80	3.79

算例	TSGA		GAP/%	AAGM		GAP/%	SATO
算例	最好解	时间/s	GAP/%	最好解	时间/s	GAP/%	最好解	时间/s
平均值		3.27	-2.68		7.27	-2.56		16.40
c101	1 529.86	3.17	-2.52	1 569.41	6.23	-3.97	1 593.11	14.13
c102	1 530.32	3.13	-1.87	1 559.48	6.35	-1.25	1 549.69	13.85
c103	1 533.75	3.11	-5.74	1 627.20	6.47	0.08	1 532.52	14.47
c104	1 533.12	3.22	-3.12	1 582.49	6.59	-4.14	1 599.33	13.89
c105	1 543.94	3.37	-0.93	1 558.43	6.71	-3.10	1 593.33	13.71
r101	1 359.70	3.42	-4.18	1 419.01	8.18	-2.52	1 394.85	17.68
r102	1 367.59	3.54	0.67	1 358.49	7.89	-3.66	1 419.55	18.19
r103	1 322.03	3.58	-5.28	1 395.72	8.21	0.42	1 316.50	17.71
r104	1 354.41	3.30	-2.36	1 387.15	8.13	-4.32	1 415.56	17.93
r105	1 349.77	3.64	0.45	1 343.72	8.04	-2.73	1 387.65	18.64
rc101	2 211.19	3.12	-4.61	2 318.05	7.12	-0.91	2 231.50	16.92
rc102	2 209.63	3.13	-1.82	2 250.59	7.24	-2.31	2 261.88	16.94
rc103	2 214.98	2.93	-3.44	2 293.89	7.36	-3.88	2 304.39	17.26
rc104	2 192.45	3.09	0.22	2 187.64	7.28	-1.6	2 228.10	16.98
rc105	2 185.25	3.26	-5.63	2 315.62	7.19	-4.43	2 286.54	17.59

[1]	肖鹏, 谢锋, 倪海鸿, 张敏, 汤志荔, 李霓. 多机任务分配与路径规划协同优化法研究[J]. 系统仿真学报, 2024, 36(5): 1141-1151.
[2]	唐进君, 胡立鹏, 李明洋, 张璇. 基于Kriging遗传算法的高速公路应急车道管控优化[J]. 系统仿真学报, 2024, 36(5): 1165-1178.
[3]	万远鹏, 梁承姬, 王思洪, 王钰. 考虑订单替换的冷链配送-库存联合优化与仿真[J]. 系统仿真学报, 2024, 36(3): 578-594.
[4]	阎世梁, 王银玲, 路丹丹, 潘小琴. 基于深度神经网络的永磁直线电机仿真与优化[J]. 系统仿真学报, 2024, 36(3): 713-725.
[5]	卫翔, 刘星璇, 付殿峥, 杨天吉, 杨家轩. 基于声纳搜索累积探测概率的平台路径优化方法[J]. 系统仿真学报, 2024, 36(11): 2674-2683.
[6]	陈加俊, 谭代伦. 基于动态缩减机制的多策略单亲遗传算法求解CVRP问题[J]. 系统仿真学报, 2024, 36(10): 2396-2412.
[7]	张红历, 邓井双. 基于遗传算法的人工人口生成与应用研究[J]. 系统仿真学报, 2023, 35(9): 1965-1974.
[8]	吴玉文, 牛智越, 李珍萍. 基于改进遗传算法的货箱机器人拣选路径规划[J]. 系统仿真学报, 2023, 35(5): 1086-1097.
[9]	李志强, 李元龙, 殷来祥, 马向平. 智能无人蜂群作战系统适应性进化模型仿真研究[J]. 系统仿真学报, 2023, 35(4): 878-886.
[10]	张虎成, 杨镜宇. 基于GABC算法的作战体系智能优化方法研究[J]. 系统仿真学报, 2023, 35(1): 221-227.
[11]	徐佳, 韩逢庆, 刘奇鑫, 薛晓霞. 一种求解TSP的生物信息启发式遗传算法[J]. 系统仿真学报, 2022, 34(8): 1811-1819.
[12]	于淼, 李曼茹, 赵愈. 考虑等待提示机制的呼叫中心联合排班方法[J]. 系统仿真学报, 2022, 34(7): 1651-1661.
[13]	李智杰, 石昊琦, 李昌华, 张颉. 基于改进遗传算法的影像中心布局优化方法[J]. 系统仿真学报, 2022, 34(6): 1173-1184.
[14]	付建林, 丁国富, 张剑, 江海凡, 郭沛佩. 基于响应面和NSGA-II的AGV系统多目标优化配置[J]. 系统仿真学报, 2022, 34(5): 994-1002.
[15]	王喆, 邵鸿远, 丛子皓, 马雯雯. 考虑供应商聚类的应急医疗物资协同配送仿真[J]. 系统仿真学报, 2022, 34(10): 2303-2311.