带时间窗车辆路径问题的多目标文化基因算法

Multi-objective memetic algorithm for vehicle routing problem with time windows

针对物流配送中带时间窗的车辆路径问题,以最小化车辆使用数和行驶距离为目标,建立了多目标数学模型,提出了一种求解该问题的多目标文化基因算法。种群搜索采用遗传算法的进化模式和Pareto排序的选择方式,局部搜索采用禁忌搜索机制和存储池的结构,协调两者得到的Pareto非占优解的关系。与不带局部搜索的多目标遗传算法和单目标文化基因算法的对比实验表明,本文算法的求解质量较高。

The Vehicle Routing Problem with Time Windows （VRPTW） is addressed in the paper. A multi-objective mathematic model is designed with goals of minimizing the vehicle number and the travel distance. A memetic algorithm is proposed, targeting this problem. The pattern of population search is genetic algorithm and Pareto ranking selection, while the local search uses tabu and solution pool to coordinate Pareto non-dominated solutions obtained by the two searches. Compared with the multi-objective genetic algorithm without the local search and the single-objective memetic algorithm, experimental results show the effectiveness of the proposed algorithm.