动态需求下车辆路径问题的周期性优化模型及求解

A Periodic Optimization Model and Solution for Capacitated Vehicle Routing Problem with Dynamic Requests

针对客户点不断更新的动态需求车辆路径问题,依据滚动时域对配送中心工作时间进行划分,提出基于延迟服务的周期性客户点实时重置策略,策略中延迟服务机制能结合车辆启动延迟系数对照当前时域的时间进行检验,满足所有客户点的服务需求,保证车辆满足中心时间窗约束。设计多阶段求解的混合变邻域人工蜂群算法对各时间片内子问题进行连续迭代优化,算法中子路径动态转变的设计能较好平衡原有客户点和新客户点对路径更新和车辆实时信息匹配的要求。算例验证及对比分析表明本文策略和算法在求解动态问题时的有效性和可行性。

Capacitated vehicle routing problem with dynamic requests(CVRPDR) is one important variant of vehicle routing problem(VRP), in which not all customers are known in advance, but are revealed as the system progresses. In CVRPDR, routes must be reconfigured dynamically while executing the current simulation. Considering the dynamic characteristic of customers information, a real-time rescheduling strategy which based on the idea of periodic optimization is presented to solve dynamic optimization problems. And according to receding horizon control the whole working time of distribution center is divided into time slices, then CVRPDR can realize periodic optimization for sub-problem of each time slice. In addition, the service delay mechanism based on vehicle starting delay coefficient is applied to constrain behaviors of vehicle distribution. By means of service delay mechanism, additional original customers and new dynamic customers can be utilized to implement rescheduling of sub paths when vehicle capacity and time constraints are satisfied. In this paper, CVRPDR is solved while using a metaheuristic algorithm based on variable neighborhood search and artificial bee colony algorithm that tries to increase both diversity and the capability to escape from local optima. And information such as optimal routing scheme and customer node status will be transmitted along time slices. The effect of vehicle starting delay coefficient perturbation upon the system is discussed by means of sensitivity analysis. The effectiveness of our approach is demonstrated by comparing its results with those of existing methods in the literature on a popular set of benchmark instances. The proposed algorithm can efficiently optimize the dynamic problems and provide highly competitive solution on both the best and average results.