Euler is standing in line dial-a-ride problems with precedence-constraints

Citation
D. Hauptmeier et al., Euler is standing in line dial-a-ride problems with precedence-constraints, DISCR APP M, 113(1), 2001, pp. 87-107
Citations number
17
Categorie Soggetti
Engineering Mathematics
Volume
113
Issue
1
Year of publication
2001
Pages
87 - 107
Database
ISI
SICI code
Abstract
In this paper we study algorithms for "Dial-a-Ride" transportation problems . In the basic version of the problem we are given transportation jobs betw een the vertices of a graph and the goal is to find a shortest transportati on that serves all the jobs. This problem is known to be NP-hard even on tr ees. We consider the extension when precedence relations between the jobs w ith the same source are given. Our results include a polynomial time algori thm on paths and approximation algorithms for general graphs and trees with performances of 9/4 and 5/3, respectively. (C) 2001 Elsevier Science B.V. All rights reserved.