Optimal safety path model and algorithm in transportation networks

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.