Algorithms for Multi-objective Network Equilibrium Problems

Abstract

Multiple real life processes can be modelled as network equilibrium problems. Such models originate in areas as diverse as transportation, telecommunication, supply chains and energy. In this thesis we focus on a particular application of network equilibrium models called traffic assignment (TA). The TA problem aims to predict traffic flows in a given transportation network. TA models describe interactions between road users. The route choice of every individual influences travel times and level of congestion in the network, and, as a result, influences the route choice of other road users. Over time, such interactions lead to an equilibrium state when no road user can reduce their travel time by switching to another route. In the beginning of the thesis we focus on the conventional TA problem which assumes that road users make their route choices based on travel time only. We perform a comprehensive study of solution algorithms available in the literature, compare performance of these algorithms on benchmark instances, study different approaches to solve sub-problems and analyse numerical stability of solution methods. In order to ensure consistent comparison of algorithms, we implement a flexible software framework that maximises the usage of common code. The central topic of our study is multi-objective user equilibrium (MUE). MUE extends the definition of equilibrium to the case when the route choice of road users is based on multiple factors such as travel time, monetary cost, etc., and allows multiple solutions. First, we focus on theoretical aspects of MUE. We show that an equilibrium solution of a TA model based on non-linear aggregation of criteria is also a MUE solution, and vice versa. We study several properties of BUE flows that allow to establish necessary background for developing solution algorithms. Second, we focus on bi-objective user equilibrium (BUE) which is a special case of MUE when two criteria are considered. We study how one or a subset of BUE solutions can be found. For this purpose, we adapt the path equilibration algorithm. We propose several speed-up techniques that allow to significantly improve its performance. We also extend the developed software framework to accommodate BUE.