MINIMUM VEHICLE SCHEDULING ON TREE

• INSTANCE: Rooted tree $T=\left(V,E,v_0\right)$, a forward travel time $f : E \rightarrow N$, a backward travel time $b: E \rightarrow N$, a release time $r: V \rightarrow N$, and an handling time $h: V \rightarrow N$.

• SOLUTION: A vehicle routing schedule that starts from $v_0$, visits all nodes of T, returns to $v_0$, and, for any node $v_{i}$, starts processing $v_{i}$ not before the release time $r(v_i)$, i.e., a permutation $\pi$ of $1, \ldots, \vert V\vert$ and a waiting function w such that, for any i,

  
  

  $$d(v_0,v_{\pi(1)})+\sum_{j=1}^{i-1}[w(v_{\pi(j)})+h(v_{\pi(j)})+ d(v_{\pi(j)},v_{\pi(j+1)})] \geq r(v_{\pi(i)})$$
  
  
  where d(u,v) denotes the length of the unique path from u to v.

• MEASURE: The total completion time, i.e.,
  $$\begin{eqnarray*} & & d(v_0,v_{\pi(1)})+\sum_{j=1}^{n-1}[w(v_{\pi(j)})+h(v_{\pi... ...\pi(j+1)})] + w(v_{\pi(n)}) + h(v_{\pi(n)}) + d(v_{\pi(n)},v_0). \end{eqnarray*}$$
  
  
  
  
  

  
  

• Good News: Approximable within 2 [298].