摘要
提出了考虑多时间窗的多行程车辆路径优化问题,是带时间窗的多行程车辆路径问题的扩展,不仅决策每辆车服务客户的顺序,还需确定为每个客户提供服务的时间窗,同时要求送货服务时间满足选定的时间窗,且车辆每个行程服务的客户需求量之和不超过车辆的最大载重量等约束。以最小化车辆总行驶时间为目标构建了该问题的混合整数规划模型,并设计了迭代局部搜索算法进行求解。在迭代局部搜索算法框架下设计了适用于多时间窗和多行程场景的改进Solomon贪婪插入算法生成初始解,还设计了Or-opt和Relocate局部搜索算子以及随机交换扰动操作。基于初始解或当前最优解,通过交替使用这两种算子进行迭代搜索,更新当前最优解。算例结果表明了提出的模型和算法的有效性,验证了为客户提供多时间窗选项承运人可灵活地规划车辆路径和选择服务时间窗,从而减少车辆使用数量和总行驶时间。
In recent years,the rapid development of online retail has greatly increased the demand for"last mile"order delivery.However,large freight vehicles are usually kept off of city central roads by urban trans⁃portation authorities,so much so that carriers have to rely on vans to complete the"last mile"delivery.Hence,reasonable vehicle route planning can efficiently complete the delivery tasks,which is crucial to im⁃proving delivery efficiency and user experience.Therefore,the vehicle routing problem(VRP)has always been a hot topic in academia.Traditional VRPs assume that in each cycle,a vehicle can only perform one trip.Due to their limited capacity,vans could not accomplish much in a single trip,which,combined with limited fleet size,in order to improve vehicle utilization and reduce operating costs,necessitates us to allow the vans to"multi-trip"a distribution center.As a result,the VRP is extended into the multi-trip vehicle routing problem(MTVRP),which has higher practical value in the"last mile"delivery scenario.As a result,MTVRP and its variants have gradually attracted the attention of scholars in recent years.In order to meet the demand for large-scale distribution and increase the flexibility of vehicle route plan⁃ning,and avoid the excessive concentration of customer order within a single time window,we proposed a multi-trip vehicle routing problem with multiple time windows(MTVRPMTW),which is an extension of the multi-trip vehicle routing problem with time windows.It not only determines the order in which each vehicle serves the customers,but also determines the time window for providing such services.At the same time,it requires that the specific time windows for the delivery services be met,and also that the sum of the customer demand on each single trip not exceed the maximum load of the vehicle.Then we constructed a mixed integer programming model with the goal of minimizing the total driving time.In view of the com⁃plexity of the problem and the weakness of the optimization software CPLEX in
作者
宋慧心
吴影辉
SONG Huixin;WU Yinghui(School of Economics&Management,Jiangsu University of Science&Technology,Zhenjiang 212100,China)
出处
《物流技术》
2024年第4期34-46,共13页
Logistics Technology
基金
国家自然科学基金面上项目(72371119)。
关键词
多时间窗
多行程
车辆路径问题
混合整数规划
迭代局部搜索
multiple time windows
multi-trip
vehicle routing problem
mixed integer programming
it⁃erative local search
