On the Dial-a-Ride problem – 2
July 29, 2010 Leave a comment
We consider here the capacitated Dial-a-Ride problem on the tree metric. The demand pairs are assumed to be on the leaves of the tree, .
- For each demand pair , we have a unique path from to in .
- Call all vertices which are on any of the paths as interesting.
- Call all edges which are on any of the paths as essential.
- Clearly, any tour that satisfies all demand pairs must cover all essential edges, and hence, all interesting vertices.
We present two lower bounds on the number of edge traversals in the optimal tour.
1. Steiner tree lower bound:- Let be the least cost Steiner tree spanning all interesting vertices. would include all essential edges, and if is not connected, will include other edges too. Clearly, any tour that satisfies all demand pairs must traverse every edge of at least twice. We call this the Steiner tree lower bound.
2. Flow lower bound:- With every edge in , we associate two quantities and . For every edge , fix, for the purpose of computation of and , an ordering of the end points. equals the number of paths, which require an item to pass from vertex to vertex . corresponds to the number of paths, which require an item to pass from vertex to vertex . (Here, ‘u’ denotes ‘upwards’, and ‘d’ denotes ‘downwards’.)
Clearly, for a vehicle of capacity , edge must be traversed at least in any feasible Dial-a-Ride tour. We call this the flow lower bound.
- The flow lower bound provides a positive lower bound only for essential edges. The Steiner tree lower bound provides a positive constant lower bound of 2 for all essential edges, and, in case is disconnected, for certain non-essential edges.
- The flow lower bound is always at least as strong as the Steiner tree lower bound for essential edges.
- The two bounds can be combined in the obvious manner to give a stronger lower bound.
- For infinite or arbitrarily high capacity , the flow lower bound translates to a lower bound of 2 for all essential edges and zero for non-essential edges. The Steiner tree bound remains 2 for all edges in .
- For , the flow bound translates expectedly to . Intuitively, it is clear that as the capacity of the vehicle decreases, the Steiner tree lower bound, which does not take this into account, becomes progressively weaker as compared to the flow bound for essential edges.
- Intuitively, the flow bound is concerned with the capacity of the vehicle for the flow of items across essential edges. The Steiner tree bound is concerned with the connectivity requirement in order to complete the tour using a least cost superset of essential edges.
M. Charikar, B. Raghavachari: The Finite Capacity Dial-a-Ride Problem, 2001.