最优问题的论文.docx

交通建模中的最短路径算法分析与测试 任 刚，张 永，周竹萍 （东南大学江苏省交通规划与管理重点实验室，南京 210096） 摘 要：交通建模一直以来就是最短路径算法极为重要的应用领域。介绍主流的最短路径算法标号算法，通过交通网络特征分析和实际城市道路网络中的算法测试，给出如何选择适合交通网络的一般最短路径算法的建议。分析交通建模中各类特殊最短路径算法的研究需求，包括带转向约束的算法，带时窗约束的算法，动态、随机、自适应算法，k-最短路径算法，启发式搜索算法，再优化算法等。最后对未来研究趋势作出展望。 关键词：交通运输规划与管理；交通建模；最短路径算法；分析与测试 中图分类号：U491 文献标识码：A 文章编号：16737180(2009)1007086 Analysis and testing of shortest path algorithms in transportation modeling Ren Gang，Zhang Yong，Zhou Zhuping (Jiangsu Provincial Key Laboratory of Transportation Planning and Management, Southeast University, Nanjing 210096, China) Abstract: Transportation modeling is an important application field of shortest path (SP) algorithms. In this paper, labeling algorithms are introduced. Some suggestions on selecting the general SP algorithms suitable for realistic transportation networks are proposed according to analysis of transportation network characteristics and to experimental results over realistic road networks. Some special cases of SP algorithms in transportation modeling, including algorithms with turning constraints, algorithms with time-window constraints, dynamic, stochastic and adaptive algorithms, k-shortest path algorithms, heuristic search algorithms, and reoptimization algorithms, are reviewed. Future researches are prospected at last. Key words: transportation planning and management；transportation modeling；shortest path algorithms；analysis and testing 0 引 言 自20世纪50年代以来，经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得各种最短路径算法不断涌现1-3。交通建模一直以来就是最短路径研究成果极为重要的应用领域，其应用内涵包括2部分：一般的最短路径算法在交通建模中的直接应用；针对交通建模的特殊要求设计和应用一些特殊类型的算基金项目：高等学校博士学科点专项科研基金(20070286006)；住房和城乡建设部科学技术项目(2008-K5-11)；东南大学优秀青年教师教学科研资助计划 作者简介：任刚(1976 )，男，研究员， 中国科技论文在线 Sciencepaper Online 第4卷 第10期 2009年10月 709法（如带转向约束的最短路径问题等）。这两部分彼此联系，前者是基础，解决的是交通网络区别于一般抽象网络的共性问题；后者是拓展，解决的是交通网络针对不同特殊需要的个性问题。本文在介绍主流的标号算法基础上，对交通网络中一般最短路径算法的效率进行测试、比较并给出算法选取建议，回顾交通建模中各类特殊最短路径算法的研究进展，最后对未来研究情况作一展望。 1 最短路径算法的主流技术标号算法 根据路径源点和终点的数目，最短路径问题可分为单源单汇、单源多汇、多源多汇等类型，其核心是单源多汇问题。求解最短路径问题的大部分算法都基于如下事实：网络中从某个源点到其余所有节点的最短路径集，构成该网络以源点为根的生成树即最短路径树。主流的最短路径算法是标号算法，核心思想是通过节点扫描不断更新生成树和节点标号最终获得最短路径树。 根据节点选取策略的不同，标号算法又可以分为标号设定和标号修正2类。标号设定算法基于最短优先搜索，当弧长非负时每一步都能得到一条从源点到当前扫描节点的最短路径，由此若仅需要单源单汇最短路径，则一旦终点被扫描即可结束。而标号修正算法是基于列表搜索，算法不管弧长的正负，即使单源单汇问题也需等到算法完全结束时才能得到。 常用的标号技术包括数据结构、节点存取策略和生成树更新技术等。数据结构中，一类是适合于标号设定算法的各种优先队列，如堆、桶以及组合结构，另一类是适合于标号修正算法的各种列表，如队列、栈、门限以及组合结构deque等。除了由数据结构本身决定的存取策略之外，用以提高算法效率的辅助存取策略还包括阈值设置、拓扑排序等。生成树更新技术（包括标号更新）通过子树分解关系，将标号更新范围扩展到相应子树中的所有节点，而不局限于当前的扫描节点。已知的标号算法均可以视为一个统一的原型算法基于各种标号技术的不同实现形式，这有助于更好地理解所有标号算法之间的联系和差异，并拓展出更多有效算法。表1列出了主要标号算法的相关信息。 表 1 主要的标号算法一览表 Table 1 The major labeling algorithms 分类 算法名称 主要结构和技术 时间复杂度 备注 Dijkstra 无序列表 O(n2) S-heap 二叉堆 O(mlogn) S-heap-F Fibonacci 堆 O(m+nlogn) 非负弧长 S-heap-R1 单层基数堆 O(m+nlogC*) S-heap-R2 双层基数堆 O(m+nlogC*/loglogC*) S-heap-R3 基数堆Fibonacci堆 Om n C ( log ) + S-bucket 桶 O(m+nC*) S-bucket-M 限制桶的个数 O(m+n(C*/B+B) 标号设定算法 S-bucket-D 双桶 O(m+n(C*/+) L-bucket-A 近似桶 O(m+n(C*/+) 非负整数弧长 L-queue 队列 O(nm) L-deque 队列栈 O(n2n) L-2queue 双队列 O(n2m) L-threshold 队列阀值指针 O(nm) Topological Ordering 队列拓扑排序 O(nm) 标号修正算法 SLF 队列首元素比较 O(nm) 任意弧长 注：m为弧数，n为节点数，C*为最大弧长，B为桶数， 为桶间距，时间复杂度在备注要求 的情况下取得。 交通建模中的最短路径算法分析与测试 第4卷 第10期 2009年10月 710 中国科技论文在线 Sciencepaper Online 2 一般最短路径算法在交通网络中的适应性测试 2.1 交通网络的特征及其表示法 选择适合交通网络的最短路径算法，首先必须分析交通网络的特征并且设计高效率的交通网络表示法。实际的交通网络自有不同于一般网络的具体特点： 1) 交通网络由弧数和节点数之比 m/n 决定的平均邻接度比较低，一般在3左右，属于稀疏网络。一个有趣的现象是国内城市道路网络的平均邻接度较高，达3.3 左右，而国外城市则通常在 3 以下4。究其原因在于，国外发达城市的交通管理措施（如路段单向通行、机动车禁行等）比较完善，使得实际弧数有所降低。 2) 交通网络的弧长一般非负，虽然弧长的实际含义不一定是路段长度，但即使是广义的弧长（比如费用、行程时间等）通常也与路段长度呈近似正比关系，因此弧长分布范围比较均匀。 3) 交通网络结构比较规则，接近于平面图，但是又可能存在一定的复杂性，比如在同一城市路网中，市区道路密集，郊区道路就相对稀疏。 对于网络的存储和表示，通常有邻接矩阵、邻接表、邻接多重表和十字链表等。邻接矩阵由于其空间复杂度高（一般为 O(n2)）和关联节点查询速度慢（一般为O(n)），对于动辄具有成千上万节点的稀疏交通网络很不适合。邻接多重表和十字链表由于结构和操作比较复杂，在实践中的应用也仅限于某些专有领域。邻接表是另一种存储网络拓扑的数据结构，它是一种链式存储结构，其空间复杂度是 O(m+n)，对于路径分析中关键的操作关联节点的查询是O(m/n)，已被证明是网络表达中最为有效的结构。因此，对于交通网络这样的大型稀疏图应用邻接表（包括其特殊形式星形表）来存贮数据已经成为业界的共识3。 2.2 实际城市道路网络中的算法测试 针对缺乏在实际城市（尤其是国内城市）道路网络环境下最短路径算法测试的情况，最近我们将Cherkassky等2在Unix环境下开发且已为业内所认可的最短路径算法C语言代码适当修改后，移植到一台装有Windows XP操作系统和Unix模拟环境软件Cygwin、具有256M内存的Pentium 4计算机上，设计了具有可比性的测试环境和测试方案，选用了国内外7个真实的城市道路网络数据对表1中的14种算法进行了测试。 测试用的网络包括镇江、郑州、鞍山和昆山等4个国内城市路网以及美国芝加哥(Chicago)、西班牙巴塞罗那(Barcelona)和加拿大温尼伯(Winnipeg)等 3 个国外城市路网。网络数据取自作者所在实验室以及国外开放数据网站5。各个网络特征如表2所示。 表 2 测试网络特征 Table 2 Properties of tested networks 城市路网 节点数 弧数 平均邻接度 （弧数/节点数） 镇江 252 814 3.230 郑州 317 1 076 3.394 鞍山 347 1 178 3.395 昆山 378 1 186 3.138 芝加哥 993 2 950 2.971 巴塞罗那 1 020 2 522 2.473 温尼伯 1 052 2 848 2.707 本次算法测试的指标以计算速度为主，适当考虑稳定性。计算速度以查找最短路径树所需的运算时间（不包括数据录入和结果输出时间）为评价标准，时间越小则速度越快；稳定性以一定样本群中的上述运算时间的标准差为评价标准，标准差越高说明这个算法针对某些源点时要花更多的时间，因此稳定性越差。测试过程中，对每个测试网络随机选出100个源点，分别测定创建各个最短路径树需要的时间，最后计算这100个时间数据的平均值与标准差。由于数量级很小，为了保证精确性，每个最短路径树的运算时间以重复1 000次并求平均值的方法获取。 测试结果如表 3 所示，时间数据的单位为 ms。最后一行给出对应网络中最快算法的运算时间。其他各行数据对应各个算法，并按算法在测试网络上所表现出来的总体的计算速度排序（见黑字体列）。其中，“分网络性能”栏下列出该算法在各个网络中相对于最快算法的运算时间比，即运算时间与最快算法时间的比率；“总体性能”栏下显示该算法在所有网络中的运算时间的总和、运算时间标准差的平均值以及相对于总体最快算法总运算时间的比率。例如：SLF算法是郑州路网上的最快算法，计算每个最短路径树的平均时间为 0.40 ms；S-bucket 则是该网络上的最慢算法，平均运算时间是SLF 算法的 7.45 倍。而综合各个网络上的表现，L-2queue算法是总体最快算法，S-heap-F则是总体最慢算法，总运算时间是L-2queue算法的4.21 倍。 第4卷 第10期 2009年10月 711表 3 测试结果 Table 3 Testing results ms 分网络性能 总体性能 算法 镇江 郑州 鞍山 昆山 芝加哥 巴塞罗那 温伯尼 总时间 比率 平均标准差L-2queue 1.19 1.05 1.00 1.02 1.00 1.02 1.27 6.36 1.00 2.12 L-deque 1.24 1.13 1.04 1.10 1.04 1.00 1.20 6.39 1.00 1.99 SLF 1.00 1.00 1.08 1.00 1.12 1.31 1.80 7.64 1.20 2.81 L-threshold 2.03 2.00 1.57 1.43 1.55 1.08 1.00 7.85 1.23 0.85 L-bucket-A 2.57 2.95 2.08 2.02 1.37 1.36 1.00 9.14 1.44 1.15 S-bucket-D 2.03 2.50 2.19 2.08 1.55 1.54 1.10 9.42 1.48 0.68 L-queue 1.16 1.18 1.25 1.35 1.55 1.56 2.24 9.56 1.50 3.96 S-bucket-M 3.35 4.53 3.32 3.80 1.46 1.37 1.02 11.94 1.88 1.03 Topological Ordering 2.78 2.70 2.64 2.47 2.72 2.25 2.04 13.93 2.19 5.05 S-heap 2.38 3.15 2.70 2.57 3.39 2.30 2.02 14.83 2.33 1.34 S-heap-R1 4.38 5.33 4.53 4.35 2.41 2.06 1.51 16.25 2.56 0.80 S-bucket 6.41 7.45 6.77 8.12 1.39 1.39 1.01 18.58 2.92 2.34 Dijkstra 1.95 2.85 2.32 2.25 2.83 6.44 3.65 20.71 3.26 2.15 S-heap-F 4.16 5.43 4.66 4.47 5.45 4.94 3.81 26.77 4.21 1.21 最小时间 0.37 0.40 0.53 0.60 1.14 1.08 1.67 5.79 就单源多汇问题而言，上述测试结果表明：标号修正算法总体上优于标号设定算法，L-2queue，L-deque，SLF和L-threshold算法尤为出色；而在标号设定算法内部，基于桶结构的算法又要好于基于堆结构的算法。L-2queue，L-deque 算法的运算时间基本都保持在所在网络中最快算法的1.2 倍以下，对各种网络的适应性最好。SLF 算法更适合平均邻接度较高（如大于 3.2）的网络，但稳定性有所欠缺（平均标准差达2.81 ms）。与此相反，L-threshold算法更适合平均邻接度较低（如小于 3.0）的网络，并且有很好的稳定性。至于其他类型问题测试以及更详尽的分析结论可参阅文献4。 3 交通建模中特殊类型的最短路径算法分析 多样化的交通建模对最短路径问题设置了更多的约束条件，由此衍生出不少应用于但不局限于交通领域的特殊类型的最短路径算法，包括带转向约束的算法，带时窗约束的算法，动态、随机、自适应算法，k-最短路径算法，启发式搜索算法，再优化算法等。 3.1 带转向约束的算法 交通建模中经常需要求解转向约束下的最短路径问题，例如考虑交叉口的转向延误和转向禁行、考虑不同出行方式间的换乘费用。普通的算法对此无能为力，解决问题的途径有2条：间接法通过变换网络形式将转向约束直接体现在网络结构中，然后用普通算法求解，包括对偶网络法、扩展网络法等；直接法从算法本身入手直接求解问题，包括Vine-building算法、弧标号算法、节点标号算法等。其中，Vine-building算法和扩展网络法存在明显缺陷，其余3种方法更为有效。 任刚等全面分析了此类问题6-8，提出对偶最短路径树(DSPT)概念并利用其在现有方法中建立联系，使得将普通最短路径算法成果借用于此类问题中成为可能。 3.2 动态、随机和自适应算法 与普通（静态）最短路径问题相比，动态最短路径问题中的路段权重、节点延误等均为时间的函数，这更符合城市交通网络的时变特征。在假定路径长度服从先入先出(FIFO)原则的前提下，任何静态标号算法均可以交通建模中的最短路径算法分析与测试 第4卷 第10期 2009年10月 712 中国科技论文在线 Sciencepaper Online 扩展为动态最短路径算法9。 由于城市交通网络充满不确定因素，路段权重不再是一个常数而是一个满足某种概率分布函数的随机变量，由此异于普通（确定）最短路径问题的随机问题应运而生。在此类问题中，求解期望最短路径比求解可能最短路径更具实用意义。幸运地是，若用路段的期望权重替代随机权重，期望最短路径可用普通最短路径算法求解。当路段权重既是动态的又是随机的，问题变得更为复杂。 上述算法中，一旦路段权重的概率密度时变函数已知，某个起终点之间的期望最短路径在出行者离开起点前就能确定下来，即这样得到的期望最短路径是先验的、非自适应的。而在ITS环境中，出行者在出行途中可以接收到关于前方路段的最新信息，并结合已经历路段的实际情况，不断调整自己的决策、找出从当前位置通向目的地的最短路径，这就是自适应的动态随机最短路径搜索过程。 3.3 带时窗约束的算法 时窗(time window)是最普遍的时间约束形式，即网络节点只能在特定时间段内被访问，城市道路交叉口信号配时即可视为一个循环的时窗序列。时窗约束分2类：硬时窗和软时窗。在硬时窗约束下，算法目标是找到从源点到终点的最小费用路径使得所有中间节点能在各自的时窗内被访问。在软时窗约束下，路径费用最小依然是优化目标，但是一旦违例（即访问中间节点的时间超过了这些节点的时窗范围），则需要额外附加与违例次数相关的惩罚费用。 3.4 k-最短路径算法 在许多情况下不仅仅要考虑最短路也要考虑次短路、次次短路等，即k-最短路径问题。比如，为增大用户的选择余地，路径诱导系统通常要为用户提供几条可行的路径（包括最短路径），以便用户根据自己的习惯和喜好进行选择，也适合于当最短路径不可行时选择更为现实的同时也是较好的代用方案。k-最短路径算法可以同时求出长度从小到大排列的k条最短路径，有2种解决思路10：递推法在最短路径（称为第一最短路径）的基础上，求解一条次最短路径（称为第二最短路径），重复此过程k1次，就可得到k条最短路径；直接法直接求出k条最短路径。 3.5 启发式搜索算法 面对路网交通瞬息万变的运行状态，最短路径算法的时效性在诸如实时路径诱导系统等应用场合中是首要的。对此，除了采用对硬件要求较高的并行计算策略外，可以考虑采用启发式搜索策略“以精度换速度”。启发式搜索是一种尽可能基于现有信息的搜索策略，即在搜索过程中尽量利用目前已知的诸如迭代步数以及从初始状态和当前状态到目标状态估计所需要的费用等信息，通常采用限制搜索范围、分解搜索目标等策略11。目前最流行的启发式搜索算法当属由Hart等首先提出的A*算法12。 3.6 再优化算法 在交通建模中（例如均衡交通分配）经常会有如下需要：多次甚至不断地搜索最短路径树，但相邻2次搜索的条件和要求差别不大，要么是源点改变而网络中所有弧的长度保持不变，要么是源点不变而网络中部分弧的长度发生了改变（增加或减少）。尽管这可以通过 2次独立的、完整的最短路径算法调用来实现，但是另一种做法对于大型网络而言通常更节省计算时间1，即：采用一定的再优化(reoptimization)技术，更新前一次得到的最短路径树，获得源点或弧长改变后的新的最短路径树，这就是最短路径再优化算法的基本思路。此类算法多借助于对偶算法技术、图及其生成树的分解技术。 4 研究 展望 由国内外研究现状及其应用需求可见，未来关于交通建模中最短路径问题的研究除了进一步分析各种普通的最短路径算法在交通网络中的实际性能以外，面向交通建模尤其ITS应用领域的各种特殊问题类型将是研究热点和重点，并且在总体上呈现出3大趋势： 1) 约束条件的多样性。异于一般的最短路径搜索，从路径形式、路权准则和网络状态等方面设置更多的约束条件，例如：最短路径必须经过某些节点或某些弧，满足各种交通管理与控制措施的限制条件，路权中考虑时间和成本双准则，路权信息动态、随机且自适应等。 2) 算法效率的实时性。实时路径诱导系统等现代交通科技的发展和实施对最短路径算法研究提出了新的挑战在约束条件日趋多样、问题结构日益复杂的同时对算法实时性的要求却更为苛刻13，包括启发式搜索、再优化策略特别是并行计算均是实时性要求的产物。针对串行计算机的最短路径算法几乎已达到理论上的时间复杂度极限14，基于图分解的并行算法将成为一个主要研究方向。 3) 算法设计的针对性。最短路径算法研究的切入点应由寻求普遍适用的“最佳算法”转移到寻求面向问题的“特定算法”上，也就是抓住所要解决的交通建模问题的特征，设计适合问题的特定数据结构、运行结构与搜索策略，尽可能提高算法在实际问题上的时空效率。 第4卷 第10期 2009年10月 713 参考文献(References) 1 Pallottino S, Scutella M G. Shortest path algorithms in transportation models: classical and innovative aspects. C/ Marcotte P, Nguyen S, eds. Equilibrium and Advanced Transportation Modeling. Boston: Kluwer, 1998: 245-281. 2 Cherkassky B V, Goldberg A V, Radzik T. Shortest paths algorithms: theory and experimental evaluation (Technical report 94-1480) R. California: Computer Science Department, Stanford University, 1993. 3 陆锋. 最短路径算法: 分类体系与研究进展J. 测绘学报, 2001, 30(3): 269-275. Lu Feng. Shortest path algorithms: taxonomy and advance in research J. Acta Geodaetica Et Cartographic Sinica, 2001, 30(3): 269-275. (in Chinese) 4 李岩. 城市交通网络中最优路径算法的比较分析D. 南京：东南大学交通学院，2006. Li Yan. Comparison and analysis of optimal path algorithm in urban transportation network D. Nanjing: School of Transportation, Southeast University, 2006. (in Chinese) 5 Transportation Network Test Problems EB/OL. http:/www.bgu.ac.il/bargera/tntp/ 6 任刚，王炜，邓卫. 带转向延误和限制的最短路径问题及其求解方法J. 东南大学学报: 自然科学版, 2004, 34(1): 104-108. Ren Gang, Wang Wei, Deng Wei. Shortest path problem with turn penalties and prohibitions and its solutions J. Journal of Southeast University: Natural Science Edition, 2004, 34(1): 104-108. (in Chinese) 7 任刚. 交通管理措施下的交通分配模型与算法M. 南京：东南大学出版社，2007. Ren Gang. Traffic assignment models and algorithms with traffic management M. Nanjing: Southeast University Press, 2007. (in Chinese) 8 任刚，王炜. 转向约束网络中的对偶最短路径树原理及其原型算法J. 交通运输工程学报, 2008, 8(4): 84-89. Ren Gang, Wang Wei. Principles and its prototype algorithm for dual shortest path tree in networks with turning constraints J. Journal of Traffic and Transportation Engineering, 2008, 8(4): 84-89. (in Chinese) 9 Subramanian S. Routing algorithms for dynamic, intelligent transportat