基于动态订单合并的滚动配取路径多目标优化  

Multi-objective optimization of pickup and delivery routing based on dynamic order combination

作　　者：邵乾虔 李冲 代广徽 林鑫[2] SHAO Qianqian;LI Chong;DAI Guanghui;LIN Xin(School of Transportation and Geomatics Engineering,Shenyang Jianzhu University,Shenyang 110000,China;School of Management,Zhejiang University,Hangzhou 310058,China)

机构地区：[1]沈阳建筑大学交通与测绘工程学院,辽宁沈阳110000 [2]浙江大学管理学院,浙江杭州310058

出　　处：《管理工程学报》2024年第6期140-155,共16页Journal of Industrial Engineering and Engineering Management

基　　金：2022年度沈阳市社会科学课题(SYSK2022-01-138)。

摘　　要：外卖配取过程中实时订单的不断插入具有强烈的不确定性,需持续进行滚动优化以动态更新配取路径。动态条件下,有效地合并取餐与配送作业(dynamic order combination,DOC)可显著减少冗余路径。本文将动态配取路径规划问题转化为变长开放链滚动优化问题,并构建多目标滚动配取路径规划模型对DOC与节点排序进行集成决策。考虑滚动优化框架下紧前决策对紧后决策的调度影响,模型在兼顾配取效率和客户满意度的同时,考虑了基于look-forward的滚动调度后效性。针对该模型,本文基于NSGA-Ⅲ框架开发了多目标元启发式算法进行求解,并设计了基于插入限制规则的元胞数组解编码和混合PMX&SBX交叉方式以适应模型的复杂可行域结构。通过一系列的仿真实验,本文验证了所提出的模型和算法的有效性与优越性。In the Internet age,the number of takeout users has increased widely and rapidly.As an essential competitiveness of the Internet delivery platform,delivery efficiency and customer waiting time play a key role in improving customer satisfaction,and the optimization of the pickup and delivery routing has attracted more and more attention.The generation of orders is unpredictable from the micro-scheduling perspective,which leads to a strong dynamic process of pickup and delivery,requiring takeout staff to constantly adjust the routing in the pickup and delivery process to deal with new orders inserted in real-time.Under a series of realistic constraints(such as time window and rated load limit),it is challenging for the industry to perform robust scheduling of dynamic pickup and delivery routing considering customer satisfaction and delivery efficiency.Solving this problem is crucial for improving the service level of the Internet takeout platform.The current research on Internet takeout pickup and delivery routing planning focuses on three hotspots.The first is how to deal with the dynamic nature of order insertion to optimize the routing in real-time;The second is to study the order combination strategy in routing planning;The third is how to consider the interests of riders(improving pickup and delivery efficiency)and customers(reducing the waiting time)in the operation process through the multi-objective optimization.For the first point,the current research only considers the optimal strategy under the current order conditions without considering its impact on the subsequent rolling scheduling.For the second point,the existing research only optimized the combination pickup under the single customer service mode(one customer for multiple businesses)or bundled the orders for delivery from the same business perspective.They have not optimized the order combination operations(combination pickup and delivery)at the micro perspective under the complex mapping conditions of multi-customers and multi-business.Given the

关 键 词：配取路径 开放链 订单合并 滚动调度后效性 NSGA-Ⅲ 

分 类 号：U116.2[交通运输工程] C93[经济管理—管理学]