雒 应,何 强

(长安大学 公路学院，陕西 西安 710064)

0 引 言

最短路径算法是交通运输工程领域应用最广泛的算法之一，是智能交通分配、交通规划和交通控制的基础算法。最短路径算法评估一条路径是否为最短路径的度量衡是该路径的代价，一般为该路径花费的时间，或者该路径的其他成本。一般的最短路径算法在计算路径代价时仅考虑路段的阻抗，这种情况对公路是适用的，因为公路路段长度大而节点较少，路径的路段行程时间一般远远大于节点消耗的时间，因而车辆的交叉口延误可以忽略。但是城市道路路段长度一般较短，交叉口数量多，交叉口作为城市道路网络中通行能力的瓶颈严重影响交通流的运行，拥堵情况下车辆在交叉口处花费的时间甚至可能超过在相邻路段的行驶时间[1]。因此，应用于城市路网的最短路径算法应该考虑交叉口延误。

1 研究现状分析

考虑交叉口延误和转向限制最短路径问题(shortest path with turn penalties and prohibitions)的难点在于转向路径没有很好的数学描述[1]，因而解决问题的关键在于如何表现转向关系。目前国内外学者对此问题的解决办法按照对算法使用的网络分类可分为直接法和间接法两大类[2]。

1.1 间接法

间接法对原始网络按照一定规则进行变换， 将转向延误和限制直接体现在变换网络中，然后在变换网络中计算最短路径，最后基于变化规则逆向转换在变化网络中得到的最短路径，输出原始网络的最短路径，包括扩展网络法、对偶网络法等。……