Minimizing Latency of Capacitated k-Tours

We study variants of the capacitated vehicle routing problem. In the multiple depot capacitated k-travelling repairmen problem (MD-CkTRP), we have a collection of clients to be served by one vehicle in a fleet of k identical vehicles based at given depots. Each client has a given demand that must be satisfied, and each vehicle can carry a total of at most Q demand before it must resupply at its original depot. We wish to route the vehicles in a way that obeys the constraints while minimizing the average time (latency) required to serve a client. This generalizes the Multi-depot k-Travelling Repairman Problem (MD-kTRP) (Chaudhuri et al. in 44th IEEE-FOCS, pp 36–45, 2003; Post and Swamy in 26th ACM-SIAM SODA, pp 512–531, 2015) to the capacitated vehicle setting, and while it has been previously studied (Lysgaard and Wholk in Eur J Oper Res 236(3):800–810, 2014), no approximation algorithm with a proven ratio is known. We give a 42.49-approximation to this general problem, and refine this constant to 25.49 when clients have unit demands. As far as we are aware, these are the first constant-factor approximations for capacitated vehicle routing problems with a latency objective. We achieve these results by developing a framework allowing us to solve a wider range of latency problems, and crafting various orienteering-style oracles for use in this framework. We also show a simple LP rounding algorithm has a better approximation ratio for the maximum coverage problem with groups (MCG), first studied by Chekuri and Kumar (Approximation, randomization, and combinatorial optimization, algorithms and techniques, pp 72–83, 2004), and use it as a subroutine in our framework. Our approximation ratio for MD-CkTRP when restricted to uncapacitated setting matches the best known bound for it (Post and Swamy in 26th ACM-SIAM SODA, pp 512–531, 2015). With our framework, any improvements to our oracles or our MCG approximation will result in improved approximations to the corresponding k-TRP problem.

1. This differs slightly from the typical definition of a tour, since a tour here must be composed of exactly one cycle.

2. The approximation ratio was stated in [10] to be 12, but due to a technical issue in their analysis, they were off by a factor of 2. We provide the corrected analysis in the appendix.

3. We omit the \(\epsilon \) for the remainder of this discussion for clarity.

4. Note that any F that is a linear function of x satisfies this condition.

5. There is an annoying detail hidden here - this lower bound only holds if no client has latency less than b in OPT. However, by scaling distances we can ensure this is always the case.

6. This construction was first described in [2], and can be used to prove Inequality 11.

7. If Q is not poly-bounded, note there is a simple poly-time algorithm to do this that avoids explicitly building the graph and trying more than |V| values of R.

8. We omit the \(\epsilon \) from the rest of the discussion for clarity.

9. We drop the \(\epsilon \) here for convenience, but it can be also dropped from the final approximation ratio due to arguments in [9].

We would like to thank anonymous referees for their suggestions and comments.

Authors and Affiliations

1. Department of Computing Science, University of Alberta, Edmonton, Canada

   Christopher S. Martin & Mohammad R. Salavatipour

Corresponding author

Correspondence to Mohammad R. Salavatipour.

A preliminary version of this paper appeared in Proceedings of ISAAC 2016.

Supported by Alberta Innovates Technology Futures. Supported by NSERC.

Appendix: Corrected Analysis of MD-kTRP Algorithm from [10]

The analysis given in Sect. 3.1 does not appear to improve significantly over the analysis given in [10], despite the increased complexity, since they claim a 12-approximation for the uncapacitated multi-depot k-TRP using \(\ell \)-MST as a subroutine (we achieve 11.89). We re-derive the approximation ratio for their algorithm using the same ideas and tools in this section, and show that it is in fact a 24-approximation. The difference arises from a small miscalculation made in their paper.

The algorithm of [10] is similar to the one presented in Sect. 3. Computations are done in phases, and in each phase j we are given a set of uncovered clients \(C_j^u\) and a budget \(2^j\). We use a subroutine \(\mathcal {C}\) to find a tour of cost \(\le 2^j\) rooted at each depot, and which cumulatively cover as many clients in \(C_j^u\) as possible.

The algorithm for phase j is the following:

We define \(\mathcal {C}\) similar to how we did in Sect. 3, with the exception that we no longer need to specially define the sets \(\mathcal {W}_i\); since we are dealing with the uncapacitated problem, \(\mathcal {W}_i\) becomes all possible walks from \(r_i\). Thus, our oracle for the MCG instance can be the \(\ell \)-MST oracle described in Sect. 3.2 (also what is used in [10]).

For the purpose of analysis, we require that \(j \ge 1\). As in Sect. 3.1, we will define \(n_j\) to be the number of clients we do not cover by the end of phase j, and similarly \(n_j^{OPT}\) will be the number of clients in a fixed optimal solution which have latency \(\ge 2^j\). We define \(n_{j \le 0}\) and \(n_{j\le 0}^{OPT}\) to be n.

We can bound what we cover in each iteration, and what we have left to cover after each iteration, using the following two lemmas, which are proven in a similar way to Lemma 3 and Lemma 4. We only need to take into account that in each iteration we find 2 tours per depot instead of one, and explicitly use the \(\ell \)-MST based uncapacitated oracle:

Lemma 9

(Lemma 4 in [10]) At the end of phase j, we have covered at least \(\frac{3}{4}|O_j - C_{j-1}^v|\) clients.

Lemma 10

(Lemma 5 in [10]) \(n_j \le \frac{1}{4}n_{j-1} + \frac{3}{4}n_j^{OPT}.\)

In our solution, any client covered in phase j has latency bounded by \(4 \sum _{i\le j} 2^i\), since we must traverse any tour we buy in a previous iteration as well as the one we bought in phase j.^{Footnote 9} Summing this for all clients and using the definition of \(n_j\), we can bound the total latency for our solution by

This bound is primarily where we differ from [10]. The bound they present is \(4 \sum _j 2^j n_j\), using an equivalent definition of \(n_j\). This implies that each client has latency bounded by \(4 \sum _{i < j} 2^i\), which does not include the tours bought when the client was visited.

The cost of an optimum solution is bounded from below by

which by re-arranging the summation and noting that \(2^j - 2^{j-1} = 2^{j-1}\), is equivalent to

We can now use Lemma 10 to bound the cost of our solution against the optimum solution. Each step is derived by re-arranging sums.

We thus have a 24-approximation to the uncapacitated multi-depot k-TRP.

Reprints and permissions