The disaggregated integer L-shaped method for the stochastic vehicle routing problem

In two-stage stochastic programs, first-stage decisions are taken before the realization of uncertain parameters. Once these parameters are revealed, second-stage decisions are taken to correct the first-stage solution. The objective is to find a first-stage solution that minimizes the cost of the first stage and the expected cost of the second stage. These problems have typically been solved using Benders decomposition (Benders,, 1962), or equivalently the L-shaped method (Van Slyke and Wets,, 1969) when they have continuous variables and a large number of scenarios. For solving programs with binary variables in both stages, researchers historically relied on the integer L-shaped method of Laporte and Louveaux, (1993). These methods can be regarded as branch-and-cut (B&C) algorithms where the expectation function of the objective is relaxed and replaced by a variable that is linearly bounded with inequalities. Nowadays, the L-shaped and integer L-shaped methods are considered to be computationally impractical because of their slow convergence. Several techniques have been proposed in the literature to mitigate this problem. A common approach is to add lower bounding functionals (LBFs) (Birge and Wets,, 1986) to the model. These inequalities bound the recourse for a much broader range of solutions than optimality cuts. However, many of the most impactful ones are problem-specific, which limits their range of application. Other methods like the logic-based Benders decomposition of Hooker and Ottosson, (2003) try to overcome the problem by providing cuts that include only a small subset of variables. These cuts are then effective for a large number of solutions. Other enhancements are reported in Rahmaniani et al., (2017).

This paper introduces a new integer L-shaped method, named the disaggregated integer L-shaped method (DL-shaped method). This method is tailored for a specific class of two-stage stochastic programs in which, given a first-stage solution, the recourse cost can be expressed as a sum of independent recourse functions involving disjoint sets of first-stage variables. The DL-shaped method also requires each of the resulting recourse functions to be monotonic. In the case of a minimization problem, this property means that adding first-stage variables to a component cannot decrease its recourse cost. Many two-stage stochastic programs have such structure and property. For example, in the bin packing problem with uncertain weights, it is possible to decompose the first-stage solution by bin. This problem is found in the allocation of surgeries to operating rooms (Denton et al.,, 2010). Similarly, in job scheduling problems (Li et al.,, 2022; Elçi and Hooker,, 2022), jobs are assigned to machines, and their first-stage solution can be decomposed by machine. In the latter application, the monotonicity of the objective function corresponds to the fact that assigning more jobs to a machine cannot decrease the expected makespan of its operations.

We propose an implementation of the DL-shaped method for the vehicle routing problem with stochastic demands (VRPSD). In this problem, each customer has to be visited exactly once by a fleet of capacitated vehicles. This structure makes it possible to decompose the recourse cost by route. Customer demands are modeled by independent random variables (RVs) with known distributions and are only observed when a vehicle arrives at the customer’s location. A failure occurs when a vehicle arrives at a customer’s location with a remaining capacity smaller than the customer’s demand. When this happens, a recourse action must be implemented to satisfy the current and next customer demands. This work applies the detour-to-depot (DTD) recourse action, which performs a back-and-forth trip from the customer to the depot to restock the vehicle. We will show that this recourse action has the property of monotonicity under some conditions.

The contributions of this paper are as follows. First, we introduce the DL-shaped method in the context of the VRPSD. Second, we demonstrate that, although the DTD recourse function is not monotonic in general, it is for Poisson distributions and some normal, binomial, Erlang, and negative binomial distributions when the sum of the expected demands on each route respects the vehicle capacity. Third, we present several new lower bounds on the DTD recourse function that take advantage of its monotonicity and are used by the LBFs. To our knowledge, we perform the first numerical comparison of the different lower bounds on the recourse. Our numerical experiments show our new lower bounds greatly improve over the ones found in the literature and that our new method achieves state-of-the-art results on existing benchmark instances. This leads us to propose new instances that are more challenging than the existing ones from the literature.

The remainder of this paper is organized as follows. Section 2 presents the literature on stochastic vehicle routing problems. Section 3 presents the mathematical formulation of the problem. Section 4 presents theoretical results on the monotonicity of the recourse function. Section 5 details the implementation of the new method as well as the new lower bounds for the problem. Section 7 presents the numerical results for our implementation, and lastly, Section 8 presents the conclusion.

