车辆路线问题的自适应遗传模拟退火算法

A self-adaptive genetically simulated annealing algorithm of vehicle routing problem

针对目前大多数车辆路线问题的模型和及其算法都是针对单车型而设计,而对带有时间窗的多目标多车型车辆路线问题研究较少这一不足,在考虑了车辆载货状况、车辆类型、时间窗等约束条件的基础上,建立了基于总费用最小的双层目标规划模型,其中上层目标是车辆购买成本最小,下层目标为运输距离成本最小。综合考虑自适应遗传算法和模拟退火算法的优点,设计了1种自适应遗传模拟退火算法求解车辆路线问题。算例结果表明:相比于标准遗传算法,自适应遗传模拟退火算法减少了9%的运输成本,能跳出局部收敛获得最优解,从而提供更为合理的车辆数量和车辆路线。

Nowadays, many models and algorithms of vehicle routing problem （VSP） were designed for single-type vehicle instead of multi-objective and multi-type vehicle with time window. A bi-level objective programming model based on the minimum total cost was developed under the vehicle loading condition and constraints of vehicle type and the time window. Among them, the minimum vehicle purchase cost was taken as the upper-level model while the minimum the transport distance costs as the lower- level one. Considering the advantages of genetic algorithm and simulated annealing algorithm, the algorithm can significantly im-prove the global and local search ability, a self-adaptive genetically simulated annealing algorithm was designed to solve the vehicle routing problem. The example showed that was compared with standard genetic algorithm, the self-adaptive genetically simulated annealing algorithm can reduce the transportation cost by 9% and jump out of local convergence to obtain the optimal solution, which provides a more reasonable number of vehicles and vehicle routing.