If you are interested in details about current projects with industrial participation please do not hesitate to contact me. Here are the headlines:

Algorithms for Robust and online Railway optimization: Improving the Validity and reliAbility of Large-scale systems (ARRIVAL)

Algorithmic methods have reached a state of maturity as a consequence of decades of research where real-world problems were posed to the algorithms community triggering important developments in the field. Despite this success, the current state of algorithmic research still faces severe difficulties, or cannot cope at all, with highly-complex and data-intensive applications as those dealing with optimization issues in large-scale communication and transportation networks. The complexity and size of such optimization problems pose new challenges for algorithmic research, and their efficient solution requires a radically new foundational paradigm.

In this project, we are interested in establishing such a new paradigm and considerably advance the current state of algorithmic research by attacking optimization questions in perhaps the most complex and largest in scale (transportation) setting: that of railway systems. Railway optimization deals with planning and scheduling problems over several time horizons. We focus on two important and actually unexplored facets of planning that pose even harder optimization questions: robust planning and online (real-time) planning. These two, tightly coupled, facets constitute a proactive and a reactive approach, respectively, to deal with disruptions to the normal operation.

Our main goal is to develop the necessary foundational algorithmic research in order to provide ingenious and sound answers to the fundamental efficiency and quality issues encapsulated in robust and online planning of complex, largescale systems as those in railways. We will endeavor to develop a thorough understanding of the fundamental issues that make robust and online railway optimization problems hard and to subsequently develop new algorithmic and complexity principles to deal with hardness through an integrated, interdisciplinary approach drawn from algorithmic, operations research, and constraint programming techniques.

ARRIVAL project home page

Funded by:

FP6 Sixth Framework Programme of the European Commission



Optimal rail car allocation (2000-2003)

We consider the rail car management at industrial in-plant railroads. Demands for materials or empty cars are characterized by a track, a car type, and the desired quantity. If available, we assign cars from the stock, possibly substituting types, otherwise we rent additional cars. Transportation requests are fulfilled as a short sequence of pieces of work, the so-called blocks. Their design at a minimal total shunting and transportation cost is the planning task considered in this project.

In a first step, the railroad network is decomposed into regions. For each region the supply of cars of each type is known. We construct a bipartite graph which represents feasible supply-demand pairs. The rough distribution of cars among regions is then easily determined by solving a standard transportation problem.

(railroad network)

In each region, when the upper level transportation problem is solved, the demand for each car type is fixed. We face the following shunting problem. Each track is attributed a cost, which occurs when pulling any one car out of the track. The goal is to provide at least the demand of cars from each type at minimal total cost. A practical assumption is that no space limitations apply to intermediate car storage. Currently, neither pushing surplus cars back onto their tracks give rise to any cost, nor exists a prescribed sequence of ordering the cars in the resulting train.

(solution to shunting problem)

It can be shown by a reduction from vertex cover that this problem is NP-hard. We present integer programming formulations for the two problem levels separately, and an integrated model. Several modeling alternatives take more pratical details into account. In our computational experiments instances of practical size can be optimally solved within seconds.

Funded by:
bmb+f
Research program: New Mathematical Methods in Industry and Services

Cooperation with:

CSC
CSC Ploenzke AG

Participants: Marco Lübbecke, Uwe Zimmermann

Journal Article: PostScript PDF

Optimal locomotive routing and scheduling (1997-2000)


In-plant railroad engine scheduling involves routing and scheduling decisions for a heterogeneous fleet of switching engines in order to serve a set of time window and capacity constrained transportation requests. The problem is related to the multiple-vehicle pickup and delivery problem. Exploiting the structure of admissible schedules of our particular railroad situation, we introduce two formulations of the problem; as mixed integer and set partitioning programs. We propose solving the linear programming relaxation of the set partition model by column generation. The pricing problem, a constrained shortest path problem, is NP-complete in the strong sense. An exact label correcting algorithm is developed which prunes the search space in a novel manner. Heuristically obtained integer solutions of a practical quality are proposed as well. All the claims are demonstrated by computational experiments on both, artificial and real-life data. We largely discuss implementation details.

