|
|||
|
IMADA - Department of Mathematics and Computer Science |
|
The Multi-Vehicle Dial-a-ride problem consists of a set V of n vertices in a metric space (denoting travel time between vertices) and a set of objects represented as source-destination pairs (si,ti), i=1,...,m, where each object requires to be moved from its source to destination. The objects are served by a set of q vehicles each having a finite capacity k, where each vehicle j originates at depot rj. A feasible schedule consists of a capacitated route for each vehicle (where the route of vehicle j starts and ends at its depot rj) that together move all objects from their sources to destinations. We consider multi-vehicle dial-a-ride with the objective of finding a feasible schedule that minimizes the maximum completion time of vehicles, where the completion time of vehicle j is the time when it returns to its depot rj at the end of its route. In the preemptive version, an object may be left at intermediate vertices while being moved from source to destination. For the uncapacitated case (i.e. vehicle capacity k=∞, we obtain an O(log t) approximation, where t is the number of distinct depot-vertices. Our main result is an O(log3 n) approximation algorithm for the general preemptive case. When the underlying metric is the Euclidean plane, we improve the guarantee to O(log2 n). The approximation factors also improve when all the q vehicles are located at a single depot, from O(log t) to 5 in the uncapacitated case and from O(log3 n) to O(log2 n) in the capacitated case. This is joint work with V. Nagarajan and R. Ravi. Host: Jørgen Bang-Jensen SDU HOME | IMADA HOME | Previous Page Daniel Merkle |