1 Introduction

Vehicle routing is a term that is used in the context of Operations Research to refer to a variety of optimization problems. These problems have in common that they are defined on a graph which is traversed by one or multiple vehicles of finite capacity to supply demand of customers. There are many variants, many real-world applications, and many exact and heuristic algorithms, see, e.g., [1].

Most exact algorithms, and even some heuristics, rely on LP bounds of a mixed integer programming formulation. Moreover, some of the fastest algorithms for computing LP bounds use subroutines that require pseudo-polynomial computation time. In particular, their computation time is polynomial in the vehicle capacity, like in the case of [2] and [3]. Our contribution is a preprocessing method to reduce the vehicle capacity, which improves the LP bounds and reduces the computation time of the aforementioned algorithms.

In this paper, we focus specifically on the capacitated vehicle routing problem (CVRP) although the results carry over to other vehicle routing problems. The CVRP is defined on a complete digraph \(G=(N,A)\), where \(N=\{0\}\cup N'\), 0 represents the depot and \(N'\) the set of customers. An unlimited number of vehicles of finite capacity Q are used to satisfy demand. The demand of customer \(i\in N'\) is denoted by \(q_i\), satisfying \(0\le q_i\le Q\). A route is a simple cycle in G which starts and ends at the depot, such that the total demand of the visited nodes does not exceed the vehicle capacity. A cost \(c_{ij}\) is incurred for traversing an arc \((i,j)\in A\). The CVRP is to find a collection of routes such that all demands are satisfied at minimum cost.

In Section 2, we demonstrate the preprocessing method. Here we also provide an example of an instance for the CVRP and a well-known formulation for which the LP bound improves after preprocessing. Next, we indicate in Section 3 that for none of the 233 considered well-known benchmark instances of the CVRP, the capacity can be reduced using our preprocessing method. We then show a series of simulations which perhaps surprisingly suggest that in many cases the vehicle capacity can only be reduced by a very small amount, if at all. We comment on the implications of this in Section 4.

2 Preprocessing

Next we provide our preprocessing method and discuss the computational gains it provides. Observe that there might not exist a subset of customers for which the total demand is exactly the vehicle capacity. Determining whether this is the case is precisely a Subset-Sum-Decision problem, one of the 21 NP-complete problems of [4] which was referred to as the Knapsack problem. We denote by \(Q'\) the maximum total demand that fits in a vehicle amongst subsets of customers, i.e.,

$$Q\kern0.1500em^{\prime}=\max _{S\subseteq N'}\left\{ \sum\limits_{i\in S}q_i:\sum\limits_{i\in S}q_i\le Q\right\}.$$

Finding \(Q\kern0.1500em^{\prime}\) is a Subset-Sum-Optimization problem, which first appeared in [5] with the name Value-Independent Knapsack problem, and should not be confused with the Subset-Sum-Decision problem. Solving the Subset-Sum-Optimization problem is weakly NP-hard, since Subset-Sum-Decision reduces to it and pseudo-polynomial time algorithms exist to solve it.

Modifying an instance of the CVRP by replacing Q with \(Q\kern0.1500em^{\prime}\) does not alter the set of feasible solutions. Moreover, this can be done as a preprocessing method. Next, we show that there are computational gains from doing this.

We provide an instance for which the LP bound improves after replacing Q with \(Q\kern0.1500em^{\prime}\) for the well-known two-index vehicle flow formulation (2ICF) of the CVRP by [6]. Denoting by \(x_{ij}\) the decision variable indicating whether arc \((i,j)\in A\) is used, 2ICF is

$$\begin{aligned} \min&\sum\limits _{(i,j)\in A}c_{ij}x_{ij} && \\ {}\sum\limits _{j\in N} x_{ji} &= 1 &&\forall i \in N' \\ {}\sum \limits _{j\in N} x_{ij} &= 1 && \forall i \in N' \\ {}\sum \limits _{i\in S, j\in N\backslash S} x_{ij} &\ge \left\lceil \frac{\sum\limits{\textbf {}}_{i\in S}q_i}{Q}\right\rceil &&\forall S\subseteq N' \end{aligned}$$
(1)
$$\begin{aligned} x_{ij} & \in \{0,1\} &&\forall (i,j)\in A. \end{aligned}$$

The last set of constraints in Eq. (1) are known as rounded capacity inequalities, and there are exponentially many. They are strongly NP-hard to separate, see [7], and heuristics like those of [8] are commonly used for this purpose. Observe that for all sets of customers that fit in one vehicle, i.e., \(S\subseteq N'\) for which \(\sum _{i\in S}q_i\le Q\), the corresponding rounded capacity cut is not affected by replacing Q with \(Q'\) since \(\left\lceil \frac{\sum _{i\in S}q_i}{Q}\right\rceil =1=\left\lceil \frac{\sum _{i\in S}q_i}{Q'}\right\rceil\). Nevertheless, for the following instance the LP bound improves from replacing Q with \(Q'\).

Consider an instance with three customers. Let \(c_{0i}=c_{i0}=5\) and \(c_{ij}=8\) for all \(i,j\in N'\). Let \(q_i=2\) for all \(i\in N'\) and \(Q=3\). Note that \(Q'=2\) for this instance, and replacing Q with \(Q'\) affects only a single constraint of 2ICF. In particular the rounded capacity cut \(x_{10}+x_{20}+x_{30}\ge 2\) becomes \(x_{10}+x_{20}+x_{30}\ge 3\). It is easily verified that \(x_{0i}=x_{i0}=\frac{2}{3}\) and \(x_{ij}=\frac{1}{6}\), for all \(i,j\in N'\), is a feasible solution to the LP relaxation of 2ICF, with objective value 28. In fact it is optimal. When replacing Q with \(Q'\), there is only one feasible solution to the LP relaxation of 2ICF, namely \(x_{0i}=x_{i0}=1\) for all \(i\in N'\) with objective value 30, which is therefore optimal. Coincidentally, this is even the optimal integer solution. We conclude that the LP bound has improved from replacing Q with \(Q'\).

While an improved LP bound might provide computational gains in a branching algorithm, next we discuss a more direct computational gain. Consider the set partitioning formulation, which is one of the strongest known CVRP formulations, see [9]. Denoting by R the set of all routes, \(x_r\) the decision variable indicating whether route \(r\in R\) is selected, \(c_r\) the cost of \(r\in R\), and \(a_{ir}\) indicating whether \(i\in N'\) is visited on \(r\in R\), the set partitioning formulation is

$$\begin{aligned} \begin{aligned}\text {min} &\sum \limits _{r \in R}c_rx_r &&\\ {}\sum \limits _{r\in R} a_{ir}x_r &= 1 && \forall i \in N^{\prime } \\ {}x_r &\in \{0,1\} && \forall r\in R. \end{aligned} \end{aligned}$$

First note that the set partitioning formulation is not affected by replacing Q with \(Q'\). Indeed, the set R remains the same, and as a result so does the LP bound. However, fast algorithms do not use this formulation, for which an explanation might be that computing the set partitioning bound of the CVRP is NP-hard, see [10]. Instead, the set R is extended with routes that visit customers more than once, allowing to compute the LP bound in pseudo-polynomial time. Two examples are q-routes, see [2], and ng-routes, see [11], which allow for computation time that is polynomial in the vehicle capacity. Hence, the computation time goes down when replacing Q with \(Q'\). Of course, also in this case the LP bound might improve, since the extended set corresponding to \(Q'\) might be smaller.

3 Experiments

To assess the computational gains of our preprocessing procedure, we consider the following sets of benchmark instances of the CVRP: A, B, CMT, E, F, M, P, Tai, X by [12-16] and [17], which can all be conveniently downloaded from [18]. Out of the 14 CMT instances we only consider 7 because they come in pairs with the same demand. In total, these are 233 instances.

For each instance we compute \(Q'\) by using our own implementation of a standard dynamic programming algorithm for the Subset-Sum-Optimization problem from [19]. For none of the 233 instances does \(Q'\) differ from Q. The question is now whether there is something particular about these benchmark instances, or whether \(Q'\) and Q are generically not much different. Next, we show simulation experiments that perhaps surprisingly suggest that the latter seems to be the case.

Consider the following simulation experiment. For a given number of customers, we randomly generate demand. In the benchmark instances demand is always integer. Although we deviate from this, note that given the finite precision of modern computers, we can effectively only sample from discrete distributions. That is, we consider a discrete support, resulting in only a finite number of different demand realizations. Given Q, we then compute \(Q'\) and assess their difference.

The demand distribution affects the difference between \(Q'\) and Q. Roughly stated, for a fixed number of customers, the higher the cardinality of the support the less likely it becomes that a subset of demands sums precisely to Q. Furthermore, this becomes more likely when the number of customers increases. Next, we evaluate the magnitude of these effects in a simulation experiment.

In Table 1, the results are shown of replicating the simulation experiment 100,000 times. In each replication, demand for 30 customers is generated using a discrete uniform distribution between 1 and 30, where we vary the decimal precision from 0 to 6 decimals. This means that for 0 decimals the support has cardinality 30, and for 6 decimals the support has cardinality 29,000,001. We use a vehicle capacity of 100. For the case of 0 decimals, this resembles the demand generating process of the A and B instances, although for those instances 10% of the demands are multiplied by 3.

The column ‘# Dec’ in Table 1 indicates the number of decimals considered. The column ‘# Diff’ indicates the number of replications out of 100,000 for which \(Q'\) and Q are different. The columns ‘Min. Diff’, ‘Avg. Diff’ and ‘Max. Diff’ show the minimum, average and maximum difference between \(Q'\) and Q respectively, only considering those replications for which a difference was observed. Note that the minimum and maximal difference can be computed with absolute precision and are displayed as such, while for the average difference this is not the case and we report only relevant decimal places.

Table 1 Difference between \(Q'\) and Q, 100,000 replications, 30 customers, 100 capacity, discrete uniform demand between 1 and 30
Full size table

Observe from Table 1 that there are no differences for any replications with a precision of up to three decimals. With a precision of 4 decimals or more, the number of differences increases. These results support the claim that it becomes more likely to observe a difference between \(Q'\) and Q as the cardinality of the support grows. Furthermore, note that in none of the 700,000 cases the vehicle capacity can be reduced by more than 0.0004%. We consider this a rather small difference, especially taking into account that only 30 customers are used. We finally remark that for a precision of 4 decimal places and higher, the minimum difference is always the smallest possible difference given the precision.

We repeat this experiment with a different demand distribution and more customers. The demands in the Tai instances are generated using an exponential distribution, with realizations rounded to the nearest integer and truncated at the vehicle capacity. The smallest Tai instance has 75 customers. To resemble this case, we generate exponentially distributed demand with a mean of 175 for 75 customers, with realizations rounded to 0 up to 5 decimal places and truncated at the vehicle capacity. We use a vehicle capacity of 1500, and again replicate each experiment 100,000 times. In none of these 600,000 new cases is a difference observed.

4 Conclusion

In this paper, a preprocessing method is provided which reduces the vehicle capacity of a CVRP instance. This provides computational gains by improving LP bounds of mixed integer programming formulations of the CVRP, and decreases computation time for algorithms of which the computation time depends on vehicle capacity.

Although we demonstrate these computational gains with concrete examples, in none of the 233 considered benchmark instances is there any gain from preprocessing. Moreover, our simulation experiments suggest that in many cases, we should not expect a big difference between the vehicle capacity and the preprocessed capacity. This would imply that generically we might not expect much direct computational gains from the preprocessing method.

However, the insights provided in this paper might also prove beneficial in future analysis and algorithmic development. We claim that we may now assume that vehicle capacity is tight, in the sense that there exists at least one subset of customers of which the total demand is precisely the capacity. Either this is immediately the case, or an instance can be modified to make it so in pseudo-polynomial time.

The preprocessing method straightforwardly carries over to other vehicle routing problems. In future research, the preprocessing method can be refined further for such problems. For example, for the vehicle routing problem with time windows, one can consider only those subsets of customers for which a feasible route exists satisfying all time windows. This might provide larger reductions of the vehicle capacity, or a reduction in more cases, potentially leading to more computational gains.