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

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

作　　者：高志波[1] 龙科军[1] 王倩[2] 李峰[1] 

机构地区：[1]长沙理工大学交通运输工程学院,长沙410004 [2]中国民航大学空中交通管理学院,天津300300

出　　处：《中国科技论文》2017年第7期764-769,共6页China Sciencepaper

基　　金：国家自然科学基金资助项目(51678076)

摘　　要：针对目前大多数车辆路线问题的模型和及其算法都是针对单车型而设计,而对带有时间窗的多目标多车型车辆路线问题研究较少这一不足,在考虑了车辆载货状况、车辆类型、时间窗等约束条件的基础上,建立了基于总费用最小的双层目标规划模型,其中上层目标是车辆购买成本最小,下层目标为运输距离成本最小。综合考虑自适应遗传算法和模拟退火算法的优点,设计了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.

关 键 词：车辆路线问题 多车型 时间窗 遗传算法 模拟退火算法 遗传模拟退火算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]