大规模邻域搜索算法求解时变车辆调度问题

摘要

对时变网络车辆调度问题提出一种满足先入先出准则的时变处理方法,并建立相应的数学模型,提出一种基于大规模邻域搜索技术的智能优化算法进行求解,算法顶层采用动态规划算法搜索环状交换邻域以得到每辆车的最佳服务顾客集合；底层设计动态搜索算法用以安排每辆车的最佳服务路线.在此基础上提出顶层加入虚拟顾客和底层嵌入insert两类改进策略.通过实验仿真比较,验证了所提算法的有效性.%Time dependent vehicle routing problem was formulated by dealing with time periods crossing with first-in first-out property, and a novel intelligent optimization algorithm based on very large scale neighborhood search technology was developed to solve it. In the upper level dynamic programming algorithm was adopted to search cycle transfer neighborhood so as to obtain the optimal customer set for each vehicle, while in the lower level dynasearch heuristics was developed to rank the customers in each vehicle. Based on this, two improvements were given: adding dummy customer in the upper level and embedding insert in the lower level. The efficiency of the method are testified with the results of extensive computational tests.