Locating Depots for Capacitated Vehicle Routing

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].