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

Optimal Safety Path Model and Algorithm in Transportation Networks

作　　者：苏兵[1] 徐寅峰[1] 肖鹏[1] 

机构地区：[1]西安交通大学管理学院

出　　处：《西安交通大学学报》2008年第4期395-398,422,共5页Journal of Xi'an Jiaotong University

基　　金：国家自然科学基金资助项目(70525004,70121001,70471035);中国博士后科学基金资助项目(20060401003);陕西省教育厅基金项目(06JK099)

摘　　要：针对交通网络任意路段均可能发生中断的最小损失路径选择问题,提出交通网络最优安全路径选择模型,并设计了2种不同网络结构下最优安全路径选择算法.首先用模型计算任意一条路径上每条边中断后产生的从起点到终点最短替代路径长度的最大值,然后选择一条最短替代路径长度最大值最小且自身长度最小的路径.在网络中,当最短路径删除后该网络依然连通时,最优安全路径问题转化为最短路径问题,其计算复杂度为O(n2);当最短路径删除后该网络不再连通时,最优安全路径问题转化为最小最大问题,其计算复杂度为O(mn),且仅与网络中节点和边的数量有关.最后,结合交通网络的实际情况对最优安全路径进行了算例分析.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^2） time; and in another case, the problem can be converted to a rain-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.

关 键 词：交通网络 最优安全路径 路径选择 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]