论文部分内容阅读
随着交通运输业的发展，车辆导航系统被越来越多的人们所接受，用来在行驶过程中，快速准确地确定车辆的位置，为司机指出到达指定目的地的合理路径。在车辆导航系统中，如何引导车辆是一个至关重要的问题，因为如果采用不合适的引导策略，导航系统的应用可能反而会对交通系统的效率产生负面影响。事实上，传统的贪婪引导法，也就是将所有车辆都引导到最优路径上，可能会因为最优路径上聚集了超过其交通容量的车流，而造成堵车等现象，从而降低交通系统的效率。从这个角度来讲，适当分流，让一部分车辆选择其他路径行驶，反而会提高交通系统的整体效率。而如何分流才能使得交通系统中所有车辆的总行驶时间最短，是一个值得探讨的问题。
本文提出了一种新型的启发式算法-Boltzmann全局最优寻路算法，该算法为交通系统中从不同起点出发开往不同终点的所有车辆，寻找近似全局最优的交通流分配方案。该算法的主要思想是反复迭代地根据在当前的交通状况下，车辆通过各路段所要花费的行驶时间，结合基于Q值的动态规划算法和Boltzmann分布为交通系统寻找拟最优路径，根据该拟最优路径分配交通流，然后再根据分配后的交通流，启发式地更新路段行驶时间，再次寻找新的拟最优方案，直到交通系统中所有的路段行驶时间收敛，我们找到近似全局最优交通流分配方案为止。
该算法分别在静态交通系统和动态交通系统中与Greedy算法，即将所有车辆都引导到最优路径上的车辆引导算法进行了比较。这里，在静态交通系统中，我们假设流入交通系统的车流量是静态不变的；而在动态交通系统中，从不同起点出发到达不同终点的车流量，都将随机不断生成。实验结果显示，应用Boltzmann全局最优寻路算法能够合理地分配交通流，为交通系统带来更高的整体效率。
本文所做的主要贡献有：(1)结合基于Q值的动态规划算法，提出了Boltzmann全局最优寻路算法(2)分别在静态和动态模拟交通系统中对其加以了验证(3)对实验结果进行分析和评估，并提出了改进建议。