Distance constrained vehicle routing problem to minimize the total cost: algorithms and complexity

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. is an input indicating the assignment cost of a single cycle. For DVRP-TC on tree metric, we show a 2-approximation algorithm and give an LP relaxation whose integrality gap lies in the interval [2, 5/2]. For the unrooted version of DVRP-TC, we devise a 5-approximation algorithm and give an LP relaxation whose integrality gap is between 2 and 25. For unrooted DVRP-TC on tree metric we develop a 3-approximation algorithm. For unrooted DVRP-TC on line metric we obtain an O(n(3)) time exact algorithm, where n is the number of vertices. Moreover, we give some examples to demonstrate that our results can also be applied to the path-version of (unrooted) DVRP-TC.