TY - GEN A1 - Krumke, Sven A1 - Rambau, Jörg A1 - Weider, Steffen T1 - An Approximation Algorithm for the Non-Preemptive Capacitated Dial-a-Ride Problem N2 - 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. T3 - ZIB-Report - 00-53 KW - NP-completeness KW - polynomial-time approximation algorithms KW - stacker-crane problem KW - vehicle Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6217 ER -