基于存储点联合调度的社区无人车配送问题研究

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

摘要/Abstract

摘要：

随着智慧社区的不断推进，社区无人车配送成为政府、经营者和学者关注的热点问题。为均衡各存储点的运力需求并降低无人车的投入成本，将社区中的多个存储点联合调度，即一辆无人车可以往返于社区中不同的存储点取派货。社区无人车配送问题包括卸货子问题和无人车调度子问题，针对卸货子问题，以货车等待时间最小为目标，各存储点卸货效率、货车最大等待时间等为约束，优化货车的卸货方案；针对社区无人车调度子问题，以配送成本最小为目标，无人车最大载重、客户需求等为约束，优化无人车的路径方案。构建了两阶段规划模型并设计了一种两阶段变邻域搜索智能算法，将设计的货车组隶属度法和货车组指派法嵌入到两阶段算法中，提高了问题的处理效率。算例分析验证了模型和算法的有效性。针对存储点卸货效率、人工费用和无人车最大载重进行敏感性分析，结果表明，货车计划抵达时间相对集中时，提高存储点的卸货效率可以极大地减少货车在存储点的等待时间；过高或过低的单次人工费用都不会引起无人车调度方案改变，仅当单次人工费用在某个区间内变化时才会使无人车调度方案发生改变；增加无人车最大载重只能引起无人车配送费用有限地降低。

关键词: 社区配送, 无人车配送, 存储点联合调度, 两阶段模型, 启发式算法

Abstract:

With the development of smart communities, the distribution of driverless vehicles in communities has become a focus of government, operators and researchers. The joint cooperation of storage points in communities is designed to balance the the distribution of each storage point and avoid the high input cost of driverless vehicles, which means that driverless vehicles can travel between different storage points. The driverless vehicle distribution problem proposed in this paper includes the unloading subproblem and the driverless vehicle scheduling subproblem. For the unloading subproblem, the unloading scheme of vehicles at storage points is optimized with the aim of minimizing the waiting time of vehicles, and the unloading efficiency of each storage point and the maximum waiting time of vehicles are considered. For the driverless vehicle scheduling subproblem, the driverless vehicles routes are optimized with the objective of minimum distribution cost, and the maximum loading of driverlessvehicles and customer demands are considered. The two-stage model and one two-stage variable neighborhood search heuristic algorithm are designed, in addition, embedding the van group membership method and the van group assignment method into this algorithm improves the efficiency of handling this problem. The validity of the model and the algorithm is ensured by examples. For the sensitivity analysis on the unloading efficiency at the storage points, the labor cost and the maximum loading of the driverless vehicles, the results show that improving the unloading efficiency of the storage points can significantly reduce the waiting time of the vehicles when the planning arrival time of external vehicles is relatively concentrated. The change of unit labor cost at some interval will make the driverless vehicle scheduling plan change, and excessive or low unit labor cost will not do so. Increasing the maximum loading of the driverless vehicles can only reduce the delivery cost to a limited extent.

Key words: distribution in communities, driverless vehicle distribution, cooperation of storage points, two-stage model, heuristic algorithm

中图分类号:

TP391.9

刁小龙 . 基于存储点联合调度的社区无人车配送问题研究[J]. 系统仿真学报, 2025, 37(1): 284-298.

Diao Xiaolong . Driverless Vehicles Distribution Problem in Communities in Cooperation of Storage Points[J]. Journal of System Simulation, 2025, 37(1): 284-298.

图/表 16

图1

图2

图3

图4

图5

图6

图7

表1

图8

图9

表2

表3

图10

图11

图12

表4

参考文献 31

