关键词: 车辆路径问题；动态需求；周期性优化策略；人工蜂群算法；变邻域搜索算法

Abstract: 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.

Key words: vehicle routing problem; dynamic requests; periodic optimization strategy; artificial bee colony algorithm; variable neighborhood search algorithm