Vehicle routing optimization algorithm based on time windows and dynamic demand

基于时间窗和动态需求的车辆路径优化算法

To provide the supplier with the minimizum vehicle travel distance in the distribution process of goods in three situations of new customer demand,customer cancellation service,and change of customer delivery address,based on the ideas of pre-optimization and real-time optimization,a two-stage planning model of dynamic demand based vehicle routing problem with time windows was established.At the pre-optimization stage,an improved genetic algorithm was used to obtain the pre-optimized distribution route,a large-scale neighborhood search method was integrated into the mutation operation to improve the local optimization performance of the genetic algorithm,and a variety of operators were introduced to expand the search space of neighborhood solutions;At the real-time optimization stage,a periodic optimization strategy was adopted to transform a complex dynamic problem into several static problems,and four neighborhood search operators were used to quickly adjust the route.Two different scale examples were designed for experiments.It is proved that the algorithm can plan the better route,and adjust the distribution route in time under the real-time constraints.Therefore,the proposed algorithm can provide theoretical guidance for suppliers to solve the dynamic demand based vehicle routing problem.

为了满足供应商在货物配送过程中,面对新增客户需求、客户取消需求和客户改变收货地址三种信息更新的情况,能够实现最小化车辆行驶距离的目标,结合预优化与实时优化的思想,建立了带时间窗约束的动态需求车辆路径问题的两阶段规划模型。在预优化阶段,采用改进的遗传算法获得预优化配送路径,在变异操作中融合大规模邻域搜索方法提升遗传算法的局部寻优能力,并引入多种操作算子扩大邻域解的搜索空间。在实时优化阶段,采用周期性优化策略,将复杂的动态问题转化为若干个静态问题,采用四种邻域搜索算子实现路径快速调整。设计了两种不同规模的算例进行实验,证明了该算法能够规划出较优路径,且在满足实时性约束下,能及时调整配送路线。该方法为供应商解决动态需求下的车辆路径问题提供了理论指导。