Simulation of uncertain Optimization problems with applications for train scheduling and machine scheduling

Uncertainties occur in most practically relevant optimization problems: Often, not all of the important parameters are known in advance. In economic problems, for example, price developments, sales or demand figures have to be estimated. When it comes to technical problems, physical parameters can often be determined only with certain inaccuracies. It is particularly difficult to plan for unexpected interferences as they occur in traffic networks or during the execution of major projects. A set of possible values for these unknown parameters is denoted as a scenario.

In this project, uncertainty or interference should be included already during the planning process by means of simulation. This approach exploits the fact that there are efficient algorithms for finding optimal solutions for a given fixed scenario. On the other hand, the quality of a given solution under various scenarios can be evaluated by simulation. This optimization algorithms and the simulation are to be connected in an iterative process with each other in order to derive robust solutions or good online strategies. By including given probability distributions on the set of possible scenarios, the disadvantages of conservative strategies for robust optimization and online optimization can be mitigated - thus creating new concepts combining robust and stochastic optimization.

The method to be developed for optimization under uncertainty shall be applied to two specific network optimization problems from transport and logistics:

• It shall be used to develop robust (which means "less susceptible to interference") timetables for public transport. Based on real-world data from the software package LinTim, a macroscopic simulation of delays shall be compared with those computed by an agent-based simulation.
• The individual production sites of the truck manufacturer MAN and the flow of goods between them constitute an economic network that is subject to many uncertainties. Our goal is, to apply our method to real world data provided by MAN, in order to develop strategies for better synchronization of the individual stages of the underlying complex production networks.

In the case that uncertainty or interference should already be taken into account in the planning process, we speak generally of an optimization problem under uncertainty. There are various mathematical disciplines that deal with the optimization under uncertainty: In robust optimization no probability distributions of uncertain parameters are provided. Instead, one tries to hedge against the worst case. In stochastic optimization optimal strategies are developed based on a known probability distribution and often aim at a solution with the best expected objective function value. Another objective may be to minimize the likelihood of infeasible or very bad solutions. In online optimization, strategies are developed, how to deal with uncertainties at the time of their occurrence. These three approaches to the treatment of uncertain problems are usually considered separately. Nevertheless, there is some recent work comparing these concepts with each other.

In order to find a strictly robust solution or a competitive online strategy, the worst case always has to be considered when evaluating a solution or strategy: in robust optimization the planner wants to protect himself against the worst case scenario and in order to determine the competitivity of an online algorithm the worst case has to be considered as well. The basic idea of our approach now is to use such worst-case scenarios to iteratively perform the following two steps:

• For one (or more) fixed scenarios a robust solution or an optimal online strategy is determined by optimization.
• For a given solution or strategy their quality is evaluated through simulation. This way, a worst-case scenario for this solution/strategy is determined.

The worst-case scenario which has been found in the simulation step can then be used as a given scenario in the optimization step. In contrast to simulation-based optimization, simulation is here not just used as a black box but collects insights about worst-case scenarios during the simulation step. These insights then help to determine new solutions or strategies.

• Prof. Dr. Stephan Westphal
• Prof. Dr. Anita Schöbel