Operations Research Transactions >
2022 , Vol. 26 >Issue 3: 17 - 30
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2022.03.002
Optimization model and algorithm for Online to Offline dynamic take-out delivery routing problem centered on business districts
Received date: 2022-01-31
Online published: 2022-09-07
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.
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 . DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.002
| 1 | 颜贤斌. 浅谈中国餐饮外卖O2O模式的现状与发展[J]. 商场现代化, 2015, (22): 45- 46. |
| 2 | 刘云忠, 宣慧玉. 车辆路径问题的模型及算法研究综述[J]. 管理工程学报, 2005, 19 (1): 124- 130. |
| 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. |
| 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. |
/
| 〈 |
|
〉 |