Distance constrained vehicle routing problem to minimize the total cost: algorithms and complexity
- PDF / 347,270 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 99 Downloads / 241 Views
Distance constrained vehicle routing problem to minimize the total cost: algorithms and complexity Wei Yu1
· Zhaohui Liu1 · Xiaoguang Bao2
Accepted: 1 November 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Given λ > 0, an undirected complete graph G = (V , E) with nonnegative edgeweight function obeying the triangle inequality and a depot vertex r ∈ V , a set k V (Ci ) {C1 , . . . , Ck } of cycles is called a λ-bounded r -cycle cover if V ⊆ i=1 and each cycle Ci contains r and has a length of at most λ. The Distance Constrained Vehicle Routing Problem with the objective of minimizing the total cost (DVRP-TC) aims to find a λ-bounded r -cycle cover {C1 , . . . , Ck } such that the sum of the total length of the cycles and γ 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, 25 ]. 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. Keywords Vehicle routing · Cycle cover · Path cover · Approximation algorithm · Complexity · Integrality gap
B
Wei Yu [email protected] Zhaohui Liu [email protected] Xiaoguang Bao [email protected]
1
Department of Mathematics, East China University of Science and Technology, 130 Meilong Road, Shanghai 200237, China
2
College of Information Technology, Shanghai Ocean University, 999 Huchenghuan Road, Shanghai 201306, China
123
Journal of Combinatorial Optimization
1 Introduction In the Distance Constrained Vehicle Routing Problem (DVRP), we are given a set of n vertices in a metric space, a specified depot r , and a distance bound λ, the aim is to find a set of tours, which start from and end at r and have a length of at most λ, for the vehicles to cover all the vertices such that one of the following objectives is minimized: (i) the total distance of the tours; (ii) the number of tours. We denoted by DVRP-D (DVRP-N) the DVRP with the first (second) objective. In unrooted DVRP, the depot r is not specified and the tours are allowed to contain any set of vertices as long as their length do not exceed λ. The (unrooted) DVRP arises naturally in many practical applications including daily routes scheduling for courier carriers, milkruns from manufacturing facilities, sensor coverage in wireless sensor networks, and so on (see Assad 1988; Nagarajan and Ravi 2012; Liang et al. 2019; Xu et al. 2015). Both (unrooted) DVRP-D and (unrooted) DVRP-N are NP-hard since they generalize the well-known Traveling Salesman Problem. Moreover, due to the NPCompleteness of the Hamiltonian
Data Loading...
