智能交通车流自动导引系统

张宇

【摘 要】 随着中国经济的发展和人民生水平的提高，交通活动已经成为人们生活的重要组成部分，本文首先介绍了道路数据的数据结构和存储方式，然后依据实际情况，考虑车辆在动态环境下寻找最优路径，提出了使用强化学习方法作为主要研究算法，对车辆智能体进行道路选择的结果给予一定的奖励，从而使车辆最终选取理论上最优的一条道路。

【关键词】 强化学习 车辆路径规划 动态环境

一、系统功能分析

本课题是研究动态环境中车辆路径规划的问题，并设计出可视化的仿真软件以达到模拟现实情况下驾驶者在道路上的行车路线。此仿真软件要满足以下功能：设置车辆的起始地点和目的地点，并可设置车輛行驶过程中道路环境，例如某一道路上会发生交通堵塞等问题的情况。对于在现实世界中，道路完全具有实时性和动态性，因此在程序中可将路障设置为随机路障，即完全由程序随即决定当前时刻是哪条道路有障碍。该系统在设置完车辆行车环境后，通过算法和程序的计算，找到一条在当前环境下最适合的行车路线，以达到满足本课题的要求，模拟出现实世界中动态环境下的车辆路径规划问题。

系统功能主要可以划分为三个部分：一是给出车辆在不同行车方案下的运行成本，二是设计算法寻找车辆行驶的最优路径，还有一个是显示车辆的行车路线。最后给出系统的功能概图，为软件的总体设计和详细设计提供依据。

二、系统详细结构

在仿真系统软件的设计上，系统的大体思想是输入->处理->输出。模拟选择输入车辆的起始地点和目的地点，并选择产生路障的类型，这些都是输入问题。之后在后台运行，根据选择的条件进行路径规划，此为处理部分，最后将处理的结果以文字和在系统界面上显示的形式进行表示，这位输出部分。

输入模块又可分为三个子输入模块部分：起始地点选择模块，目的地点选择模块和道路障碍选择模块。其中，在起始地点和目的地点两个选择模块中，可模拟选择车辆的起始位置和目的位置。在这两个模块中，都可以使用选择已确定的地点，或可以通过输入其地理坐标，作为用户选择的起始地点或目的地点。对于道路障碍子模块来说，可以对其选择产生随机路障，或者自己选择有路障的路段，但是对系统进行设置随机路障更符合现实情况。

处理模块就是对车辆的路径选择进行算法设计和编写程序。在这一部分，使用强化学习算法进行动态环境中的车辆路径规划问题，同时在预测车辆可能的行驶路线的情况，据此对车辆下一步行驶的路段进行预测。

输出模块由两个子模块构成。一个是车辆进行路径选择后，在界面上的显示，即使用划线的方式对车辆行驶的路线进行标注，此为画图模块，在线程中进行处理。另一个是车辆在行驶的过程中，输出其选择的路线，行驶的状态，和当前环境下的交通堵塞等状况。

三、详细设计

路径规划各要素间不是互相孤立的，而是存在着复杂的关系。具体来说就是两个基本要素结点和路段之间有着复杂的关系，在现实世界中，结点即为道路上的一条路段的两端的路口。路段就可看作是不间断的没有路口的一条马路，或者也可以看做是几条路段和结点组成对的复合路段。

在本课题中Dijkstra算法的思想是：按照路径长度递增次序产生最短路径算法。

即假设无向图G=（V，E）中，每条边E[i]的长度为w[i]，找到由顶点V0到其余各点的最短路径。

把V分成两组：

（1）s：已求出最短路径的顶点的集合

（2）V-S=T：尚未确定最短路径的顶点集合

将T中顶点按最短路径递增的次序加入到S中，

保证：（1）从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度

（3）每个顶点对应一个距离

S中顶点：从V0到此顶点的最短路径长度

T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度

可以证明：V0到T中顶点Vk的最短路径，是从V0到Vk的直接路径的权值

本课题的车辆路径规划算法的实现过程大体如下：

初始时，设置车辆的起始地点和目的地点，判断车辆当前地点和目的地点是否相同，若相同，则表明当前位置与终点重合，认为到达终点，规划结束；若不相同，则开始寻找车辆要走的下一条路径。

在当前位置寻找下一步要走的路段，在当前结点处，判断可走向的与之在同一路段上的另一端的结点，即选择出将要走向的那个结点，在局部情况下可使付出的代价最小。在此处要计算，从与当前结点位置在同一路段上的其他结点分别到目的结点的最短路径值，比较它们之间的大小，找到权值最小的那个结点，下一步，车辆就向着那个结点行驶，一直到到达目的地结点。

四、系统测试

测试用例的设计

（1）测试用例1

用例描述：测试起始地点输入模块是否能够正确使用

前置条件：起始地点输入模块正确编写并编译成功

输入：选取下拉列表中的某一个元素

预期结果：在软件的车辆当前位置文本框中输出选择的结果

（2）测试用例2

用例描述：测试终点输入模块是否能够正确使用

前置条件：输入模块正确编写并编译成功

输入：向文本框中输入数据

预期结果：在软件的车辆当前位置文本框中输出选择的结果

（3）测试用例3

用例描述：测试目的结点输入模块是否能够正确使用

前置条件：目的结点输入模块正确编写并编译失败

输入：选取下拉列表中选择新地址

预期结果：在软件的车辆当前位置文本框中输出选择的结果

（4）测试用例4

用例描述：测试设置路线查询是否能够正确使用

前置条件：起始点目的地正确编写并编译成功

输入：点击目的地

预期结果：若设置成功，则弹出成功对话框

五、结论

本软件系统的设计是基于百度地图API进行的动态环境下的车辆路径规划。在设计过程中，重点解决了在模拟现实世界中交通路况具有动态性和不确定性的情况下，车辆进行最优路径的选择。在解决这个问题时使用到了很多方法和技巧，虽然在实现的过程中，遇到了很多难题和麻烦，也遭遇到很多瓶颈，但最后还是转换了思维，使用了其他的方法解决了问题。

【参考文献】

[1] 陆琳.不确定信息车辆路径问题及其智能算法研究[M].第一版.北京：科学出版社，2010.