# A Polynomial-Time Exact Algorithm fork-Depot Capacitated Vehicle Routing Problem on a Tree

Authors: Liang Xu; Tong Zhang; Rantao Hu; Jialing Guo
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

This paper proposes a polynomial-time exact algorithm for thek-depot capacitated vehicle routing problem on a tree for fixed k (k-depot CVRPT for short), which involves dispatching a fixed number of k capacitated vehicles in depots on a tree-shaped graph to serve customers with the objective of minimizing total distance traveled. The polynomial-time exact algorithm improves the 2-approximation algorithm when k is a constant.


---

## Body

## 1. Introduction

This article investigates routingk capacitated vehicles in fixed depots to serve customers. According to [1], this problem is equivalent to dispatching k vehicles located at distinct depots (referred to as k-depot CVRP). The k-depot CVRP can be described as follows: Given a complete, undirected graph G=V,E with vertex set V and edge set E, there is a given depot set D with D=k, where a vehicle of capacity Q is located at each depot in D, and a nonempty set of customer locations J=V∖D. Each edge e∈E is associated with a nonnegative edge weight we. The k-depot CVRP involves determining a set of k tours to cover all the customers in J such that the total customer demand served by each vehicle does not exceed Q. The objective is to minimize the total edge weight of all tours.If demand of a customer cannot be split, thek-depot CVRP has a feasible solution if and only if its corresponding Bin Packing Problem [2], with the number of bins equal to that of depots and bin capacity equal to vehicle capacity, has a feasible solution. Then, polynomial-time exact algorithm is unavailable even for the tree-shaped graph. According to Li and Simchi-Levi [3], if demand of a customer can be split (demand of a customer can be served by more than one vehicle), the problem reduces to a k-depot CVRP with each customer having unit demand and with vehicle capacity Q of each vehicle equal to the maximum number of customers that can be served by a vehicle. This paper considers the splittable demand case and develops polynomial-time exact algorithm under the assumption that each customer has a unit demand.We useℐ=G,D,J,w,Q to denote an instance of the k-depot CVRP. A feasible solution to ℐ can be defined as a k-cycle collection C which satisfies the following: (i) Each customer is served by exactly one cycle in C. (ii) Number of customers served by each cycle in C does not exceed Q. (iii) Each cycle in C contains a distinct depot in D. It is noted that if there exists a k-tree collection T which also satisfies (i), (ii), and (iii), we call it a k-tree cover of G. Duplicating each edge in a k-tree cover T constitutes a k-cycle collection C.For the min-maxk-traveling salesmen problem on a tree (min-max k-TSPT), which involves determining a set of k tours for k salesmen who have infinite capacity to serve all customers located on a tree-shaped network T, with the objective of minimizing the greatest weight among all tours, Xu et al. [4] developed a pseudo-polynomial-time exact algorithm through dynamic programming. Supposing that the underlying tree T is a fully binary tree [4], the basic idea underlying the dynamic programming for the min-max k-TSPT is to join subtrees in Tl (the subtree of T rooted at vertex l) and Tr (a subtree of T rooted at vertex r) to form subtrees in Tv, in which l and r are the left child and right child of v, respectively. However, in the k-depot CVRPT, each vehicle has a capacity of Q. Although the dynamic programming in [4] has been extended to solve a k-TSPT under a min-sum objective in the same article, it cannot be directly extended to the capacitated case. Meanwhile, it is noted that the best approximation algorithm for the k-depot CVRPT was provided in the thesis of Hu [5] and achieved an approximation ratio of 2. The CVRPT with number of depot part of the instance has been proved to be NP-hard by [5], and the 2-approximation algorithm was proposed for this NP-hard case.Concerning thek-depot TSP, a special case of the k-depot CVRP with infinite capacity, and the first constant approximation algorithm was obtained by [6], which achieves an approximation ratio of 2. For the same problem, Xu et al. [7] provided an extended Christofides heuristic, which is proved to achieve a tight approximation ratio of 2−1/k. To answer the question of whether or not there exists a 3/2-approximation algorithm for the k-depot TSP, Xu and Rodrigues [8] designed an edge exchange algorithm which is proved to achieve an approximation ratio of 3/2.For the multiple-depot CVRP with unlimited vehicles, Li and Simchi-Levi [3] first provided a tour partitioning approximation algorithm for the problem and analyzed the worst-case performance ratios of the approximation algorithms. Moreover, Cardon et al. [9] also considered multiple-depot CVRP with unlimited vehicle number and extended the Polynomial Time Approximation Scheme (PTAS) for CVRP in [10] to the multiple-depot case and obtained a PTAS with its time complexity corresponding to both the number of vehicles and the vehicle capacity. For the k-depot CVRP on a general graph, which has a fixed number of k vehicles in depots, there is no constant ratio approximation algorithm as far as we know.We propose the first, as far as we are aware, polynomial-time exact algorithm for the CVRPT with the number of depotk a constant. The proposed algorithm in this article is based on a novel network-flow-based dynamic programming rather than the existing subtree-joining-based dynamic programming in Xu et al.’s work [4]. The network-flow-based dynamic programming provides a more general framework to solve both capacitated and uncapacitated vehicle routing problems on trees. The contribution and significance of this article can be summarized as follows:(1)
This article designs a novel polynomial-time exact algorithm based on a network-flow-based dynamic programming for thek-depot CVRPT(2)
The polynomial-time exact algorithm for this problem improves the existing 2-approximation algorithm whenk is a constant


## 2. Dynamic Programming for thek-Depot CVRPT

