Logistics and Production

Logistics and Production

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.

Ongoing Projects

Joint Locomotive Scheduling and Driver Rostering in Rail Freight Traffic

This project aims at developing solution methods for problems arising in the operations management of the railway companies. More specifically, locomotives and their drivers need to be assigned to trains in order to generate shift plans. These in turn need to consider working time regulations, locomotive maintenance needs as well as the compatibilities between trains, drivers and locomotives. Also, some of the company-specific planning requirements need to be taken into account.

For that end, we develop a large and complex binary model. It combines the structures of set covering with multiple-choice constraints with multicommodity-flow problem. We also devise a novel decomposition approach to allow for the solution of the problem, dividing the model into a master locomotive scheduling problem and driver rostering subproblem. We also supplement it with a presolve heuristic for the difficult subproblem.

When implemented into the planning systems of the industrial partner, our approach will enable efficiency increases. It will also allow for a significant simplification of planning process.

This project is developed in collaboration with DB Cargo Polska. It is a company from the network of DB Cargo AG. With 2800 employees, 220 locomotives and 2820 wagons, it is the second largest rail freight carrier in Poland in terms of weight carried.

Our project is a part of a ROMSOC – an European Industrial Doctorate program aiming at development of novel mathematical modeling, simulation, and optimization as well as model order reduction techniques for numerous industrial applications (including adaptive optics, lightning, microchip design, finance and others).

Participants: Andreas Bärmann, Jonasz Staczek

Driver Assistance Systems in Railway Traffic

In energy-efficient timetabling, the aim is to bring the following three targets into balance:
– the choice of energy-efficient velocity profiles of the trains.
– increasing the the utilization of recuperated braking energy.
– limiting peak power consumption.

This project builds on previous experience of the chair in the design of energy-efficient railway timetables. In a joint cooperation with Deutsche Bahn AG, we have derived efficient model formulations and decomposition schemes to compute timetables which limit peak power consumption by avoiding too many simultaneous train departures. This includes approaches to maximize the use of recuperated braking energy by favourably synchronizing the departures and departures of the trains. In a later project with VAG Verkehrs-Aktiengesellschaft Nürnberg, we have derived extensions of the methods to include the choice of energy-efficient velocity profiles of the trains.

The next target will now be to make the above methods work in real-time, which represents a significant and ambitious step forward. It means that an optimal control of the train departures in the stations and the velocity profiles on the tracks shall occur in real time, realized via a driver assistance system. The mathematical methods we use for this purpose are based on mixed-integer linear programming, which enables the inclusion of logical constraints as they are prevalent in timetable optimization. In our work, we thus aim to resolve the following challenges to algorithm development:
– Optimization of the velocity profiles of a train: For the non-linear differential equations governing the driving behaviour of a trains, we develop efficiently solvable linearizations which allow for the computation of velocity profiles in real-time. They are continuously updated and communicated to the driver in the form of an assistance system.
– Forecasting of traffic situations in the railway: As a basis for forward-looking driver assistance systems, we develop algorithms of machine learning and data science which allow to extrapolate the local, short-term history of traffic flow in the vicinity of a given train. These forecasts form the basis for a globally coordinatedd optimization of the driving behaviour of the trains.
– Globally coordinated optimization of the departures and velocity profiles in Germany-wide railway traffic. In order to become utilizable for the 30,000 trains operated in German railway traffic each day, we derive efficient algorithms for the solution of timetable optimization problems under ressource constraints. In order to make them solvable in real time, we conduct dedicated polyhedral studies and develop branch-and-cut algorithms based on their results. Furthermore, we derive stochastic extensions of the underlying models to incorporate the short-term traffic forecasts from the prior step. This allows to make the computed timetables robust against disruption in traffic flow.

The overarching aim is to create a driver assistance system which incorporates a combination of artificial intelligence and mathematical models for energy-efficient train control. As a perspective, we aim to develop these techniques further to make them the core of a future autonomous train control system.

 

Participants: Andreas Bärmann, Patrick Gemander, Lukas Hager, Oskar Schneider

Optimized Production Planning in the Tea Industry

