以商圈为中心的O2O动态外卖配送路径优化模型与算法

doi:10.15960/j.cnki.issn.1007-6093.2022.03.002

Abstract

Abstract:

In the take-out food industry, improper path planning by couriers often leads to low delivery efficiency. Most of the existing VRP research focuses on the optimization of express delivery and other industries, and there is a lack of optimization algorithm research for the food delivery with real-time characteristics. Aiming at the Online to Offline (O2O) take-out delivery routing optimization problem, this paper takes a comprehensive consideration of its dynamic delivery requirements, cargo differentiation and other characteristics as well as constraints such as time windows and cargo capacities, and establishes an O2O dynamic route optimization model of the take-out delivery personnel, in which the business districts are regarded as a delivery centre, and the number of delivery personnel and the total travel time by the delivery personnel are taken as the minimization targets. Using the method of periodically processing new orders, the resultant dynamic adjustment problem of the delivery personnel's route is converted into a series of static TSP sub-problems and thereby a phased heuristic real-time delivery routing optimization algorithm framework is designed, and a concrete algorithm and a numerical example are given. A set of test cases centered on business districts is generated on the basis of a number of widely used VRP instances, the algorithm is tested through simulation experiment and compared with other algorithms. The results show that the algorithm proposed in this paper can make full use of the delivery personnel near the location of the new orders to conduct the delivery, optimize the corresponding delivery route, and effectively reduce the number of delivery personnel for delivery and the total travel time by the delivery personnel.

Key words: NP-hard problem, vehicle routing problem, genetic algorithm, KNN classification algorithm, dynamic delivery demand, business district

CLC Number:

TP301.6

Chenghao ZHOU, Boxuan LYU, Hanyu ZHOU, Haiyan LU. Optimization model and algorithm for Online to Offline dynamic take-out delivery routing problem centered on business districts[J]. Operations Research Transactions, 2022, 26(3): 17-30.

Figures/Tables 12

References 19

1	颜贤斌. 浅谈中国餐饮外卖O2O模式的现状与发展[J]. 商场现代化, 2015, (22): 45- 46. doi: 10.3969/j.issn.1006-3102.2015.22.026
2	刘云忠, 宣慧玉. 车辆路径问题的模型及算法研究综述[J]. 管理工程学报, 2005, 19 (1): 124- 130. doi: 10.3969/j.issn.1004-6062.2005.01.027
3	郎茂祥. 动态车辆配送优化调度问题的两阶段算法[J]. 交通运输系统工程与信息, 2009, 9 (4): 140- 144.
4	宁涛, 陈荣, 郭晨, 等. 一种基于双链量子编码的动态车辆路径问题解决策略[J]. 运筹学学报, 2015, 19 (2): 72- 82.
5	Pureza V , Laporte G . Waiting and buffering strategies for the dynamic pickup and delivery problem with time windows[J]. INFOR: Information Systems and Operational Research, 2008, 46 (3): 165- 176. doi: 10.3138/infor.46.3.165
6	张景玲, 王万良, 赵燕伟. 基于沿途补货的多配送中心动态需求VRP建模及优化[J]. 计算机集成制造系统, 2013, 19 (4): 869- 878.
7	Chen S , Chen R , Gao J . A modified harmony search algorithm for solving the dynamic vehicle routing problem with time windows[J]. Scientific Programming, 2017,
8	杨善林, 马华伟, 顾铁军. 时变条件下带时间窗车辆调度问题的模拟退火算法[J]. 运筹学学报, 2010, 14 (3): 83- 90.
9	李桃迎, 吕晓宁, 李峰, 等. 考虑动态需求的外卖配送路径优化模型及算法[J]. 控制与决策, 2019, 34 (2): 406- 413.
10	靳志宏, 鞠新诚, 郭加佳, 等. O2O模式下外卖骑手的的配送路径优化[J]. 大连海事大学学报, 2019, 45 (4): 55- 64.
11	王帅, 赵来军, 胡青蜜. 随机旅行时间的外卖O2O配送车辆路径问题[J]. 物流科技, 2017, 40 (1): 93- 101.
12	曾庆成, 马佳慧, 张晓琳. 混合下单模式下在线餐饮订单配送优化模型[J]. 交通运输系统工程与信息, 2019, 19 (6): 184- 190.
13	洪涛. 现代商圈及其动态发展—兼论北京南城商圈及其定位[J]. 商业时代, 2002, (23): 10- 12.
14	葛继科, 邱玉辉, 吴春明, 等. 遗传算法研究综述[J]. 计算机应用研究, 2008, 25 (10): 2911- 2916.
15	陆子强, 郭国雄, 蒋金山. 基于邻域搜索的混合遗传算法及其在对称TSP中的应用[J]. 计算机工程与应用, 2005, 41 (7): 79- 81.
16	Paul S. Using constraint programming and local search methods to solve vehicle routing problems[C]//Fourth International Conference on Principles and Practice of Constraint Programming, 2003: 417-431.
17	Guo G, Wang H, Bell D, et al. KNN model-based approach in classification[C]//OTM Confederated International Conferences "On the Move to Meaningful Internet Systems", 2003: 986-996.
18	The VRP Web[EB/OL]. [2022-01-31]. http://www.bernabe.dorronsoro.es/vrp/.
19	Ausiello G , Feuerstein E , Leonardi S , et al. Algorithms for the on-line travelling salesman[J]. Algorithmica, 2001, 29 (4): 560- 581.