To simplify the presentation, we first define a “standard” instance of thek-depot CVRPT as follows.Definition 1.
An instance of thek-depot CVRPT is standard if, and only if, the underlying tree is a full binary tree, which means that each vertex in the tree other than the leaves has exactly two children.
According to [11], given any instance ℐ of the k-depot CVRPT defined on an arbitrary tree, we can transform it to a standard instance ℐ′ of the k-depot CVRPT defined on a full binary tree as follows:(1)
LetT′=T and w′=w.(2)
For eachv in T′ that has only one child, insert a new vertex v′ into T′ to be the second child of v by adding an edge v,v′ and setting w′v,v′=0.(3)
Consider eachv in T′ that has more than two children. For each child u of v, other than the first child, move u to be a child of a new vertex v′ by replacing the edge v,u with an edge v′,u and setting w′v′,u=w′v,u. Insert v′ into T′ to be the second child of v by adding an edge v,v′ and setting w′v,v′=0.
Similar to the arguments in [11], it can be verified that any feasible solution of ℐ can be transformed to a feasible solution of ℐ′ with the same objective value, and vice versa. Accordingly, if there exists a polynomial-time exact algorithm for ℐ′, then the same algorithm can be applied to obtain a polynomial-time exact algorithm for ℐ, and vice versa.
Based on the definition of standard instance, we assume without loss of generality that the instances in this article are standard and introduce the dynamic programming for thek-depot CVRPT for those standard instances. An outline of dynamic programming is presented in Section 2.1. The dynamic programming has two main phases, (1) flow-enumerating phase and (2) flow-splitting phase, which are introduced in Sections 2.2 and 2.3, respectively. Finally, the correctness and time complexity for the dynamic programming are proved in Section 2.4.
Furthermore, to facilitate the presentation, we can assume without loss of generality that vertices inV=v1,v2,…,vn are labeled in a nonincreasing order on their depths in T. We assume without loss of generality that vn is the root of T, and the tree satisfies that all the customers and depots are at the leaves [5]. Figure 1 shows an example of the mentioned tree. In the tree T, there are in total three customers, v1, v4, and v6, and two depots, v5 and v2. Furthermore, the edge weights are shown near the edges. For each v∈V, let Tv denote the subtree of T that contains v and all descendants of v. In this problem instance, the vehicle capacity Q=2.Figure 1
Example to illustrate the tree in the problem instance.


### 2.1. Algorithm

Denote any edgee as u,v and u is the parent of v. Given any feasible solution to the k-depot CVRPT, let the flow fu,v be the total customer number within Tv served by the depots outside Tv minus the total number of customers outside Tv served by depots within Tv (also called the net customer number). Thus, for a leaf vertex v which is a customer, the flow fu,v equals 1; for a leaf vertex v which is a depot, the flow fu,v equals −s and s equals the total number of customers served by the depot. For any nonleaf vertex v, the flow fu,v satisfies the flow conservation property [5]; that is, fu,v=fv,v1+fv,v2, where v1 and v2 denote the two children of v. Therefore, given any feasible solution C to the k-depot CVRPT, there exists a unique flow fC corresponding to C, in which the flow fe equals the total net customer number on edge e. In the flow-enumerating phase of the dynamic programming, we try to figure out the flow fC∗ corresponding to the optimal solution C∗.Letvi,di be the unique edge connected to depot di for i=1,2,…,k. Since the flow f∗e on each edge e, connected to a customer vertex, equals 1 in any optimal solution C∗, the flow fC∗ can be found by an enumeration of flows on v1,d1,v2,d2,…,vk,dk. In an optimal solution, since the total net customer number f∗vi,di on vi,di belongs to a bounded set 0,1,…,Q, the flows f∗v1,d1,f∗v2,d2,…,f∗vk,dk also belong to a bounded set 0,1,…,Qk. Based on the flows on all edges connected to the leaves, the flow fC∗ can be constructed according to the flow conservation property.Then, after we have obtained the flowfC∗, in the flow-splitting phase, we further figure out the number of customers served in an optimal solution, via a specific edge e, by the depot di for i=1,2,…,k. For each edge e=u,v, we associate a state f1u,v,f2u,v,…,fku,v with e, where fiu,v denotes the net customer number served by di in Tv for i=1,2,…,k. Noticing that, given any Tv, the depot di is either outside Tv or inside Tv, we can conclude that fiu,v≥0 when di is outside Tv and fiu,v≤0 when di is inside Tv. Furthermore, according to the definition of fu,v, we have fu,v=∑i=1kfiu,v. For any state f1u,v,f2u,v,…,fku,v, we define its state value gf1u,v,f2u,v,…,fku,v as the minimum total edge length traversed by all vehicles with the ith vehicle serving fiu,v net customers within Tv for i=1,2,…,k (including the length traversed on u,v). Then, one can notice that, for any leaf vertex v, if v is a customer, it can be served by exactly one depot, and thus the state f1u,v,f2u,v,…,fku,v satisfies ∑i=1kfiu,v=1; if v is a depot, the state f1u,v,f2u,v,…,fku,v satisfies fiu,v=−si for a certain i, where si denotes the number of customers served by di. Therefore, the states for any edge u,v connected to a leaf vertex v can be computed by a boundary procedure, and the states are further added to a state collection ℋv. Based on the state collections for all the leaves, the dynamic programming constructs a state collection ℋv for any nonleaf vertex v in an increasing order, iteratively. In such a manner, when we construct the state collection for a nonleaf vertex v, the state collections ℋv1 and ℋv2 have been constructed for the two children of v, respectively. Then, the state collection ℋv can be constructed based on ℋv1 and ℋv2, by a state recursion procedure.After all the state collectionsℋv have been constructed for v=v1,v2,…,vn, the optimal solution to the k-depot CVRPT can be returned as the “feasible” state with minimum state value in ℋvn.The details of the dynamic programming can be found in Algorithm1.Algorithm 1:The dynamic programming algorithm for the k-depot CVRPT.
Input: Any instanceℐ=T,D,J,w,Qto thek-depot CVRPT on a treeT.Output: A minimum length over allk-tree cover ofT.(1)
(Flow-enumerating Phase)(2)
Apply the flow-enumerating procedureFlowT,D to return a flow collection F.(3)
(Flow-splitting Phase)(4)
forv=v1,v2,…,vn−1do(5)
Setℋv to be empty.(6)
ifv is a leaf then(7)
Construct the state collectionℋv by the boundary procedure Boundv,F.(8)
else(9)
Construct the state collectionℋv by the state recursion procedure Recursionv,ℋv1,ℋv2, where v1 and v2are two children of v.(10)
end if(11)
end for(12)
(Optimal solution return phase)(13)
Whenv=vn, add a new vertex vn+1 to the graph with wvn+1,vn=0 and fvn+1,vn=0. Construct ℋvn by the state recursion procedure Recursionv,ℋv1,ℋv2, where v1 and v2denote the two children of vn. Among all states S=f1vn+1,vn,f2vn+1,vn,…,fkvn+1,vn in ℋvn, with fivn+1,vn=0 for i=1,2,…,k, return the objective value as the minimum state value.Note that the feasible solution returned by Algorithm1 is a k-tree cover T. Therefore, the optimal objective value to ℐ is exactly twice the value of the minimum length of k-tree cover of T.


