动态需求下考虑订单聚类的外卖配送路径优化

doi:10.16182/j.issn1004731x.joss.21-0965

摘要/Abstract

摘要：

外卖配送路径优化包括骑手间订单分配和骑手配送路径规划两部分。针对其中订单动态产生和骑手位置不断变化的问题，基于预优化后动态调整的思想建立以最小化超时订单比例、单均配送时间和单均行驶距离为目标的两阶段优化模型。在预优化阶段，设计改进变邻域搜索算法获得初始配送方案；在动态调整阶段，采用周期性优化策略，将不断变换的骑手位置转化为虚拟配送中心车辆问题进行求解；在每一阶段采用不同的聚类方法对订单进行聚类，优化初始解的质量以更快求解。结果验证了本文策略和算法在求解动态外卖配送路径问题时的有效性和可行性。研究成果不仅深化拓展了PDVRP(pickup and delivery vehicle routing problem with time window)相关理论研究，也为外卖平台提供一种科学的优化方案。

关键词: 外卖配送, 动态需求, 订单聚类, 周期性优化, 改进变邻域搜索

Abstract:

Takeout distribution optimization includes order allocation and route planning. Aiming at dynamic order and rider position change, with the goal of minimizing the overtime order proportion, average delivery time and average travel distance,a two-stage mathematical model is established based on the idea of pre-optimization and dynamic adjustment. In the pre-optimization stage, an improved variable neighborhood search algorithm is designed to obtain the initial distribution scheme. In the dynamic adjustment stage, a periodic optimization strategy is adopted to transform the problem into a virtual distribution center vehicle problem for solution. In each stage,different clustering methods are used to optimize the initial solution quality for faster solution. The effectiveness and feasibility of the proposed strategy and algorithm to solve the dynamic takeout distribution routing problem are verified and comparatively analzed. The research results not only deepen and expand PDVRP related theoretical research, but also provide a scientific takeout distribution optimization scheme for the takeout distribution platform.

Key words: takeout distribution, dynamic demand, order clustering, period optimization, improved VNS

中图分类号:

TP391.9

范厚明, 咸富山, 王怀奇. 动态需求下考虑订单聚类的外卖配送路径优化[J]. 系统仿真学报, 2023, 35(2): 396-407.

Houming Fan, Fushan Xian, Huaiqi Wang. Takeout Distribution Routes Optimization Considering Order Clustering under Dynamic Demand[J]. Journal of System Simulation, 2023, 35(2): 396-407.

图/表 12

图1

图 2

图3

图 4

图 5

图 6

表 1

表 2

表 3

表 4

表 5

图 7

参考文献 25

1	徐倩, 熊俊, 杨珍花, 等. 基于自适应大邻域搜索算法的外卖配送车辆路径优化[J]. 工业工程与管理, 2021, 26(3): 115-122.
	Xu Qian, Xiong Jun, Yang Zhenhua, et al. Route Optimization of Takeout Delivery Vehicles Based on Adaptive Large Neighborhood Search Algorithm[J]. Industrial Engineering and Management, 2021, 26(3): 115-122.
2	Goetschalckx M, Jacobs-blecha C. The Vehicle Routing Problem with Backhauls[J]. European Journal of Operational Research(S0377-2217), 1987, 42(1): 39-51.
3	Min H. The Multiple Vehicle Routing Problem with Simultaneous Delivery and Pick-Up Points[J]. Transportation Research Part A: General(S0965-8564), 1989, 23(5): 377-386.
4	王新玉, 赵志明. 动态取送问题研究综述[J]. 系统工程理论与实践, 2021, 41(2): 319-331.
	Wang Xinyu, Zhao Zhiming. Survey of the Dynamic Pickup and Delivery Problems[J]. Systems Engineering-Theory & Practice, 2021, 41(2): 319-331.
5	孙宝凤, 杨悦, 史俊妍, 等. 考虑真实场景动态事件的动态取送货问题[J]. 浙江大学学报(工学版), 2020, 54(8): 1604-1612, 1644.
	Sun Baofeng, Yang Yue, Shi Junyan, et al. Dynamic Pick-up and Delivery Problem Considering Dynamic Events in Real-world Environment[J]. Journal of Zhejiang University(Engineering Science), 2020, 54(8): 1604-1612, 1644.
6	王恒, 徐亚星, 王振锋, 等. 基于道路状况的生鲜农产品配送路径优化[J]. 系统仿真学报, 2019, 31(1): 126-135.
	Wang Heng, Xu Yaxing, Wang Zhenfeng, et al. Distribution Routing Optimization of Fresh Agricultural Products Based on Road Conditions[J]. Journal of System Simulation, 2019, 31(1): 126-135.
7	徐东洋, 李昆鹏, 郑飘, 等. 多车场多车型多品类供需未匹配与可任意拆分取送货车辆路径问题优化[J]. 管理学报, 2020, 17(7): 1086-1095.
	Xu Dongyang, Li Kunpeng, Zheng Piao, et al. The Optimization Research of Multi-Category Unpaired Supply-Demand and Arbitrary Split Pickup and Delivery Vehicle Routing Problem with Multi-Depot and Multi-Type Trucks[J]. Chinese Journal of Management, 2020, 17(7): 1086-1095.
