基于多智能体的网购生鲜无人车配送调度仿真

doi:10.16182/j.issn1004731x.joss.20-1050

摘要/Abstract

摘要：

无人车配送可有效缓解目前末端配送效率低、人力成本高、安全隐患多等问题。以城市社区网购生鲜无人车配送为研究对象，搭建了网购生鲜时空需求数据驱动的多智能体仿真平台，构建了基于实际路网的仿真环境及无人车、客户、配送站3类智能体，以运营成本最小及客户满意度最大为优化目标，设计并测试了动静态订单分配策略及距离最近或时间最紧配送路径规划策略。基于上海某生鲜电商实际订单数据，对不同策略展开情景模拟及敏感度分析，实现了运力资源的优化配置。

关键词: 多智能体仿真, 无人车配送, 网购生鲜, 订单分配, 路径规划

Abstract:

Autonomous delivery can solve the last-mile delivery problems of low efficiency, high manual cost, and potential safety hazard. The autonomous delivery of the online fresh food in urban communities is discussed and a data-driven agent-based platform with the actual spatial-temporal demand is built. Three kinds of agents including the autonomous vehicles, customers, and distribution center and the simulation environment based on the actual road network are construct. To achieve the objectives of the minimum total operating costs and maximum customer satisfaction, the different static and dynamic order dispatch strategies and the route planning strategies with the principle of the closest and most urgent are designed and tested. Based on the real order data collected from a fresh food e-commerce platform in Shanghai, the scenario simulation and sensitivity analysis are conducted based on the different strategies to optimize the transport capacity resource of autonomous vehicle.

Key words: multi-agent simulation, autonomous delivery, online fresh food shopping, order dispatch, route planning

中图分类号:

TP391

陆淼嘉, 黄承媛, 滕靖. 基于多智能体的网购生鲜无人车配送调度仿真[J]. 系统仿真学报, 2022, 34(6): 1185-1195.

Miaojia Lu, Chengyuan Huang, Jing Teng. Multi-agent Simulation for Online Fresh Food Autonomous Delivery[J]. Journal of System Simulation, 2022, 34(6): 1185-1195.

图/表 13

图1

图2

图3

图4

表1

图5

图6

图7

图8

表2

表3

图9

图10

参考文献 26

1	艾瑞咨询. 2019年中国生鲜电商行业研究报告[EB/OL].[2020-07-18]. .
	Iresearch. 2019 Chinese Fresh E-commerce Industry Research Report[EB/OL].[2020-07-18]. .
2	艾媒咨询. 2019年中国生鲜电商行业商业模式与用户画像分析报告[EB/OL].[2020-07-18]. .
	Iresearch. 2019 Chinese Fresh E-commerce Industry Business Model and User Portrait Analysis Report[EB/OL].[2020-07-18]. .
3	张珉. 新冠肺炎疫情下的无人配送[J]. 企业观察家, 2020(3): 46-47.
	Zhang Min. Autonomous Delivery in the Context of COVID-19[J]. Corporate Observer, 2020(3): 46-47.
4	史映红. 生鲜产品物流配送中存在的问题及对策[J]. 现代商业, 2020(2): 60-61.
	Shi Yinghong. Problems and Countermeasures in Logistics Distribution of Fresh Products[J]. Modern Commerce, 2020(2): 60-61.
5	邓娜, 张建军. O2O外卖订单配送任务分配模式研究[J].上海管理科学, 2018, 40(1): 63-66.
	Deng Na, Zhang Jianjun. Study on Assign Mode of O2O Takeaway Order Delivery Tasks[J]. Shanghai Management Science, 2018, 40(1): 63-66.
6	刘鹏宇, 陈淮莉. 采用超售策略的在线订单配送时隙运能分配[J]. 上海海事大学学报, 2018, 39(4): 38-43.
	Liu Pengyu, Chen Huaili. Capacity Distribution of Online Order Delivery Time Slot Using Oversold Strategy[J]. Journal of Shanghai Maritime University,2018, 39(4): 38-43.
7	戴大鹏. 网购物流城市共同配送联盟环境下的订单分配问题研究[D]. 重庆: 重庆大学, 2018.
	Dai Dapeng. Research on Order Allocation Problem in Online Shopping Stream City Common Distribution Alliance[D]. Chongqing: Chongqing University, 2018.
8	Kuhnle A, Schäfer L, Stricker N, et al. Design, Implementation and Evaluation of Reinforcement Learning for an Adaptive Order Dispatching in Job Shop Manufacturing Systems[J]. Procedia CIRP(S2212-8271),2019, 81: 234-239.
9	Malus A, Kozjek D, Vrabič R. Real-Time Order Dispatching for a Fleet of Autonomous Mobile Robots Using Multi-Agent Reinforcement Learning[J]. CIRP Annals-Manufacturing Technology(S0007-8506), 2020, 69(1): 397-400.
10	Xu Z, Li Z X, Guan Q W, et al. Large-Scale Order Dispatch in On-Demand Ride-Hailing Platforms[C]// 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: Association for Computing Machinery, 2018: 905-193.
11	Tang Xiaocheng, Qin Zhiwei, Zhang Fan, et al. A Deep Value-Network Based Approach for Multi-Driver Order Dispatching[C]// 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: Association for Computing Machinery, 2019: 1780-1790.
12	Zhang R, Rossi F, Pavone M. Model Predictive Control of Autonomous Mobility-on-Demand Systems[C]// International Conference on Robotics and Automation (ICRA). Stockholm: IEEE, 2016: 1382-1389.
13	张嘉琦. 基于移动子目标的复合式路径规划算法[J]. 中国公路学报, 2017, 30(11): 138-146.
	Zhang Jiaqi. Compound Path Planning Algorithm Based on Sliding Subtarget[J]. China Journal of Highway and Transport, 2017, 30(11): 138-146.
14	郭蓬, 吴学易, 戎辉, 等. 基于代价函数的无人驾驶汽车局部路径规划算法[J]. 中国公路学报, 2019, 32(6): 79-85.
	Guo Peng, Wu Xueyi, Rong Hui, et al. Local Path Planning of Driverless Cars Based on Cost Function[J]. China Journal of Highway and Transport, 2019, 32(6): 79-85.
15	胡觉亮, 张宇涛, 韩曙光. 城市物流中电动无人车配送优化研究[J]. 浙江理工大学学报(社会科学版), 2020, 44(2): 124-133.
	Hu Jueliang, Zhang Yutao, Han Shuguang. Research on Distribution Optimization of Electric Unmanned Vehicles in Urban Logistics[J]. Journal of Zhejiang Sci-Tech University(Social Sciences Edition), 2020, 44(2): 124-133.
16	Rabta B, Wankmuller C, Reiner G. A Drone Fleet Model for Last-Mile Distribution in Disaster Relief Operations[J]. International Journal of Disaster Risk Reduction(S2212-4209), 2018, 28: 107-112.
17	Agatz N, Paul B, Schmidt M. Optimization Approaches for the Traveling Salesman Problem with Drone[J]. Transportation Science(S0041-1655), 2018, 52(4): 965-981.
18	Paul B, Agatz N, Schmidt M. Dynamic Programming Approaches for the Traveling Salesman Problem with Drone[J]. Networks(S1097-0037), 2018, 72(4): 528-542.
19	Chang Y S, Lee H J. Optimal Delivery Routing with Wider Drone-Delivery Areas Along a Shorter Truck-Route[J]. Expert Systems with Applications(S0957-4174), 2018, 104: 307-317.
20	Yurek E E, Ozmutlu H C. A Decomposition-Based Iterative Optimization Algorithm for Traveling Salesman Problem with Drone[J]. Transportation Research Part C: Emerging Technologies (S0968-090X), 2018, 91: 249-262.
21	彭勇, 黎元钧. 考虑疫情影响的"卡车-无人机"协同配送路径优化[J]. 中国公路学报, 2020, 33(11): 73-82.
	Peng Yong, Li Yuanjun. Optimization of " Truck-drone" Collaborative Distribution Route Considering the Impact of Epidemic Situation[J]. China Journal of Highway and Transport, 2020, 33(11): 73-82.
22	Macal C M, North M J. Tutorial on Agent-Based Modeling and Simulation [C]// International Conference on Robotics and Automation (ICRA). Orlando Florida: IEEE, 2005: 2-15.
23	Barbati M, Bruno G, Genovese A. Applications of Agent-Based Models for Optimization Problems: A literature Review[J]. Expert Systems with Applications(S0957-4174), 2012, 39(5): 6020-6028.
24	Derksen C, Brabki C, Unland R, et al. A Framework for Agent-Based Simulations of Hybrid Energy Infrastructures [C]// Federated Conference on Computer Science and Information Systems (FedCSIS). Wroclaw Poland: IEEE, 2012: 1293-1299.
25	Ma T, Nakamori Y. Modeling Technological Change in Energy Systems-From Optimization to Agent-Based Modeling[J]. Energy(S0360-5442), 2009, 34(7): 873-879.
26	新石器. 新石器无人车让服务触手可及[EB/OL]. [2021-03-03]..
	Neolix. Neolix Autonomous Vehicle Makes Services at Your Fingertips[EB/OL]. [2021-03-03]. .