The stochastic vehicle routing problem with random customer demands and multiple depots by Tillman, (1969) is considered to be the first studied version of the VRPSD. Nowadays, the state-of-the-art exact methods can solve instances with more than 100 customers (Florio et al.,, 2020). By this measure, since Tillman, (1969), the field has linearly increased over time in its solution capability. Although this is considerable progress for an NP-Hard problem like the VRPSD, Gendreau et al., (2016) conclude that we are still in the early stages of the field, with room for significant improvement in exact solution methods. In this section, we present a historical review of the exact methods developed for the VRPSD.

The a priori and re-optimization paradigms are the two modeling paradigms used in the literature. The choice of either of these paradigms depends on when the stochastic parameters are revealed in the solution process. Formalized by Bertsimas et al., (1990), the a priori paradigm relies on the design of routes that cannot be modified after they have been fixed. Re-optimization was formalized by Dror et al., (1989) as a Markov decision process (MDP) and allows for the construction and adjustment of routes as information is gradually revealed. In recent decades, the increasing availability of information technologies has simplified the gathering of real-time information that helps decision-makers re-optimize a priori routes on the fly. As a consequence, new paradigms have emerged, such as the dynamic and online vehicle routing problems, where the parameter are updated throughout the solution process. A comprehensive survey on the dynamic vehicle routing problem is presented in Pillac et al., (2013).

The DTD and optimal restocking (OR) policies are the most common in the literature. Under the DTD policy, restocking trips are only allowed in case of failure. Studies of the VRPSD with this policy include the works of Gendreau et al., (1995), Laporte et al., (2002), and Jabali et al., (2014). For the OR policy, vehicles are allowed to perform preventive returns to the depot to avoid costly failures. Yang et al., (2000) have shown that the OR policy can be calculated by solving a Bellman equation. Relevant works under this policy include Louveaux and Salazar-González, (2018), Salavati-Khoshghalb et al., (2019), Florio et al., (2020), and Hoogendoorn and Spliet, (2023). Additionally, variants of these two policies have also been studied. For example, Ak and Erera, (2007) propose a recourse policy that is based on pairwise sets of a priori routes. Also, in Secomandi and Margot, (2009), an a priori planned tour is partly re-optimized using a MDP that is limited to a restricted set of states. Florio et al., (2022) apply another type of partial re-optimization in which the order of visit of successive customers in a planned route is allowed to be switched.

Several numerical experiments have been performed in the literature to compare the effectiveness of the proposed policies. Those of Louveaux and Salazar-González, (2018) show that the OR policy might yield some savings compared to the DTD policy, but they also noticed that the optimal a priori routes are most of the time the same as those from the DTD policy. Their results also indicate that more instances can be solved when using the DTD policy. Salavati-Khoshghalb et al., (2019) computed the cost of the DTD policy from an optimal OR policy solution. An average increase in the optimal value of about 0.63% could be observed. Florio et al., (2020) indicate that the benefit of using the OR policy over the DTD policy is close to none. However, savings of 1.6% on average can be obtained when reducing the number of possible routes and allowing the capacity to be exceeded. They also noted that the benefit of using the OR policy decreases when the demand variability increases. Finally, the partial re-optimization policy of Florio et al., (2022) can further reduce costs compared to the OR policy by 0.73% on average. There are still open questions from these observations. Those analyses are limited to relatively few instances of small sizes. In light of these results, the DTD policy is still worth studying.

