Deferment Control for Reoptimization – How to Find Fair Reoptimized Dispatches

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 usefule 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 new policy of flow and makespan constrained reoptimization with reoptimization admission control is introduced. The main result is that, under 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.