基于A*算法的复杂交通环境下出行者最优路径分析研究

李少伟 曹成涛

摘  要：传统的路径规划未充分考虑出行者行车习惯和复杂交通环境的影响，通常搜索到的路径不一定符合出行者预期，本文将影响出行者路径选择的多种因素进行分析，运用层次分析法（AHP）建立了行程时间最短的出行者道路综合权值模型，并结合交通规则及实际道路环境使用A*算法进行最优路径分析，通过广州市天河区部分道路进行实例验证，结果证明了本文算法的有效性。

关键词：最优路径;A*算法;交通规则;道路权值

中图分类号：TP312      文献标识码：A

Abstract：Traditional path planning does not fully consider the influence of traveler's driving habits and complex traffic environment.Usually the searched path does not necessarily meet the traveler's expectations.This paper analyzes the various factors affecting the traveler's path selection，and adopts Analytic Hierarchy Process （AHP） to establish the model of the comprehensive road weight for the traveler with the shortest travel time.A* algorithm is used to analyze the optimal path in combination with the traffic rules and the actual road environment.Example verification is conducted on some roads in Tianhe District of Guangzhou.The results have proven the effectiveness of the proposed algorithm.

Keywords：optimal path;A* algorithm;traffic rules;road weight

1   引言（Introduction）

随着移动地理信息系统（GIS）技术、全球卫星定位（GPS）技术、无线通信技术的迅猛发展和广泛应用，出行者利用移动智能终端进行路径诱导的行为越来越普遍。最优路径问题是智能交通系统（Intelligent Transportation System，ITS）中路径诱导子系统（Route Guidance System，RGS）的核心问题[1]，传统最优路径搜索主要依据道路等级进行，未充分顾及出行者行车习惯和复杂交通环境的影响，得到的路径往往只考虑距离最短，结果通常包含拥挤的道路、过多红绿灯等，不符合出行者预期，因此，规划符合出行者行车习惯的行程，不但能提高出行者的行车效率和驾驶体验，也能缓解城市交通拥堵压力，具有重要的现实意义。

2   城市道路网络模型（Urban road network model）

最优路径分析本质属于图论研究中的一个经典问题，但在实际应用中，需要结合交通规则和实际道路环境，将其抽象为有现实意义的城市道路网络模型。

城市交通的快速发展，使得城市道路网除了具有一般道路网的特点之外，还有其特殊之处：①路段及节点众多，对于大型城市来说，城市道路及交叉口数量多而复杂;②道路网络密集且结构复杂，多车道、单行线、转弯限制、限速车道、交通管制、立交系统等交通特征和新的越来越多的交通规则使得城市道路网的结构变得越来越复杂[2]。

①路况，通过百度地图API获取城市道路拥堵情况，分为畅通、缓行、拥挤、严重拥堵四种通行狀态，道路拥堵情况在时间上表现出明显的周期性，由于道路拥堵程度的易变性，对于出行时间较长的路况预测需要综合实时交通信息和历史交通信息。

②道路等级，城市道路等级分为快速路（高速公路市内路段）、主干道、次干道、支路四类，道路设计行车速度依次降低。

③路口延误，包括红绿灯等待时间、通行延误时间等，人们因为交通拥堵等待交通灯消耗的时间越来越长[7]。

④车道数量，通常将车道数分为四类：4车道及以上、2或3车道、1车道、0车道。

依据图1的层次结构图，运用Saaty的1—9及其倒数作为标度的方法构造Ci对目标W的相对重要性判断矩阵，本文参考文献[6]多位专家对道路属性指标的评价意见，给出判断矩阵元素的值，判断矩阵W-C及特征向量如表1所示。

由表3和表4可见，因为实际交通环境不同，道路综合权值并未完全按道路等级划分，传统静态的最短路径和道路综合权值下的最优路径并非同一条路径，后者得到的路径未必是距离最短的，但一定是考虑了路况等多种影响因素的最优路径，出行体验更好。

6   结论（Conclusion）

自驾出行已成为出行者主要出行方式之一，如何合理的规划路径减少行程时间是出行者关注的重要话题。本文针对城市道路网的特点，将影响出行者路径选择的多种因素进行分析，运用层次分析法建立基于行程时间的出行者道路综合权值模型，并结合交通规则及实际道路环境使用A*算法进行最优路径分析，通过广州市天河区部分道路进行验证，相较于传统最佳路径分析结果，本文提出的最优路径算法不仅满足复杂交通环境下的交通规则约束，而且搜索出的最优路径更加符合出行者行车习惯和实际情况。

参考文献（References）

[1] 潘义勇，孙璐.随机交通网络环境下自适应最可靠路径问题[J].吉林大学学报（工学版），2014，44（6）：1622-1627.

[2] 朱庆，李渊.2007道路网络模型研究综述[J].武汉大学学报（信息科学版），2007，32（06）：471-476.

[3] Bekhor S，Ben-Akiva M E，Scott Ramming M.Adaptation of logit kernel to route choice situation[J].Transportation Research Record： Journal of the Transportation Research Board，2002，1805（1）：78-85.

[4] 高明霞.道路交通网络最短路径关键转向研究[J].公路，2018（9）：199-202.

[5] 孙秋霞，孙璐，刘新民.基于出行个体行为的交通网络效率研究[J].重庆交通大学学报（自然科学版），2016，35（2）：110-113.

[6] 段丽琼，刘立国.应用层次分析法确定道路属性指标的权重[J].海洋测绘，2004，24（3）：44-46.

[7] 朱云虹，袁一.基于改进A*算法的最优路径搜索[J].计算机技术与发展，2018，28（4）：55-59.

[8] 阮于洲，蒋捷.基于层次分析法的路段属性求权方法[J].地理信息世界，2004，2（2）：44-48.

[9] 王少帅，蔡忠亮，任福.加权路网分层的最优路径计算[J].测绘科学，2015，40（3）：127-131;122.

[10] 欧阳圣，胡望宇.几种经典搜索算法研究与应用[J].计算机系统应用，2011，20（5）：243-247.

作者简介：

李少伟（1981-），男，硕士，讲师.研究领域：GIS/GPS在智能交通中的应用.

曹成涛（1981-），男，博士，教授.研究领域：智能交通技术.