Exact methods from the literature for the VRPSD divide into two categories, namely integer L-shaped and branch-and-price (B&P) methods. For the integer L-shaped method, its main advantages are that it can manage solutions that include long routes (40+ nodes per route), it is compatible with several demand distributions, including continuous ones, and it can handle many different types of recourse functions. Unfortunately, it is less efficient for instances requiring more than three vehicles. Although several authors have devoted important efforts to propose LBFs (Laporte et al.,, 2002; Jabali et al.,, 2014; Hoogendoorn and Spliet,, 2023) that alleviate this limitation, solving instances with a large number of vehicles remains a challenge. On the other hand, B&P methods have shown to be efficient for instances that require a large number of short routes, but they also have important limitations. They have been almost exclusively implemented for demands following Poisson distributions. Also, for the OR policy, they require to store entire routes in the labeling algorithm of the column generation subproblem, which greatly limits the length of the routes the method can handle. Finally, for the DTD policy, they do not scale well when the demands and the capacity of vehicles are high since the size of the pricing subproblem depends on the vehicle capacity. To mitigate this limitation, some methods from the literature divide each instance’s capacity and expected demands by their greatest common divisor to produce subproblems of tractable size in their column generation procedures. Although the instances resulting from this transformation are usually good approximations of the original problems, they are not equivalent in general and can have different optimal solutions and values.

The idea of disaggregating the recourse, i.e., separating it into independent disjoint functions, was studied by Wets, (1966). They show that the recourse can be disaggregated trivially when the second-stage linear programming matrix can be decomposed into blocks. In such cases, a variable is added in the first stage for each block. Then, in each iteration, the second-stage problem of each block is solved, and an optimality cut that contains only first-stage variables of the block is added. Extending this idea to problems whose second-stage matrix is not decomposable is challenging.

The second stage of vehicle routing problems does not present this block structure. One of the reasons for this is that the uncertain parameters are progressively revealed as the clients are visited. However, the first-stage solutions of vehicle routing problems have a separable structure, as they form independent routes. Some works have introduced techniques to exploit this separability. Séguin, (1996) proposed to disaggregate the recourse by routes, Côté et al., (2020) proposed to bound the recourse for sets of nodes, and Hoogendoorn and Spliet, (2023) for unstructured sets. These methods add variables in the first stage to bound some parts of the second stage by using linear inequalities. Numerical experiments show that these valid inequalities help at reducing computation times. The superiority of the DL-shaped method over these previous works comes from its new optimality cuts and new LBFs that simultaneously bound the recourse for paths and sets of nodes that apply to a broad range of first-stage solutions.

As noted in the introduction, the DL-shaped method requires the monotonicity of the recourse function. The topic of monotonicity received little attention in the VRPSD literature. To the best of our knowledge, the articles by Dror and Ball, (1987) and Kreimer and Dror, (1990) constitute the only theoretical works on the matter. They both give sufficient conditions for the probability of a failure to increase at each customer on a route. Although we show that this property is sufficient for the recourse function to be monotonic under the DTD policy, the results of Dror and Ball, (1987) and Kreimer and Dror, (1990) only apply to independent and identically distributed (i.i.d.) demands. This paper introduces sufficient conditions for the monotonicity of the recourse function that can be applied in the independent but not identically distributed case. We show conditions under which it is respected for Poisson, normal, binomial, Erlang, and negative binomial demands.

This section introduces the notation that will be used throughout the paper and the mathematical model of the problem.

The VRPSD is defined as follows. Let $G=\{N_{0},E\}$ be an undirected graph where $N_{0}=\{0,1,...,n\}$ is the set of nodes, with node $0$ being the depot, $N=\{1,...,n\}$ the set of customer nodes, and $E=\{(i,j):i,j\in N,i<j\}$ the set of edges. Traveling on edge $(i,j)$ incurs a travel cost of $c_{ij}$. Each customer $i\in N$ has a non-negative demand given by the RV $\xi_{i}$, with an expected value $\mu_{i}$ and a standard deviation $\sigma_{i}$. It is assumed that the demand variables are independently distributed. A fleet of identical vehicles is available to satisfy customer requests. Each vehicle has a capacity $Q$ and must follow a route that starts and ends at the depot. Each customer must be visited exactly once. A route is defined as a sequence of customers starting and ending at the depot, and a sequence is feasible if the sum of the expected demands respects the vehicle capacity. This condition was added by Laporte et al., (2002) to avoid routes that systematically fail while having others that are underutilized. Let $M\subseteq\mathds{N}$ be the set specifying the number of vehicles that can be used in a solution. For unlimited fleet problems, this set is given by $M=\{\lceil(\sum_{i\in S}\mu_{i})/Q\rceil,\dots,|N|\}$, and when exactly $\bar{m}$ vehicles must be used, $M=\{\bar{m}\}$.

