License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-668
URL: http://drops.dagstuhl.de/opus/volltexte/2005/66/
Go to the corresponding Portal


Rambau, Jörg

Deferment Control for Reoptimization -- How to Find Fair Reoptimized Dispatches

pdf-format:
Document 1.pdf (112 KB)


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 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.

BibTeX - Entry

@InProceedings{rambau:DSP:2005:66,
  author =	{J{\"o}rg Rambau},
  title =	{Deferment Control for Reoptimization -- How to Find Fair Reoptimized Dispatches},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  year =	{2005},
  editor =	{Susanne Albers and Rolf H. M{\"o}hring and Georg Ch. Pflug and R{\"u}diger Schultz},
  number =	{05031},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2005/66},
  annote =	{Keywords: online optimization , dynamic vehicle dispatching , reoptimization , integer linear program , dynamic column generation , infinite deferment ,}
}

Keywords: online optimization , dynamic vehicle dispatching , reoptimization , integer linear program , dynamic column generation , infinite deferment ,
Seminar: 05031 - Algorithms for Optimization with Incomplete Information
Issue Date: 2005
Date of publication: 30.05.2005


DROPS-Home | Fulltext Search | Imprint Published by LZI