In this project, we work together with a leading German producer of herbal and fruit infusions as well as medicinal teas. The aim in this cooperation within the ADA Lovelace Center is to develop mathematical methods for the optimized selection of raw and semi-manufactured materials for tea production. The task is to select among all available batches of the ingredients on stock those which are best suited for the production of the tea mixtures ordered by the customers according to their recipe specifications. Most importantly, it has to be decided in an optimal fashion which precise batches are used for the production of each ordered mixture in order to attain the highest possible coverage of fulfilled production orders at any given point in the planning horizon. In doing so, the defined quality requirements of the customers, as well as all market demands concerning the final products, have to be met. By an optimal utilization of the available batches, the company will be able to benefit from high savings in production costs and a much more sustainable stock management. Furthermore, an automated generation of proposals for the production plans will significantly shorten the time and effort required in the planning phase. This will free up resources that can be dedicated to addressing more strategic questions in customer demand satisfaction.

Participants: Andreas Bärmann, Oskar Schneider

Energy-Efficient Timetable Optimization in the Nuremberg Underground System

©VAG – Claus

A significant part of the electricity cost incurred by VAG Verkehrs-Aktiengesellschaft Nürnberg is due to the traction energy of the trains in the Nuremberg underground system. These costs can be reduced significantly by optimization the driving behaviour of the trains in an energy-efficient fashion. VAG already undertakes great efforts to educate their drivers to drive economically on the human-operated line U1. Furthermore, the computer-controlled automatic lines U2 and U3 are calibrated in the same fashion. Via the cooperation with the ADA Lovelace Center, the energy-efficiency of the underground system shall be increased further. To this end, we use the remaining degrees of freedom in the timetable planning phase such that on each segment between two stations, the train are operated with optimization velocity profiles. Moreover, the recuperated energy from braking trains shall be used best possible by other accelerating trains. The novelty in the approach lies in the fact the driving behaviour is not optimized for each train individually but in coordination with the behaviour of all other trains such that a global optimum in energy savings can be attained. At the same time, the approach keeps up the high level of service and convenience for the passenger as well as all safety restrictions and further operative requirements. Our results point to six-digit savings in energy costs every year.

Participants: Andreas Bärmann, Patrick Gemander, Lukas Hager

HOTRUN – Holistic optimization of trajectories and runway scheduling

Project Information

Supported by

This project is part of the German BMWi research program „Fünftes ziviles Luftfahrtforschungsprogramm, 3. Aufruf“ (BMWi). This program sponsors the development of technologies, which can be applied to solve various problems of the commercial aviation industry.

Description

The subproject „Entwicklung mathematischer Optimierungsmethoden für robustes Runway Scheduling“ (RobRun) executed by our group, aims at generating optimal schedules using discrete optimization methods and respecting aircraft trajectories. Furthermore, uncertainties will be considered by using techniques of robust optimization. This enables the user to compute trajectories and schedules which, for example, hedge against disruptions (in a predefined range), or are able to recover as efficient as possible after a disruption occurred.
Thus, the overall goal of this project is to combine trajectory and runway schedule computation, including resilience against uncertainties, in order to obtain stable flight routes and landing, resp. take off, times. From a theoretical point of view, the relatively young field of robust opimization offers a lot of space for the development of new methods and the planned integrated solution of optimal control (for trajectory planning) and combinatorial optimization problems (scheduling) has hardly been investigated and bears great potential.

People involved

  • Benno Hoch
  • Frauke Liers

Contact

For further details on this project, please contact Benno Hoch (benno.hoch[at]fau.de).
If you are interested in information about the BMWi’s aviation research program, click here.

OPs-TIMAL – Optimized processes for trajectory, maintenance and management of ressources and operations in aviation

Project Information

Contracting Entity: Federal Ministry of Economic Affairs and Energy (Opens external link in new windowBMWi)
Project Duration: 42 months, January 2018 – June 2021
OPs-TIMAL is executed by four universities and research institutes and nine industrial partners.

Supported by

This project is part of the German BMWi research program „Fünftes ziviles Luftfahrtforschungsprogramm, 3. Aufruf“ . This program sponsors the development of technologies, which can be applied to solve various problems of the commercial aviation industry.

Description

