The
shortest path problem is a classic and important combinatorial
optimization problems. It often appears as a subproblem when
solving difficult combinatorial problems like multicommodity
network flow (MCNF) problems.
Most
shortest path algorithms in the literature are either to compute
the 1-ALL single source shortest path (SSSP) tree, or to compute
the ALL-ALL all pairs shortest paths (APSP). However, most
real world applications require only multiple pairs shortest
paths (MPSP), where the shortest paths and distances between
only some specific pairs of origin-destination nodes in a
network are desired. The traditional single source shortest
path (SSSP) and all pairs shortest paths (APSP) algorithms
may do unnecessary computations to solve the MPSP problem.
We
survey and summarize many shortest path algorithms, and discuss
their pros and cons. We also investigate the Least Squares
Primal-Dual method, a new LP algorithm that avoids degenerate
pivots in each primal-dual iteration, for solving 1-1 and
1-ALL shortest path problems with nonnegative arc lengths,
show its equivalence to the classic Dijkstra's algorithm,
and compare it with the original primal-dual method.
We propose
two new shortest path algorithms to save computational work
when solving the MPSP problem. Our MPSP algorithms are especially
suitable for applications with fixed network topology but
changeable arc lengths. We discuss the theoretical details
and complexity analyses. We test several implementations of
our new MPSP algorithms extensively and compare them with
many state-of-the-art SSSP algorithms for solving many families
of artificially generated networks and a real Asia-Pacific
flight network.
Our MPSP
computational experiments show that there exists no "killer"
shortest path algorithm. Our algorithms have better performance
for dense networks, but become worse for larger networks.
Although they do not have best performance for the artificially
generated graphs, they seem to be competitive for the real
Aisa-Pacific flight network.
We provide
an extensive survey on both the applications and solution
methods for MCNF problems in this thesis. Among those methods,
we investigate the combination of the primal-dual algorithm
with the key path decomposition method. In particular, to
efficiently solve the restricted primal problem (RPP) in each
primal-dual iteration, we relax the nonnegativity constraints
for some set of basic variables, which makes the relaxed RPP
smaller and easier to solve since the convexity constraint
will be implicitly maintained.
We implement
our new primal-dual key path method (KEY), propose new methods
to identify max step length, and suggest perturbation methods
to avoid degenerate pivots and indefinite cycling problems
caused by primal and dual degeneracy. We perform limited computational
experiments to compare the running time of the generic primal-dual
(PD) method, the Dantzig-Wolfe (DW) decomposition method,
and the CPLEX LP solver that solves the node-arc form (NA)
of the MCNF problems, with our method KEY. Observations from
the computational experiments suggest directions for better
DW implementation and possible remedies for improving PD and
KEY.
