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

被引：23

作者：

任刚

王炜

邓卫

机构：

[1] 东南大学交通学院

来源：

东南大学学报(自然科学版) | 2004年 / 01期

关键词：

最短路径; 转向延误和限制; 对偶图; 标号; 扩展邻接表;

D O I：

暂无

中图分类号：

U491 [交通工程与交通管理];

学科分类号：

摘要：

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

引用

页码：104 / 108

页数：5