### 2.2. Flow-Enumerating Phase

As mentioned before, we present in this section a flow-enumerating procedure, denoted asFlowT,D, which finds the flow fC∗.Procedure 1.
Flow-enumerating procedure, FlowT,D.Input: A treeTand a depot setD.Output: A collectionFof flowsf.(1)
LetF=∅.(2)
for eachs1,s2,…,sk∈0,1,…,Qksuch that∑i=1ksi=Jdo(3)
(Construction of flows on edges connected to customers)(4)
for each customervinTdo(5)
Letfu,v=1, whereuis the parent ofv.(6)
end for(7)
(Construction of flows on edges connected to depots)(8)
fori=1,…,kdo(9)
Letfu,di=−si, whereuis the parent ofdi.(10)
end for(11)
(Construction of flows on edges connected to non-leaf vertices)(12)
Construct the flowfs1,s2,…,sk=fe|e∈ET, by the flow conservation property, i.e., the flow onfu,vis calculated byfv,v1+fv,v2, wherev1andv2are two children ofv.(13)
Add the flowfs1,s2,…,skintoF.(14)
end for(15)
ReturnF.
In the following lemma, it is stated that the flowfC∗ corresponding to C∗ is in F.Lemma 1.
The flowfC∗ corresponding to C∗ is in F, and the flow collection F returned by Procedure 1 has a cardinality in OQk.Proof.
Consider the flowfC∗. First, for any edge e connected to a customer vertex, the flow on e is equal to one. Second, for any edge e connected to a depot di, the flow on e is equal to si∗, where si∗ denotes the total number of customers served by di in C∗. Thus, since si∗≤Q for i=1,2,…,k, according to Step 8-Step 10 of Procedure 1, there exists a flow fs1∗,s2∗,…,sk∗ in F such that flow fvi,di satisfies fvi,di=si∗ for i=1,2,…,k, where vi denotes the parent of depot di for i=1,2,…,k. Meanwhile, due to Step 12, according to the flow conservation property, it can be verified that fu,v equals the net customer number in Tv in the optimal solution C∗. Meanwhile, consider the k edges connected to D. Procedure 1 constructs at most Qk flow combinations on the k edges. Therefore, the cardinality of F can be seen to be OQk.Example 1.
Consider the tree shown in Figure1. Let D=d1,d2=v2,v5, J=v1,v4,v6, and Q=2. We apply the flow-enumerating procedure to construct the flow collection F.
The flow-enumerating procedure is shown for the case in whichs1,s2=2,1, where fv3,v2=−2 and fv8,v5=−1. First, for the vertex v1, let fv3,v1=1. Similarly, the flow-enumerating procedure sets fv3,v2=1, fv7,v4=1, and fv8,v6=1. Second, for d1=v2, let fv3,v2=−2. Similarly, the flow-enumerating procedure sets fv8,v5=−1. Third, for v3, noticing that v2 and v1 are two children of v3, the flow fv7,v3 is constructed by the flow conservation property; that is, fv7,v3=fv3,v2+fv3,v1=−1. For v7, noticing that v4 and v3 are two children of v7, the flow fv9,v7 is constructed by the flow conservation property; that is, fv9,v7=fv7,v4+fv7,v3=0. Similarly, we can obtain that fv9,v8=0. Therefore, the flow f2,1 in F is shown in Figure 2, in which the flows are indicated near the edges.
For the cases1,s2=1,2, the flow constructed by the flow-enumerating procedure is shown in Figure 3.
Since the capacityQ=2 and the customer number J=3, it can be seen that any feasible solution to ℐ satisfies that s1,s2=2,1 or s1,s2=1,2. In summary, the flow collection F contains the flows f2,1 and f1,2, as indicated in Figures 2 and 3.Figure 2
The flow constructed froms1,s2=2,1 by the flow-enumerating procedure.Figure 3
The flow constructed froms1,s2=1,2 by the flow-enumerating procedure.


### 2.3. Flow-Splitting Phase

