关键词: 带时间窗车辆路径问题,多目标,差分进化算法,双种群,变邻域下降搜索

Abstract: Aiming at the vehicle routing problem with time windows,a multi-objective mathematical model was built with goals of minimizing the vehicle number and the travel distance,and it was solved by a hybrid differential evolution algorithm which is based on Pareto-dominance,combined with improved differential evolution algorithm and variable neighborhood descent.First,redefined method to produce new individual was employed.Then,the global exploration and the local exploitation were balanced by combining the dual populations strategy and variable neighborhood descent technology,and the diversity of the population was maintained through the method which uses the random individuals to replace the repetition individuals.Third,Pareto-dominance was applied to compare different solutions,and Arena’s principle was adopted to construct non-dominated solution set.Finally computational results on the 18 Solomon problems with the different sizes show that the solution quality of the proposed algorithm averagely increases 2.04% and 14.95% than artificial bee colony algorithm in the travel distance and the vehicle number,and averagely increases 14.53% than the best known solutions in the vehicle number,verifying the effectiveness of the proposed algorithm.

Key words: Vehicle routing problem with time windows,Multi-objective,Differential evolution algorithm,Dual populations,Variable neighborhood descent