2011 | OriginalPaper | Chapter
Locating Depots for Capacitated Vehicle Routing
Authors : Inge Li Gørtz, Viswanath Nagarajan
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We study a location-routing problem in the context of capacitated vehicle routing. The input to
k
-LocVRP is a set of demand locations in a metric space and a fleet of
k
vehicles each of capacity
Q
. The objective is to
locate
k
depots, one for each vehicle, and
compute routes
for the vehicles so that all demands are satisfied and the total cost is minimized. Our main result is a constant-factor approximation algorithm for
k
-LocVRP. To achieve this result, we reduce
k
-LocVRP to the following generalization of
k
median, which might be of independent interest. Given a metric (
V
,
d
), bound
k
and parameter
ρ
∈ ℝ
+
, the goal in the
k median forest
problem is to find
S
⊆
V
with |
S
| =
k
minimizing:
$$\sum_{u\in V} d(u,S) \quad + \quad \rho\cdot d\big(\,\mbox{MST}(V/S)\,\big),$$
where
d
(
u
,
S
) = min
w
∈
S
d
(
u
,
w
) and
$\mbox{MST}(V/S)$
is a minimum spanning tree in the graph obtained by contracting
S
to a single vertex. We give a (3 +
ε
)-approximation algorithm for
k
median forest, which leads to a (12 +
ε
)-approximation algorithm for
k
-LocVRP, for any constant
ε
> 0. The algorithm for
k
median forest is
t
-swap local search, and we prove that it has locality gap
$3+\frac2t$
; this generalizes the corresponding result for
k
median [3].
Finally we consider the
k
median forest problem when there is a different (unrelated) cost function
c
for the MST part, i.e. the objective is
$\sum_{u\in V} d(u,S) \,+ \,c (\,\mbox{MST}(V/S)\,)$
. We show that the locality gap for this problem is unbounded even under multi-swaps, which contrasts with the
c
=
d
case. Nevertheless, we obtain a constant-factor approximation algorithm, using an LP based approach along the lines of [12].