Chapter
3 Shortest path algorithms: 1ALL, ALLALL, and SOMESOME
[pdf:210kB] [ps:447kB]
In this thesis, we focus on solving ODMCNF, a class of mincost
MCNF problems where the commodities represent origindestination
(OD) pairs.
As introduced in Section 2.3.2, when we use DantzigWolfe
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 primaldual algorithmic
framework to solve sequences of nonnegative least squares
(NNLS) problems, and show its connection to the wellknown
Dijkstra's algorithm.
Summary on least squares
primaldual shortest path algorithms
In summary, the
LSPD algorithm is identical to Dijkstra's algorithm for solving
both ALL1 and 11 shortest path problems. The original PD
algorithm, on the other hand, is identical to the Dijkstra's
algorithm for solving the ALL1 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.