In this section, we present the procedures developed to constructℋv for a leaf vertex and a nonleaf vertex, respectively.Procedure 2.
Boundary procedure,Boundv,F.Input:A leaf vertexvand a given flow collectionF.Output:A state collectionℋv.(1)
Letℋv=∅.(2)
foranyfs1,s2,…,sk∈Fdo(3)
ifvis a depot andv=dithen(4)
Addf1u,v,f2u,v,…,fku,vtoℋvwithfiu,v=siandfju,v=0for anyj≠i. Let the state valuegf1u,v,f2u,v,…,fku,v=wu,vifsi>0; and let the state value to be zero ifsi=0.(5)
else(6)
Addf1u,v,f2u,v,…,fku,vtoℋvwithfiu,v∈0,1fori=1,2,…,kand∑i=1kfiu,v=1. Let the state valuegf1u,v,f2u,v,…,fku,v=wu,v.(7)
end if(8)
end for(9)
Returnℋv.Example 2.
Let us continue Example1. We construct the state collection ℋv for all the leave vertices, v1,v2,v4,v5,v6, respectively. Note that the flow collection F contains two flows f2,1 and f1,2. For v=v1, since v1 is a customer, for f2,1, the boundary procedure adds two states 0,1,1,0 into ℋv1. Meanwhile, for f1,2, the boundary procedure adds the same states 0,1,1,0 into ℋv1. Therefore, the state collection ℋv1 contains two states 0,1,1,0 with the state values g0,1=1 and g1,0=1. For v=v2, since v2 is a depot where the first vehicle is located and v2=d1, for f1,2, the boundary procedure adds −1,0 into ℋv2; for f2,1, the boundary procedure adds −2,0 into ℋv2. Therefore, the state collection ℋv2 contains two states −1,0,−2,0 with the state values g−1,0=1 and g−2,0=1. Similarly, one can obtain all the state collections ℋv for v=v1,v2,v4,v5,v6 in Table 1.
Next, we present the state recursion procedure. For any nonleaf vertexv∈V, it constructs ℋv based on ℋv1 and ℋv2, where v1 and v2 are the two children of v.Table 1
Construction ofℋv for all the leaves.
State collectionStateState valueℋv60,111,01ℋv50,−220,−12ℋv40,131,03ℋv2−1,01−2,01ℋv10,111,01Procedure 3.
State recursion procedure,Recursionv,ℋv1,ℋv2.Input:A non-leaf vertexv∈V,ℋv1andℋv2, wherev1andv2are two children forv.Output:A state collectionℋv.(1)
Letℋv=∅.(2)
foranyS1,S2∈ℋv1×ℋv2, in whichS1=f1v,v1,f2v,v1,…,fkv,v1andS2=f1v,v2,f2v,v2,…,fkv,v2do(3)
forj=1,2,…,kdo(4)
fju,v=fjv,v1+fjv,v2.(5)
end for(6)
Determine the state value forf1u,v,f2u,v,…,fku,vas∑j=1k⌈fju,v/Q⌉wu,v+∑i=12gf1v,vi,f2v,vi,…,fkv,vi.(7)
Addf1u,v,f2u,v,…,fku,vtoℋvif it satisfiesfju,v≤Qforj=1,2,…,k, and there exists no statef1′u,v,f2′u,v,…,fk′u,vinℋvwithfju,v=fj′u,vforj=1,2,…,kandf1′u,v,f2′u,v,…,fk′u,vhas a smaller state value.(8)
end for(9)
Returnℋv.Example 3.
Let us apply the state recursion procedure to constructℋv3, ℋv7, ℋv8, and ℋv9, respectively. First, we construct ℋv3 based on ℋv1 and ℋv2. In Table 2, all combinations of S1,S2∈ℋv1×ℋv2 are shown in the first column, the states constructed based on S1,S2 are shown in the second column, and their state values are indicated in the third column.
Furthermore, based onℋv3 and ℋv4, the state collection ℋv7 can be constructed as depicted in Table 3 (those states with “∗” are kept in ℋv7).
Similarly, we can constructℋv8 as in Table 4, in which S1,S2∈ℋv6×ℋv5 are shown in the first column.
Finally, we can constructℋv9 based on ℋv7 and ℋv8. Since vn=v9, we add one more vertex v10 into the graph with wv10,v9=0 and fv10,v9=0. Next, we construct the state collection ℋv9 as depicted in Table 5.
According to Algorithm1, only those flows f1v10,v9,f2v10,v9 with f1v10,v9=0 and f2v10,v9=0 are added to ℋv9. Then, the two states with “∗” are kept. Since the minimum state value in the state collection ℋv9 is 8, Algorithm 1 returns an optimal objective value as 8. Since the minimum total edge length for serving customers in J equals 8, by the fact that each edge is traversed exactly twice in any tour in a tree, the optimal solution to the instance can be seen to be 16.Table 2
Construction ofℋv3.
S1,S2StateState value0,1,−2,0,−2,121,0,−2,0−1,021,0,−1,00,020,1,−1,0−1,12Table 3
Construction ofℋv7.
S1,S2StateState value0,1,−1,0,−1,1∗71,0,−1,00,0∗51,0,−2,1−1,170,1,−2,1−2,2∗70,1,−1,1,−1,2∗71,0,−1,10,1∗61,0,0,01,0∗60,1,0,00,16Table 4
Construction ofℋv8.
S1,S2StateState value0,1,0,−20,−1∗51,0,0,−21,−2∗70,1,0,−10,0∗31,0,0,−11,−1∗7Table 5
Construction ofℋv9.
S1,S2StateState value0,0,0,−10,−1–0,0,1,−21,−2–0,0,1,−11,−1–0,0,0,00,0∗8−1,1,0,−1−1,0–−1,1,1,−20,−1–−1,1,1,−10,014−1,1,0,0−1,1–−2,2,0,−1−2,1–−2,2,1,−2−1,0–−2,2,1,−1−1,1–−2,2,0,0−2,2–1,0,0,−11,−1–1,0,1,−22,−2–1,0,1,−12,−1–1,0,0,01,0–−1,2,0,−1−1,1–−1,2,1,−20,0∗14−1,2,1,−10,1–−1,2,0,0−1,2–0,1,0,−10,0∗110,1,1,−21,−1–0,1,1,−11,0–0,1,0,00,1–


### 2.4. Correctness and Time Complexity for Dynamic Programming

