Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 12 von 15
Zurück zur Trefferliste

An Approximation Algorithm for the Non-Preemptive Capacitated Dial-a-Ride Problem

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-6217
  • In the Capacitated Dial-a-Ride Problem (CDARP) we are given a transportation network and a finite set of transportation jobs. Each job specifies the source and target location which are both part of the network. A server which can carry at most $C$~objects at a time can move on the transportation network in order to process the transportation requests. The problem CDARP consists of finding a shortest transportation for the jobs starting and ending at a designated start location. In this paper we are concerned with the restriction of CDARP to graphs which are simple paths. This setting arises for instance when modelling applications in elevator transportation systems. It is known that even for this restricted class of graphs CDARP is NP-hard to solve. We provide a polynomial time approximation algorithm that finds a transportion of length at most thrice the length of the optimal transportation.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Sven Krumke, Jörg Rambau, Steffen Weider
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:NP-completeness; polynomial-time approximation algorithms; stacker-crane problem; vehicle
MSC-Klassifikation:68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Qxx Theory of computing / 68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) [See also 68Q85]
68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Qxx Theory of computing / 68Q25 Analysis of algorithms and problem complexity [See also 68W40]
Datum der Erstveröffentlichung:19.12.2000
Schriftenreihe (Bandnummer):ZIB-Report (00-53)
ZIB-Reportnummer:00-53
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.