符号	含义
$ i, j $	节点编号
$ k $	快递员编号
$ p $	优化轮次
$ m $	总快递员个数
$ L_{i} $	客户点$ i $的订单量
$ EET_{i} $	节点$ i $的最早到达时间
$ ELT_{i} $	节点$ i $的最晚到达时间
$ r_{ij} $	客户点$ i $是否需要商家点$ j $的货物
$ t^{kp}_{j} $	第$ p $轮优化中快递员到达节点时的时间
$ l^{kp}_{j} $	第$ p $轮优化中快递员$ k $到达节点时的载货量
$ c_{ij} $	快递员从节点$ i $到节点$ j $的行驶时间
$ x^{kp}_{j} $	第$ p $轮优化中快递员$ k $的路径中是否有从节点$ i $前往节点$ j $
$ y^{kp}_{i} $	第$ p $轮优化中快递员$ k $是否经过节点$ i $
$ z^{p}_{i} $	第$ p $轮优化中，节点$ i $是否在当前需要前往的节点集合中
$ h^{kp}_{ij} $	第$ p+1 $次优化之前，快递员$ k $是否经过$ i $到$ j $

参数	商家覆盖半径	最大载货量/kg	总行驶时间权重	快递员个数权重
取值	50	150	1	20

订单编号	客户点坐标	出现时间/min	时间窗/min	订单需求量/kg	所属商家点
1	$ (-37, 66) $	11	[318, 323]	17	3
2	$ (-71, 27) $	13	[317, 331]	16	3
3	(37, 23)	12	[162, 169]	6	2
4	(45, 59)	3	[401, 405]	22	2
5	$ (-37, 42) $	23	[248, 258]	9	3
6	$ (-81, 98) $	18	[279, 303]	3	3
7	$ (-68, -24) $	17	[82, 85]	12	4
8	$ (-45, 75) $	12	[356, 379]	2	3

快递员编号	起始商家点	时间成本
快递员编号	起始商家点	初始时间成本	分配新订单	最终时间成本
3	1	160	5	173
4	1	91	3	94
6	2	102	4	183
8	3	194	2、6、8	288
11	3	141	1	161
13	4	185	7	179

测试实例	节点数	指标	快递员数量	时间成本	总成本
Pr01	48	Mean	16.6	2 535	2 874
		Best	16	2 411	2 620
		Std	1.06	115	122
Pr02	48	Mean	14.1	2 567	2 844
		Best	14	2 328	2 608
		Std	0.67	26	52
Pr03	144	Mean	31	4 411	5 031
		Best	29	4 399	4 979
		Std	1.17	55	64
Pr04	192	Mean	45	6 076	6 976
		Best	41	5 885	6 705
		Std	1.71	87	95
Pr05	204	Mean	73.5	9 402	10 872
		Best	72	9 325	10 765
		Std	4.04	144	103
Pr06	288	Mean	66	8 765	10 085
		Best	65	8 725	10 025
		Std	1.41	14	93
Pr14	192	Mean	41.5	5 556	6 386
		Best	40	5 444	6 244
		Std	1.57	79	91
Pr15	240	Mean	64.6	8 010	9 302
		Best	62	7 776	9 016
		Std	1.4 654	153	153

Optimization model and algorithm for Online to Offline dynamic take-out delivery routing problem centered on business districts

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 19

Related Articles 4

Recommended Articles

Metrics

Comments

测试实例	本文算法			本文算法(无大规模邻域搜索)			对照算法			对照算法算法(无大规模邻域搜索)			优化率/%
测试实例	快递员	时间	总成本	快递员	时间	总成本	快递员	距离	总成本	快递员	时间	总成本	优化率/%
pr01	16	2 170	2 490	25	2 758	3 258	20	2 487	2 887	29	2 804	3 384	13.8
pr02	14	2 282	2 562	25	3 270	3 770	18	2 756	3 116	18	3 230	3 590	17.7
pr03	29	4 006	4 586	58	7 148	8 308	34	4 617	5 297	34	4 616	5 296	13.4
pr04	41	5 179	5 999	67	10 446	11 786	47	6 086	7 026	47	11 352	12 292	14.6
pr05	72	8 650	10 090	98	23 461	25 421	75	9 161	10 660	76	6 090	7 610	5.3
pr06	65	8 084	9 384	100	25 524	27 524	71	8 990	10 410	71	9 490	10 910	9.8
Pr14	40	5 007	5 807	64	9 703	10 983	45	5 736	6 636	45	5 735	6 635	12.4
Pr15	62	7 273	8 513	97	18 121	20 061	69	7 776	9 156	69	7 976	9 356	7

[1]	GUO Xiaoling, ZHUANG Yuanxin, LIU Yifan. Research on the quadratic programming model and solution algorithm of critical nodes in metro network [J]. Operations Research Transactions, 2020, 24(4): 51-62.
[2]	NING Tao, CHEN Rong, GUO Chen, LIANG Xu. A scheduling strategy for dynamic vehicle routing problem based on double chains coding [J]. Operations Research Transactions, 2015, 19(2): 72-82.
[3]	JIANG Jianlin, LI Xue, ASSANI Saeed, WU Pu, WANG Cancan. An extended p-median problem with investment constraint and uncertain p [J]. Operations Research Transactions, 2013, 17(4): 69-79.
[4]	WANG Hong, LIN Dan, LI Min-Qiang. Genetic Algorithm for Aircraft Landing Problem with Predetermined Time Window and Earliness/Tardiness Penalties [J]. Operations Research Transactions, 2012, 16(1): 67-76.