We first establish Lemma2 to prove the feasibility of all the states in ℋvn.Lemma 2.
For eachv=v1,v2,…,vn, and for each state f1u,v,f2u,v,…,fku,v∈ℋv obtained in Algorithm 1, it satisfies that (i) each customer in Tv is served by exactly one depot and (ii) each depot serves no more than Q customers.Proof.
First, according to Step 6 of the boundary procedure, it can be verified that each customer is served by exactly one depot. Second, according to Step 7 of the state recursion procedure, it can be verified that each depot serves no more thanQ customers. Thus, (i) and (ii) can be verified for v=v1,v2,…,vn−1. For the case v=vn, since fivn+1,vn=0∑jfivn,vj=0 for i=1,2,…,k, one can see that the total customer number assigned to di equals si, where si denotes the flow on u,di in the flow fs1,s2,…,sk, which implies that each state in ℋvn corresponds to a feasible solution to the k-depot CVRPT.
We then establish Lemma3 to prove the optimality of Algorithm 1, which, together with Lemma 2, will be used to prove the correctness of Algorithm 1 in Theorem 1.Lemma 3.
Considerf1C∗,f2C∗,…,fkC∗, in which fiC∗ denotes the flow corresponding to di in fC∗. For each v=v1,v2,…vn, there exists a state f1u,v,f2u,v,…,fku,v∈ℋv, obtained by Algorithm 1, such that fiu,v=fi∗u,v for i=1,2,…,k and the state value gf1u,v,f2u,v,…,fku,v is not greater than gf1∗u,v,f2∗u,v,…,fk∗u,v, where fi∗u,v denotes the flow in fiC∗ on the edge u,v, and gf1∗u,v,f2∗u,v,…,fk∗u,v denotes the shortest length traversed by all the k vehicles with the ith vehicle serving fi∗u,v net customers in Tv for i=1,2,…,k.Proof.
We prove Lemma3 by induction. For each leaf v which is a customer, we know that fi∗u,v∈0,1 for i=1,2,…,k and ∑ifi∗u,v=1, which implies that f1∗u,v,f2∗u,v,…,fk∗u,v∈ℋv. For each leaf v which is a depot, we can conclude that f1∗u,v,f2∗u,v,…,fk∗u,v∈ℋv according to Lemma 1. Furthermore, since fiu,v=f1∗u,v for i=1,2,…,k, according to the definition of gf1u,v,f2u,v,…,fku,v and gf1∗u,v,f2∗u,v,…,fk∗u,v, we have gf1u,v,f2u,v,…,fku,v≤gf1∗u,v,f2∗u,v,…,fk∗u,v, which implies that the lemma holds for any leaf vertex v
Next, consider anyv∈V that is not a leaf. Let v1 and v2 denote the two children of v. Assume that Lemma 3 holds for each child of v, denoted as v1 and v2. We are going to show as follows that Lemma 3 holds for v.
First, for anyvi for i=1,2, there exists a state f1v,vi,f2v,vi,…,fkv,vi∈ℋvi such that, for j=1,2,…,k, fjv,vi=fj∗v,vi and gf1v,vi,f2v,vi,…,fkv,vi≤gf1∗v,vi,f2∗v,vi,…,fk∗v,vi. Since ∑i=12fjv,vi=∑i=12fj∗v,vi for j=1,2,…,k, we can conclude that there exists a state f1u,v,f2u,v,…,fku,v in ℋv such that fiu,v=fi∗u,v for i=1,2,…,k. Then, it remains to prove that gf1u,v,f2u,v,…,fku,v≤gf1∗u,v,f2∗u,v,…,fk∗u,v.
According to the calculation ofgf1u,v,f2u,v,…,fku,v in Step 6 of Procedure 3, it satisfies(1)gf1u,v,f2u,v,…,fku,v=∑j=1kfju,v/Qwu,v+∑i=12gf1v,vi,f2v,vi,…,fkv,vi≤∑j=1kfju,v/Qwu,v+∑i=12gf1∗v,vi,f2∗v,vi,…,fk∗v,vi≤∑j=1kc∗u,vwu,v+∑i=12gf1∗v,vi,f2∗v,vi,…,fk∗v,vi=gf1∗u,v,f2∗u,v,…,fk∗u,v,in which the first inequality holds by the induction, and the second inequality holds by the fact that fju,v/Q is the lower bound for the vehicle in dj to serve fju,v net customers for all vehicles within Tv and c∗u,v denotes the number of times for the vehicle in dj traversing on u,v in the optimal solution C∗ (each edge is traversed at most once by one vehicle in an optimal solution).
Based on Lemma3, the optimality for Algorithm 1 is proved. Notice that, for each leaf vertex v, at most Qk states f1u,v,f2u,v,…,fku,v are kept in ℋv because the cardinality of F is at most Qk. Meanwhile, for any nonleaf vertex v, since each fiu,v has at most Q possibilities for i=1,2,…,k and thus at most Qk states f1u,v,f2u,v,…,fku,v are kept in ℋv, the maximum number of states kept in Algorithm 1 is OQk. Then, the following theorem holds.Theorem 1.
Algorithm1 returns an optimal solution to any given instance of the k-depot CVRPT in OnQk time.SinceQ≤n, one can see that Algorithm 1 is a polynomial-time exact algorithm for the k-depot CVRPT.


## 2.1. Algorithm

Denote any edgee as u,v and u is the parent of v. Given any feasible solution to the k-depot CVRPT, let the flow fu,v be the total customer number within Tv served by the depots outside Tv minus the total number of customers outside Tv served by depots within Tv (also called the net customer number). Thus, for a leaf vertex v which is a customer, the flow fu,v equals 1; for a leaf vertex v which is a depot, the flow fu,v equals −s and s equals the total number of customers served by the depot. For any nonleaf vertex v, the flow fu,v satisfies the flow conservation property [5]; that is, fu,v=fv,v1+fv,v2, where v1 and v2 denote the two children of v. Therefore, given any feasible solution C to the k-depot CVRPT, there exists a unique flow fC corresponding to C, in which the flow fe equals the total net customer number on edge e. In the flow-enumerating phase of the dynamic programming, we try to figure out the flow fC∗ corresponding to the optimal solution C∗.Letvi,di be the unique edge connected to depot di for i=1,2,…,k. Since the flow f∗e on each edge e, connected to a customer vertex, equals 1 in any optimal solution C∗, the flow fC∗ can be found by an enumeration of flows on v1,d1,v2,d2,…,vk,dk. In an optimal solution, since the total net customer number f∗vi,di on vi,di belongs to a bounded set 0,1,…,Q, the flows f∗v1,d1,f∗v2,d2,…,f∗vk,dk also belong to a bounded set 0,1,…,Qk. Based on the flows on all edges connected to the leaves, the flow fC∗ can be constructed according to the flow conservation property.Then, after we have obtained the flowfC∗, in the flow-splitting phase, we further figure out the number of customers served in an optimal solution, via a specific edge e, by the depot di for i=1,2,…,k. For each edge e=u,v, we associate a state f1u,v,f2u,v,…,fku,v with e, where fiu,v denotes the net customer number served by di in Tv for i=1,2,…,k. Noticing that, given any Tv, the depot di is either outside Tv or inside Tv, we can conclude that fiu,v≥0 when di is outside Tv and fiu,v≤0 when di is inside Tv. Furthermore, according to the definition of fu,v, we have fu,v=∑i=1kfiu,v. For any state f1u,v,f2u,v,…,fku,v, we define its state value gf1u,v,f2u,v,…,fku,v as the minimum total edge length traversed by all vehicles with the ith vehicle serving fiu,v net customers within Tv for i=1,2,…,k (including the length traversed on u,v). Then, one can notice that, for any leaf vertex v, if v is a customer, it can be served by exactly one depot, and thus the state f1u,v,f2u,v,…,fku,v satisfies ∑i=1kfiu,v=1; if v is a depot, the state f1u,v,f2u,v,…,fku,v satisfies fiu,v=−si for a certain i, where si denotes the number of customers served by di. Therefore, the states for any edge u,v connected to a leaf vertex v can be computed by a boundary procedure, and the states are further added to a state collection ℋv. Based on the state collections for all the leaves, the dynamic programming constructs a state collection ℋv for any nonleaf vertex v in an increasing order, iteratively. In such a manner, when we construct the state collection for a nonleaf vertex v, the state collections ℋv1 and ℋv2 have been constructed for the two children of v, respectively. Then, the state collection ℋv can be constructed based on ℋv1 and ℋv2, by a state recursion procedure.After all the state collectionsℋv have been constructed for v=v1,v2,…,vn, the optimal solution to the k-depot CVRPT can be returned as the “feasible” state with minimum state value in ℋvn.The details of the dynamic programming can be found in Algorithm1.Algorithm 1:The dynamic programming algorithm for the k-depot CVRPT.
Input: Any instanceℐ=T,D,J,w,Qto thek-depot CVRPT on a treeT.Output: A minimum length over allk-tree cover ofT.(1)
(Flow-enumerating Phase)(2)
Apply the flow-enumerating procedureFlowT,D to return a flow collection F.(3)
(Flow-splitting Phase)(4)
forv=v1,v2,…,vn−1do(5)
Setℋv to be empty.(6)
ifv is a leaf then(7)
Construct the state collectionℋv by the boundary procedure Boundv,F.(8)
else(9)
Construct the state collectionℋv by the state recursion procedure Recursionv,ℋv1,ℋv2, where v1 and v2are two children of v.(10)
end if(11)
end for(12)
(Optimal solution return phase)(13)
Whenv=vn, add a new vertex vn+1 to the graph with wvn+1,vn=0 and fvn+1,vn=0. Construct ℋvn by the state recursion procedure Recursionv,ℋv1,ℋv2, where v1 and v2denote the two children of vn. Among all states S=f1vn+1,vn,f2vn+1,vn,…,fkvn+1,vn in ℋvn, with fivn+1,vn=0 for i=1,2,…,k, return the objective value as the minimum state value.Note that the feasible solution returned by Algorithm1 is a k-tree cover T. Therefore, the optimal objective value to ℐ is exactly twice the value of the minimum length of k-tree cover of T.


