On the Dial-a-Ride problem
July 29, 2010 Leave a comment
Dial-a-Ride problem: Given an undirected graph with a non-negative length function , a set of ordered source-destination pairs (demand pairs) (each requiring an item to be carried from to ), and a vehicle with capacity , find a minimum length tour which satisfies all demand pairs such that the number of items carried by the vehicle during any point in the tour does not exceed .
- The problem definition may or may not specify a particular starting vertex for the tour.
- Dial-a-Ride is a restricted version of k-delivery TSP. k-delivery TSP allows an item from any particular source to be carried to any of the specified destinations, and hence generalizes Dial-a-Ride.
- Dial-a-Ride generalizes TSP, and hence is NP-hard. Consider a TSP instance, . Mark any one of the vertices in as the source vertex, and mark the remaining vertices vertices as destination vertices, to obtain demand pairs. Set the capacity of the Dial-a-Ride tour vehicle to be arbitrarily high (infinite), and set the starting vertex as the one selected to be the source. A Dial-a-Ride tour on the reduced instance corresponds to an optimal TSP tour on the original instance.
- There are two versions of the Dial-a-Ride problem. The preemptive version allows an item to be dropped off by the vehicle at an intermediate location (different from its destination). The non-preemptive version is more restrictive and does not allow this freedom.
- Metric version: Here the underlying graph is an n-vertex metric space .
- Dial-a-Ride on the tree metric: The source and destination points are assumed to be on the leaves. Apart from this restriction, the problem statement remains the same as before.