8	张景玲, 刘金龙, 赵燕伟, 等. 时间依赖型同时取送货VRP及超启发式算法[J]. 计算机集成制造系统, 2020, 26(7): 1905-1917.
	Zhang Jingling, Liu Jinlong, Zhao Yanwei, et al. Hyper-heuristic for Time-dependent VRP with Simultaneous Delivery and Pickup[J]. Computer Integrated Manufacturing Systems, 2020, 26(7): 1905-1917.
9	Pei Yilei, Li Dandan, Xue Wanxin. The Evaluation of Customer Experience Using BP Neural Network-Taking Catering O2O Takeout[J]. Concurrency and Computation: Practice and Experience(S1532-0626), 2019, 32(23): e5515.1-e5515.8
10	郑文, 窦晨希, 张喆. 外卖平台专送式利益分配仿真[J]. 系统仿真学报, 2021, 33(3): 631-644.
	Zheng Wen, Dou Chenxi, Zhang Zhe. Simulation of Benefit Distribution in Platform Delivery Mode[J]. Journal of System Simulation, 2021, 33(3): 631-644.
11	陈萍, 李航. 基于时间满意度的O2O外卖配送路径优化问题研究[J]. 中国管理科学, 2016, 24(增1): 170-176.
	Chen Ping, Li Hang. Optimization Model and Algorithm Based on Time Satisfaction for O2O Food Delivery[J]. Chinese Journal of Management Science, 2016, 24(S1): 170-176.
12	Liang Decui, Dai Zhuoyin, Wang Mingwei. Assessing Customer Satisfaction of O2O Takeaway Based on Online Reviews by Integrating Fuzzy Comprehensive Evaluation with AHP and Probabilistic Linguistic Term Sets[J]. Applied Soft Computing(S1568-4946), 2021,98: 106847.
13	Lang Kun, Zhao Yuxin. Cloud Computing Resource Scheduling Based on Improved ANN Model Takeaway Order Volume Forecast[J]. Journal of Intelligent & Fuzzy Systems(S1064-1246), 2020, 40(12): 1-10.
14	赵道致, 杨洁. O2O外卖配送预计送达时间决策模式的选择策略[J]. 工业工程与管理, 2018, 23(5): 8-14, 23.
	Zhao Daozhi, Yang Jie. Research on Decision-making Model of Estimated Delivery Time in O2O Food Delivery[J]. Industrial Engineering and Management, 2018, 23(5): 8-14, 23.
15	吴腾宇, 陈嘉俊, 蹇洁, 等. O2O模式下的配送车辆实时取送货路径选择问题[J]. 系统工程理论与实践, 2018, 38(11): 2885-2891.
	Wu Tengyu, Chen Jiajun, Jian Jie, et al. The Oline Pick-up and Delivery Rounting Problem under O2O Delivery[J]. Systems Engineering-Theory & Practice, 2018, 38(11): 2885-2891.
16	靳志宏, 鞠新诚, 郭加佳, 等. O2O模式下外卖骑手的配送路径优化[J]. 大连海事大学学报, 2019, 45(4): 55-64.
	Jin Zhihong, Ju Xincheng, Guo Jiajia, et al. Optimization on Distribution Routes of the Takeaway Delivery Staff under the O2O Mode[J]. Journal of Dalian Maritime University, 2019, 45(4): 55-64.
17	赵向南, 邢磊, 靳志宏. 考虑不确定行驶时间的双目标外卖配送路径优化[J]. 大连海事大学学报, 2019, 45(4): 65-72.
	Zhao Xiangnan, Xing Lei, Jin Zhihong. Bi-objective Takeaway Distribution Route Optimization Considering Uncertain Drivingtime[J]. Journal of Dalian Maritime University, 2019, 45(4): 65-72.
18	余建军, 程文琪, 吴永忠. 考虑顾客满意度的生鲜外卖路径规划[J]. 工业工程与管理, 2021, 26(4): 158-167.
	Yu Jianjun, Cheng Wenqi, Wu Yongzhong. Path Planning of Fresh Takeout Considering Customer Satisfaction[J]. Industrial Engineering and Management, 2021, 26(4): 158-167.
19	张力娅, 张锦, 肖斌. 考虑顾客优先级的多目标O2O外卖即时配送路径优化研究[J]. 工业工程与管理, 2021, 26(2): 196-204.
	Zhang Liya, Zhang Jin, Xiao Bin. Multi-objective O2O Take-out Instant Delivery Routing Optimization Considering Customer Priority[J]. Industrial Engineering and Management, 2021, 26(2): 196-204.
