**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. |