Transportation systems (e.g. automated shelf systems, automated guided vehicles) are targeted to accomplish their tasks as efficiently as possible. However, many aspects of transportation problems are inherently online. During the operation decisions have to be made without knowledge of future events which might be relevant for the current choice: new transportation requests arrive and old ones are cancelled; unpredictable disruptions and jams change the system state. Thus, these systems require online planning; good decisions how to handle requests must be made in real time while the system is running .
Competitive analysis has become one standard yardstick to measure the quality of online algorithms. In competitive analysis one compares the solution produced by an online algorithm to that of an optimal (clairvoyant) offline algorithm. This analysis is often overly pessimistic since the ``offline adversary'' against which performance is measured is extremely powerful. An online strategy might perform well for inputs occuring in practice, but badly compared to the optimal offline algorithm in some situations; thus it would be ruled out as a good algorithm from a competitive analysis point of view. For online transporation and logistic systems there had not been any concept in literature to disallow ridicously high requirements for the system to affect the theoretical analysis. Goal of the project is the design and analysis of mathematical models for online (and real-time) problems which can be used in practice. Our focus is on combinatorial optimziation problems (with stochastic components) in transportation and logistics. We aim at designing online algorithms with mathematically provable performance guarantees. For selected specific transportation problems we want to construct real-time capable algorithms and to test their applicability in practice. This is done in cooperation with partners from industry.
In the longer run, we aim implementing a complete simulation of the transportation system of the Herlitz PBS AG. This is accomplished with the help of AMSEL, a discrete event oriented simulation tool developed at the Konrad-Zuse-Zentrum; simulation enables us to verify the quality of the models and algorithms for practice relevant situations by using real data.
