An Approximation Algorithm for the Non-Preemptive Capacitated Dial-a-Ride Problem
Please always quote using this 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.
Download full text files
Additional Services
| Author: | Sven Krumke, Jörg Rambau, Steffen Weider |
|---|---|
| Document Type: | ZIB-Report |
| Tag: | NP-completeness; polynomial-time approximation algorithms; stacker-crane problem; vehicle |
| MSC-Classification: | 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] | |
| Date of first Publication: | 2000/12/19 |
| Series (Serial Number): | ZIB-Report (00-53) |
| ZIB-Reportnumber: | 00-53 |
