Journal article
Minimum Makespan Multi-Vehicle Dial-a-Ride
Dial-a-Ride problems consist of a set V of n vertices in a metric space (denoting travel time between vertices) and a set of m objects represented as source-destination pairs {(s(i), t(i))}(i-1)(m), where each object requires to be moved from its source to destination vertex. In the multi-vehicle Dial-a-Ride problem, there are q vehicles, each having capacity k and where each vehicle j epsilon [q] has its own depot-vertex r(j) epsilon V.
A feasible schedule consists of a capacitated route for each vehicle (where vehicle j originates and ends at its depot r(j)) that together move all objects from their sources to destinations. The objective is to find a feasible schedule that minimizes the maximum completion time (i.e., makespan) of vehicles, where the completion time of vehicle j is the time when it returns to its depot r(j) at the end of its route.
We study the preemptive version of multi-vehicle Dial-a-Ride, in which an object may be left at intermediate vertices and transported by more than one vehicle, while being moved from source to destination. Our main results are an O(log(3) n)-approximation algorithm for preemptive multi-vehicle Dial-a-Ride, and an improved O(log t)-approximation for its special case when there is no capacity constraint (here t
Language: | English |
---|---|
Publisher: | ACM |
Year: | 2015 |
Pages: | 1-29 |
ISSN: | 15496333 and 15496325 |
Types: | Journal article |
DOI: | 10.1145/2629653 |
ORCIDs: | Gørtz, Inge Li |
APPROXIMATION ALGORITHMS Approximation algorithms BULK NETWORK DESIGN COMPUTER DELIVERY PROBLEM GRAPHS MATHEMATICS, PICKUP ROUTING-PROBLEMS scheduling vehicle routing