允许取送交叉和中途接单的外卖配送路径优化

The Optimization of Takeout Delivery Route that Allows Cross Picking and Delivery and Order Halfway

现有关于外卖配送路径优化的研究中,大多数采用的路径生成方式是商家节点和顾客节点根据订单号成对插入。而在实际配送中,取送交叉的配送方式最为常用。目前暂无研究考虑外卖配送中骑手中途接单后的配送路径优化。因此,本文针对取送交叉和中途接单对外卖配送路径优化问题深入研究。首先,以时间惩罚成本和运输成本作为目标函数,将相同商家不同顾客和相同顾客不同商家的订单进行拆分,并考虑了骑手载重约束、时间窗约束、中途接单后的路径变化约束和其他可行性约束,建立了数学模型;其次,针对允许取送交叉的配送方式,设计了考虑订单有序性的初始种群生成方式、随机比对交叉方式和基于订单号的变异方式;针对骑手中途接单这一扰动因素,将骑手分为有已取餐未送餐的订单和没有已取餐未送餐的订单两种情况,分别设计了单点交叉和按照订单号交叉两种方式,以及单点变异和按照订单号变异两种变异方式。最后,通过算例分析进一步验证了模型和算法的有效性。本文可为外卖平台提供重要参考。

The objective function setting of the existing route optimization problem of takeout is incomplete, for rider pick-up and halfway ordering are not considered. Firstly, by splitting the takeaway orders of different customers of the same merchant and different merchants of the same customer, a takeaway delivery route model with time penalty cost and transportation cost minimized is established. Secondly, for the delivery methods that allow pickup and delivery crossover, the ordered initial population generation method, the random comparison crossover method, and the variation method based on order number are designed;for the case of rider intermediate pickup, the rider intermediate pickup is divided into two cases: orders that have been picked up but not delivered and orders that have not been picked up but not delivered, and two crossover methods, single-point crossover and crossover based on the order number, and two variation methods, single-point variation, and variation based on the order number, are designed respectively. Finally, the example analysis verifies the validity of the model and algorithm. This paper can provide an important reference for takeout platforms.