(switching engine)

Funded by:
bmb+f
Research program: Mathematical Methods for Problems in Industry and Business

Cooperation with:
CSC VPS VPS
CSC Ploenzke AG
Verkehrsbetriebe Peine-Salzgitter
Eisenbahn und Häfen
EKO Trans

Participants: Marco Lübbecke, Uwe Zimmermann

Journal Article: PostScript PDF
Ph.D. thesis: PostScript PDF
Visit the project web site (German)

Optimal line planning in public transportation (2001-2002)


In a public transportation network, we refer to a line as a route, or itenerary, together with the specification of how often the route is operated. The line planning problem asks for the design of lines which meet several operational constraints, most notably the passengers' demand for transportation. Two objectives have been considered in the literature, and these reflect both sides of the story, viz service versus cost aspects. While travelers demand for convenient, ideally direct connections, railroads are forced to make most efficient use of their resources, not least for the reason of market deregulations. Minimizing operational cost is the focus of our investigation as well.

Both, linear and non-linear integer programming are adequate and intuitive modeling approaches for this problem. We present a heuristic variable fixing procedure which builds on problem knowledge from both techniques. We derive and compare lower bounds from different linearizations in order to assess the quality of our solutions. The involved integer linear programs are strengthened by means of problem specific valid inequalities. Computational results with practical data from the Dutch Railways indicate that our algorithm gives excellent solutions within minutes of computation time.

Funded by:
bmb+f
Research program: Application Oriented Joint Projects in Mathematics

Participants: Michael Bussieck, Thomas Lindner, Marco Lübbecke, Uwe Zimmermann

Journal Article: PostScript PDF
Ph.D. thesis: PDF

Optimal scrap combination in steel production (1997)


In steel production, scrap metal is used for cooling the enormous quantity of heat produced by blowing oxygen on hot metal. Scrap differs in regard to the content of iron and of some tramp elements. The price of the scrap depends on these attributes. Each melting bath unit of steel has its own material constraints for the amount of iron and tramp elements in order to guarantee the desired quality. In addition, the transportation of scrap is restricted because it needs time and space: the scrap is kept in some railroad cars in the scrap hall; empty cars must leave the hall, filled cars must be taken from several railroad tracks in the scrap yard and assembled to a train before transportation to the hall. There are upper limits for the number of cars in the hall and in the train, also for the number of railroad tracks used for assembly. Our objective is to find a minimum cost scrap combination for each melting bath unit of steel that obeys the material and transportation constraints. We model the problem using a mixed integer linear programming approach. Real-life situations are solved. We present computational results which show significant improvement compared to the strategy applied today.

Cooperation with:
HKM
Hüttenwerke Krupp Mannesmann

Participants: Michael Bussieck, Thomas Lindner, Marco Lübbecke, Uwe Zimmermann

Journal Article: PostScript PDF

Vertex enumeration for 0/1 polytopes

zerOne

Given the linear description P = {x | Ax <= b} of a polytope P entirely contained in the unit hypercube {0 <= x <= 1}, our software zerOne dumps P's integral vertices. In other words, it lists all vertices with all coordinates equal to zero or one (regardless of the 0-1 property of P). This is a frequent (sub-)task when designing models or analyzing the associated (integral) polytopes in combinatorial optimization and is usually done by listing (virtually or actually) all vertices and filtering out the integral ones.

Unlike incremental algorithms for more general input (e.g., porta), our algorithm has an output independent memory consumption and runs in time linear in the output (which, by the way, is the theoretical achievement here). Currently, the code relies on a working CPLEX licence installed on your machine.

Participants: Michael Bussieck, Marco Lübbecke

Journal Article: PostScript PDF
Software download from the zerOne home page

Last modified: Thu Oct 7 06:56:34 CEST 2010 Valid CSS!