20	Yang Aifang. Research on Takeaway Distribution Path under Multiple Constraints[J]. International Core Journal of Engineering(S2414-1895), 2020, 6(3): 204-208.
21	Qi Mingyao, Lin Weihua, Li Nan, et al. A Spatiotemporal Partitioning Approach for Large-Scale Vehicle Routing Problems with Time Windows[J]. Transportation Research Part E(S1366-5545), 2011, 48(1): 248-257.
22	王旭坪, 李新宇, 张珺. 考虑时空距离的异车型同时集送车辆路径优化[J]. 管理学报, 2018, 15(6): 918-926.
	Wang Xuping, Li Xinyu, Zhang Jun. The Optimization Research of Vehicle Routing Problem with Heterogeneous Fleet, Simultaneous Pickup-Delivery Considering Temporal-Spatial Distance[J]. Chinese Journal of Management, 2018, 15(6): 918-926.
23	李敏, 倪少权, 周凌, 等. 基于订单邻域的成品油二次配送中带时间窗车辆路径规划问题[J]. 计算机集成制造系统, 2015, 21(8): 2158-2169.
	Li Min, Ni Shaoquan, Zhou Ling, et al. Vehicle Routing Problem with Time Windows of Petroleum Products Distribution Based on Order Neighborhood System[J]. Computer Integrated Manufacturing Systems, 2015, 21(8): 2158-2169.
24	李桃迎, 吕晓宁, 李峰, 等. 考虑动态需求的外卖配送路径优化模型及算法[J]. 控制与决策, 2019, 34(2): 406-413.
	Li Taoying, Xiaoning Lü, Li Feng, et al. Routing Optimization Model and Algorithm for Takeout Distribution with Multiple Fuzzy Variables under Dynamics Demand[J]. Control and Decision, 2019, 34(2): 406-413.
25	Shaw P. Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems[C]//International Conference on Principles and Practice of Constraint Programming. Berlin, Heidelberg: Springer, 1998: 417-431.

订单编号	商家坐标	顾客坐标	下单时刻	预计送达时刻
1	(53.13， 62.12)	(61.27， 34.38)	11:00:06	11:30:06
2	(19.59， 84.97)	(98.40， 59.31)	11:01:54	11:31:54
3	(98.40， 59.31)	(21.67， 67.73)	11:02:00	11:32:00
4	(89.91， 77.57)	(96.21， 78.13)	11:02:30	11:32:30
5	(53.84， 9.41)	(46.35， 33.08)	11:03:42	11:33:42
6	(27.00， 48.18)	(8.75， 66.79)	11:04:00	11:34:00
7	(47.04， 29.28)	(20.67， 26.22)	11:04:18	11:34:18

算法策略	目标函数	超时比例Z₁/%	单均成本Z₂/元	单均时长Z₃/min	算法求解累计时间/s
1：随机+改进变邻域	0.26	8	5.75	22.66	45.34
2：聚类+模拟退火	0.32	12	5.83	24.43	17.52
3：聚类+改进变邻域	0.21	6	5.52	21.25	40.27

骑手编号	骑手聚类位置	已取餐未配送点	阶段分配订单	阶段配送路径
1	商家点1	1	11	1-(11)-11
2	商家点2	2	无	2
3	商家点3	3	4	3-(4)-4
4	商家点5	5	无	5
5	商家点6	6	无	6
6	商家点7	7	无	7
7	配送中心	无	无	无
8	配送中心	无	9， 12	(9)-9-(12)-12
9	配送中心	无	13	(13)-3-13
10	配送中心	无	8， 10	(8)-8-(10)-10

订单编号	商家坐标	顾客坐标	下单时刻	预计送达时刻
14	(95.54， 52.52)	(92.62， 33.44)	11:10:24	11:40:24
15	(75.68， 80.28)	(78.25， 94.20)	11:11:00	11:41:00
16	(21.03， 60.81)	(4.47， 78.76)	11:11:42	11:41:42
17	(16.69， 46.64)	(19.12， 37.84)	11:12:06	11:42:06
18	(34.04， 21.93)	(20.26， 34.82)	11:12:12	11:42:12
19	(37.94， 68.60)	(40.70， 73.49)	11:12:42	11:42:42
20	(55.88， 73.22)	(33.42， 71.93)	11:13:12	11:43:12
21	(12.86， 22.08)	(5.52， 2.62)	11:14:54	11:44:54
22	(71.88， 41.86)	(73.89， 31.94)	11:15:00	11:45:00

骑手编号	骑手聚类位置	已取餐未配送点	阶段分配订单	阶段配送路径
1	顾客点1	无	22	(22)-22
2	顾客点2	2	16	2-(16)-16
3	顾客点3	3	4， 15	3-(4)-4-(15)-15
4	顾客点5	无	11	(11)-11
5	顾客点6	无	17	(17)-17
6	顾客点7	无	18	(18)-18
7	配送中心	无	20， 19	(20)-(19)-20-19
8	商家点9	9	12	9-(12)-12
9	商家点13	13	14	13-(14)-14
10	商家点8	8	21， 10	8-(21)-(10)-21-10