肖自乾，陈经优

(海南软件职业技术学院 软件工程系，海南 琼海 571400)

基于改进遗传算法的动态路径优化研究

肖自乾，陈经优

(海南软件职业技术学院 软件工程系，海南 琼海 571400)

日常出行中，由于道路养护、天气变化等原因，导致部分路段交通受阻甚至禁止通行，这种情况下需要避开此路段。在基于改进遗传算法查找最优路径的基础上，对如何根据路况变化动态寻找更为合适的最优路径进行了探讨。

遗传算法；动态优化；路权

1 最优路径主要影响因素

本文探讨的最优路径主要影响因素包括道路是否畅通和道路通行缓慢两方面[1]。最优路径定义不同意义也不同，路权的标定方法有5种：①将车辆行驶距离作为优化目标；②将行驶时间作为优化目标；③将行驶费用作为优化目标；④将是否选择高速路、减少费用等作为优化目标；⑤将实际交通情况如拥挤程度作为优化目标。本文主要将行驶路径作为优化目标，在此基础上考虑实际交通状况，将这些因素转换后纳入路权进行路径分析。

(1)道路是否畅通。在静态路网模型中，可以直观地将路段长度作为最优路径的判断依据,只需将其转换为经典的TSP问题即可求解。而实际情况中，往往一些道路因为维修或天气原因导致无法通行，在最优路径的搜索中应避开这样的路段，寻找其它最优路径。

(2)通行时间。如果通行时间非常缓慢，则考虑搜索其它更优路径。

2 改进遗传算法基本思想

改进遗传算法相比传统遗传算法具有收敛快、较好的全局最优搜索能力等特点。……