## 2.2. Flow-Enumerating Phase

As mentioned before, we present in this section a flow-enumerating procedure, denoted asFlowT,D, which finds the flow fC∗.Procedure 1.
Flow-enumerating procedure, FlowT,D.Input: A treeTand a depot setD.Output: A collectionFof flowsf.(1)
LetF=∅.(2)
for eachs1,s2,…,sk∈0,1,…,Qksuch that∑i=1ksi=Jdo(3)
(Construction of flows on edges connected to customers)(4)
for each customervinTdo(5)
Letfu,v=1, whereuis the parent ofv.(6)
end for(7)
(Construction of flows on edges connected to depots)(8)
fori=1,…,kdo(9)
Letfu,di=−si, whereuis the parent ofdi.(10)
end for(11)
(Construction of flows on edges connected to non-leaf vertices)(12)
Construct the flowfs1,s2,…,sk=fe|e∈ET, by the flow conservation property, i.e., the flow onfu,vis calculated byfv,v1+fv,v2, wherev1andv2are two children ofv.(13)
Add the flowfs1,s2,…,skintoF.(14)
end for(15)
ReturnF.
In the following lemma, it is stated that the flowfC∗ corresponding to C∗ is in F.Lemma 1.
The flowfC∗ corresponding to C∗ is in F, and the flow collection F returned by Procedure 1 has a cardinality in OQk.Proof.
Consider the flowfC∗. First, for any edge e connected to a customer vertex, the flow on e is equal to one. Second, for any edge e connected to a depot di, the flow on e is equal to si∗, where si∗ denotes the total number of customers served by di in C∗. Thus, since si∗≤Q for i=1,2,…,k, according to Step 8-Step 10 of Procedure 1, there exists a flow fs1∗,s2∗,…,sk∗ in F such that flow fvi,di satisfies fvi,di=si∗ for i=1,2,…,k, where vi denotes the parent of depot di for i=1,2,…,k. Meanwhile, due to Step 12, according to the flow conservation property, it can be verified that fu,v equals the net customer number in Tv in the optimal solution C∗. Meanwhile, consider the k edges connected to D. Procedure 1 constructs at most Qk flow combinations on the k edges. Therefore, the cardinality of F can be seen to be OQk.Example 1.
Consider the tree shown in Figure1. Let D=d1,d2=v2,v5, J=v1,v4,v6, and Q=2. We apply the flow-enumerating procedure to construct the flow collection F.
The flow-enumerating procedure is shown for the case in whichs1,s2=2,1, where fv3,v2=−2 and fv8,v5=−1. First, for the vertex v1, let fv3,v1=1. Similarly, the flow-enumerating procedure sets fv3,v2=1, fv7,v4=1, and fv8,v6=1. Second, for d1=v2, let fv3,v2=−2. Similarly, the flow-enumerating procedure sets fv8,v5=−1. Third, for v3, noticing that v2 and v1 are two children of v3, the flow fv7,v3 is constructed by the flow conservation property; that is, fv7,v3=fv3,v2+fv3,v1=−1. For v7, noticing that v4 and v3 are two children of v7, the flow fv9,v7 is constructed by the flow conservation property; that is, fv9,v7=fv7,v4+fv7,v3=0. Similarly, we can obtain that fv9,v8=0. Therefore, the flow f2,1 in F is shown in Figure 2, in which the flows are indicated near the edges.
For the cases1,s2=1,2, the flow constructed by the flow-enumerating procedure is shown in Figure 3.
Since the capacityQ=2 and the customer number J=3, it can be seen that any feasible solution to ℐ satisfies that s1,s2=2,1 or s1,s2=1,2. In summary, the flow collection F contains the flows f2,1 and f1,2, as indicated in Figures 2 and 3.Figure 2
The flow constructed froms1,s2=2,1 by the flow-enumerating procedure.Figure 3
The flow constructed froms1,s2=1,2 by the flow-enumerating procedure.


## 2.3. Flow-Splitting Phase

