  The concept of bounded highway dimension was developed to capture observed
properties of the metrics of road networks. We show that a graph with bounded
highway dimension, for any vertex, can be embedded into a a graph of bounded
treewidth in such a way that the distance between $u$ and $v$ is preserved up
to an additive error of $\epsilon$ times the distance from $u$ or $v$ to the
selected vertex. We show that this theorem yields a PTAS for Bounded-Capacity
Vehicle Routing in graphs of bounded highway dimension. In this problem, the
input specifies a depot and a set of clients, each with a location and demand;
the output is a set of depot-to-depot tours, where each client is visited by
some tour and each tour covers at most $Q$ units of client demand. Our PTAS can
be extended to handle penalties for unvisited clients.
  We extend this embedding result to handle a set $S$ of distinguished
vertices. The treewidth depends on $|S|$, and the distance between $u$ and $v$
is preserved up to an additive error of $\epsilon$ times the distance from $u$
and $v$ to $S$.
  This embedding result implies a PTAS for Multiple Depot Bounded-Capacity
Vehicle Routing: the tours can go from one depot to another. The embedding
result also implies that, for fixed $k$, there is a PTAS for $k$-Center in
graphs of bounded highway dimension. In this problem, the goal is to minimize
$d$ such that there exist $k$ vertices (the centers) such that every vertex is
within distance $d$ of some center. Similarly, for fixed $k$, there is a PTAS
for $k$-Median in graphs of bounded highway dimension. In this problem, the
goal is to minimize the sum of distances to the $k$ centers.
