Personal planning, freight transport, network extentions or charging of automatic teller machines, all state problems in logistics. Although the problems sound very different, all of them have one thing in common. They are solvable by models and methods from discrete optimization. Why using discrete optimization methods? Because they provide provably good solutions, because they can approximate the potential of further improvements, and because this way new strategies can be developed producing solutions that were tought to be out of reach so far. The following projects document some of our success stories.
Robust Network Design
In this project, we address a robust network design problem where the traffic demands change over time. For k different times of the day, we are given for each node the single-commodity flow it wants to send or to receive. The task is to determine the minimum-cost edge capacities such that the flow can be routed integrally through the net at all times.
Expansion of the German Rail Freight Network
In recent years, rail freight traffic in Germany has attained a significant growth. In contrast, the expansion of the available transportation capacities in the German railway network has always dragged behind this development. The short term drop in demand due to the economic crisis offers the opportunity to make up for this deficit. The goal is to prepare the railway network for the demand growth forecasted for the upcoming years. Recent studies predict annual growth rates of 5% within the next 15 years, which would result in a freight traffic more than twice as high as nowadays. This requires extensive investments in the construction of new tracks and the expansion of existing ones.
Robust Schedules for Air Traffic Management
Increasing air traffic and new procedures in air traffic management require a very efficient use of limited ATM resources. It is impossible to create schedules for future use which never need to be adapted. Reasons are e.g., unexpected weather conditions, late passengers, and intended and unintended deviations from schedules. We tackle scheduling problems in ATM, like the planning of airplanes on runways. Therefore, the focus of the assigned task lies on modeling, understanding and controlling uncertainty in ATM problems. So it is important to concern with Resilience and Adaptation to continue having air transport and to be competitive to alternative transportation. Thus we have to accept these phenomena and have to incorporate uncertainty into the model.
RobustATM: Robust Optimization of ATM Planning Processes by Modelling of Uncertainty Impact
As possibilities of enlarging airport capacities are limited, one has to enhance the utilization of existing capacities in Air Traffic Management (ATM) to meet the continuous growth of traffic demand. Therefore, it is crucial for the performance of the whole ATM System that the traffic on a runway is planned efficiently. However, uncertainty, inaccuracy and non-determinism almost always lead to deviations from the actual plan or schedule. A typical strategy to deal with these changes is a regular re-computation or update of the schedule. These adjustments are performed in hindsight, i.e. after the actual change in the data occurred. The challenge is to incorporate uncertainty into the initial computation of the plans so that these plans are robust with respect to changes in the data, leading to a better utilization of resources.
Robust Power Load Balancing in Railway Networks
The aim of this project are robust train schedules with respect to the power consumption from the power supply stations. The input is a given schedule which is slightly adapted to desynchronize simultaneous train departures. On the other hand, train departures are synchronized with the recuperation phases of other trains to make use of their braking energy. Preliminary results show that significant savings with respect to the provision of reserve power can be achieved.
Free Flight Optimization
Based on the increasing relevance of aviation as a crucial component of the modern traffic, the use of optimal flight paths gains in importance. There have been severe instructions ascertaining on which path a plane is allowed to fly which have constrained the possible flight paths. The so-called Air Traffic Network (ATN) consists of arterial roads and it was only permitted to fly along these specified streets. The ATN describes all segments of possible paths in the structure of a graph. By means of this graph, the best possible flight path could be determined, for example with the help of a shortest path algorithm like Dijkstra's Algorithm. By now, aviation is used more and more which exceeds the capacity of the existing airways. Furthermore, the accuracy of the navigation has been improved. Therefore, it can be done without the demand of an ATN and flight paths can be chosen more freely in the airspace. We call the possibility of finding flight paths independent from the ATN free flight. This gives the possibility to compute and fly shorter and more efficient routes. From this approach it is also expected that delays and charges caused by the ATN can be reduced.
Vehicle Scheduling in Rail Freight Service
Due to many contributions on vehicle scheduling, much progress has been made in this field in recent years. However, additional constraints like maintenence planning and homogenity make it remain a challenging optimization problem, especially for large instances. We support DB Mobility Logistics AG in developing an optimization algorithm for rail freight service.
Consolidating Car Routes in Rail Freight Service
One of the most significant measures for costs in rail freight transportation is the number of train miles, that is, the number of trains times the distance they travel. In order to reduce the number of train miles, the aim is to find routes for the cars through the network from their origin via possibly visited intermediate shunting yards to their destination, such that the cars travel as a bundle and the utilization of the trains is as high as possible.
Optimization and Simulation of Duty Rosters for Railway Crews
Employees of transportation companies typically work in shifts at irregular times. These shifts have to be served every day of the year including weekends and bank holidays. Also, a lot of shift changes occur at short notice, which may result from construction sites or illness of the drivers. The aim of our work was to generate cost-efficient duty rosters that are valid with respect to the regulations of the labor agreements but more stable with respect to real-life influences.
Optimizing Aircraft Rotation in Passenger Transport
Scheduling planes to planned flights alone has high optimization potential. Combining this with the permission to make small changes on the departure times (time windows) makes it even more promising – though much harder to solve.
Facility Location Problems
Facility Location Problems deal with the problem of deciding where to open certain facilities in order to serve a given set of customers best possible. These problems show up in various application arising in telecommunication, energy supply or parallel computing. In this project we develop optimization methods that provide solutions of proven quality.
UMTS site location and configuration
The Universal Mobile Telecommunications System (UMTS) is a 3rd generation cellular system for mobile telecommunication. The project aimed at planning UMTS radio networks. We formulated the problem as mixed-integer program with the aim to select and configure base stations (including height, azimuth, tilt and antenna type). The objective was to minimize the cost for the network while certain capacity restrictions were to be met.