In this section, we present the procedures developed to constructℋv for a leaf vertex and a nonleaf vertex, respectively.Procedure 2.
Boundary procedure,Boundv,F.Input:A leaf vertexvand a given flow collectionF.Output:A state collectionℋv.(1)
Letℋv=∅.(2)
foranyfs1,s2,…,sk∈Fdo(3)
ifvis a depot andv=dithen(4)
Addf1u,v,f2u,v,…,fku,vtoℋvwithfiu,v=siandfju,v=0for anyj≠i. Let the state valuegf1u,v,f2u,v,…,fku,v=wu,vifsi>0; and let the state value to be zero ifsi=0.(5)
else(6)
Addf1u,v,f2u,v,…,fku,vtoℋvwithfiu,v∈0,1fori=1,2,…,kand∑i=1kfiu,v=1. Let the state valuegf1u,v,f2u,v,…,fku,v=wu,v.(7)
end if(8)
end for(9)
Returnℋv.Example 2.
Let us continue Example1. We construct the state collection ℋv for all the leave vertices, v1,v2,v4,v5,v6, respectively. Note that the flow collection F contains two flows f2,1 and f1,2. For v=v1, since v1 is a customer, for f2,1, the boundary procedure adds two states 0,1,1,0 into ℋv1. Meanwhile, for f1,2, the boundary procedure adds the same states 0,1,1,0 into ℋv1. Therefore, the state collection ℋv1 contains two states 0,1,1,0 with the state values g0,1=1 and g1,0=1. For v=v2, since v2 is a depot where the first vehicle is located and v2=d1, for f1,2, the boundary procedure adds −1,0 into ℋv2; for f2,1, the boundary procedure adds −2,0 into ℋv2. Therefore, the state collection ℋv2 contains two states −1,0,−2,0 with the state values g−1,0=1 and g−2,0=1. Similarly, one can obtain all the state collections ℋv for v=v1,v2,v4,v5,v6 in Table 1.
Next, we present the state recursion procedure. For any nonleaf vertexv∈V, it constructs ℋv based on ℋv1 and ℋv2, where v1 and v2 are the two children of v.Table 1
Construction ofℋv for all the leaves.
State collectionStateState valueℋv60,111,01ℋv50,−220,−12ℋv40,131,03ℋv2−1,01−2,01ℋv10,111,01Procedure 3.
State recursion procedure,Recursionv,ℋv1,ℋv2.Input:A non-leaf vertexv∈V,ℋv1andℋv2, wherev1andv2are two children forv.Output:A state collectionℋv.(1)
Letℋv=∅.(2)
foranyS1,S2∈ℋv1×ℋv2, in whichS1=f1v,v1,f2v,v1,…,fkv,v1andS2=f1v,v2,f2v,v2,…,fkv,v2do(3)
forj=1,2,…,kdo(4)
fju,v=fjv,v1+fjv,v2.(5)
end for(6)
Determine the state value forf1u,v,f2u,v,…,fku,vas∑j=1k⌈fju,v/Q⌉wu,v+∑i=12gf1v,vi,f2v,vi,…,fkv,vi.(7)
Addf1u,v,f2u,v,…,fku,vtoℋvif it satisfiesfju,v≤Qforj=1,2,…,k, and there exists no statef1′u,v,f2′u,v,…,fk′u,vinℋvwithfju,v=fj′u,vforj=1,2,…,kandf1′u,v,f2′u,v,…,fk′u,vhas a smaller state value.(8)
end for(9)
Returnℋv.Example 3.
Let us apply the state recursion procedure to constructℋv3, ℋv7, ℋv8, and ℋv9, respectively. First, we construct ℋv3 based on ℋv1 and ℋv2. In Table 2, all combinations of S1,S2∈ℋv1×ℋv2 are shown in the first column, the states constructed based on S1,S2 are shown in the second column, and their state values are indicated in the third column.
Furthermore, based onℋv3 and ℋv4, the state collection ℋv7 can be constructed as depicted in Table 3 (those states with “∗” are kept in ℋv7).
Similarly, we can constructℋv8 as in Table 4, in which S1,S2∈ℋv6×ℋv5 are shown in the first column.
Finally, we can constructℋv9 based on ℋv7 and ℋv8. Since vn=v9, we add one more vertex v10 into the graph with wv10,v9=0 and fv10,v9=0. Next, we construct the state collection ℋv9 as depicted in Table 5.
According to Algorithm1, only those flows f1v10,v9,f2v10,v9 with f1v10,v9=0 and f2v10,v9=0 are added to ℋv9. Then, the two states with “∗” are kept. Since the minimum state value in the state collection ℋv9 is 8, Algorithm 1 returns an optimal objective value as 8. Since the minimum total edge length for serving customers in J equals 8, by the fact that each edge is traversed exactly twice in any tour in a tree, the optimal solution to the instance can be seen to be 16.Table 2
Construction ofℋv3.
S1,S2StateState value0,1,−2,0,−2,121,0,−2,0−1,021,0,−1,00,020,1,−1,0−1,12Table 3
Construction ofℋv7.
S1,S2StateState value0,1,−1,0,−1,1∗71,0,−1,00,0∗51,0,−2,1−1,170,1,−2,1−2,2∗70,1,−1,1,−1,2∗71,0,−1,10,1∗61,0,0,01,0∗60,1,0,00,16Table 4
Construction ofℋv8.
S1,S2StateState value0,1,0,−20,−1∗51,0,0,−21,−2∗70,1,0,−10,0∗31,0,0,−11,−1∗7Table 5
Construction ofℋv9.
S1,S2StateState value0,0,0,−10,−1–0,0,1,−21,−2–0,0,1,−11,−1–0,0,0,00,0∗8−1,1,0,−1−1,0–−1,1,1,−20,−1–−1,1,1,−10,014−1,1,0,0−1,1–−2,2,0,−1−2,1–−2,2,1,−2−1,0–−2,2,1,−1−1,1–−2,2,0,0−2,2–1,0,0,−11,−1–1,0,1,−22,−2–1,0,1,−12,−1–1,0,0,01,0–−1,2,0,−1−1,1–−1,2,1,−20,0∗14−1,2,1,−10,1–−1,2,0,0−1,2–0,1,0,−10,0∗110,1,1,−21,−1–0,1,1,−11,0–0,1,0,00,1–


## 2.4. Correctness and Time Complexity for Dynamic Programming