Within the joint research project OPs-TIMAL the FAU has two main contributions. The first one is to provide robust solutions for fleeting and routing aircrafts, also under uncertain conditions and under disruptions. Therefore it is necessary to find an effective algorithm, which should be structured in a way, that the outcome is a practicable flight plan – even in case of major disruptions. The second main part executed by the FAU is to supervise the combination of the partial solutions obtained by the project partners in a holistic optimization framework. Goals are to detect and compensate the conflicts between the partial solutions, to find holistic solutions and to realize benefits by taking advantage of dependencies.

People involved

  • Lukas Glomb
  • Frauke Liers
  • Florian Rösel

Contact

For further details on this project, please contact Florian Rösel (florian.roesel[at]fau.de) or Lukas Glomb (lukas.glomb[at]fau.de).
If you are interested in information about the BMWi’s aviation research program, visit.

Optimization of medical care in rural environments

HealthFaCT – Health: Facility Location, Covering, and Transport is a collaborative project of the BMBF-funding measure “Mathematics for Innovations in Industry and Services”.
HealthFaCT will be funded from December 01, 2016 to November 30, 2019.

Description

The main goal of HealthFaCT is the development of an innovative and software-aided system for optimization and decision making to improve three essential pillars of medical care: pharmacies, emergency physicians as well as scheduling of ambulances. The main focus of this project lies on rural environments. Mathematical methodologies can make an important contribution in terms of data-driven facts rather than political argumentation. Detailed information about the contents of this project can be found here.

Partners

HealthFaCT is executed by

Furthermore, Apothekerkammer Nordrhein, Kreisverwaltung Mainz-Bingen, Stadtverwaltung Kaiserslautern, Gesundheitsamt der StädteRegion Aachen, Informatikgesellschaft für Software-Entwicklung mbH and Gesundheitsregion plus Erlangen-Höchstadt & Erlangen take also part in HealthFaCT. The HealthFaCT team also cooperates with IBOSS.

 

Poster

Process optimization for hospital logistics

Project Information

  • Contracting Entity: OrgaCard Siemantel & Alt GmbH
  • Minimal Project Duration: 24 months, January 2020 – December 2021

Description

This project aims at developing solution methods for problems arising in the logistics management of the public health care sector. More specifically, transport orders in hospitals or other medical facilities should be allocated to employees in order to generate a plan of transport, that also incorporates the routes and execution times of all orders. In this plan, the routing of the transport orders shall be computed considering the infectiousness of the patients, the properties of the means of transportation and, among other requirements, the location of the responsible employee. Moreover the scheduled plan shall minimize order delays, transport distances and the burden of executing employees or other configurable criteria specified by the customers of OrgaCard.
Thus, the overall goal of this project is to organize transport logistics of medical facilities in an integrated mathematical framework in real time, using techniques of machine learning and combinatorial respectively discrete optimization.

News

 

The DMEA Young Talent Award is presented annually to the best Bachelor and Master theses in the fields of medical informatics, e-health, health IT, health management, health economics and healthcare management. In 2020, Alexander Müller’s master’s thesis “Ein Spaltenerzeugungsalgorithmus zur Optimierung von Transporten im Krankenhaus“ took first place in the master’s thesis category.

Link: https://www.dmea.de/Presse/News-Blog/Artikel/DMEA-Nachwuchspreis2020DieDiesjaehrigenGewinnerinnenUndGewinner.html

Alexander Müller, as last years winner of the DMEA Young Talent Award,
was interviewed by the organisers of the DMEA.

The interview can be read here:
https://www.dmea.de/Presse/News-Blog/Artikel/DMEA-NachwuchspreistraegerImPortraet.html

People involved

Contact

Link:  https://www.orgacard.de/software-loesungen/logistik/logistik-management/

Finished Projects

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.

Participants: Andreas Bärmann

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.

Participants: Frauke Liers

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.

 

Participants: Andreas Heidt

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.

 

Participants: Andreas Bärmann

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.

 

Participants: Andreas Heidt, Manu Kapolke, Frauke Liers

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.

Participants: Alexander Martin, Andrea Peter, Armin Fügenschuh

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.

Participants: Hanno Schülldorf

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.

Participants: Henning Homfeld

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.

Participants: Henning Homfeld, Andrea Peter, Christine Hayn

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.

Participants: Henning Homfeld

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.

Participants: Alexander Martin

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.

Participants: Alexander Martin