交通路网中最优路径算法的道路权重选择.pdfVIP

交通路网中最优路径算法的道路权重选择

［摘要］在交通路网中，寻找任意两点间最优路径是出行导航的基本功能。

除了最优路径算法自身性能外，道路权重的选择也直接决定了寻径结果的优劣。

现有最优路径算法通常以通行能力为道路权重，其可能导致不合理的寻径结果，

同时也不具有全局负载均衡的能力。因此本文以Dijkstra算法为例，引入可达性

概念作为道路权重，从而弥补以通行能力为道路权重的缺陷。

［关键词］Dijkstra算法；道路权重；通行能力；可达性

doi:10.3969/j.issn.1673-0194.2009.15.017

1引言

在交通路网中，两点间最优路径算法的优劣主要受到两个因素的影响，即所

使用的通用最短路径算法和所选择的道路权重。通用最短路径算法是最优路径选

择的有哪些信誉好的足球投注网站工具，决定了如何在庞大的路网数据库中找到最优（或者最满意）的可

行路径。道路权重则是最优路径选择的有哪些信誉好的足球投注网站指标，它的标定决定了通用最短路径

算法有哪些信誉好的足球投注网站的依据。所谓最优路径选择就是使用通用最短路径算法有哪些信誉好的足球投注网站道路权重最

高（或者局部最高）的可行路径。因此，通用最短路径的选择直接影响到最优路

径选择的效率和优化度，而道路权重直接影响到最优路径选择的合理性。

其中，研究人员普遍关注所选用的通用最短路径算法。为解决这个问题，现

在已有多种优秀的最优路径算法，如Dijkstra算法、Floyd算法、A*算法等。但

是，研究人员常常忽视了道路权重问题，提供给出行者的道路权重选择没有贴近

出行者的实际出行习惯，并不能真正满足出行者的需求。

在现有的静态驾驶导航和出行者信息系统中，普遍选择通行能力为道路权

重。所谓通行能力是指两点间行驶路径的平均通行流量，如果出行者所行驶的道

路平均通行流量最大，就意味着出行者能够以最短的时间到达终点。这是一种以

时耗为优先衡量标准的最优路径算法，贴近于城市出行者的出行特点。但是以通

行能力为道路权重所得出的最优路径有以下缺陷：

（1）忽视出行者能耗（出行距离远近）损失；

（2）缺乏城市路网全局负载均衡能力。

因此，本文以较为经典的Dijkstra算法为通用最短路径算法，解析以通行能

力为道路权重的最优路径算法产生以上两个缺陷的原因，并进一步提出道路权重

的选择应考虑城市路网的可达性，在算法中引入路网可达性的概念，从而使算法

兼顾出行者的能耗和时耗，同时能够对城市路网起到全局负载均衡的作用。

2Dijkstra算法简介

Dijkstra算法是由E.W.Dijkstra于1959年提出的一个最短路径算法，也是目

前公认的求解最短路径问题的最经典的算法。其基本思想是用逐点增长的方法构

造一棵路径树，从而得到从该树的根节点（即起点）到其他所有节点的最优路径。

其基本原理是：［1］

（1）从起点出发，遍历所有直接连通节点，将其中权重最大的节点作为中

间节点；

（2）扩展出该中间节点的所有后续节点，并遍历该中间节点的所有直接连

通节点，并修改其他节点在加入该中间节点后距离起点的距离；

（3）选择出权重最大的节点，将其加为中间节点，并修改其他的中间节点；

（4）循环执行第（2）、（3）步，直至找到终点。

由此可以得到按权重递增次序排列的从起点出发经过各中间节点到达终点

的最优路径序列。

从以上描述可以看到，Dijkstra算法首先寻找道路权重最大的节点，以后中

间节点的道路权重顺次递减。那么如果以通行能力为道路权重，该算法会首先找

到起点周边通行能力最高的道路，然后顺次扩展。

3选择通行能力为道路权重

本节以Dijkstra算法为通用最短路径算法，解释在最优路径算法中选择通行

能力为道路权重时的两个缺陷。

3.1忽视出行者能耗损失

本文利用某应用以通行能力为道路权重的Dijkstra算法的寻径软件，演示该

算法在面对同一小区内距离较近的两点时，所得出的最优路径。

图1软件对同一小区内近距离两点之间所得出的最优路径

从图1中可以看到，某小区是一正方形区域，四角分别为A、B、C、D四

个点。小区四边有4条道路：其中AD和DC是主要道路，通行能力较强，但绕

行距离较远；AB和BC路段则是连接路网不同小区的次要道路，通行能力较弱，

但很明显起点和终点都是在一条AB线路附近。从图中起点到终点，该软件给出

了