We first establish Lemma2 to prove the feasibility of all the states in ℋvn.Lemma 2.
For eachv=v1,v2,…,vn, and for each state f1u,v,f2u,v,…,fku,v∈ℋv obtained in Algorithm 1, it satisfies that (i) each customer in Tv is served by exactly one depot and (ii) each depot serves no more than Q customers.Proof.
First, according to Step 6 of the boundary procedure, it can be verified that each customer is served by exactly one depot. Second, according to Step 7 of the state recursion procedure, it can be verified that each depot serves no more thanQ customers. Thus, (i) and (ii) can be verified for v=v1,v2,…,vn−1. For the case v=vn, since fivn+1,vn=0∑jfivn,vj=0 for i=1,2,…,k, one can see that the total customer number assigned to di equals si, where si denotes the flow on u,di in the flow fs1,s2,…,sk, which implies that each state in ℋvn corresponds to a feasible solution to the k-depot CVRPT.
We then establish Lemma3 to prove the optimality of Algorithm 1, which, together with Lemma 2, will be used to prove the correctness of Algorithm 1 in Theorem 1.Lemma 3.
Considerf1C∗,f2C∗,…,fkC∗, in which fiC∗ denotes the flow corresponding to di in fC∗. For each v=v1,v2,…vn, there exists a state f1u,v,f2u,v,…,fku,v∈ℋv, obtained by Algorithm 1, such that fiu,v=fi∗u,v for i=1,2,…,k and the state value gf1u,v,f2u,v,…,fku,v is not greater than gf1∗u,v,f2∗u,v,…,fk∗u,v, where fi∗u,v denotes the flow in fiC∗ on the edge u,v, and gf1∗u,v,f2∗u,v,…,fk∗u,v denotes the shortest length traversed by all the k vehicles with the ith vehicle serving fi∗u,v net customers in Tv for i=1,2,…,k.Proof.
We prove Lemma3 by induction. For each leaf v which is a customer, we know that fi∗u,v∈0,1 for i=1,2,…,k and ∑ifi∗u,v=1, which implies that f1∗u,v,f2∗u,v,…,fk∗u,v∈ℋv. For each leaf v which is a depot, we can conclude that f1∗u,v,f2∗u,v,…,fk∗u,v∈ℋv according to Lemma 1. Furthermore, since fiu,v=f1∗u,v for i=1,2,…,k, according to the definition of gf1u,v,f2u,v,…,fku,v and gf1∗u,v,f2∗u,v,…,fk∗u,v, we have gf1u,v,f2u,v,…,fku,v≤gf1∗u,v,f2∗u,v,…,fk∗u,v, which implies that the lemma holds for any leaf vertex v
Next, consider anyv∈V that is not a leaf. Let v1 and v2 denote the two children of v. Assume that Lemma 3 holds for each child of v, denoted as v1 and v2. We are going to show as follows that Lemma 3 holds for v.
First, for anyvi for i=1,2, there exists a state f1v,vi,f2v,vi,…,fkv,vi∈ℋvi such that, for j=1,2,…,k, fjv,vi=fj∗v,vi and gf1v,vi,f2v,vi,…,fkv,vi≤gf1∗v,vi,f2∗v,vi,…,fk∗v,vi. Since ∑i=12fjv,vi=∑i=12fj∗v,vi for j=1,2,…,k, we can conclude that there exists a state f1u,v,f2u,v,…,fku,v in ℋv such that fiu,v=fi∗u,v for i=1,2,…,k. Then, it remains to prove that gf1u,v,f2u,v,…,fku,v≤gf1∗u,v,f2∗u,v,…,fk∗u,v.
According to the calculation ofgf1u,v,f2u,v,…,fku,v in Step 6 of Procedure 3, it satisfies(1)gf1u,v,f2u,v,…,fku,v=∑j=1kfju,v/Qwu,v+∑i=12gf1v,vi,f2v,vi,…,fkv,vi≤∑j=1kfju,v/Qwu,v+∑i=12gf1∗v,vi,f2∗v,vi,…,fk∗v,vi≤∑j=1kc∗u,vwu,v+∑i=12gf1∗v,vi,f2∗v,vi,…,fk∗v,vi=gf1∗u,v,f2∗u,v,…,fk∗u,v,in which the first inequality holds by the induction, and the second inequality holds by the fact that fju,v/Q is the lower bound for the vehicle in dj to serve fju,v net customers for all vehicles within Tv and c∗u,v denotes the number of times for the vehicle in dj traversing on u,v in the optimal solution C∗ (each edge is traversed at most once by one vehicle in an optimal solution).
Based on Lemma3, the optimality for Algorithm 1 is proved. Notice that, for each leaf vertex v, at most Qk states f1u,v,f2u,v,…,fku,v are kept in ℋv because the cardinality of F is at most Qk. Meanwhile, for any nonleaf vertex v, since each fiu,v has at most Q possibilities for i=1,2,…,k and thus at most Qk states f1u,v,f2u,v,…,fku,v are kept in ℋv, the maximum number of states kept in Algorithm 1 is OQk. Then, the following theorem holds.Theorem 1.
Algorithm1 returns an optimal solution to any given instance of the k-depot CVRPT in OnQk time.SinceQ≤n, one can see that Algorithm 1 is a polynomial-time exact algorithm for the k-depot CVRPT.


## 3. Conclusion

In this article, we provide the polynomial-time exact algorithm for thek-depot CVRPT. We can see that, with Q=n, the polynomial-time exact algorithm for the k-depot CVRPT can be applied to solve the k-depot TSPT. It is worth noting that although the dynamic programming devised in this paper can solve the k-depot CVRPT and k-depot TSPT with a min-sum objective, it cannot be applied directly to the min-max k-depot TSPT in Xu et al.’s work [4].Furthermore, the exact algorithm may set a basis for developing approximation algorithms fork-depot CVRP on general graphs. The approximation algorithms can be designed as in the following two steps: (1) Find a capacitated constrained spanning forest, in which each tree in the forest contains enough vehicles to serve all the customers within the tree. (2) Apply the exact algorithm for the k-depot CVRPT to find an optimal solution for the subinstance restricted on each tree, respectively. Finally, the optimal solution on the capacitated constrained spanning forest is returned as the approximated solution to the k-depot CVRP. However, we can see that developing approximation algorithms for the k-depot CVRP has the following two difficulties: (1) Polynomial-time exact algorithm for finding a capacitated constrained spanning forest is unknown in the literature. (2) How to bound the total edge weight for the optimal solution to the k-depot CVRPT remains an issue.



---

*Source: 6648044-2021-03-08.xml*