On the Dial-a-Ride problem – 2

We consider here the capacitated Dial-a-Ride problem on the tree metric. The $m$ demand pairs $\{(s_i, t_i)\}_{i=1}^{m}$ are assumed to be on the leaves of the tree, $T$.

• For each demand pair $(s_i, t_i)$, we have a unique path $p_i$ from $s_i$ to $t_i$ in $T$.
• Call all vertices which are on any of the paths $\{p_i\}_{i=1}^{m}$ as interesting.
• Call all edges which are on any of the paths $\{p_i\}_{i=1}^{m}$ 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 $Q$ be the least cost Steiner tree spanning all interesting vertices. $Q$ would include all essential edges, and if $\cup_{i=1}^{m} p_i$ is not connected, $Q$ will include other edges too. Clearly, any tour that satisfies all demand pairs must traverse every edge of $Q$ at least twice. We call this the Steiner tree lower bound.

2. Flow lower bound:- With every edge $e$ in $T$, we associate two quantities $flow_u(e)$ and $flow_d(e)$. For every edge $e = \{u,v\}$, fix, for the purpose of computation of $flow_u(e)$ and $flow_d(e)$, an ordering of the end points. $flow_u(e)$ equals the number of paths, $p_i$ which require an item to pass from vertex $u$ to vertex $v$. $flow_d(e)$ corresponds to the number of paths, $p_i$ which require an item to pass from vertex $v$ to vertex $u$. (Here, ‘u’ denotes ‘upwards’, and ‘d’ denotes ‘downwards’.)

Clearly, for a vehicle of capacity $k$, edge $e$ must be traversed at least $2 max \{ \lceil \frac{flow_u(e)}{k}\rceil, \lceil \frac{flow_d(e)}{k}\rceil \}$ in any feasible Dial-a-Ride tour. We call this the flow lower bound.

Notes:

• 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 $\cup_{i=1}^{m} p_i$ 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 $k$, 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 $Q$.
• For $k=1$, the flow bound translates expectedly to $2 max\{flow_u(e), flow_d(e)\}$. 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.

References:

M. Charikar, B. Raghavachari: The Finite Capacity Dial-a-Ride Problem, 2001.