Shortest paths and multicommodity network flows

Shortest path problem is one of the classic and important combinatorial optimization problems. It usually appears as a subproblem of difficult combinatorial problems, for example, the 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). The traditional SSSP and APSP algorithms may do unnecessary computation to solve the MPSP problem.; We have surveyed and summarized shortest path algorithms. We also investigate the least squares primal-dual method, a new primal-dual algorithm that avoids degenerate pivots, for solving the 1-1 and 1-ALL shortest path problems with nonnegative arc lengths, and show its equivalence to Dijkstra's algorithm.; Two new MPSP algorithms have been proposed, as well as their proofs and complexity. They are especially suitable for applications with fixed topology but changeable arc lengths. Several implementations of our MPSP algorithms have been extensively tested and compared with many state-of-the-art SSSP algorithms on many artificially generated networks and a real Asia-Pacific flight network.; Our MPSP computational experiments show that there exists no “killer” shortest path algorithm that dominates others. Our algorithms have better performance for dense networks, but become worse for larger networks. Although they are not the fastest algorithms for the artificially generated graphs, they are competitive for the real Asia-Pacific flight network.; Comprehensive survey on both the applications and solution methods for MCNF problems have been made. We give a new primal-dual MCNF algorithm (KEY) using a key path decomposition method, propose new ways to compute the max step length, and suggest perturbation methods to resolve the primal and dual degeneracy. Thus many degenerate pivots and indefinite cycling problems are avoided.; We compare the running time of KEY with the generic primal-dual (PD) method, Dantzig-Wolfe (DW) decomposition method, and CPLEX that solves MCNF problems in node-arc form (NA). Computational results show the importance of efficient MPSP algorithms and suggest directions for better DW implementation and possible remedies for improving the primal-dual methods PD and KEY.