### Optimization and Systems Theory Seminar

Friday, September 12, 1997, 11.00-12.00, Room 3721, Lindstedtsvägen 25

**Andreas Nõu**

Division of Optimization and Systems Theory

Department of Mathematics

KTH

####
Large-scale combinatorial optimization with transportation science
applications

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

*Last update: September 10, 1997 by
Anders Forsgren,
andersf@math.kth.se.
*