On the Dial-a-Ride problem

Dial-a-Ride problem: Given an undirected graph G = (V,E) with a non-negative length function l : E \rightarrow \mathbb{R}^{+}, a set of m ordered source-destination pairs (demand pairs) \{(s_i, t_i)\}_{i=1}^{m} \subset V \times V (each requiring an item to be carried from s_i to t_i), and a vehicle with capacity k, 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 k.

  • 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, G=(V,E). Mark any one of the vertices in V as the source vertex, and mark the remaining vertices |V|-1 vertices as destination vertices, to obtain |V|-1 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 (V,d).
  • 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: