Optimal Safety Path Model and Algorithm in Transportation Networks

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

您当前的位置：

首页 >

文章列表页 >

Optimal Safety Path Model and Algorithm in Transportation Networks

更新时间：2025-12-08

- Optimal Safety Path Model and Algorithm in Transportation Networks
- Vol. 42, Issue 4, Pages: 395-398+422(2008)
- 作者机构：
  
  1. 西安交通大学管理学院,西安,710049
  2. 西安工业大学经济管理学院,西安,710032
- 作者简介：
- 基金信息：
- DOI：
  CLC： TP393
- Online First：10 April 2008，
  
  Published：2008
- 稿件说明：
移动端阅览
苏兵 1, 2, 徐寅峰 1, et al. Optimal Safety Path Model and Algorithm in Transportation Networks[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.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Energy Efficiency Optimization of the Cryogenic Air Separation Process for Electronic-Grade Ultra Pure Nitrogen

Bi-Level Multi-Obj ective Optimization of a Wind-Solar Coupled Hydrogen Production System Based on the Synergy of Hybrid Electrolyzer Arrays

Research on the Electrohydrodynamic Effects of Ionic Liquid-Modified Fuels

Influence of Structural Parameters on the Summer Operational Characteristics of a Three-Tower-in-One Indirect Air-Cooling System

Numerical Simulation of the Energy Conversion Process in Thermoacoustic Engines with Different Stack Materials

Related Author

No data

Related Institution

No data

⁰