Chapter 3 Shortest path algorithms: 1-ALL, ALL-ALL, and SOME-SOME

[pdf:210kB] [ps:447kB]

        In this thesis, we focus on solving ODMCNF, a class of min-cost MCNF problems where the commodities represent origin-destination (OD) pairs.
As introduced in Section 2.3.2, when we use Dantzig-Wolfe decomposition and column generation to solve ODMCNF, we generate new columns by solving sequences of shortest path problems for specific commodities (OD pairs) using c+p^{*} as the new arc lengths where c is the original arc cost vector and -p^{*} is the optimal dual solution vector associated with the bundle constraint after we solve the RMP. Since the RMP changes at each iteration of the DW procedures, p^{*} will also change. Therefore, the shortest paths between specific OD pairs have to be repeatedly computed with different arc costs on the same network. Efficient shortest path algorithms will speed up the overall computational time needed to solve the ODMCNF.
In this chapter, we first survey shortest path algorithms that have appeared in the literature, and then discuss the advantages and disadvantages of these shortest path algorithms in solving multiple pairs shortest path problems. Finally, we introduce a new shortest path algorithm based on a new LP solution technique that follows the primal-dual algorithmic framework to solve sequences of nonnegative least squares (NNLS) problems, and show its connection to the well-known Dijkstra's algorithm.

Summary on least squares primal-dual shortest path algorithms

        In summary, the LSPD algorithm is identical to Dijkstra's algorithm for solving both ALL-1 and 1-1 shortest path problems. The original PD algorithm, on the other hand, is identical to the Dijkstra's algorithm for solving the ALL-1 shortest path problem, but needs to choose a specific dual improving direction (there are multiple ones) so that it will be identical to the Dijkstra's algorithm.
For the general arc cost cases, both LSPD and the original PD algorithms can be applied, but Dijkstra's algorithm is not applicable. The theoretical and practical performances of LSPD and the original PD algorithms for solving shortest path problems with general arc costs remain to be investigated.