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

Given $$\lambda >0$$ λ > 0 , an undirected complete graph $$G=(V,E)$$ G = ( V , E ) with nonnegative edge-weight function obeying the triangle inequality and a depot vertex $$r\in V$$ r ∈ V , a set $$\{C_1,\ldots ,C_k\}$$ { C 1 , … , C k } of cycles is called a $$\lambda $$ λ -bounded r-cycle cover if $$V \subseteq \bigcup _{i=1}^k V(C_i)$$ V ⊆ ⋃ i = 1 k V ( C i ) and each cycle $$C_i$$ 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,\ldots ,C_k\}$$ { C 1 , … , C k } such that the sum of the total length of the cycles and $$\gamma k$$ γ 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 and give an LP relaxation whose integrality gap lies in the interval [2, $$\frac{5}{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)$$ 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.