带时间窗车辆路径问题的差分进化混合算法

摘要

研究了带时间窗的车辆路径问题(Vehicle Routing Problem with Time Windows,VRPTW),建立了数学模型,并设计了求解VRPTW的离散差分进化混合算法.算法采用随机车辆配载方法构造初始解,并通过构造新的变异和交叉算子进行改进.进一步,利用插入可行邻域和2-Opt可行邻域两种搜索可行解的邻域结构,引入禁忌搜索进一步进行局部搜索以提高算法的寻优能力.实验结果表明该算法是求解VRPTW的一种有效方法.%The Vehicle Routing Problem with Time Windows(VRPTW) is addressed in this paper.A mathematical model is built and a discrete differential evolution hybrid algorithm for VRPTW is designed.In the algorithm, the population is initialized by a random vehicle loading method,and improved by new discrete mutation and crossover operators.Moreover,the tabu search is introduced to enhance the local searching capability of the algorithm, in which insertion and 2-Opt feasible neighborhoods are used to search feasible solutions.Experimental results show the effectiveness of the proposed approach for the VRPTW.