摘要
给出了有时间窗车辆路径问题的通用数学模型 ,该模型不仅能够满足大多数实际问题的需要 ,而且通过对特定参数的设定 ,还能够转换成其他几种典型的组合优化问题的数学模型。通过引入新颖交叉算子 ,构造了一种改进遗传算法。该算法摆脱了对群体多样性的要求 ,不存在传统遗传算法常见的“早熟收敛”问题。该算法已用于解决有时间窗的车辆路径问题 ,实验结果表明 ,它可以有效地求得有时间窗车辆路径问题的优化解 ,是求解车辆路径问题的一个较好方案。
We state a universal mathematical model of vehicle routing problem with time windows,which can satisfy numerous practical requirements and transform into other typical combination optimal problems by setting different parameters.An improved genetic algorithm (IGA) is proposed based on the novel crossover operator.IGA avoids effectively the common defects of early convergence and the diversity of population in traditional genetic algorithm.This algorithm can find the optimal or nearly optimal solution to the vehicle routing problem with time windows effectively,which is proved bya number of experiments.
关键词
时间窗
车辆路径问题
数学模型
遗传算法
交叉算子
群体多样性
mathematical model
genetic algorithm
vehicle routing problem with time windows
crossover operator
population diversity
early convergence
