Dynamic Multi-Period Routing With Two Classes

  • In the Dynamic Multi-Period Routing Problem, one is given a new set of requests at the beginning of each time period. The aim is to assign requests to dates such that all requests are fulfilled by their deadline and such that the total cost for fulling the requests is minimized. We consider a generalization of the problem which allows two classes of requests: The 1st class requests can only be fulfilled by the 1st class server, whereas the 2nd class requests can be fulfilled by either the 1st or 2nd class server. For each tour, the 1st class server incurs a cost that is alpha times the cost of the 2nd class server, and in each period, only one server can be used. At the beginning of each period, the new requests need to be assigned to service dates. The aim is to make these assignments such that the sum of the costs for all tours over the planning horizon is minimized. We study the problem with requests located on the nonnegative real line and prove that there cannot be a deterministic online algorithm with a competitive ratio better than alpha. However, if we require the difference between release and deadline date to be equal for all requests, we can show that there is a min{2*alpha, 2 + 2/alpha}-competitive algorithm.

Volltext Dateien herunterladen

Metadaten exportieren

  • Export nach Bibtex
  • Export nach RIS

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:Sven O. Krumke, Christiane Zeck
URN (Permalink):urn:nbn:de:hbz:386-kluedo-16615
Schriftenreihe (Bandnummer):Report in Wirtschaftsmathematik (WIMA Report) (129)
Dokumentart:Bericht
Sprache der Veröffentlichung:Englisch
Jahr der Fertigstellung:2010
Jahr der Veröffentlichung:2010
Veröffentlichende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):16.08.2010
Fachbereiche / Organisatorische Einheiten:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011

$Rev: 13581 $