Multi-agent Simulation for Online Fresh Food Autonomous Delivery

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

Abstract

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

CLC Number:

TP391

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.

Figures/Tables 13

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Table 1

Fig. 5

Fig. 6

Fig. 7

Fig. 8

Table 2

Table 3

Fig. 9

Fig. 10

References 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]	Sun Ling, Dong Ya, Liu Wei, Yang Guanyun. Simulation Analysis of Self-driving Travelling Routes [J]. Journal of System Simulation, 2019, 31(3): 429-437.
[2]	Du Zhe, Wen Yuanqiao, Huang Liang, Zhou Chunhui, Xiao Changshi. Route Planning for Vessel Based on Dynamic Complexity Map [J]. Journal of System Simulation, 2018, 30(6): 2390-2398.
[3]	Hu Dongbo, Shen Yue, Heng Rudan, Zhang Binbin. Simulation on Global Demand Information Sharing Value in B2B Supply Chain [J]. Journal of System Simulation, 2017, 29(7): 1611-1617.
[4]	Yang Yong, Yan Xijun, Zhang Heng. Efficiency Simulation of System of UAV Patrol System Base on STK [J]. Journal of System Simulation, 2015, 27(9): 2031-2037.
[5]	Li Feng, Wei Ying. Simulation Research on Impact of Consumer Bounded Rationality on Optimal Pricing Strategy in Supply Chain [J]. Journal of System Simulation, 2015, 27(12): 2898-2907.