Let $E(S)$ be the edges with both endpoints in $S$ and $E(h)$ the set of edges linked with node $h$. The VRPSD can be formulated as follows. The variable $x_{ij}$ indicates the number of times edge $(i,j)\in E$ is traversed. The variables associated with pairs of customers are binary, and those linking the depot to a customer can take the values 0, 1, or 2. The variable $x_{0i}$ equals 2 if a vehicle serves a single customer $i\in E$. A binary variable $z_{m}$ decides whether $m$ vehicles are used in the solution. Let $\mathcal{Q}(x)$ denote the expected recourse cost of the first-stage solution $x=(x_{ij})$. The model is:

The objective (1) is to minimize the sum of travel costs plus the expected recourse cost. Constraint (2) imposes that $m$ routes must be connected to the depot if $m$ vehicles are used. Constraints (3) ensure that customers are visited exactly once. Constraints (4) impose that the expected demand on each route does not exceed the vehicle capacity and that the routes are connected to the depot. Constraint (5) ensures that the number of vehicles that are used in the solution is an element of $M$. Constraints (6) and (7) define the domain of the variables.

For the DTD recourse policy, it is possible to separate the calculation of the recourse by route. Let $\mathcal{R}^{\nu}$ be the set of routes in solution $x^{\nu}$. Then, the expected recourse cost is defined as:

where $\mathcal{Q}(r)=\min\{\mathcal{Q}^{1}(r),\mathcal{Q}^{2}(r)\}$ is the minimum expected recourse cost of both orientations of route $r=(0,i_{1},\ldots,i_{t},0)$. The computation of both orientations is required because model (1)-(7) does not capture routes orientation. The expected recourse cost is denoted by $\mathcal{Q}^{1}(r)$ and $\mathcal{Q}^{2}(r)$ in the two orientations. Under the DTD strategy, a cost of $2c_{0i}$ is incurred when the demand of customer $i$ cannot be satisfied. The expected recourse of route $r$, in the first orientation, is thus calculated as follows.

Note that a restocking trip occurs only when a customer’s demand exceeds the vehicle’s residual capacity. We exclude the case of going to the depot and then moving to the next customer when an exact stock-out occurs. If it is assumed that $\xi_{i}\leq Q$ for all $i$ with probability 1, then the second summation of (9) can be limited to $j-1$ instead of going to $\infty$. If demands can exceed the capacity of the vehicles, the probability $\mathds{P}\left(\sum_{k=1}^{j-1}\xi_{k}\leq lQ\leq\sum_{k=1}^{j}\xi_{k}\right)$ tends to zero as $l$ increases and the summation can be stopped when it reaches a probability close to zero. In our implementation, the summation is stopped when the probability is lower than 0.0001. Throughout the paper, the expected recourse cost $\mathcal{Q}(r)$ of a route $r=(0,p,0)$ will equivalently be denoted by $\mathcal{Q}(p)$.

Our algorithm relies on new optimality cuts and lower bounds that require the recourse function to decrease monotonically when removing customers from a route. This section formalizes this property by the so-called monotonicity condition and monotonicity property, which respectively apply to sets of customers and instances of the VRPSD. Based on these definitions, we prove sufficient conditions for the recourse function to be monotonic under the DTD policy when the demands follow independent Poisson, normal, binomial, Erlang, and negative binomial distributions. We also provide counterexamples to illustrate that the recourse function is not monotonic in general.

The above definition can be applied by enumeration to verify whether an instance respects the monotonicity property, but it might be unpractical for large instances since the number of comparisons grows exponentially with $|N|$. In Propositions 1 and 2, we introduce an equivalent formulation of the monotonicity condition and a sufficient condition which will later be used to prove that the monotonicity property is respected if the demands are modeled by specific distributions.

We now prove that, if the customers of a path respect the monotonicity condition, removing customers from this path cannot increase its recourse cost. This is shown in Proposition 3.

Propositions 4 and 5 show that, under some conditions, the monotonicity property is respected for customer demands following independent Poisson, normal, binomial, Erlang, and negative binomial distributions.