# 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.