带转向延误和限制的最短路径问题及其求解方法

摘要：

阐述了带转向延误和限制的最短路径问题(SP-Turn)的基本原理,系统介绍了现有的求解方法,包括扩展网络法、对偶网络法和弧标号算法,并提出了一个节点标号算法用于对比.分析指出弧标号、节点标号算法在算法原理上是一致的,对偶网络法是对它们的直观化.同时指出在SP-Turn方法中,扩展邻接表是高效的网络表示形式,在合理选择的前提下,一般SP算法的标号设定、标号修正等标号技术同样适用,最短路径可由节点至弧的形式转换为节点至节点的常规形式.

关键词：最短路径、转向延误和限制、对偶图、标号、扩展邻接表

所属期刊栏目：34

分类号：U491(交通工程与公路运输技术管理)

资助基金：国家科技攻关项目2001BA402A06

在线出版日期：2004-03-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：104-108