Abstract:
Real life decision making takes into account multiple, often conflicting, criteria.
This gives rise to multi-objective optimisation. We discuss a range of different
bi-objective routing or transportation problems, in particular the shortest
path, integer minimum cost flow, and traffic assignment problems.
The first part of this thesis is dedicated to the bi-objective shortest path problem.
The problem is presented together with several well-known solution algorithms,
namely bi-objective labelling, ranking, and the Two Phase method.
Computational experiments highlight the strengths and weaknesses of the algorithms
for different types of problem instances. We introduce new variations
of the algorithms above and propose an easily implemented improvement for
bi-objective labelling. Cyclist route choice in road networks is presented as a
new application of the bi-objective shortest path problem, where cyclists aim
to reach their destination in minimal travel time, but also along a safe route.
For the bi-objective integer minimum cost flow problem, we introduce one of
the first solution algorithms based on the Two Phase method and demonstrate
its performance based on different types of problem instances. An improvement
of the algorithm for the transportation problem, a special case, is also
discussed.
Finally, multi-objective traffic assignment is discussed. Traffic assignment is
the process of modelling route choice of users of a (road) network in order to
determine the total traffic on each road of the network. This is an equilibrium
problem as the route choice of one traveller affects other travellers. We
show how, traditionally, multiple objectives are treated in traffic assignment,
often by combining them into a generalised cost function which may entail
strong assumptions on road user behaviour. Instead, we suggest to explicitly
distinguish the objectives in a multi-objective framework. We discuss existing literature, which is of mainly theoretical nature, and comment on several articles
presenting erroneous results. We contribute to the understanding of the
theoretical concepts of vector equilibrium, vector variational inequalities, and
vector optimisation. For the solution of bi-objective traffic assignment, we propose
novel heuristic algorithms based on bi-objective shortest path algorithms
as an important building block.