Eingang zum Volltext

Urheberrechtshinweis / Copyright notice

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URL: http://opus.kobv.de/zib/volltexte/2004/793/

Hiller, Benjamin ; Krumke, Sven O. ; Rambau, Jörg

Reoptimization Gaps versus Model Errors in Online-Dispatching of Service Units for ADAC

pdf-Format:
Dokument 1.pdf (328 KB) (Final version) Dokument 2.pdf (1.046 KB) (Original Version) Dokument 3.pdf (216 KB) (Revised Version (DEC04))
ps-Format:
Dokument 1.ps (551 KB) (Original Version) Dokument 2.ps (838 KB) (Revised Version (DEC04))

Kurzfassung in Englisch

Under high load, the automated dispatching of service vehicles for the German Automobile Association (ADAC) must reoptimize a dispatch for 100--150 vehicles and 400 requests in about ten seconds to near optimality. In the presence of service contractors, this can be achieved by the column generation algorithm ZIBDIP. In metropolitan areas, however, service contractors cannot be dispatched automatically because they may decline. The problem: a model without contractors yields larger optimality gaps within ten seconds. One way-out are simplified reoptimization models.
These compute a short-term dispatch containing only some of the requests: unknown future requests will influence future service anyway. The simpler the models the better the gaps, but also the larger the model error. What is more significant: reoptimization gap or reoptimization model error? We answer this question in simulations on real-world ADAC data: only the new model ZIBDIP{\footnotesize dummy} can keep up with ZIBDIP.

Freie Schlagwörter (englisch): vehicle dispatching , soft time windows , online , real-time , ADAC , optimality gap , high load
MSC - Klassifikation 90B06
Abteilung: ZIB Allgemein
DDC-Sachgruppe: Allgemeines, Wissenschaft
Dokumentart: ZIB-Report
Schriftenreihe: ZIB-Report
Band Nummer: 04-17
Quelle: The rev. vers. appeared in: Electronic Notes in Discrete Mathematics Vol. 18, 1 December 2004, 157-163. The final vers. appeared in: Discrete Applied Mathematics 154 (2006) 1897-1907
Sprache: Englisch
Erstellungsjahr: 2004
Publikationsdatum: 25.05.2004

Metadatensuche | Volltextsuche | Browsen | Die neuesten Publikationen | Veröffentlichen
Fragen und Anregungen an bibliothek@zib.de
Letzte Änderung: