Next: Mathematical Programming Up: Miscellaneous Previous: MINIMUM SCHEDULE LENGTH Index

### MINIMUM VEHICLE SCHEDULING ON TREE

- INSTANCE: Rooted tree , a forward travel time , a backward travel time , a release time , and an handling time .

- SOLUTION: A vehicle routing schedule that starts from v0, visits all nodes of T, returns to v0, and, for any node vi, starts processing vi not before the release time r(vi), i.e., a permutation of and a waiting function w such that, for any i,

  where d(u,v) denotes the length of the unique path from u to v.

- MEASURE: The total completion time, i.e.,

- Good News: Approximable within 2 [283].