运筹学学报 ›› 2022, Vol. 26 ›› Issue (3): 17-30.doi: 10.15960/j.cnki.issn.1007-6093.2022.03.002

• • 上一篇    下一篇

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

周成昊1, 吕博轩1, 周翰宇1, 鲁海燕1,2,*()   

  1. 1. 江南大学理学院, 江苏无锡 214122
    2. 无锡市生物计算工程技术研究中心, 江苏无锡 214122
  • 收稿日期:2022-01-31 出版日期:2022-09-15 发布日期:2022-09-07
  • 通讯作者: 鲁海燕 E-mail:luhaiyan@jiangnan.edu.cn
  • 作者简介:周翰宇, E-mail: luhaiyan@jiangnan.edu.cn
  • 基金资助:
    国家自然科学基金(61772013);江苏省大学生创新创业训练项目(202010295136Y)

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

Chenghao ZHOU1, Boxuan LYU1, Hanyu ZHOU1, Haiyan LU1,2,*()   

  1. 1. School of Science, Jiangnan University, Wuxi 214122, Jiangsu, China
    2. Wuxi Engineering Technology Research Center for Biocomputing, Wuxi 214122, Jiangsu, China
  • Received:2022-01-31 Online:2022-09-15 Published:2022-09-07
  • Contact: Haiyan LU E-mail:luhaiyan@jiangnan.edu.cn

摘要:

针对线上到线下(Online to Offline,O2O) 外卖路径优化问题,综合考虑其动态配送需求、货物区分等特点以及时间窗、载货量等约束条件,将商圈看作配送中心,将快递员数量与快递员总行驶时间作为最小化目标,提出了以商圈为中心的O2O动态外卖配送路径优化模型。采用周期性处理新订单的方法将相应的快递员路径的动态调整问题转化为一系列静态TSP子问题,设计了一种分阶段启发式实时配送路径优化算法框架,并给出了一个具体算法和一个数值计算实例。在VRP通用算例的基础上,以商圈为中心生成测试算例,对本文算法进行仿真实验,并与其他算法比较。结果表明:本文算法能充分利用新订单附近的快递员进行配送,并优化其配送路径,有效减少了快递员数量与快递员总行驶时间。

关键词: NP-难问题, 车辆路径问题, 遗传算法, KNN分类算法, 动态配送需求, 商圈

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

中图分类号: