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.


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

Leave a Reply

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

You are commenting using your 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: