Suppose we have a metric space $(X,d)$ and we call $r$ to be a root vertex and then there are $n$ clients(i.e. $n$ vertices/nodes) who need packages delivered to them from $r$. The $i$th client demands a package of weight $w_i$ and is $d(r,i)$ distance away. Two clients $i,j$ are $d(i,j)$ distance away. Initially, all the packages are at the root.

Now we will deliver these packages and we can carry at most $W$ weight during delivery. Once delivered, we will have to come back to the root again and collect more packages and deliver again until all the packages have been delivered. We are given the weights of all packages and also the set of all distances. Our goal is to find the shortest route. Design a constant factor approximation algorithm for a tree.

By this, I mean that $r$ is the root of the tree and the clients are at the other nodes of the tree including the leaves of the tree, i.e. there are $n$ nodes. We need to design the shortest route. Note that we are not going to visit each client only once because of the tree structure. (If we only think of the clients as the leaves of the tree and say there are $n$ nodes, then is the problem equivalent? I don't know.)

I have found this link that talks about the general problem: http://dimacs.rutgers.edu/programs/challenge/vrp/vrpsd/

But since my graph is only a tree, it should be much easier to give a constant factor approximation algorithm. Any help will be appreciated.

  • $\begingroup$ The paper "CAPACITATED VEHICLE ROUTING ON TREES" by Labbe, Laporte & Mercure gives a 2-approximation algorithm for the problem when solved on trees, which was my question essentially. The proof is clear from sections 1 and 2. Here is the link: jstor.org/stable/171168?seq=4 $\endgroup$
    – Sandra
    Mar 10, 2023 at 1:35


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.