1	彭宏勤, 张国伍. 未来城市交通及其对未来城市发展影响-"交通7+1论坛"第五十六次会议[J]. 交通运输系统工程与信息, 2020, 20(1): 2-5.
	Peng Hongqin, Zhang Guowu. Future Urban Traffic and Its Influence on Cities Development[J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(1): 2-5.
2	《中国公路学报》编辑部. 中国汽车工程学术研究综述·2017[J]. 中国公路学报, 2017, 30(6): 1-197.
	Editorial Department of China Journal of Highway and Transport. Review on China's Automotive Engineering Research Progress: 2017[J]. China Journal of Highway and Transport, 2017, 30(6): 1-197.
3	Liu Shuai, Hua Guowei, Cheng T C E, et al. Unmanned Vehicle Distribution Capacity Sharing with Demand Surge Under Option Contracts[J]. Transportation Research Part E: Logistics and Transportation Review, 2021, 149: 102320.
4	Shi Jintian, Ma Ke. Digital Touchpoints in Campus Slow Traffic Service System[C]//Advances in Human Aspects of Transportation. Cham: Springer International Publishing, 2018: 349-361.
5	Shi Jintian, Sun Xiaohua. Service System-based Urban Mobility System Design for Chinese Metropolis[C]//Intelligent Human Systems Integration. Cham: Springer International Publishing, 2018: 693-699.
6	Jennings D, Figliozzi M. Study of Sidewalk Autonomous Delivery Robots and Their Potential Impacts on Freight Efficiency and Travel[J]. Transportation Research Record, 2019, 2673(6): 317-326.
7	Guo Yanhong, Chen Xinxin, Yang Yanyan. Multimodal Transport Distribution Model for Autonomous Driving Vehicles Based on Improved ALNS[J]. Alexandria Engineering Journal, 2022, 61(4): 2939-2958.
8	Yu Shaohua, Puchinger Jakob, Sun Shudong. Two-echelon Urban Deliveries Using Autonomous Vehicles[J]. Transportation Research Part E: Logistics and Transportation Review, 2020, 141: 102018.
9	Boysen Nils, Schwerdfeger Stefan, Weidinger Felix. Scheduling Last-mile Deliveries with Truck-based Autonomous Robots[J]. European Journal of Operational Research, 2018, 271(3): 1085-1099.
10	Anderluh Alexandra, Hemmelmayr Vera C, Nolz Pamela C. Synchronizing Vans and Cargo Bikes in a City Distribution Network[J]. Central European Journal of Operations Research, 2017, 25(2): 345-376.
11	Luo Chuanwen, Li Deying, Ding Xingjian, et al. Delivery Route Optimization with Automated Vehicle in Smart Urban Environment[J]. Theoretical Computer Science, 2020, 836: 42-52.
12	Cai Lecai, Wenya Lü, Xiao Liyang, et al. Total Carbon Emissions Minimization in Connected and Automated Vehicle Routing Problem with Speed Variables[J]. Expert Systems with Applications, 2021, 165: 113910.
13	Zhang Yong, Shi Lei, Chen Jing, et al. Analysis of an Automated Vehicle Routing Problem in Logistics Considering Path Interruption[J]. Journal of Advanced Transportation, 2017, 2017(1): 1624328.
14	王愚勤, 胡卉, 刘富鑫, 等. 智能网联下无人车配送路径优化[J]. 运筹与管理, 2021, 30(8): 52-58.
	Wang Yuqin, Hu Hui, Liu Fuxin, et al. Optimization of Unmanned Vehicle Distribution Path Under Intelligent Network Connection[J]. Operations Research and Management Science, 2021, 30(8): 52-58.
15	胡卉, 唐子淇, 刘富鑫, 等. 疫情下医用防护物资"无接触"配送优化[J]. 中国管理科学, 2023, 31(5): 152-163.
	Hu Hui, Tang Ziqi, Liu Fuxin, et al. Optimization of Contactless Distribution of Medical Protective Materials During the Outbreak of Spreading Epidemic Disease[J]. Chinese Journal of Management Science, 2023, 31(5): 152-163.
16	陆淼嘉, 黄承媛, 滕靖. 基于多智能体的网购生鲜无人车配送调度仿真[J]. 系统仿真学报, 2022, 34(6): 1185-1195.
	Lu Miaojia, Huang Chengyuan, Teng Jing. Multi-agent Simulation for Online Fresh Food Autonomous Delivery[J]. Journal of System Simulation, 2022, 34(6): 1185-1195.
17	王雷, 王欣, 刘德海, 等. 智能网联下无人驾驶汽车配送路径优化方法[J]. 系统科学与数学, 2020, 40(11): 1984-1998.
	Wang Lei, Wang Xin, Liu Dehai, et al. Route Optimization Methodology for Unmanned Vehicle Distribution in Intelligent Network[J]. Journal of Systems Science and Mathematical Sciences, 2020, 40(11): 1984-1998.
18	Wang Zheng, Sheu J B. Vehicle Routing Problem with Drones[J]. Transportation Research Part B: Methodological, 2019, 122: 350-364.
19	Wang Yong, Yuan Yingying, Guan Xiangyang, et al. Collaborative Two-echelon Multicenter Vehicle Routing Optimization Based on State-space-time Network Representation[J]. Journal of Cleaner Production, 2020, 258: 120590.
20	王勇, 李慧星, 罗思妤, 等. 资源共享模式下多中心共同配送电动车辆路径优化问题[J]. 系统管理学报, 2023, 32(6): 1119-1141.
	Wang Yong, Li Huixing, Luo Siyu, et al. Electric Vehicle Routing Optimization of Multi-center Joint Distribution Based on Resource Sharing Modes[J]. Journal of Systems & Management, 2023, 32(6): 1119-1141.
21	Diao Xiaolong, Fan Houming, Ren Xiaoxue, et al. Multi-depot Open Vehicle Routing Problem with Fuzzy Time Windows[J]. Journal of Intelligent & Fuzzy Systems, 2021, 40(1): 427-438.
22	范厚明, 刘鹏程, 刘浩, 等. 多中心联合配送模式下集货需求随机的VRPSDP问题[J]. 自动化学报, 2021, 47(7): 1646-1660.
	Fan Houming, Liu Pengcheng, Liu Hao, et al. The Multi-depot Vehicle Routing Problem with Simultaneous Deterministic Delivery and Stochastic Pickup Based on Joint Distribution[J]. Acta Automatica Sinica, 2021, 47(7): 1646-1660.
23	张珺. 无人车"快递员"跑进高校一天能送300个快递[N]. 武汉晚报, 2021-06-17(8).
24	李泽伟, 陈蕾. 10辆无人车上岗单车日送货900件[N]. 北京青年报, 2022-05-19(A05).
25	Li Haizhen, Ding Xilun. Adaptive and Intelligent Robot Task Planning for Home Service: A Review[J]. Engineering Applications of Artificial Intelligence, 2023, 117, Part B: 105618.
26	范厚明, 张轩, 任晓雪, 等. 多中心开放且需求可拆分的VRPSDP问题优化[J]. 系统工程理论与实践, 2021, 41(6): 1521-1534.
	Fan Houming, Zhang Xuan, Ren Xiaoxue, et al. Optimization of Multi-depot Open Split Delivery Vehicle Routing Problem with Simultaneous Delivery and Pick-up[J]. Systems Engineering-Theory & Practice, 2021, 41(6): 1521-1534.
27	Dror Moshe, Trudeau Pierre. Split Delivery Routing[J]. Naval Research Logistics, 1990, 37(3): 383-402.
28	刘树立, 于丽英. 人数与任务数不相等的指派问题[J]. 运筹与管理, 2005, 14(2): 64-66.
	Liu Shuli, Yu Liying. An Assignment Problem with Which the Quantities of Workers and Projects Are Different[J]. Operations Research and Management Science, 2005, 14(2): 64-66.
29	张进, 郭浩, 陈统. 基于可适应匈牙利算法的武器-目标分配问题[J]. 兵工学报, 2021, 42(6): 1339-1344.
	Zhang Jin, Guo Hao, Chen Tong. Weapon-target Assignment Based on Adaptable Hungarian Algorithm[J]. Acta Armamentarii, 2021, 42(6): 1339-1344.
30	张丽萍, 柴跃廷. 车辆路径问题的改进遗传算法[J]. 系统工程理论与实践, 2002, 22(8): 79-84.
	Zhang Liping, Chai Yueting. Improved Genetic Algorithm for Vehicle Routing Problem[J]. Systems Engineering-Theory & Practice, 2002, 22(8): 79-84.
31	陈迎欣. 基于改进蚁群算法的车辆路径优化问题研究[J]. 计算机应用研究, 2012, 29(6): 2031-2034.
	Chen Yingxin. Study on VRP Based on Improved Ant Colony Optimization[J]. Application Research of Computers, 2012, 29(6): 2031-2034.

货车组(客户组)	存储点
货车组(客户组)	A	B	C
P_(E,H)	L₁	L₂	L₃
P_(F)	L₄	L₅	L₆
P_(G)	L₇	L₈	L₉

40客户的算例		D₁T₁	D₁T₂	D₁T₃	D₂T₁	D₂T₂	D₂T₃	D₃T₁	D₃T₂	D₃T₃
CPLEX	等待时间	3	0	0	6	0	3	7	0	3
CPLEX	求解时间/s	3.47	3.62	3.43	3.68	3.67	2.92	3.62	3.43	3.49
TA	最小等待时间	3	0	0	6	0	3	7	0	3
	求解时间/s	0.35	0.35	0.36	0.37	0.37	0.34	0.34	0.34	0.38
	平均等待时间	3	0	0	6	0	3	7	0	3
80客户的算例		D₄T₁	D₄T₂	D₄T₃	D₅T₁	D₅T₂	D₅T₃	D₆T₁	D₆T₂	D₆T₃
CPLEX	等待时间	9	5	0	3	5	31	7	11	13
CPLEX	求解时间/s	3.34	3.14	3.51	3.89	3.2	3.41	3.63	3.57	3.53
TA	最小等待时间	9	5	0	3	5	31	7	11	13
	求解时间/s	0.34	0.35	0.39	0.37	0.37	0.37	0.36	0.33	0.38
	平均等待时间	9	5	0	3	5	31	7-	11	13
160客户的算例		D₇T₁	D₇T₂	D₇T₃	D₈T₁	D₈T₂	D₈T₃	D₉T₁	D₉T₂	D₉T₃
CPLEX	等待时间	35	31	0	47	26	11	55	21	23
CPLEX	求解时间/s	3.57	3.66	3.39	3.72	3.65	3.22	3.58	3.64	3.51
TA	最小等待时间	35	31	0	47	26	11	55	21	23
	求解时间/s	0.35	0.36	0.35	0.36	0.35	0.37	0.35	0.37	0.37
	平均等待时间	35	31	0	47	26	11	55	21	23

40客户的算例		S₁H₁	S₁H₂	S₁H₃	S₂H₁	S₂H₂	S₂H₃	S₃H₁	S₃H₂	S₃H₃
GA	最小费用	1 070	1 540	520	1 990	1 510	330	1 700	750	520
	求解时间/s	0.46	0.47	0.47	0.47	0.46	0.48	0.45	0.48	0.49
	平均费用	1 074	1 566	550	2 146	1 544	338	1 748	776	546
ACA	最小费用	990	1 390	490	1 960	1 420	310	1 630	700	520
	求解时间/s	0.47	0.46	0.48	0.47	0.53	0.53	0.49	0.48	0.49
	平均费用	1 064	1 486	506	2 020	1 458	324	1 676	742	532
TA	最小费用	920	1 250	490	1 880	1 180	310	1 520	610	490
	求解时间/s	0.48	0.47	0.49	0.47	0.47	0.45	0.46	0.47	0.48
	平均费用	940	1 324	496	1 920	1 220	314	1 570	676	500
80客户的算例		S₄H₁	S₄H₂	S₄H₃	S₅H₁	S₅H₂	S₅H₃	S₆H₁	S₆H₂	S₆H₃
GA	最小费用	2 140	2 310	600	2 700	2 000	340	2 550	2 350	580
	求解时间/s	0.49	0.52	0.51	0.51	0.48	0.48	0.48	0.52	0.5
	平均费用	2 192	2 402	644	2 740	2 160	350	2 620	2 454	604
ACA	最小费用	2 030	2 310	570	2 630	1 870	320	2 540	2 350	520
	求解时间/s	0.49	0.47	0.55	0.47	0.54	0.55	0.52	0.55	0.58
	平均费用	2 088	2 368	608	2 690	1 960	330	2 566	2 360	560
TA	最小费用	2 030	2 180	530	2 470	1 740	320	2 400	2 180	500
	求解时间/s	0.56	0.49	0.51	0.49	0.54	0.48	0.47	0.68	0.49
	平均费用	2 044	2 244	562	2 524	1 780	328	2 446	2 260	522
160客户的算例		S₇H₁	S₇H₂	S₇H₃	S₈H₁	S₈H₂	S₈H₃	S₉H₁	S₉H₂	S₉H₃
GA	最小费用	3 890	2 430	890	4 150	2 300	770	4 200	2 240	830
	求解时间/s	0.54	0.59	0.6	0.52	0.53	0.51	0.57	0.59	0.65
	平均费用	4 010	2 520	928	4 242	2 400	798	4 266	2 374	864
ACA	最小费用	3 730	2 400	850	4 150	2 270	760	4 140	2 170	810
	求解时间/s	0.54	0.52	0.55	0.54	0.6	0.59	0.53	0.61	0.67
	平均费用	3 880	2 434	878	4 184	2 308	784	4 210	2 252	836
TA	最小费用	3 710	2 300	800	4 090	2 250	740	4 100	2 110	790
	求解时间/s	0.63	0.59	0.54	0.65	0.68	0.56	0.5	0.72	0.59
	平均费用	3 768	2 346	830	4 114	2 254	750	4 120	2 146	792

算例Q	A	B	C	D	E	F	G	H	I
10	1 042	2 060	1 672	544	2 520	2 594	3 896	4 244	4 238
20	884	2 036	1 636	540	2 498	2 320	3 082	3 462	3 536
30	880	2 008	1 624	536	2 380	2 248	3 056	3 454	3 500
40	846	1 982	1 612	534	2 122	2 178	2 922	3 366	3 354

[1]	马华伟, 闫伯英. 面向防疫物资分区配送车机协同路径规划问题[J]. 系统仿真学报, 2025, 37(1): 234-244.
[2]	赵彦霖, 田云娜. 基于K-means聚类的超启发式跨单元调度方法[J]. 系统仿真学报, 2024, 36(4): 941-956.
[3]	庄鹤林, 夏小云, 李康顺, 陈泽丰, 张先超. 电动汽车路径规划模型与算法研究进展[J]. 系统仿真学报, 2024, 36(2): 320-337.
[4]	李珍萍, 施莹, 吴凌云. 多约束混流线平衡与排序优化问题研究[J]. 系统仿真学报, 2023, 35(1): 27-40.
[5]	陆淼嘉, 黄承媛, 滕靖. 基于多智能体的网购生鲜无人车配送调度仿真[J]. 系统仿真学报, 2022, 34(6): 1185-1195.
[6]	沈鹏, 王艳, 纪志成, 张建华. 超启发式DE算法求解零等待发酵工艺调度[J]. 系统仿真学报, 2020, 32(11): 2235-2243.
[7]	邢志伟, 唐云霄. 枢纽机场航班保障服务时间估计[J]. 系统仿真学报, 2017, 29(11): 2856-2865.