基于多目标遗传算法求解时间窗车辆路径问题

Multi-Objective Genetic Algorithm for Vehicle Routing Problem with Time Windows

有别于传统的单目标方法,将带时间窗约束的车辆路径问题描述成为一个多目标最优化问题,并为之提出了一种多目标遗传算法。在算法中设计了擂台法则作为构造非支配集的方法,提出了可变爬山率的局部爬山法,并通过将组合种群分成多层非支配集来实现精英保留策略。实验结果表明,该算法能有效地求解车辆路径问题并且为决策者提供了强有力的决策支持。

Unlike traditional single objective method,Vehicle Routing Problem with Time Windows（VRPTW） is represented as a multi-objective optimization problem.This paper presents a multi-objective genetic algorithm to solve VRPTW, Arena＇s principle is designed to construct non-dominated set and a hill-climbing method with alterable probability is proposed too.In order to keep elitism,the combined population is divided into multiple layers.The experimental results indicate that this algorithm is quite effective for VRPTW and provides powerful decision support to the decision-maker.