智能交通混合动态路径优化算法
在仿真实时环境下, 反复实验的基础上, 选取一组为实例分析并列举了多组对比实验。实验数据采用上述实验测试集, 并在仿真线程中每5 s更新一次数据。为验证算法性能, 将优化算法与A* 算法进行了对比实验。为形象地显示实验结果, 分别以图示及评价参数表格进行对比分析。
3.3.1 实例分析算法性能
在仿真实时环境下, 以起始点100到目标节点4056为一组实例进行分析。为验证节点100~4056解的多样性, 依次得到测试集1、2、3、4、5的基于时间最短的最优路径如图4所示, 其中红、黄、白、紫、绿色路径分别表示时间测试集1、2、3、4、5下的最优路径。
 | 图4 基于5个时间测试集下节点100到节点4056最优路径Fig.4 The optimal path from node 100 to node 4056 based on 5 time test sets |
由图4可知:有红、黄、紫、绿4种颜色, 则说明在不同测试集下有不同的最优路径, 即节点100~4056, 在不同测试集下有4种不同的最优路径, 而图中没有白色显示, 则说明当前测试集下的最优路径与其后的最优路径重合, 即测试集3下的最优路径被测试集4、5覆盖。为进一步分析, 分别得到5个测试集的最优解如表2所示。
 | 表2 测试集的最优解 Table 2 The optimal solution of test set |
由表2可知:5个测试集的解均不一样, 但由图4可知, 在5个测试集下节点100~4056的最优路径仅有4条。由表中节点数可知:2、3、4测试集的节点数相同, 进一步分析, 由图4可知, 测试集3的最优路径与其后的测试集重合, 因此, 可得出测试集3与测试集4的最优路径相同, 但最优解不同。这种情况是由于实时环境下, 同一条路径下, 其值大小有所差异。
基于上述实验的基础上, 在仿真线程中, 数据一共更新47次。为简化实验并达到实验目的, 将车辆的运行时间与仿真时间之间进行了转换处理, 即运行时间1000 s等价于仿真时间的1 s。其数据随时间更新过程及测试集分布统计结果如图5所示。
 | 图5 仿真实验环境Fig.5 Simulation experiment environment |
在图5(a)中, 图中实心圆点表示当前仿真数据所处的测试集中, 为更清晰显示数据随时间的变化过程, 以虚折线描述该过程。而图5(b)是对图5(a)数据分布的统计结果。
基于上述仿真环境下, 优化算法与A* 算法的对比结果如图6、图7所示。图6是算法第一次调用A* 算法得到的局部最优路径; 图7是在动态信息下, 调用优化算法得到的局部最优路径; 黑色矩形框为出行者行驶过的路径。
 | 图6 A* 算法的最优路径Fig.6 A* algorithm to solve the optimal path |
 | 图7 本文优化算法的最优路径Fig.7 Optimization algorithm to solve the optimal path |
由图6、图7可知:两图局部最优路径相同, 源于剪枝策略。当实时数据更新后, 更新局部最优解, 并以此为阈值限制算法的搜索区域。当发生剪枝时, 优化算法寻优过程结束, 则当前局部最优即为当前最优路径。为进一步验证算法的性能, 分别在运行时间、最优解、节点个数等参数上进行了对比实验, 其结果如表3所示。
| 表3 对比实验结果 Table 3 The comparison of experimental results |
由表3可知:在同等测试集下, 优化算法的运行速率是A* 算法的13倍, 甚优于A* 算法。算法初始化时, 实时环境为初始态, 由图5可知:当前测试集为1。调用A* 得到局部最优解, 其解值为229 471。由表2可知:测试集1下最优解值为229 471, 因此, 局部最优解与测试集1最优解相同。当黑色矩形区域行驶完成后, 所用时间为8289 s, 则当前局部最优解为221 182 s。在当前起始点下, 观察函数的返回结果为1, 调用优化算法, 得到局部最优解为228 468 s。优化算法的局部最优解大于A* 算法, 其原于实时信息下, 导致局部最优解增大。在执行A* 算法时实时环境为测试集1, 而由图5可知:执行优化算法时实验数据为测试集3。且由上述分析可知:在优化算法中发生剪枝, 则原路径即为测试集3下的最优路径。但测试集3下的最优解值远大于测试集1, 因此, 局部最优解增大。A* 算法的最优路径节点个数为122, 优化算法的节点个数为119, 则两者相差3个节点, 即为图7矩形框内的节点。
3.3.2 实例分析优化策略
为验证优化策略的合理性, 针对PSO局部最优及全局最优智能存储方式以及模糊时间窗进行了实验。由于以局部最优为剪枝算法的阈值, 当观察函数检测到当前路径减少或者有折回现象时, 仅更新局部最优解而无需调用优化算法。因此, 基于局部最优优化策略下, 算法的运行时间均在4 ms左右, 运行速率明显优于优化算法。因此, 在混合优化算法中引入局部最优是有效的。
全局最优解是一个逐步求解的过程, 全局最优解随起始点变化而变化, 直到到达目标节点。基于上述求解过程, 全局最优解为233 836 s。在仿真线程中, 数据更新了47次, 则47× 5 s× 1000=235 000 s接近于车辆行驶时间23 2300 s, 因此, 模糊时间窗在控制仿真时间是有效的。由表3可知:1、2测试集最优解优于全局最优, 而3、4、5劣于全局最优。进一步结合测试集分布情况可知:测试集1、2共执行了17次, 则3、4、5测试集共执行了30次。由此可见, 全局最优解是有效的, 全局最优路径如图8所示。
 | 图8 全局最优路径Fig.8 Global optimal path |
3.3.3 多组对比实验
为进一步验证算法的性能, 列举10组对比实验, 且每组实验测试20次求均值, 统计结果如表4所示。
| 表4 10组20次实验均值统计结果 Table 4 Statistical results of 20 experiments in 10 groups |
10组对比结果统计如图9所示, 图9(a)为A* 算法与优化算法运算速率比值统计结果, 图9(b)为优化算法与优化算法中引入优化策略的运算速率比值的统计结果。
 | 图9 对比实验统计结果Fig.9 The contrastive experiment result |
由图9可知:优化算法的运算速率均优于A* 算法, 比值分布在不同区间。由于算法是基于广义自适应A* 算法的基础上结合剪枝算法的优化算法, A* 算法中以优先队列Q存储待扩展节点, 并以剪枝阈值为结束条件之一, 进而加快算法运算速率。相比优化算法与优化策略速率比值可知:引入优化策略后, 算法运行速率均甚优于优化算法, 原于优化策略适应于实时环境。基于上述优化策略, 在观察函数中, 判断当前起始点Sstart下的wij是否发生变化:当wij减小且发生在局部最优解, 则无需调用优化算法重构最优路径, 仅需修改Plocal值, 因此节省大量运行时间; 当wij未发生变化, 同样, 无需调用优化算法, 等待仿真线程更新数据。因此, 优化策略可有效避免调用优化算法, 提高算法运行效率, 从而更好的适应动态实时环境。因此, 进一步证明了优化策略的有效性。
