多车场带时间窗车辆路径问题的改良自适应大邻域搜索算法

Improved adaptive large neighborhood search algorithm for multi-depot vehicle routing problem with time window

针对多车场带时间窗车辆路径问题(MDVRPTW),提出一种改良自适应大邻域搜索算法(IALNS)。首先,在构造初始解阶段改进一种路径分割算法;其次,在优化阶段利用设计的移除和修复启发式算子相互竞争择优选取算子,为各算子引入评分机制,采用轮盘赌方式选取启发式算子;同时,将迭代周期分段,动态调整各周期内的算子权重信息,有效避免算法陷入局部最优;最后,采取模拟退火机制作为解的接受准则。在Cordeau规范算例上进行实验,确定IALNS的相关参数,将所提算法求解结果与该领域其他代表性研究成果对比。实验结果表明,所提算法与变邻域搜索(VNS)算法的求解误差不超过0.8%,在某些算例上甚至更优;与多相位改进的蛙跳算法相比,算法的平均耗时减少12.8%,所提算法在绝大多数算例上运行时间更短。因此,验证了所提算法是求解MDVRPTW的有效算法。

Aiming at the Multi-Depot Vehicle Routing Problem with Time Window(MDVRPTW),an Improved Adaptive Large Neighborhood Search algorithm(IALNS)was proposed.Firstly,a path segmentation algorithm was improved in the stage of constructing the initial solution.Then,in the optimization stage,the designed removal and repair heuristic operators were used to compete with each other to select the optimal operator,a scoring mechanism was introduced for the operators,and the heuristic operator was selected by roulette.At the same time,the iteration cycle was segmented and the operator weight information was dynamically adjusted in each cycle,effectively to prevent the algorithm from falling into local optimum.Finally,simulated annealing mechanism was adopted as the acceptance criterion of the solution.The relevant parameters of the IALNS were determined by experiments on the Cordeau normative instances,and the solution results of the proposed algorithm were compared with other representative research results in this field.The experimental results show that the solution error between IALNS and Variable Neighborhood Search(VNS)algorithm does not exceed 0.8%,even better in some cases;compared with the multi-phase improved shuffled frog leaping algorithm,the average time-consuming of the proposed algorithm is reduced by 12.8%,and the runtime is shorter for most instances.So the above results verify IALNS is an effective algorithm for solving MDVRPTW.