不确定车辆数的有时间窗车辆选径问题的混合算法

Hybrid algorithm for variable fleet vehicle routing problem with time window

针对标准遗传算法在求解车辆选径问题中出现的早熟、收敛、易陷入局部极值点的问题,提出了一种由遗传算法结合模拟退火算法的混合算法求解车辆选径问题,并与遗传算法进行了比较。该算法利用了模拟退火算法具有的较强的局部搜索能力的特性,有效地克服了传统遗传算法的“早熟收敛”问题。实验结果表明,该算法具有计算效率高、收敛速度快和求解质量优的特点,是解决车辆选径问题的有效方法。

The standard Genetic Algorithm was applied into Vehicle Routing Problem, and it was the common defects of early convergence and easily falling into local minimization. According to it, a new stochastic approach called the genetic simulated annealing algorithm （GSAG） was proposed to solve vehicle routing problems and the solution wass then compared with that from simulated algorithm. Making full of preventing into local minimization in simulated annealing, GSAG avoided effectively the common defects of early convergence. Results from case studies show that the proposed algorithm has better convergence property and find the optimal or near-optimal solution effectively as well as time and quickly convergence property. So, it is an efficient method for vehicle routing problem.