Abstract:
The multi-commodity minimum cost ow problem is a fundamental network ow problem that arises in a variety of real-world decision making applications such as transportation, telecommunications, biology, medicine, economics, finance, etc. In many of these applications there is more than one objective that has to be taken into account, but there is a lack of research on the problem with two or more objectives. In this thesis, we investigate the multi-commodity minimum cost ow problem with two objectives as a bi-objective linear optimisation problem. We present a novel algorithm for solving the problem by integrating Dantzig-Wolfe decomposition in the iterations of the bi-objective simplex algorithm. Our algorithm is the rst application of Dantzig-Wolfe decomposition to multi-objective network ow problems. The algorithm solves the problem by reformulating it as a biobjective master problem over a set of capacity constraints and linear fractional sub-problems with single commodity ow conservation constraints. We report on the performance of the algorithm on a collection of directed bi-objective network instances with different characteristics and different numbers of commodities. Linear fractional sub-problems have to be solved in every iteration of the algorithm. We investigate this step in detail and present three algorithms for it. We compare the performance of these algorithms on a collection of directed bi-objective network instances. We also investigate the relationship between bi-objective multi-commodity minimum cost ow problems and capacitated traffic assignment with a generalised cost objective function comprising two components. Using this relationship and our algorithm for solving the bi-objective multi-commodity minimum cost ow problem, we present methods for estimating a fundamental factor in transportation modelling known as value of time.
