交通网络最优安全路径选择模型与算法

苏兵 1; 2; 徐寅峰 1; 3; 肖鹏 1; 3

您当前的位置：

首页 >

文章列表页 >

交通网络最优安全路径选择模型与算法

专题研究 | 更新时间：2025-12-08

- 交通网络最优安全路径选择模型与算法
- Optimal Safety Path Model and Algorithm in Transportation Networks
- 西安交通大学学报 2008年42卷第4期页码：395-398+422
- 作者机构：
  
  1. 西安交通大学管理学院,西安,710049
  2. 西安工业大学经济管理学院,西安,710032
- 作者简介：
- 基金信息：
  
  : 2007-08-27. 作者简介: 苏兵(1970-),女,博士后;徐寅峰(联系人),男,教授,博士生导师. 基金项目: 国家自然科学基金资助项目(70525004,70121001,70471035);中国博士后科学基金资助项目(20060401003);陕西省教育厅基金项目(06JK099)
- DOI：
  中图分类号： TP393
- 网络首发：2008-04-10，
  
  纸质出版：2008
- 稿件说明：
移动端阅览
苏兵 1, 2, 徐寅峰 1, 等. 交通网络最优安全路径选择模型与算法[J]. 西安交通大学学报, 2008,42(4):395-398+422.

苏兵 1, 2, 徐寅峰 1, et al. Optimal Safety Path Model and Algorithm in Transportation Networks[J]. 2008, 42(4): 395-398+422.
苏兵 1, 2, 徐寅峰 1, 等. 交通网络最优安全路径选择模型与算法[J]. 西安交通大学学报, 2008,42(4):395-398+422. DOI：

苏兵 1, 2, 徐寅峰 1, et al. Optimal Safety Path Model and Algorithm in Transportation Networks[J]. 2008, 42(4): 395-398+422. DOI：

摘要

针对交通网络任意路段均可能发生中断的最小损失路径选择问题

提出交通网络最优安全路径选择模型

并设计了2种不同网络结构下最优安全路径选择算法.首先用模型计算任意一条路径上每条边中断后产生的从起点到终点最短替代路径长度的最大值

然后选择一条最短替代路径长度最大值最小且自身长度最小的路径.在网络中

当最短路径删除后该网络依然连通时

最优安全路径问题转化为最短路径问题

其计算复杂度为O(n

); 当最短路径删除后该网络不再连通时

最优安全路径问题转化为最小最大问题

其计算复杂度为O(mn)

且仅与网络中节点和边的数量有关.最后

结合交通网络的实际情况对最优安全路径进行了算例分析.

Abstract

An optimal safety path model is presented for finding a new optimal path between two given nodes to reduce the inefficiency caused by the failure of an edge. The optimal safety path model computes the maximum length among all the shortest replacement paths between two given nodes produced by any edge's removal along a path

and then chooses the path whose maximum length with the shortest replacement path is minimum and whose length is minimized for all possible paths. Algorithms for computing the optimal safety path in two different network structures are proposed. In one case

the problem is the same as the shortest path problem and can be computed in O(n

)time; and in another case

the problem can be converted to a min-max problem and the optimal safety path can be computed in O(mn)time by

a labeling algorithm

where n and m denote the number of nodes and edges in the graph

respectively. Several numeral examples are given and the algorithms are validated.

关键词

Keywords

references

CORLEY H W, SHA D Y. Most vital links and nodes in weighted networks [J]. Operations Research Letters,1982, 1(4):157-161.

MALIK K, MITTAL A K, GUPTA S K. The k most vital arcs in the shortest path problem [J]. Operations Research Letters, 1989, 8(8):223-227.

NARDELLI E, PROIETTI G, WIDMAYER P. A faster computation of the most vital edge of a shortest path between two nodes [J]. Information Processing Letters, 2001, 79(2):81-85.

NARDELLI E, PROIETTI G, WIDMAYER P. Finding the most vital node of a shortest path [J]. Theoretical Computer Science, 2003, 296(1):167-177.

李引珍,郭耀煌. 交通运输网络最短路径关键边问题研究 [J]. 中国管理科学, 2004,12(4):69-73.

LI Yinzhen, GUO Yaohuang. Study on vital edges of shortest paths in traffic and transportation networks[J]. Chinese Journal of Management Science, 2004,12(4):69-73.

BHOSLE A M. Improved algorithms for replacement paths problems in restricted graphs [J]. Operations Research Letters, 2005, 33(5):459-466.

NARDELLI E, PROIETTI G, WIDMAYER P. Finding the detour critical edge of a shortest path between nodes [J]. Information Processing Letters,1998, 67(1):51-54.

HERSHBERGER J, SURI S. Vickrey prices and shortest paths: what is an edge worth? [C]∥Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. Los Alamitos, USA: IEEE Computer Society, 2001:252-259.

HERSHBERGER J, SURI S, BHOSLE A. On the difficulty of some shortest path problems [C]∥Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science. Berlin, Germany: Springer-Verlag, 2003:343-354.

XU Y, YAN H. Real time critical edge of the shortest path in transportation networks [C]∥3rd International Conference on Theory and Applications of Models of Computation,Berlin, Germany: Springer-Verlag,2006:198-205.

刘明,徐寅峰,杜源江,等.不完全信息下交通网络的关键路径问题 [J]. 系统工程, 2006,24(12):16-20.

LIU Ming, XU Yinfeng, DU Yuanjiang, et al. Most shortest vital-path problem with incomplete information on traffic network[J]. Systems Engineering, 2006,24(12):16-20.

DIJKSTRA E W. A note on two problems in connection with graphs [J]. Numerische Mathematics,1959,1(5):269-271.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

离子液体改性燃料的电流体动力学效应研究

多工况下离心压气机叶轮-机匣一体联合设计优化

水蒸气掺混对氨裂解气旋流燃烧与排放特性的影响研究

结构-语义-残差协同的图像压缩框架：面向隐私保护与高保真重建

扇贝仿生密封腔室内超临界二氧化碳泄漏流湍动能耗散机理研究