# More on the Dial-a-Ride problem

We present here a so-called Structure Theorem given by Gupta et al. [1] for the non-preemptive Dial-a-Ride problem on an n-vertex metric space $(V,d)$ having $m$ demand pairs, and a specified start vertex, $r$.

We say that a vehicle is in a pick-up phase during some portion (segment) of a tour, if it only performs pick-ups during that time interval. Similarly, we say that a vehicle is in a delivery phase during a particular segment if it only performs deliveries in that segment. If the optimal tour had a structure which allowed it to be split into pick-up and delivery phases, i.e. if the optimal tour could be split as follows: the vehicle first picks up a set of at most $k$ items; it then delivers each of those items to their destinations; it again picks up a set of at most $k$ items, and so on, – we would have been able to apply the greedy paradigm for the problem. We could select a best-possible set of (at most $k$) items to service during a segment.

However, the optimal tour may not exhibit such a structure. Gupta et al. show that a near-optimal tour displays this property.

Theorem 1. Given an instance of non-preemptive Dial-a-Ride, there exists a feasible tour, $\tau$ within $O(\log {m})$ of optimal, such that $\tau$ can be split into a set of segments – $\tau = S_1. S_2 ... S_t$, wherein each segment, $S_i$ services a set, $O_i$ of at most $k$ demand pairs (items) by first picking up all items in $O_i$ and then delivering them to their respective destinations.

Proof. Consider an optimal tour $\sigma$. Represent $\sigma$ as a line $L$ such that every edge in $L$ corresponds to an edge traversal in $\sigma$. The $i^{th}$ edge of $L$ corresponds to the $i^{th}$ edge traversed in $\sigma$. (That is, $L$ is simply the tour $\sigma$, wherein vertices visited multiple times in $\sigma$ are represented that many times in $L$.)

By the triangle inequality, we have that the number of edges in $\sigma$, denoted by $| \sigma |$ (equal to the number of edges in $L$) is at most $2m + 1$.

Let $d(\sigma)$ denote the length of $\sigma$.

Define stretch of item $i$ as the number of edges traversed in $\sigma$ after it is picked up, and before it is delivered (i.e. the number of edges it travels on the vehicle).

Divide the $m$ items into groups $G_j$, $j = 1, ..., \lceil \log {(2m)} \rceil$, such that $G_j$ is the set of all items having stretch between $2^{j-1}$ and $2^j$.

We shall service items in each group separately.

Consider group $G_j$. Denote by $\tau_j$ the portion of the tour where items in $G_j$ are serviced.

We first prove a lemma relating to $\tau_j$.

Lemma 2. There exists a tour $\tau_j$ of length at most $6 d(\sigma)$, such that $\tau_j$ can be divided into a set of segments, each servicing at most $k$ items in a manner similar to that stated in Theorem 1.

Proof. Let $r = 2^{j-1}$. Divide $L$ into segments having $r$ edges each. There are $\lceil \frac { |\sigma|} {r}$ such segments- the first $r$ edges in $L$ form the first segment (denoted by $T_{1,j}$), the next set of $r$ edges forms segment $T_{2,j}$, and so on.

Denote the set of items originating in segment $T_{l,j}$ by $O_{l,j}$. (i.e. Items in $O_{l,j}$ have sources between vertices $(l-1)r$ and $lr -1$. Note that items in $O_{l,j}$ are exactly those items that cross edge $(lr-1, lr)$ in $\sigma$. This implies that $|O_{l,j}| \leq k$. Note also that items in $O_{l,j}$ have destinations between the vertices $lr$ and $(l+2)r - 1$.

Consider set $O_{l,j}$.

We service it as follows: Start the vehicle (initially empty) at vertex $(l-1)r$. Pick up items in $O_{l,j}$ originating in $T_{l,j}$. Deliver these items ($\leq k$) to their destinations in $T_{l+1,j}$ and $T_{l+2,j}$. Return with the empty vehicle to vertex $lr$. Denote by $\omega_{l,j}$ this portion of the tour where items in $O_{l,j}$ are serviced.

By concatenating the portions $\omega_{l,j}$ for possible values of $l$, we obtain a tour, $\tau_j$ that services all items in $G_j$.

We make the following observations:

• Each edge in $L$ is a part of at most 3 portions/segments: $\omega_{l,j}$.
• Each edge is traversed at most twice in any segment/portion.
• The number of items carried by the vehicle at any time in any $\omega_{l,j}$ is at most $k$.

The above observations make it clear that $\tau_j$ has length at most $6 d(\sigma)$ proving Lemma 2.

We service items in each of the $\lceil \log {(2m)} \rceil$ groups, $G_j$ similarly. We thus get a tour that is $O(\log {m}) d(\sigma)$, completing the proof of Theorem 1.

References:

[1] A. Gupta et al – Dial-a-Ride from k-forest, 2010.