车辆路径问题的改进遗传算法研究

Study on vehicle routing problem by improved genetic algorithm

车辆路径问题(VRP)是现代物流管理中的重要环节,是一个NP-hard问题。标准遗传算法用于最优化问题时存在早熟收敛和收敛速度缓慢的特点。本文提出一种改进的多种群遗传算法,在子种群间引入竞争,设定各个子种群的规模取决于各个子种群的平均适应水平。实验结果表明,该算法能有效求得车辆路径问题的优化解,是求解车辆路径问题的一个有效方案。

Vehicle routing problem, a NP-hard problem, is an important link of modem logistic management. Canonical genetic algorithms have the defects of pre-maturity and stagnation when applied in optimizing problems. In this paper, an improved multi-population genetic algorithm is proposed. The scales of sub-populations lie on average adoption values. It is proved by a number of experiments that this algorithm can find effectively the optimal or nearly optimal solution to the vehicle routing problem.