Distance Constrained Vehicle Routing Problem to Minimize the Total Cost

Given lambda > 0, an undirected complete graph G = (V, E) with nonnegative edge-weight function obeying the triangle inequality and a depot vertex r is an element of V, a set {C-1, ... , C-k} of cycles is called a lambda-bounded r-cycle cover if V subset of boolean OR(k)(i=1) V (C-i) and each cycle C-i contains r and has a length of at most lambda. The Distance Constrained Vehicle Routing Problem with the objective of minimizing the total cost (DVRP-TC) aims to find a lambda-bounded r-cycle cover {C-1, ... , C-k} such that the sum of the total length of the cycles and gamma k is minimized, where gamma is an input indicating the assignment cost of a single cycle. For DVRP-TC on tree metric, we show a 2-approximation algorithm that is implied by the existing results and give an LP relaxation whose integrality gap has an upper bound of 5/2. In particular, when gamma = 0 we prove that this bound can be improved to 2. For the unrooted version of DVRP-TC, we devise a 5-approximation algorithm and show that a natural set-covering LP relaxation has a constant integrality gap of 25 using the rounding procedure given by Nagarajan and Ravi (2008).