Shortest Paths and Multicommodity Network Flows

Chapter 1 Introduction to multicommodity network flow problems

[pdf:198kB] [ps:494kB]

       In this chapter, we first describe an air cargo flow problem in the Asia Pacific region. It is this problem that motivates our research. Because the problem can be modeled as a multicommodity network flow (MCNF) problem, we then introduce many MCNF related research topics and applications. Finally, we review different MCNF formulations and outline this thesis.

Contributions and thesis outline

       We consider the following to be the major contributions of this thesis:

  • We survey and summarize MCNF problems and algorithms that have appeared in the last two decades.
  • We survey and summarize shortest path algorithms that have appeared in the last five decades.
  • We observe the connection between a new shortest path algorithm and the well-known Dijkstra's algorithm.
  • We propose three new multiple pairs shortest paths algorithms, discuss their theoretical properties, and analyze their computational performance.
  • We give two new MCNF algorithms, and compare their computational performance with two standard MCNF algorithms.
       This thesis has six chapters. Chapter 1 discusses MCNF applications and their formulations. Chapter 2 surveys MCNF solution techniques from the literature. Since our approaches require us to solve many multiple pairs shortest paths (MPSP) problems, we will propose new efficient MPSP algorithms. Chapter 3 first reviews the shortest path solution techniques that have appeared in the last five decades, and then introduces a new shortest path method which uses the nonnegative least squares (NNLS) technique in the primal-dual (PD) algorithmic framework, and discusses its relation to the well-known Dijkstra's algorithm. Chapter 4 discusses the theoretical details of our new MPSP algorithms. Chapter 5 presents the computational performance of our new MPSP algorithms. Finally, Chapter 6 illustrates our primal-dual MCNF algorithms, analyzes their computational performance, and suggests new techniques to improve the algorithms. Chapter 7 concludes this thesis and suggests future research.