Deferment Control for Reoptimization – How to Find Fair Reoptimized Dispatches
Abstract:
The german automobile association ADAC maintains a fleet of 1700 vehicles and has agreements with around 5000 service contractors. With these ressources, they help people whose cars have broken down on the road. Those people can call an ADAC help center, and within 10 seconds, an assignment of a service ressource to their request is made. At the same time, for all service vehicles, tours through the assigned requests have to be planned so as to minimize a certain (complicated) cost function for this so-called dispatch.No useful knowledge about future requests is available at the time being. Therefore, the current policy of the automated system, developed in joint work with Sven O. Krumke, is to reoptimize the whole dispatch upon the occurrence of each relevant event, like the arrival of a new request. A similar online-optimization problem appears in the pallet elevator group control in a large distribution center of Herlitz PBS AG in Falkensee near Berlin.
The problem with reoptimization policies in general is that, depending on the reoptimization objective, an arbitrarily large deferment of individual requests can be observed. In a way, individual requests are sacrificed in favor of a good performance according to the reoptimization objective. Nevertheless, w.r.t. the reoptimization objective, the reoptimization policies in the long run usually perform much better than the currently known policies that can not cause infinite deferment. Therefore, the goal is to modify reoptimization policies so as to prevent deferment.
Sometimes deferment can be almost eliminated by enhancing the reoptimization objective with some terms that penalize waiting, but service in a fixed time can still not be guaranteed, and this kind of objective function engineering is a very time consuming tuning issue, interfering with the orgininal management objective.
In this talk, the policy of flow and makespan constrained reoptimization with reoptimization admission control is presented. It has the property that, under so-called d-reasonable load, for any reoptimization model, this policy yields a maximal flow time that is bounded by a constant 2d, depending only on the system load parameter d, not on the instance. In simulation experiments for the elevator group control problem we still obtain a very satisfactory average performance w.r.t. the reoptimization objective.
Biography:
Jörg Rambau studied mathematics from 1987 through 1993 at the Ruhr-Universität Bochum, Germany, with focus on algebraic topology. 1996, he received his PhD. under the supervision of Günter M. Ziegler in the field of discrete geometry. From 1996 through 2004, he worked in Martin Grötschel's optimization group at Zuse Institute Berlin, where he became associate head in 2000. After his habilitation in 2002 at Technical University Berlin, he became accepted a call to the chair for Business Mathematics at the University of Bayreuth. His current research interests reach from (multistage stochastic) integer programming models for OR applications to triangulations in discrete geometry.