《硅谷》杂志：应急车辆调度中的最优路径研究 |
| 2013-02-28 14:36 作者：安一帆 来源：硅谷网-《硅谷》杂志 HV： 编辑： 【搜索试试】
|
|
硅谷网文 据《硅谷》杂志2012年第22期刊文称，突发事件发生后，公安机关需要及时调度车辆进行应急救援，而提高救援效率的关键因素在于建立合理的最优路径。结合实际的道路交通状况，建立救援时间影响因素的层次结构模型，同时，在基本蚁群算法的基础上进行改进，通过仿真实验，验证算法的可行性，缩短调度车辆的救援时间。
关键词：车辆调度；最优路径；蚁群算法
0引言
近年来，各种突发性事件的应急处理得到了人们越来越多的关注。如何在紧急事件发生之后，快速的找到一条应急车辆的最优路径，对于降低事故的危害程度起着至关重要的作用。而车辆调度的最优路径并不一定是最短路径，尤其在公安、武警、医疗救护等领域，我们重视的往往是时间的紧迫性，所以本文考虑的最优路径是在实际情况的基础上，研究的救援时间最短的车辆调度路线。
目前，随着仿生智能学的发展，蚁群算法在解决最优路径的问题上得到了广泛的应用，并且实验表明，根据自然界中生物行为衍生出的蚁群算法，相比传统的Dijkstra算法、算法等具有更好的快速计算能力、较强的鲁棒性以及可扩展性等优点[1]。因而本文在蚁群算法的基础上进行改进，并结合实际道路情况寻找车辆调度的最优路径。
1蚁群算法
1.1蚁群算法的工作原理
蚁群算法是模拟生物界中蚂蚁的觅食活动，引入具有记忆功能的虚拟蚂蚁进行路径的寻优。虚拟蚂蚁在运动过程中，会根据路径的长短释放一种特殊的物质----信息素，信息素浓度是关于路径长度的反函数。在每一个路口选择路径时，虚拟蚂蚁能够感知信息素的浓度，并倾向于朝信息素浓度高的方向移动，同时自己也会释放一定量的信息素，这样，路径越短，选择它的虚拟蚂蚁越多，该路径上的信息素浓度就越大，对其他虚拟蚂蚁的引导性能就越强[2]。正是通过这样一种协同工作，指导虚拟蚂蚁最终找到一条合理的最优路径。
1.2蚁群算法的数学计算模型
虚拟蚂蚁在移动时是根据状态转移概率选择下一条路径的[2]，设蚂蚁k在点选择点的转移概率为，j为还没有访问到的点。则
（1）
其中，表示蚂蚁k接下来可以选择的节点集合；s为蚂蚁k可以选择的下一个节点；表示路径上的信息素浓度；表示路径本身的启发信息；表示信息启发式因子；表示路径启发式因子。
虚拟蚂蚁完成一次循环后，需要按照式（2）和式（3）进行信息素的局部更新[2]，
（2）
（3）
其中，表示从t时刻到t+1时刻虚拟蚂蚁留在边上的信息素增量；为信息素的挥发系数，通常设定的取值在0和1之间；表示时间段上第k只蚂蚁在边上释放的信息素量[3]，
（4）
其中，为蚂蚁释放的总信息素量；为第只蚂蚁在本次循环中所走的路径长度。
同时，当所有虚拟蚂蚁完成一次循环后要进行信息素的全局更新，更新公式如下所示[2]：
（5）
式中，表示全局更新后的信息素浓度；表示信息素更新前路径上的信息素浓度。
2实际救援中车辆调度的情况分析
2.1影响车辆调度救援时间的主要因素
在应急救援的车辆调度中，我们往往是将时间作为主要的考虑因素。而救援车辆能否及时的到达事故地点除了与路径长度有关以外还受到很多情况的影响，如早晚高峰时期的车流量、部分道路的通行限制及由于恶劣天气导致的交通拥堵等。这些因素都在一定程度上制约了应急车辆的救援时间。因此，车辆调度过程中需要综合考虑这些特殊情况，设计出一条符合实际的最优救援路径。
在实际救援过程中，影响车辆调度救援时间的因素可以分为人为因素（如驾驶员的驾驶技术等）、车辆自身因素（如车辆的性能标准高低、车辆自身的设计车速等）、道路因素（如路径长度、交通拥堵等）和环境因素[4]。本文仅就道路和环境因素进行分析，讨论其对救援时间的影响。
2.2各影响因素层次结构模型的建立
本文建立影响因素层次结构模型的方法是层次分析法，这种方法最大的特点是可以将定性问题与定量计算相结合，对于本文中难以完全用定量计算进行分析的救援时间尤为适用。根据层次分析法的建模过程[6]，首先选取路径长度、天气因素、道路通行限制、道路服务等级以及不同时段交通流量这5个没有重复内容的一级指标，构建由目标层、一级指标层和二级指标层组成的层次结构模型，如下图所示：
图1车辆调度影响因素层次结构图
根据上面的层次结构图，就可以根据各指标的重要程度赋予相应的权重值。具体方法是构造判断矩阵，从层次结构模型的一级指标层开始，将隶属关系相同的同层元素进行两两比较，以数字的形式将结果写入判断矩阵，从而得到一级指标层和二级指标层的判断矩阵，如表1-表4所示：
A B1 B2 B3 B4 B5
B1 1 3 5 5 6
B2 1/3 1 2 2 4
B3 1/5 1/2 1 1 2
B4 1/5 1/2 1 1 2
B5 1/6 1/4 1/2 1/2 1
B2 C1 C2 C3
C1 1 3 5
C2 1/3 1 4
C3 1/5 1/4 1
B3 C1 C2 C3
C1 1 3 2
C2 1/3 1 1/2
C3 1/2 2 1
B4 C1 C2 C3
C1 1 3 5
C2 1/3 1 3
C3 1/5 1/3 1
上述判断矩阵的合理性需要进行一致性检验，检验公式如下所示[6]：
（6）
其中，CI为一致性指标，CI的计算公式为
（7）
表示最大特征根，n表示判断矩阵的阶数。RI由判断矩阵的阶数决定，表示平均随机一致性指标，当n=3时，RI=0.52；n=5时，RI=1.12。通常情况下，对于阶的判断矩阵，只有当时，才认为判断矩阵的一致性检验通过，此时的特征向量（归一化后）即为权向量。
对上述的判断矩阵进行一致性检验，得到判断矩阵A-B的CR值为0.0096，B2-C的CR值为0.0825，B3-C的CR值为0.0088，B4-C的CR值为0.037，检验结果均满足一致性的要求。
3本文算法的改进思路
基本蚁群算法在实际应用中，如果只按照公式1所示的状态转移概率进行搜索，往往由于随机性太强而增加算法的运行时间，同时，公式1所示的转移概率，只从信息素浓度和路径启发信息两方面出发，并没有结合道路的实际交通特征，求出的最短路径有时并不是所需的最优路径。因此，本文在基本蚁群算法的基础上，对虚拟蚂蚁寻找路径时的选择规则进行如下改进：
首先，结合实际的道路交通情况，在基本算法状态转移概率的基础上，引入救援时间影响因素的权重项，如公式8所示：
（8）
其中，表示的是在时刻t路段上的实际路况影响因素权重量，为权重指数，具体的计算方法如下：
（9）
（10）
式中，表示路径长度；为每条道路设计的平均速度；、、、和分别表示路径长度、天气因素、道路服务等级、不同时段交通量、道路通行限制对于路径寻优的影响权重值；表示当时的天气状况，根据不同天气对车辆行驶时间的影响情况赋予区间上不同的实数值；表示道路服务等级，由一级到四级分别赋值为（0.25、0.5、0.75、1）；表示不同时段的交通流量，将其与最大交通量作比，得到一个区间上的实数值；e表示道路通行限制，根据道路的通行情况有限制则赋值为1，无限制则赋值为0。
然后，就可以得到路径搜索过程中寻找下一节点的计算公式：
（11）
式中，表示在可选的下一个节点中，结果最大的节点标号；J是按公式8的转移概率计算出的下一节点；是取值为0～1之间的一个随机数，为概率选择因子，取值也在0～1之间。
改进后的状态转移概率在一定程度上约束了基本蚁群算法的无目的搜索。首先，算法随机产生一个0～1之间的数，如果，则虚拟蚂蚁可以随机选择下一个路口；如果，则虚拟蚂蚁按照最大概率进行选择[7]。这样，在随机搜索的基础上，又引入了一定概率的确定性搜索，从而大大提高了算法的收敛性。同时，路况实际因子将影响车辆救援时间的主要因素纳入到虚拟蚂蚁选择路径的参考依据中，提高了算法的实时性，使得算法在实际应用中更加合理可行。
4仿真实验
图2为某地区部分交通简化示意图，I点发生突发事件，应急点位于A，发生事故后，应急车辆从A点出发，前往I处实施救援。
此时为下午3点，并非早晚高峰时期；天空晴朗，能见度较高，有风；路段R8正在进行维修，只能由HG单向行驶。各路段的路径长度以及路段上的交通情况如表5所示。
表5交通道路信息表
路段名称 通行与否 路段长度（km） 当时路段通行时速（km/h） 当时路段通行时间（h） 通行方向 服务水平 备注
R1 是 9.5 58 0.164 双向 三级
R2 是 5.3 9 0.589 双向 四级 堵车
R3 是 9.6 74 0.130 双向 二级
R4 是 4.1 69 0.059 双向 二级
R5 是 5.6 52 0.108 双向 四级
R6 是 5.2 8 0.65 双向 四级 堵车
R7 是 8.7 64 0.136 双向 二级
R8 是 9.2 82 0.112 单向 一级 道路维修，通行方向HG
R9 是 7.7 73 0.105 双向 二级
R10 是 2.7 69 0.039 双向 二级
R11 是 10.2 75 0.136 双向 一级
R12 是 7.2 62 0.116 双向 二级
R13 是 8.9 57 0.156 双向 三级
R14 是 6.8 61 0.111 双向 二级
注：该部分路段的设计速度为100km/h，服务水平是以《公路工程技术标准》中一级公路的相关参数为依据划分的[4]。
根据实例中的相关数据，通过MATLAB仿真软件，首先利用基本蚁群算法进行仿真，可以得到最优路线为ABCI，此时的最优路径长度为21.4km，所需的救援时间为0.861h。而结合实际的交通情况，利用改进后的蚁群算法进行仿真，得到的最优路线为AGBHI，最优路径长度为23.8km，所用救援时间为0.345h。
通过实例仿真可以看出，改进后的蚁群算法综合考虑了影响车辆调度救援时间的实际因素，虽然得到的最优路径长度较比算法改进前稍有增加，却大大降低了应急车辆的救援时间，更加适用于强调时间最短的车辆应急救援行动中。
5结论
本文采用仿生智能学中的蚁群算法作为基本算法，并结合影响车辆调度救援时间的实际因素，从路径长度、天气因素、道路服务等级、不同时段交通量、道路通行限制五个方面建立了影响车辆调度相关因素的层次结构模型。据此，对基本蚁群算法进行改进，同时，为提高算法的收敛性，在算法中增加了一定概率的确定性搜索。最后，通过MATLAB进行实例仿真，验证了改进算法的可行性。
该方法将在一定程度上提高车辆调度最优路径的寻优效率，但是算法中权重因子的确定与实际交通路况的实时数据密切相关，还需要计算机定位等技术为救援体系提供更多的信息支持，使整个车辆调度救援体系更加完善。
作者简介：
安一帆（1987-），女，汉族，硕士研究生，中国人民公安大学安全防范工程系。
|
|
|
|
【对“《硅谷》杂志：应急车辆调度中的最优路径研究”发布评论】 |
版权及免责声明：
① 本网站部分投稿来源于“网友”，涉及投资、理财、消费等内容，请亲们反复甄别，切勿轻信。本网站部分由赞助商提供的内容属于【广告】性质，仅供阅读，不构成具体实施建议，请谨慎对待。据此操作，风险自担。
② 内容来源注明“硅谷网”及其相关称谓的文字、图片和音视频，版权均属本网站所有，任何媒体、网站或个人需经本网站许可方可复制或转载，并在使用时必须注明来源【硅谷网】或对应来源，违者本网站将依法追究责任。
③ 注明来源为各大报纸、杂志、网站及其他媒体的文章，文章原作者享有著作权，本网站转载其他媒体稿件是为传播更多的信息，并不代表赞同其观点和对其真实性负责，本网站不承担此类稿件侵权行为的连带责任。
④ 本网站不对非自身发布内容的真实性、合法性、准确性作担保。若硅谷网因为自身和转载内容，涉及到侵权、违法等问题，请有关单位或个人速与本网站取得联系（联系电话：01057255600），我们将第一时间核实处理。
|
|
|
|