参数符号及单位	参数取值
行驶速度/(km/h)	16~25
租赁成本/(元/辆)	200
行驶成本/(元/km)	2
最大容量(单位体积件数)	3~10
无人车数量	10~30

项目	动态分配与最近配送	静态分配与最近配送	动态分配与最紧配送	静态分配与最紧配送
无人车容量	3	3	3	3
无人车数量	30	28	28	30
最小延时惩罚成本(元)	4 867	3 237	5 213	3 967
无人车容量	10	10	10	10
无人车数量	10	10	10	10
最小运营成本(元)	5 832	5 714	5 988	6 200
无人车容量	3	3	3	3
无人车数量	24	28	22	28
最小系统总成本(元)	16 277	15 579	17 383	16 836
无人车容量	10	10	10	10
无人车数量	29	30	30	30
最小平均行驶公里/km	73.66	93.68	109.24	111.38

项目	静态分配与最近配送	动态分配与最近配送	静态分配与最紧配送	动态分配与最紧配送
平均延时惩罚成本(元)	12 050	16 702	20 326	26 378
平均运营成本(元)	9 372	9 062	10 205	10 111
平均系统总成本(元)	21 423	25 764	30 531	36 490
平均行驶公里/km	143	138	165	162

[1]	张莉, 张惠珍, 刘冬, 陆雨欣. 考虑紧迫度的应急物资调度及粒子群算法求解[J]. 系统仿真学报, 2022, 34(9): 1988-1998.
[2]	李腾, 丁佩佩, 刘金芳. 货到人拣选系统多阶段可穿行多AGV路径规划[J]. 系统仿真学报, 2022, 34(7): 1512-1523.
[3]	张森, 张孟炎, 邵敬平, 普杰信. 基于随机策略搜索的多机三维路径规划方法[J]. 系统仿真学报, 2022, 34(6): 1286-1295.
[4]	蒙盾, 胡卓, 张华军. 基于改进A^*算法的多层邮轮疏散系统仿真[J]. 系统仿真学报, 2022, 34(6): 1375-1382.
[5]	梁江涛, 王慧琴. 基于改进蚁群算法的建筑火灾疏散路径规划研究[J]. 系统仿真学报, 2022, 34(5): 1044-1053.
[6]	邓向阳, 张立民, 方伟, 汤淼. 基于双向汇聚引导蚁群算法的机器人路径规划[J]. 系统仿真学报, 2022, 34(5): 1101-1108.
[7]	李兆强, 张时雨. 基于快速RRT算法的三维路径规划算法研究[J]. 系统仿真学报, 2022, 34(3): 503-511.
[8]	王启明, 宗高强, 胥津铭. 多段式自动泊车最优路径规划与仿真分析[J]. 系统仿真学报, 2022, 34(2): 385-395.
[9]	陈志梅, 李敏, 邵雪卷, 赵志诚. 基于改进RRT算法的桥式起重机避障路径规划[J]. 系统仿真学报, 2021, 33(8): 1832-1838.
[10]	李颀, 汪伟. 多全向轮协同分拣平台的路径规划[J]. 系统仿真学报, 2021, 33(3): 698-709.
[11]	黄晓冬, 苑海涛, 毕敬, 刘涛. 基于DQN的海战场舰船路径规划及仿真[J]. 系统仿真学报, 2021, 33(10): 2440-2448.
[12]	林彬, 韩光辉, 宋晨晨, 张雅静. 基于辐射扫描算法的机器人路径规划与仿真[J]. 系统仿真学报, 2021, 33(1): 84-90.
[13]	朱大奇, 朱婷婷, 颜明重. 基于改进神经网络的多AUV全覆盖路径规划[J]. 系统仿真学报, 2020, 32(8): 1505-1514.
[14]	张倩, 熊英, 何明珂, 张浩. 不确定需求生鲜电商配送路径规划多目标模型[J]. 系统仿真学报, 2019, 31(8): 1582-1590.
[15]	石敏, 魏育坤, 金相臣, 王素琴, 毛天露. 可支持跃层寻径的虚拟场景漫游方法[J]. 系统仿真学报, 2019, 31(7): 1358-1366.