Stability analysis for the shortest path problems

The shortest path (SP) problem is to find the shortest (e.g. least cost) path from the origin to the destination in a given directed (or undirected) network. The cost of a path is the sum of the costs of arcs in the path. The main weakness of all the existing solution algorithms is that the optimal solution does not contain enough information to perform the needed cost Sensitivity Analysis (SA). We present a new pivotal solution algorithm which allows SA without using any artificial, slack or surplus variables, unlike the simplex method. The algorithm consists of three phases. In the Initial phase a partial basic variable set is constructed without any pivotal operations. The Push phase completes the basic variable set by pushing toward an optimal vertex or its neighborhood. If this vertex is not feasible, then the Pull phase generates an optimal vertex. Unlike simplex and network simplex-based methods, the proposed solution algorithm is free from pivotal degeneracy. The proposed SA extends ordinary SA to perform simultaneous, independent or dependent perturbation of the arc costs from their nominal values while preserving the current SP. The proposed approach also facilitates incorporation of network structural changes and side-constraints.