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

时间：2024-05-04

肖自乾，陈经优

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

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

肖自乾，陈经优

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

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

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

1 最优路径主要影响因素

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

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

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

2 改进遗传算法基本思想

改进遗传算法相比传统遗传算法具有收敛快、较好的全局最优搜索能力等特点。最优路径搜索以经典TSP问题作为研究模型，其主要实现思想是：①将遗传过程分阶段进行，设定相应的交叉、变异参数，后阶段进行自适应参数设定；②在后期先将种群中所有个体进行适应度排序，计算适应度平均值；再根据个体适应度与平均值的关系执行自适应参数的交叉和变异操作，即在交叉操作中，比较适应度值fc：当fc|favg时，执行固定的交叉概率k1；当fc>favg时，执行自适应的交叉概率。在变异操作中，选取两个个体，找出较大适应度值fm，当fm|favg时，执行固定的变异概率k4；当fm>favg时，执行自适应变异概率，同时引入精英保留策略来保留优良个体[2-3]。

对普通遗传算法(Rank)和改进的自适应遗传算法进行仿真比较，发现传统的遗传算法存在求解速度较慢问题，子代适应度低于父代适应度的情况也时有出现，而改进的自适应遗传算法寻优速度较快，能得到较为理想的结果，具有较好的收敛性[2]，如图1所示。

图1 两种算法路径寻优过程曲线

3 路径动态优化探讨

首先随机模拟出20个坐标点(模拟地点)，其坐标如图2所示。

图2 初始化模拟地点

基于改进遗传算法的最优路径优化搜索结果如图3所示。

图3 最优路径搜索结果(长度3537.2014)

路径搜索结果为：

1→7→6→4→11→14→18→8→12→17→16→5→20→13→9→3→10→19→15→2→1

3.1 路径连通情况

实际交通环境中，一些路段往往因为道路养护、天气等原因暂时不能通行，此时要另外寻找合适路径。为验证算法，根据设定条件进行动态路径优化。首先假设任意点之间都是连通的，且不考虑方向因素，据此构造各点相互连接情况如图4所示。

其中，数字1表示两点可通行，数字0表示不能通行。由图4可以看出，坐标点13和20之间不能通行，在当前情况下最优搜索结果如图5所示。

路径动态搜索结果为：

1→7→6→4→11→14→18→8→12→17→16→5→20→10→13→9→3→19→15→2→1

3.2 交通流参数

3.2.1 参数介绍

实际交通中需要考虑交通流量、行驶速度、排队长度、占有率、交通流密度以及车头间距、时距等交通参数。这些参数在一定程度上反映了实际的交通运行状态。下面将交通流量和行驶速度参数作为路径动态优化条件进行介绍[1]。

图4 各点相互连接情况

图5 道路状况发生变化后最优路径(长度3681.1895)

(1)交通流量：机动车交通流量指在单位时间内通过道路上某节点、路段或某条车道的车辆数。

(1)

其中，q为交通流量(辆/小时)，N为车辆数，T为单位时间。由于单从交通流量上很难准确反应整个交通运行状态，所以，在实际应用中不作为单独指标，需要结合其它参数综合考虑。

(2)行驶速度：道路上行驶的车辆速度有几种描述，如即时速度、平均行驶速度以及平均行程速度。其中平均行驶速度指路程与行驶时间之比，这个时间包含行驶时间和行驶过程中的等待时间，这个指标并不能很好地反映实际交通情况；平均行程速度指行驶路程与行驶时间(不含等待时间)之比，能更好地体现车辆在道路上的运行状态。

3.2.2 优化策略

当两个点之间发生拥堵，通行特别缓慢时，以平均行驶速度、交通流量作为判定标准。

(1)间断交通流情况：在间断交通流情况下，设定平均行驶速度小于每小时5公里为“慢”，大于每小时10公里小于每小时15公里为“较慢”，大于每小时20公里小于每小时25公里为“中”，可将平均行驶速度小于每小时15公里作为变换路径的判定条件，以搜索其它更为快捷的路径。

(2)连续交通流：在连续交通流情况下，设定平均行驶速度小于每小时10公里为“慢”，大于每小时30公里小于每小时40公里为“较慢”，可将平均行驶速度小于每小时30公里作为变换路径的判定条件，以搜索其它更为快捷的路径。