Andreas Nõu
Division of Optimization and Systems Theory
Department of Mathematics
KTH
In this talk we will briefly discuss some of the results contained in my thesis. Various transportation science applications can be modeled as combinatorial optimization problems. Small to medium size problems can be solved to optimality, but when considering real-world problems the instances are typically too large, and hence heuristic methods need to be utilized. The thesis deals with various aspects of large-scale combinatorial optimization. The research has been presented in six independent papers. The first three are algorithmic, whereas the last three are concerned with two different railroad applications.
In the first two papers we consider two methods for large-scale binary optimization problems. Their performance are evaluated on a test bed of set covering problems. This problem class is a main model for several important applications, e.g. airline crew scheduling.
In the third paper we consider an algorithm for a singly constrained quadratic program subject to lower bounds. This problem frequently appears as a subproblem in various application areas, e.g. in traffic equilibrium and network economics problems, but also as a subproblem in subgradient optimization.
The fourth and fifth paper considers a railway scheduling problem, which we model as an integer-programming problem. A novel optimization approach, using Lagrangian relaxation, is presented for its solution. The approach is computationally evaluated on realistic examples suggested by the Swedish National Railway Administration (Banverket).
The final paper considers a weekly locomotive scheduling problem encountered at Swedish State Railways (SJ). The aim is to find cyclic schedules that minimize operational costs while respecting maintenance constraints. A mathematical model is given, and two heuristics for its solution are presented.
Calendar of seminars