More on the Dial-a-Ride problem
August 5, 2010 Leave a comment
We present here a so-called Structure Theorem given by Gupta et al.  for the non-preemptive Dial-a-Ride problem on an n-vertex metric space having demand pairs, and a specified start vertex, .
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 items; it then delivers each of those items to their destinations; it again picks up a set of at most 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 ) 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, within of optimal, such that can be split into a set of segments – , wherein each segment, services a set, of at most demand pairs (items) by first picking up all items in and then delivering them to their respective destinations.
Proof. Consider an optimal tour . Represent as a line such that every edge in corresponds to an edge traversal in . The edge of corresponds to the edge traversed in . (That is, is simply the tour , wherein vertices visited multiple times in are represented that many times in .)
By the triangle inequality, we have that the number of edges in , denoted by (equal to the number of edges in ) is at most .
Let denote the length of .
Define stretch of item as the number of edges traversed in after it is picked up, and before it is delivered (i.e. the number of edges it travels on the vehicle).
Divide the items into groups , , such that is the set of all items having stretch between and .
We shall service items in each group separately.
Consider group . Denote by the portion of the tour where items in are serviced.
We first prove a lemma relating to .
Lemma 2. There exists a tour of length at most , such that can be divided into a set of segments, each servicing at most items in a manner similar to that stated in Theorem 1.
Proof. Let . Divide into segments having edges each. There are such segments- the first edges in form the first segment (denoted by ), the next set of edges forms segment , and so on.
Denote the set of items originating in segment by . (i.e. Items in have sources between vertices and . Note that items in are exactly those items that cross edge in . This implies that . Note also that items in have destinations between the vertices and .
Consider set .
We service it as follows: Start the vehicle (initially empty) at vertex . Pick up items in originating in . Deliver these items () to their destinations in and . Return with the empty vehicle to vertex . Denote by this portion of the tour where items in are serviced.
By concatenating the portions for possible values of , we obtain a tour, that services all items in .
We make the following observations:
- Each edge in is a part of at most 3 portions/segments: .
- Each edge is traversed at most twice in any segment/portion.
- The number of items carried by the vehicle at any time in any is at most .
The above observations make it clear that has length at most proving Lemma 2.
We service items in each of the groups, similarly. We thus get a tour that is , completing the proof of Theorem 1.
 A. Gupta et al – Dial-a-Ride from k-forest, 2010.