New formulations for the robust vehicle routing problem with time windows under demand and travel time uncertainty

Abstract

We present new formulations for the robust vehicle routing problem with time windows (RVRPTW) under cardinality- and knapsack-constrained demand and travel time uncertainty. They are the first compact models to address the RVRPTW under travel time uncertainty while considering the knapsack uncertainty set. Moreover, our models employ different types of constraints to control time propagation based on Miller–Tucker–Zemlin and single commodity flow constraints, which are derived from the linearization of recursive equations. We develop branch-and-cut methods based on the proposed formulations, leveraging a dynamic programming algorithm to verify the robust feasibility of solutions concerning both demand and travel time uncertainty, in addition to specific and standard separation procedures from the literature. We present detailed computational results on RVRPTW benchmark instances to compare the performance of our models and algorithms. Furthermore, we evaluate the impact and advantages of implementing each studied uncertainty set.

1 Introduction

In distribution problems, it is often assumed that all parameters are known and deterministic when solving a vehicle routing problem (VRP). In reality, however, these problems are associated with significant uncertainties, such as on travel times or on each customer’s demand (Boysen et al. 2021; Gendreau et al. 2014). If their probability distributions are known, one can resort to stochastic optimization (De La Vega et al. 2023; Hoogendoorn and Spliet 2023). When these are unknown, or one wants to ensure that a feasible solution is guaranteed for all scenarios, robust optimization (RO) is often more appropriate (Ordonez 2010; Munari et al. 2019; Caunhye and Alem 2023).

Moreover, to avoid overly conservative solutions with excessive costs due to overprotection against uncertainty, different uncertainty sets can model the realization of uncertain parameters whose worst-case behavior can be controlled by the decision maker. The definition of an appropriate uncertainty set is a critical step when using RO, as different sets often result in solutions with different costs and robustness levels (Subramanyam et al. 2020; Bartolini et al. 2021). From a decision maker’s perspective, these different characteristics are attractive since they can choose the one that best suits their strategy. Some examples of uncertainty sets used in the literature are the cardinality-constrained uncertainty set, in which the decision maker limits the number of parameters that simultaneously attain their worst case value, and the knapsack uncertainty set, in which the total deviation of a set of parameters is limited instead (Bertsimas and Sim 2004; Minoux 2009; Gounaris et al. 2013).

In the VRP literature, the use of different uncertainty sets has been little explored in the context of travel time uncertainty, as it appears in the robust VRP with time windows (RVRPTW). While there are studies on different uncertainty sets for the VRP under uncertain demand (Gounaris et al. 2013; Subramanyam et al. 2020; Wang et al. 2021), the vast majority of RVRPTW studies under travel time uncertainty have considered only the cardinality-constrained uncertainty set (Agra et al. 2012; Lee et al. 2012; Munari et al. 2019; De La Vega et al. 2020). Wang et al. (2021) addressed the RVRPTW considering multiple uncertainty sets, but representing travel time deviations using only the discrete and the cardinality-constrained sets.

Bartolini et al. (2021) were the first to consider travel time uncertainty with a knapsack uncertainty set, but for the robust traveling salesman problem with time windows (i.e., considering a single vehicle). Hence, to the best of our knowledge, we are the first to address the RVRPTW under demand and travel time uncertainty using a knapsack uncertainty set. This set provides more flexibility in modeling uncertain parameters compared to the cardinality-constrained uncertainty set by limiting total deviation considering a subset of uncertain parameters, instead of assuming a fixed number of parameters attaining their worst case. In the VRP context, for example, it is often more natural to estimate how late a route usually is, rather than specifying how many roads or streets will experience their worst-case traffic delays. Moreover, as pointed out by Bartolini et al. (2021), a knapsack uncertainty set can be parameterized to yield richer tradeoffs, in addition to providing more precise insights into the resilience to delays.

The main contributions of this paper are as follows:

• We introduce new compact formulations for the RVRPTW under demand and travel time uncertainty, using both cardinality-constrained and knapsack uncertainty sets. Notably, we consider single and multiple knapsack sets, and our formulation for the multiple knapsack uncertainty set does not require subsets to be disjoint, which distinguishes it from previous approaches. We are not aware of any paper that considers the knapsack uncertainty set for uncertain travel times in the RVRPTW;

• We show how to derive robust counterparts based on the well-known Miller–Tucker–Zemlin (MTZ) constraints (Miller et al. 1960) and single commodity flow (CF) constraints for both the cardinality-constrained and knapsack uncertainty sets. This involves the linearization of recursive equations that calculate the worst-case realizations of the uncertain parameters. Previous applications of the linearization technique have focused only on MTZ-based formulations and the cardinality-constrained set;

• We design tailored branch-and-cut (BC) algorithms based on the proposed formulations. These algorithms use a polynomial-time dynamic programming (DP) algorithm to verify the robust feasibility of integer solutions, for both the cardinality-constrained and knapsack uncertainty sets.

We perform detailed computational analyses on RVRPTW instances and show that, although harder to solve, instances considering the knapsack uncertainty set can provide solutions with a similar level of robustness as some configurations of the cardinality-constrained set while costing less, highlighting some advantages of its use. The BC algorithm also showed positive results, solving almost twice as many instances to optimality as a commercial solver applied to the compact models.

The remainder of this paper is organized as follows. In Sect. 2, we introduce some definitions and concepts, while in Sect. 3, we present a compact formulation based on CF constraints for the deterministic VRPTW and derive robust counterparts for demand and travel time uncertainty, considering the cardinality-constrained and knapsack uncertainty sets. In Sect. 4, we propose tailored BC algorithms. In Sect. 5, we present the results of computational experiments with benchmark instances. Finally, the concluding remarks are discussed in Sect. 6.

2 Background and literature review

In this section, we start with some background definitions and in Sect. 2.1 we describe the two uncertainty sets used in this paper. Section 2.2 reviews the existing compact formulations developed for the RVRPTW.

The notation used is as follows. Let $C = \{ 1, \ldots , n\}$ be the set of n customers; $N = C \cup \{ 0, n+1\}$ be the set of nodes including two copies of the depot; and $A = \{ (i,j) \mid i, j \in N, i < n+1, j > 0, i \ne j \}$ be the set of arcs. For each arc $(i,j) \in A$, we define $c_{ij}$ as the travel cost from i to j and assume they satisfy the triangle inequality. The set of homogeneous vehicles is K, each with capacity Q. Each customer $i \in C$ has a demand $d_i \le Q$, and we assume $d_0 = d_{n+1} = 0$.

The incorporation of time windows also requires parameters $[ a_i, b_i]$, which indicate the earliest and latest times a vehicle may start serving customer $i \in C$, respectively; $s_{i}$ is the service time of node $i \in C$; and $t_{ij}$ is the travel time of arc $(i,j) \in A$. For the sake of notation, we set $s_0 = s_{n+1} = 0$ and define time windows $[ a_0, b_0] = [ a_{n+1}, b_{n+1}]$ representing the earliest and latest times a vehicle can depart from and return to the depot. To account for these new characteristics, in compact models one often resorts to the use of constraints inspired by the MTZ formulation.

2.1 Uncertainty sets

In this section, we review the cardinality-constrained and the knapsack uncertainty sets.

2.1.1 Cardinality-constrained set

The cardinality-constrained set works with a budget $\Gamma$ representing the threshold of the total scaled variation of the uncertain parameters (Bertsimas and Sim 2004). Particularly, if $\Gamma$ is integer, we can interpret it as the number of worst-case realizations that can simultaneously occur in a route. A solution is considered robust feasible for a budget $\Gamma$ if it is feasible when up to any $\Gamma$ uncertain parameters assume their worst-case value simultaneously. For the sake of clarity, we differentiate the budget associated with the demand and the one associated with the travel time using parameters $\Gamma ^d$ and $\Gamma ^t$, respectively. For example, under demand uncertainty, this means the solution does not violate the vehicle capacity when the demands of any $\Gamma ^d$ customers assume their largest values. Likewise, if travel time is the uncertain parameter, the solution is robust feasible if all time windows are satisfied for any combination of $\Gamma ^t$ arcs attaining their worst-case travel times.

In the cardinality-constrained set, travel time uncertainty is modeled with random variables $\gamma _{ij}^t$, $0 \le \gamma _{ij}^t \le 1$, which indicate the normalized scale deviation for the travel time of arc (i, j). The sum over these random variables is limited by the travel time budget $\Gamma ^t$. Thus, the uncertainty set designed for travel times, $U^t$, is represented by:

$$\begin{aligned} U^t = \{ t \in \mathbb {R}^{|{A}|} \mid&\ {t_{ij}}=\bar{t}_{ij}+\hat{t}_{ij}\gamma _{ij}^t, \forall (i,j) \in A; \sum _{(i,j) \in A}\gamma _{ij}^t \le \Gamma ^t; \ 0 \le \gamma _{ij}^t \le 1, \forall (i,j) \in A \}, \end{aligned}$$

where the travel time $t_{ij}$ for each arc $(i,j) \in A$ ranges from its nominal value $\bar{t}_{ij}$ up to $\bar{t}_{ij}+\hat{t}_{ij}$, with $\hat{t}_{ij}$ being its maximum deviation. A similar idea applies for demand uncertainty, using a demand budget $\Gamma ^d$ and random variables $\gamma _i^d$, which leads to the uncertainty set:

$$\begin{aligned} {U^d} = \{ d \in \mathbb {R}^{|{N}|} \mid {d_{i}}=\bar{d_{i}}+\hat{d}_{i}\gamma _{i}^d, i \in N; \sum _{i \in N}\gamma _{i}^d \le \Gamma ^d; \ 0 \le \gamma _{i}^d \le 1, i \in N \}. \end{aligned}$$

Note that the worst-case values of the demand and travel time parameters occur when they assume their highest possible value since this impairs the feasibility of the route the most. Although a realization of an uncertain parameter could theoretically be lower than the nominal value, from the perspective of RO optimization, negative deviations can always be disregarded. This is because the worst-case scenario of an uncertainty set will never utilize negative deviations on parameters, as this would consume part of the budget and yield a lower total deviation than if no deviation were considered. This is consistent with other works in RVRP literature (Agra et al. 2012; Munari et al. 2019; Subramanyam et al. 2020). The same assumption also applies to the knapsack uncertainty set, which will be further discussed in the next topic.

2.1.2 Knapsack set

Unlike the cardinality-constrained set, the knapsack uncertainty set does not limit the number of worst-case realizations. Instead, it limits the total absolute deviation on a route, considering one or more knapsacks. Each knapsack l involves a subset of nodes for demands or arcs for travel times, with its own budget of uncertainty $\Delta _l$. Usually, the RVRP literature models these knapsacks by relating the realizations to geographic regions (Gounaris et al. 2013; Subramanyam et al. 2020; Pessoa et al. 2021). For example, one may group the nodes/arcs into four different quadrants (NE, SE, NW, SW) and set a budget for each quadrant based on its characteristics. A quadrant with higher variability in demand may have a larger budget than others. Additionally, one usually builds the multiple knapsacks as disjoint sets, meaning that their nodes/arcs do not overlap.

Let $L^t$ be the set of knapsacks and $S_l^t$ the set of arcs in each knapsack $l \in L^t$, regarding travel time uncertainty. We define $\Delta ^t_l$ as the budget of uncertainty for travel times in knapsack $l \in L^t$. Then, we can model this set for travel time, $U^t_L$, using the following expression:

$$\begin{aligned} U^t_{L} = \{ t \in \mathbb {R}^{|{A}|} \mid {\bar{t}_{{ij}}\le t_{ij}}\le \bar{t}_{{ij}}+\hat{t}_{ij}, \forall (i,j) \in A; \sum _{(i,j) \in S^t_l} (t_{ij}-\bar{t}_{ij}) \le \Delta _l^t, l \in L^t \}. \end{aligned}$$

In this definition, the travel time realization $t_{ij}$ ranges from $\bar{t}_{ij}$ to $\bar{t}_{ij}+\hat{t}_{ij}$, and the sum of all deviations in knapsack l is limited by $\Delta ^t_l$. A similar expression can be generated for problems under demand uncertainty, using a budget $\Delta ^d_l$, and defining $S^d_l$ as the set of nodes in each knapsack $l \in L^d$:

$$\begin{aligned} U^d_{L} = \{ d \in \mathbb {R}^{|{N}|} \mid {\bar{d}_{{i}}\le d_{i}}\le \bar{d}_{{i}}+\hat{d}_{i}, \forall i \in N; \sum _{i \in S_l^d} (d_{i}-\bar{d}_{i}) \le \Delta _l^d, l \in L^d \}. \end{aligned}$$

In practical settings, this type of representation might be more appropriate than the cardinality-constrained set, especially regarding time uncertainty. It is often easier for drivers to estimate how late they are when traveling to a specific region than to tell how many streets or roads usually achieve their worst-case traffic.

A variant of this uncertainty set we study in this work is the single knapsack uncertainty set, in which a single knapsack encompasses every arc/node for each uncertain parameter (i.e., $|L^t|=1$). Thus, budget $\Delta ^t$ limits the total deviation in travel times in a route. This set is most appropriate in systems where there is no clear distinction of behavior among customers, or if the decision-maker wants to introduce a limitation for each vehicle that is independent of the route. As mentioned before, we are not aware of any paper considering the knapsack uncertainty set for uncertain travel times in the RVRPTW.

2.2 Compact formulations for RVRPs

To the best of our knowledge, Sungur et al. (2008) were the first to use RO to incorporate uncertainty into VRPs. Specifically, they proposed compact models based on convex hull, box, and ellipsoidal uncertainty sets for the capacitated VRP (CVRP) under demand uncertainty. These, however, simply replaced the nominal demand of the deterministic formulation with an augmented modified demand, resulting in overly conservative solutions when compared to stochastic programming approaches.

To avoid this overconservatism, some resorted to the cardinality-constrained set introduced by Bertsimas and Sim (2003), using the dualization scheme to derive robust counterparts. This scheme consists of replacing the protection function of each constraint with its corresponding dual problem, ensuring the robust counterpart remains linear. More specifically, each constraint with an uncertain parameter has a protection function that consists of a continuous linear optimization problem that determines the worst-case realization for the uncertain parameters in that constraint. This subproblem is then replaced by its dual problem, which introduces new (continuous) variables and constraints to the robust counterpart. We refer to Bertsimas and Sim (2004) for further details.

Agra et al. (2012) used the dualization scheme based on the so-called layered formulation to derive a robust counterpart for the VRPTW under travel time uncertainty. The authors considered uncertainty on travel times only, inspired by a maritime transportation problem with no capacity constraints. The layered formulation is based on creating a flow problem where a graph is defined for every vehicle, and each one of them has n layers. Each l-th layer represents the node where the vehicle is after visiting $l-1$ nodes on a path from the origin. For each layer, there is a set of possible arcs that the vehicle can traverse, based on the feasibility of the time window constraints and the nodes previously visited on the route. The authors reported computational results for the obtained robust counterpart considering small-scale instances with 10 to 20 cargoes and 1 to 5 vehicles. These instances were all solved to optimality when using an additional strategy that reduces the maximum number of layers. Munari et al. (2019) tested the same formulation on instances from Solomon’s benchmark set with 25 customers to compare it with their own formulation (that is not based on the dualization approach). They observed that the layered formulation could not prove optimality for any instance and found feasible solutions or proved infeasibility for only 59.48% of them within the time limit of 3600 s.

The same problem was later revisited by Agra et al. (2013), who proposed two more efficient robust approaches, albeit not compact, capable of solving instances with up to 50 customers. The first extends the so-called resource inequalities formulation by employing adjustable robust optimization techniques, whereas the second approach implicitly considers uncertainty in a path inequalities formulation. Both strategies presented similar computational performance and were more efficient than the layered formulation of Agra et al. (2012).

Gounaris et al. (2013) used the dualization scheme to obtain robust counterparts of several traditional formulations of the CVRP. The proposed modeling approach was able to introduce any convex uncertainty set into the problem. Additionally, they also introduced a robust extension for the traditional rounded capacity inequalities (RCI) widely used in the CVRP literature. To assess their method, the authors ran experiments with a commercial solver, in which the robust RCI were introduced globally through user-defined callbacks, considering the knapsack and the factor models uncertainty sets. The most efficient formulations were able to solve most benchmark instances with fewer than 50 customers, but struggled on larger instances.

Recently, Munari et al. (2019) proposed an alternative for the dualization scheme when using cardinality-constrained sets in the context of RVRP variants. This approach is based on the linearization of recursive equations that model the worst-case realizations of the uncertain parameters. This linearization results in constraints that guarantee a robust feasible solution in a compact model. Their work considers the cardinality-constrained uncertainty set only and assumes that the budget of uncertainty is integer and thus defined as the maximum number of worst-case values taken simultaneously by the uncertain parameters. For instance, consider the budget $\Gamma ^t$ for travel time uncertainty and a given route $r = (v_0, v_1, \ldots , v_h)$. Let $w_{v_j \gamma }$ be a variable representing the worst case for service start time at node $v_j$, when the travel times at any $\gamma \le \Gamma ^t$ arcs up to this node attain their worst-case values simultaneously. The worst case for service start time at node $v_j$ is the latest between its opening time window ($a_{v_j}$) and the worst-case arrival time. Recall that $\bar{t}_{v_{j-1}v_j}$ is the nominal travel time on arc $(v_{j-1},v_j)$; $\hat{t}_{v_{j-1}v_j}$ represents the corresponding maximum deviation; and $s_{v_j}$ is the service time at node $v_j$. Then, the value of $w_{v_j \gamma }$ can be computed using the following recursive equation (Agra et al. 2013; Munari et al. 2019):

$$\begin{aligned}&\displaystyle w_{v_j\gamma }= \left\{ \begin{array}{ll} a_{v_0}, &{} \text{ if } j=0, \\ \max \{a_{v_j},w_{v_{j-1}\gamma }+\bar{t}_{v_{j-1}v_j}+s_{v_{j-1}} \}, &{} \text{ if } \gamma =0,\\ {max\{}a_{v_j},w_{v_{j-1}\gamma }+\bar{t}_{v_{j-1}v_j}+s_{v_{j-1}}, \\ \hspace{1.5cm} w_{v_{j-1}(\gamma -1)}+\bar{t}_{v_{j-1}v_j}+\hat{t}_{v_{j-1}v_j}+s_{v_{j-1}}\}, &{} \text{ otherwise }, \end{array} \right. \end{aligned}$$

(1)

for all $j = 0,\ldots , h$ and $\gamma =0,\ldots ,\Gamma ^t$. We can convert these equations into the following linear constraints for a two-index compact formulation, which guarantee a robust feasible solution with respect to time propagation and time window satisfaction:

$$\begin{aligned}&w_{j\gamma }\ge w_{i\gamma }+(s_i+\bar{t}_{ij})x_{ij}-M_{ij}(1-x_{ij}), (i,j) \in A, \gamma =0,\ldots ,\Gamma ^t, \end{aligned}$$

(2)

$$\begin{aligned}&w_{j\gamma }\ge w_{i(\gamma -1)}+(s_i+\bar{t}_{ij}+\hat{t}_{ij})x_{ij}-M_{ij}(1-x_{ij}), (i,j) \in A, \gamma =1,\ldots ,\Gamma ^t, \end{aligned}$$

(3)

$$\begin{aligned}&a_i \le w_{i\gamma } \le b_i, i \in N, \gamma =0,\ldots ,\Gamma ^t, \end{aligned}$$

(4)

where $x_{ij}$ is the commonly used binary variable that assumes the value of 1 if, and only if, a vehicle traverses arc $(i,j) \in A$, and $M_{ij}$ is a sufficiently large number that can be set as $\max \{ 0, b_i - a_j \}$, for each $(i,j) \in A$. For each $\gamma = 0, \ldots , \Gamma ^t$, constraints (2) and (3) guarantee that, if $x_{ij} =1$ for a given $(i,j) \in A$, the service starting time at node $v_j$ when $\gamma$ travel times attain their worst-case values is computed by choosing the largest between two possibilities: $\gamma$ worst-case realizations already happened in arcs that precede arc (i, j), as represented by constraints (2); or $\gamma -1$ worst-case realizations happened before (i, j) and, thus, the travel time on arc (i, j) attains its worst-case value, as represented by constraints (3). Constraints (4) impose the satisfaction of the time windows. We can apply the same strategy to derive similar constraints for demand uncertainty. Because this robust counterpart yields fewer constraints and variables than those derived using the dualization approach (Munari et al. 2019), it performs significantly better on general-purpose linear optimization solvers. Yu et al. (2022) also report superior results when using this approach to model a robust variant of the team orienteering problem. For this reason, besides the difficulties of extending dualization methods to problems with travel time variability, the models introduced in this work are based on the linearization approach.

3 New compact formulations for the RVRPTW

We develop novel RO models for the RVRPTW that use the linearization technique of recursive equations. First, we present in Sect. 3.1 a CF formulation for the deterministic VRPTW. Then, we derive its robust counterpart using the cardinality-constrained uncertainty set to obtain a new compact RO model for the RVRPTW in Sect. 3.2. Recall that an MTZ-based formulation already exists for this problem (Munari et al. 2019), but no CF-based formulation has been proposed thus far. Then, in Sect. 3.3, we propose the first CF- and an MTZ-based models for the single and multiple knapsack uncertainty sets.

3.1 CF formulation for the VRPTW

While there are formulations based on CF constraints for several VRP variants in literature (Gouveia 1995; Letchford and Salazar-González 2006, 2015), we did not find any compact formulation explicitly defined for the VRPTW in which both load and time propagation are modeled using this type of constraints. There is, however, one for the TSP with time windows (Langevin et al. 1993) and another for the split delivery VRPTW (Bianchessi and Irnich 2019; Munari and Savelsbergh 2022), both in a deterministic context, but none of them models the two types of propagation using CF constraints. In what follows, we present our developments to introduce time windows and time flow constraints.

Let $x_{ij}$ be the binary variable that assumes the value of 1 if, and only if, a vehicle traverses arc $(i,j) \in A$, which is commonly used to define two-index vehicle flow formulations. We define a continuous variable $f_{ij}$ to represent the load of the vehicle that traverses arc $(i,j) \in A$, inspired by the variables introduced by Gavish (1984). To adapt this model to the VRPTW, we treat time as a second commodity. Thus, we introduce continuous variables $g_{ij}$ that represent the elapsed time of a route when the vehicle enters arc (i, j) after serving node i. The model is then given by:

$$\begin{aligned} \text{ min }&\displaystyle \sum _{(i,j) \in A} c_{ij} x_{ij}, \end{aligned}$$

(5)

$$\begin{aligned} \text{ s.t. }&\displaystyle \sum _{i:(i,j) \in A} x_{ij} = 1, \ j \in C, \end{aligned}$$

(6)

$$\begin{aligned}&\displaystyle \sum _{h:(h,i) \in A} x_{hi} = \sum _{j:(i,j) \in A} x_{ij}, \ i \in C, \end{aligned}$$

(7)

$$\begin{aligned}&\displaystyle \sum _{j:(i,j) \in A} f_{ij} = d_i + \sum _{h:(h,i) \in A} f_{hi}, \ i \in C, \end{aligned}$$

(8)

$$\begin{aligned}&\displaystyle d_ix_{ij} \le f_{ij} \le (Q-d_j) x_{ij}, \ (i,j) \in A, \end{aligned}$$

(9)

$$\begin{aligned}&\displaystyle \sum _{j:(i,j) \in A} g_{ij} \ge s_i + \sum _{h:(h,i) \in A} \left( g_{hi} + t_{hi} x_{hi}\right) , \ i \in C, \end{aligned}$$

(10)

$$\begin{aligned}&\displaystyle (a_i + s_i)x_{ij} \le g_{ij} \le (b_i+s_i) x_{ij}, \ (i,j) \in A, \end{aligned}$$

(11)

$$\begin{aligned}&x_{ij} \in \{0, 1\}, \ (i,j)\in A. \end{aligned}$$

(12)

The objective function (5) consists of minimizing the total traveling costs. Constraints (6) ensure that each customer is visited only once, whereas (7) guarantee the correct vehicle flow through the nodes. Constraints (8) ensure the load flow propagation, enforcing that the load on the vehicle that leaves node i increases by its demand $d_i$. These constraints also forbid subtours. Constraints (9) prevent the vehicle from exceeding its capacity. Constraints (10) act similarly to (8) and guarantee the time flow propagation through the visited nodes of a route. Constraints (11) ensure that time windows are met. They also guarantee that the variable $g_{ij}$ is non-negative if arc (i, j) is traversed. Finally, constraints (12) define the binary domain of variables $x_{ij}$.

3.2 CF formulation for the cardinality-constrained RVRPTW

We obtain the robust counterpart of model (5)–(12) following the idea of the linearization technique (Munari et al. 2019). Similarly to the steps performed in the MTZ-based formulation, we add an index $\gamma$ to the variables that control the load and time propagation. Hence, let variable $f_{ij\gamma }$ represent the load carried on arc $(i, j) \in A$ considering that $\gamma$ customers attained their worst-case demand; and $g_{ij\gamma }$ represent the earliest elapsed time of the route that traverses arc $(i, j) \in A$, after serving node i, considering that $\gamma$ arcs attained their worst-case travel time simultaneously. With these variables, we can redefine the load and time flow propagation constraints of the model. First, constraints (8) and (9) are replaced with:

$$\begin{aligned}&\displaystyle \sum _{j:(i,j) \in A} f_{ij\gamma } \ge \bar{d_i} + \sum _{h:(h,i) \in A} f_{hi\gamma }, \ i \in C, \gamma =0,\ldots ,\Gamma ^d, \end{aligned}$$

(13)

$$\begin{aligned}&\displaystyle \sum _{j:(i,j) \in A} f_{ij\gamma }\ge \bar{d_i} + \hat{d_i} + \sum _{h:(h,i) \in A} f_{hi(\gamma -1)}, \ i \in C, \gamma =1,\ldots ,\Gamma ^d, \end{aligned}$$

(14)

$$\begin{aligned}&\displaystyle \bar{d}_ix_{ij} \le f_{ij\gamma } \le (Q-\bar{d}_j) x_{ij}, \ (i,j) \in A, \gamma =0,\ldots ,\Gamma ^d. \end{aligned}$$

(15)

Constraints (13) and (14) guarantee the propagation of the worst-case vehicle load, according to the following two cases: the demand of $\gamma$ nodes attained their worst-case previously, and then only the nominal demand of node i happens, as computed in the right-hand side of (13); or $\gamma -1$ worst-case realizations occurred previously and then the demand of node i also attains its maximum deviation (hence, one more worst-case value considered), as calculated in the right-hand side of (14). Constraints (15) ensure that the vehicles’ capacity is satisfied for all possible number of worst-case realizations. Note that, in the deterministic case ($\Gamma ^d = 0$), constraints (14) are not defined and constraints (13) and (15) are the same as (8) and (9).

Likewise, we can apply the same process to the constraints associated with time flow and, then, we obtain the following RO model for the RVRPTW with uncertainty on demands and travel times. The model consists of the objective function (5) subject to (6), (7), (12)–(15), and to:

$$\begin{aligned}&\displaystyle \sum _{j:(i,j) \in A} g_{ij\gamma }\ge s_i+\sum _{h:(h,i) \in A}(g_{hi\gamma }+\bar{t}_{hi}x_{hi}), \ i \in C, \gamma =0,\ldots ,\Gamma ^t, \end{aligned}$$

(16)

$$\begin{aligned}&\displaystyle \sum _{j:(i,j) \in A} g_{ij\gamma }\ge s_i+\sum _{h:(h,i) \in A} (g_{hi(\gamma -1)}+(\bar{t}_{hi}+\hat{t}_{hi})x_{hi}), \ i \in C, \gamma =1,\ldots ,\Gamma ^t, \end{aligned}$$

(17)

$$\begin{aligned}&\displaystyle (s_i+a_i)x_{ij} \le g_{ij\gamma } \le (b_i+s_i) x_{ij}, \ (i,j) \in A, \gamma =0,\ldots ,\Gamma ^t. \end{aligned}$$

(18)

Constraints (16) and (17) act similarly to (13) and (14) but for time load propagation. Constraints (18) ensure that the time windows are respected.

Thanks to the capacity and time windows constraints (15) and (18), only one variable related to load ($f_{ij\gamma }$) and time ($g_{ij\gamma }$) propagation are allowed to have a non-null value for each i and $\gamma$, specifically the one related to arc (i, j) where $x_{ij}=1$. Thus, suppose that in an optimal solution, we have $x_{i_1j_1}=1$ and $x_{j_1k_1}=1$. Then, time constraints (16) and (17) related to node $j_1$, for any $\gamma =1,\ldots ,\Gamma ^t$, can be simply represented as follows:

$$\begin{aligned}&\displaystyle g_{j_1k_1\gamma }\ge g_{i_1j_1\gamma }+ \bar{t}_{i_1j_1}+s_{j_1}, \end{aligned}$$

(19)

$$\begin{aligned}&\displaystyle g_{j_1k_1\gamma }\ge g_{i_1j_1(\gamma -1)}+ \bar{t}_{i_1j_1}+\hat{t}_{i_1j_1}+s_{j_1}. \end{aligned}$$

(20)

Conversely, in the MTZ-based model for the RVRPTW (Munari et al. 2019), the time constraints related to node $j_1$ in path $(i_1,j_1,k_1)$ can be written as follows:

$$\begin{aligned}&w_{j_1\gamma }\ge w_{i_1\gamma }+ \bar{t}_{i_1j_1}+s_{j_1}, \end{aligned}$$

(21)

$$\begin{aligned}&\displaystyle w_{j_1\gamma }\ge w_{i_1(\gamma -1)}+ \bar{t}_{i_1j_1}+\hat{t}_{i_1j_1}+s_{j_1}, \end{aligned}$$

(22)

where $w_{j_1\gamma }$ is a continuous variable that represents the departure time from node $j_1$ considering that up to $\gamma$ nodes attained their worst-case value. Given that variables $g_{j_1k_1\gamma }$ and $w_{j_1}$ have the same meaning, it is possible to see that constraints (19)–(20) are equivalent to (21)–(22). A similar conclusion can be drawn for the load constraints. Hence, both models have equivalent load and time propagation constraints in an integer solution. However, our CF-based formulation avoids the weak big-M constraints presented in the MTZ-based models. Indeed, as the computational results presented in Sect. 5 indicate, our new formulation yields a much tighter linear programming (LP) relaxation. Finally, it is worth mentioning that model (5)–(7), (12)–(15) is a valid RO formulation for the RCVRP under the cardinality-constrained uncertainty set.

3.3 Formulations for the knapsack-constrained RVRPTW

We can also derive MTZ- and CF-based formulations for the RVRPTW under single and multiple knapsack uncertainty sets using the linearization approach. Recall that $\Delta ^d$ and $\Delta ^t$ are the budgets of uncertainty in demand and travel times, respectively, used in the definition of the single knapsack uncertainty sets in Sect. 2.1.2. Similarly, we have $\Delta ^d_l$ and $\Delta ^t_l$ for the multiple knapsack uncertainty sets.

3.3.1 MTZ-based formulation for the single knapsack uncertainty set

To generate the MTZ-based formulation for the RVRPTW under the single knapsack uncertainty set, we define the following decision variables:

• $u_{i\delta }$: represents the load on the vehicle up to and including node $i \in N$, considering up to a total deviation of $\delta \in \{0, 1, \ldots , \Delta ^d \}$ units over the demands’ nominal values for all nodes previously visited;

• $w_{i\delta }$: indicates the earliest time that a vehicle can start the service at node $i \in N$, considering up to a total deviation $\delta \in \{0, 1, \ldots , \Delta ^t \}$ time units over the travel times’ nominal values for all arcs previously traversed.

In these definitions, the index $\delta$ represents the total load/time over their nominal values accumulated in the route up to the current node. This interpretation requires integer budget and deviations, since an index is used to represent the deviations. Moreover, for large budgets, the number of variables and constraints becomes large as they grow pseudopolynomially. Later in this section we discuss some strategies to address these issues.

To derive constraints based on variables $u_{i\delta }$ and $w_{i\delta }$, we rely on the following interpretation based on DP, inspired by the discussion presented in Sect. 2.2 for the cardinality-constrained uncertainty set. Let $r = (v_0, v_1, \ldots , v_h)$ be a route visiting $h-1$ customers. For this route, we can compute the values of $w_{v_j \delta }$ for $j = 0, \ldots , h$ and $\delta = 0, 1, \ldots , \Delta ^t$ as follows:

$$\begin{aligned}&\displaystyle w_{v_j\delta }=\left\{ \begin{array}{ll} a_{v_0}, &{} \text{ if } j=0, \\ \displaystyle \max _{\lambda = 0, \ldots , \min \{\delta , \hat{t}_{v_{j-1}v_{j}}\}} \{a_{v_j}, w_{v_{j-1}(\delta -\lambda )}+\bar{t}_{v_{j-1}v_{j}}+s_{v_{j-1}}+\lambda \}, &{} \text{ otherwise. } \\ \end{array} \right. \end{aligned}$$

(23)

The first case in (23) is a boundary condition for the first node in the route, the depot, and defines the starting time of the route. The second computes the worst-case starting time of the service at node $v_j$, considering that the travel time deviation in arc $(v_{j-1},v_{j})$, represented by $\lambda$, may attain any value from 0 to the minimum between the total budget $\delta$ and the maximum deviation $\hat{t}_{v_{j-1}v_{j}}$. Notice that this expression encompasses the deterministic cases for $\delta =0$ and $\lambda =0$. Additionally, this calculation accounts for the opening of the time window. To check the feasibility of the route with respect to time windows, we need to verify after each iteration of the DP algorithm if $w_{v_j\delta } \le b_{v_j}$ for each node $v_j$ and $\delta = 0, 1, \ldots , \Delta ^t$. In the compact model, these verifications are introduced as the upper bound of the time windows constraints.

It is possible to derive a similar expression for computing the values of variables $u_{v_j\delta }$. However, since the vehicle load is not subject to a behavior analogous to the opening of the time windows, the worst-case load at a given node can be computed by filling the knapsack with as much demand deviations as possible in the order they appear in the route. Hence, we use the following improved equation:

$$\begin{aligned}&\displaystyle u_{v_j\delta }=\left\{ \begin{array}{ll} \bar{d}_{v^{ }_{0}}, &{} \text{ if } j=0, \\ u_{v_{j-1}\delta }+\bar{d}_{v_j}, &{} \text{ if } \delta<\hat{d}_{v_j},\\ \text{ max }\{u_{v_{j-1}\delta }+\bar{d}_{v_j}, u_{v_{j-1}(\delta -\hat{d}_{v_j})}+\bar{d}_{v_j}+\hat{d}_{v_j}\}, &{} \text{ if } \hat{d}_{v_j}\le \delta < \Delta ^d, \\ \displaystyle \max _{\lambda = 0, \ldots , \min \{\hat{d}_{v_j}, \Delta ^d\}}\{ u_{v_{j-1}(\Delta ^d-\lambda )}+\bar{d}_{v_j}+\lambda \}, &{} \text{ otherwise }, \\ \end{array} \right. \end{aligned}$$

(24)

for $j = 0, \ldots , h$ and $\delta = 0, 1, \ldots , \Delta ^d$. The first two cases define boundary conditions: one sets the total load in the first node in the route, which is usually the depot; whereas the other applies when the total deviation considered in the route is lower than $\hat{d}_{v_j}$, thus resulting in adding only the nominal demand of node $v_j$ to the total load. We do not introduce any deviations in the variables with small $\delta$ because the algorithm focuses on finding $u_{v_j\Delta ^d}$, which is properly calculated by the remaining cases. The third case corresponds to whether or not we consider the full deviation of the demand on node $v_j$, with the largest between both values being chosen. Finally, the last case corresponds to $\delta = \Delta ^d$, and involves using the remaining budget of the knapsack. It considers all the possible deviations from 0 to $\hat{d}_{v_j}$, denoted as $\lambda$, as long as this value does not exceed the budget $\Delta ^d$. The value $\lambda$ represents the deviation added to the knapsack to fill it up.

With this interpretation of the variables and relying on the linearization approach to convert the recursive equations (23) and (24) to linear constraints, we developed the following model for the RVRPTW under the single knapsack uncertainty set:

$$\begin{aligned}&\text{ min } \displaystyle \sum _{(i,j) \in A} c_{ij} x_{ij}, \end{aligned}$$

(25)

$$\begin{aligned}&\text{ s.t. } \text{(6), } \text{(7), } \text{(12), } \text{ and } \text{ to } \nonumber \\&\displaystyle u_{j \delta } \ge u_{i\delta }+\bar{d}_j+Q(x_{ij}-1), \ (i,j) \in A, \delta = 0, \ldots , \Delta ^d, \end{aligned}$$

(26)

$$\begin{aligned}&\displaystyle u_{j \delta } \ge u_{i(\delta -\hat{d}_j)}+\bar{d}_j +\hat{d}_j+Q(x_{ij}-1), \ (i,j) \in A, \delta = \hat{d}_j, \ldots , \Delta ^d, \end{aligned}$$

(27)

$$\begin{aligned}&\displaystyle u_{j \Delta ^d} \ge u_{i(\Delta ^d-\lambda )}+\bar{d}_j +\lambda +Q(x_{ij}-1), \ (i,j) \in A, \lambda = 0, \ldots , \min \{ \hat{d}_j, \Delta ^d \}, \end{aligned}$$

(28)

$$\begin{aligned}&\displaystyle 0 \le u_{j\delta } \le Q, \ j\in N, \delta = 0, \ldots , \Delta ^d, \end{aligned}$$

(29)

$$\begin{aligned}\displaystyle w_{j \delta } &\ge w_{i(\delta -\lambda )}+\bar{t}_{ij} +\lambda +s_i+M_{ij}(x_{ij}-1), \\ & (i,j) \in A, \delta = 0, \ldots , \Delta ^t, \lambda = 0, \ldots , \min \{\delta , \hat{t}_{ij}\}, \end{aligned}$$

(30)

$$\begin{aligned}&\displaystyle a_j\le w_{j \delta }\le b_j, \ j \in N, \delta = 0, \ldots , \Delta ^t. \end{aligned}$$

(31)

The objective function (25) is the same as in the other formulations presented in this work. Constraints (26)–(28) determine the worst-case load at node j considering a non-negative integer budget $\delta \le \Delta ^d$, and they are the linear counterpart of the recursive equations (24). Constraints (29) ensure that the vehicle capacity is respected. Notably, we just need to verify the upper bound for $\delta = \Delta ^d$. If we consider only these constraints and the ones related to the variable’s domain, we formulate the RCVRP. Constraints (30) compute the worst-case service starting time using the same strategy as in the recursive equations (23). They compute the arrival time in node j considering the route’s total deviation of $\delta$. The right-hand side evaluates the quantity $\lambda$ of time deviation that should be considered for that particular node, while the remaining $\delta -\lambda$ units of deviation happened in previous nodes of the route, thus $w_{j\delta }$ is determined by the choice of $\lambda$ that results in the worst-case arrival time. Finally, constraints (31) ensure the time windows are respected.

3.3.2 CF formulation for the single knapsack uncertainty set

To derive a robust counterpart of the deterministic CF model (5)–(11) considering knapsack-uncertainty on demand and travel time, we define the following load and time variables:

• $f_{ij\delta }$: the load carried on arc $(i, j) \in A$ with a total deviation of $\delta \in \{0, 1, \ldots , \Delta ^d \}$ units over the nominal demand;

• $g_{ij\delta }$: earliest elapsed time of a route when the vehicle begins to traverse arc $(i,j) \in A$ after serving node i with a total deviation of $\delta \in \{0, 1, \ldots , \Delta ^t \}$ units over nominal travel times.

Using a similar interpretation as that presented in the previous section, we can derive CF-based constraints from the recursive equations (23) and (24), resulting in the following new CF formulation for the RVRPTW.

$$\begin{aligned}&\text{ min } \displaystyle \sum _{(i,j) \in A} c_{ij} x_{ij}, \end{aligned}$$

(32)

$$\begin{aligned}&\text{ s.t. } \text{(6), } \text{(7), } \text{(12), } \text{ and } \text{ to } \nonumber \\&\displaystyle \sum _{j:(i,j) \in A}f_{ij\delta } \ge \bar{d}_i + \sum _{h:(h,i) \in A}f_{hi\delta }, \ i \in N, \delta =0,\ldots ,\Delta ^d, \end{aligned}$$

(33)

$$\begin{aligned}&\displaystyle \sum _{j:(i,j) \in A}f_{ij\delta } \ge \bar{d}_i+\hat{d}_i + \sum _{h:(h,i) \in A}f_{hi(\delta -\hat{d}_i)}, \ i \in N, \delta =\hat{d}_i,\ldots ,\Delta ^d, \end{aligned}$$

(34)

$$\begin{aligned}&\displaystyle \sum _{j:(i,j) \in A}f_{ij\Delta ^d} \ge \bar{d}_i+\lambda + \sum _{h:(h,i) \in A}f_{hi(\Delta ^d-\lambda )}, \ i \in N, \lambda =0,\ldots ,\min \{\Delta ^d, \hat{d}_{i}\}, \end{aligned}$$

(35)

$$\begin{aligned}&\displaystyle \bar{d}_i x_{ij} \le f_{ij\delta } \le (Q - {\bar{d}_j }) x_{ij}, \ (i,j) \in A, \delta =0,\ldots ,\Delta ^d, \end{aligned}$$

(36)

$$\begin{aligned}&\displaystyle \sum _{j:(i,j) \in A}g_{ij\delta } \ge s_i + \sum _{\begin{array}{c} h:(h,i) \in A\\ \lambda \le \hat{t}_{hi} \end{array}} (g_{hi(\delta -\lambda )}+(\bar{t}_{hi} +\lambda )x_{hi}), \ i \in N, \delta =0,\ldots , \Delta ^t, \lambda =0,\ldots ,\delta , \end{aligned}$$

(37)

$$\begin{aligned}&\displaystyle (a_i+s_i)x_{ij}\le g_{ij\delta }\le (b_i+s_i)x_{ij}, \ (i,j) \in A, \delta =0,\ldots , \Delta ^t. \end{aligned}$$

(38)

The objective function (32) is the same as in the previous formulations. Constraints (33)–(35) are based on the recursive equations (24) and work similarly to (26)–(28), forbidding subtours and computing the worst-case load values using the CF variables. Capacity constraints are imposed via (36). Constraints (37) compute the elapsed time based on the idea of equations (23), and constraints (38) enforce the time windows.

We mention a few difficulties that the models based on single knapsack uncertainty sets might face and some possible solutions. The first issue regards the large number of variables when the budgets are large. However, budget values in real contexts are typically not large. For instance, Bartolini et al. (2021) consider $\Delta ^d = 100$ minutes of deviation as an extreme case. This would be considered a volatile environment since the delay would take roughly 20% of a worker’s day. Hence, smaller values of $\Delta ^d$ are usually reasonable in practice. Another possible workaround is to change the order of magnitude of $\delta$; for instance, instead of using the unit of $\delta$ as 1 min, one can use it in units of 5 min. This strategy may reduce the model to a tractable size. Another limitation of the proposed formulations is the impossibility of using non-integer units for $\delta$. The mentioned workaround may be used in this case as well, by multiplying the non-integer unit by a constant that turns it into an integer number, possibly at the cost of worsening the computational performance. Nonetheless, we believe the proposed approaches are still of theoretical and practical value, and may benefit researchers and practitioners interested in formulations for RVRP variants.

3.3.3 Formulations for the multiple knapsack uncertainty set

In the multiple knapsack uncertainty set, we consider a set L of knapsacks and subsets of nodes (or arcs) associated with each knapsack ($S_l$, $l \in L$) with its own budget $\Delta _l$. To extend the previous formulations to a multiple knapsack framework, we redefine the continuous variables related to demand ($u_{i\delta }$ and $f_{ij\delta }$) and time ($w_{i\delta }$ and $g_{ij\delta }$) to consider an index $\delta _l$ representing the total deviation in the route for each knapsack l. An interesting aspect of our formulation is that, unlike previous studies (Gounaris et al. 2013; Subramanyam et al. 2020), it does not require the knapsacks to be disjointed (i.e., non-overlapping). Thus, without sacrificing formulation correctness, we can model problems where nodes/arcs belong to several knapsacks simultaneously. For the sake of conciseness, we present these formulations in the appendix.

4 Branch-and-cut algorithm for the RVRPTW

In addition to the compact formulations, we designed a tailored BC algorithm to obtain better computational performance for the studied models. The cut separation is performed using a combination of strategies: a DP-based algorithm, a heuristic algorithm proposed for the RCVRP (Gounaris et al. 2013), and the CVRPSep package (Lysgaard et al. 2004). We use the latter to generate rounded capacity inequalities (RCI) only, which are stated as follows for a given set of nodes $V_S$:

$$\begin{aligned}&\displaystyle \sum _{i \in N \backslash V_S}\sum _{j \in V_S} x_{ij}\ge \Bigg \lceil \frac{\sum _{j\in V_S} {\bar{d}_j} }{Q} \Bigg \rceil ,&V_S \subset C. \end{aligned}$$

(39)

These cuts ensure that the number of vehicles entering set $V_S$ offer enough capacity to serve all the nodes in $V_S$. Since enumerating every possible set $V_S$ requires a long computational time, CVRPSep uses an efficient heuristic algorithm to generate a limited number of sets and relevant cuts.

Other than that, for instances with uncertainty on demand we also use the Robust RCI (RRCI) introduced by Gounaris et al. (2013). These cuts are a robust extension of the capacity cut previously explained, represented by the following inequalities:

$$\begin{aligned}&\displaystyle \sum _{i \in N \backslash V_S}\sum _{j \in V_S} x_{ij}\ge \Bigg \lceil {\frac{1}{Q}\max _{ d \in U^d }\sum _{j\in V_S} d_j}\Bigg \rceil ,&V_S \subset C. \end{aligned}$$

(40)

Note that these are almost identical to the deterministic version (39), the main difference being that, in the robust case, we consider the maximum possible demand inside the uncertainty set instead of the nominal demand. Since enumerating every possible RRCI would be impractical, we implemented a heuristic algorithm to dynamically separate and insert these cuts as needed, as proposed by Gounaris et al. (2013). We start with a solution and a randomly generated set of customers $V_S$; then, we iteratively perturb this set by inserting or removing a node from it. In each attempt of adding/removing a node to/from $V_S$, we analyze every potential customer and remove or insert the one with the highest impact in the difference between the right-hand side and the left-hand side of the corresponding RRCI constraint. We also maintain a tabu list of recently added/removed customers that are not allowed to be moved in or out of the set for some iterations, to avoid cycles. We stop the algorithm when we do not improve the difference between the right- and the left-hand sides of the inequality for a given number of iterations.

An important factor in this algorithm is the need to efficiently compute the right-hand side of the inequality since this value must be frequently checked. To assist in this calculation, we create an auxiliary data structure that reduces the number of steps required. For the cardinality-constrained uncertainty set, we define an auxiliary vector $\mathcal {Q} \in \mathbb {R}^{|V_S|}, \mathcal {Q} = (\hat{d}_{[1]}, \ldots , \hat{d}_{[|V_S|]})$, containing the demand deviations of all nodes in $V_S$ in non-increasing order, i.e., $\hat{d}_{[j-1]} \ge \hat{d}_{[j]}$, where $\hat{d}_{[j]}$ is the demand deviation in the jth position of this vector. We then compute $D_{V_{S}}$, the maximum demand of this set, using

$$\begin{aligned} D_{V_{S}}= \sum _{j \in V_S} \bar{d}_j + \sum _{\gamma =0}^{\min \{\Gamma ^d,|V_S|\}}\mathcal {Q}_{\gamma }. \end{aligned}$$

(41)

Then, for each iteration when we check the possibility of insertion/removal of a given node $j \in V_S$, we take the total demand of the current set $V_S$ $(D_{V_{S}})$ and compute the new right-hand side for that particular node ($RS_j$) using the following expression:

$$\begin{aligned}&\displaystyle RS_j=\left\{ \begin{array}{ll} D_{V_{S}} + \bar{d}_j+ \text{ max }{(\hat{d}_j-\mathcal {Q}_{\Gamma ^d},0)},&{} \text{ if } j \not \in V_S; \\ D_{V_{S}} - \bar{d}_j - \text{ max }{(\hat{d}_j-\mathcal {Q}_{\Gamma ^d+1},0)},&{} \text{ otherwise }, \end{array} \right. \end{aligned}$$

(42)

After determining which node j will be inserted/removed from set $V_S$, we update $D_{V_{S}}$, which takes the value of $RS_j$, and insert/remove its deviation from $\mathcal {Q}$. Note that we did not need to compute $D_{V_{S}}$ again with the equation (41), we only need to use it in the first iteration, reducing the number of operations in the procedure.

For the single and multiple knapsack uncertainty sets, we used the formulas proposed by Gounaris et al. (2013) to calculate the maximum demand deviation, which is done in $\mathcal {O}(|V_S|)$. Let L be the set of knapsacks and $S_l$ the subset of nodes inside each knapsack $l \in L$. The right-hand side of the RRCI is then given by:

$$\begin{aligned}&\displaystyle \sum _{i \in V_S}\bar{d}_i+\sum _{l \in L}\min \{ \Delta ^d_l,\sum _{i \in V_S \cap S^l} \hat{d}_i \}. \end{aligned}$$

(43)

Since we use a heuristic algorithm to generate subset $V_S$, this separation procedure might miss a violated constraint. Thus, for integer solutions we also use a DP algorithm based on the recursive equations (23), which can be executed in $\mathcal {O}(|N|\prod _{l \in L}\Delta _l^d)$. Whenever the heuristic is unable to find a new violated cut, this algorithm checks if the solution is feasible and inserts additional feasibility cuts if needed. If for a given route $r= (v_0,v_1,\ldots ,v_h)$ the infeasibility is detected in node $v_j$ for a given $j \in \{1, \ldots , h \}$ the following inequality is inserted into the problem:

$$\begin{aligned}&\displaystyle \sum _{0 < i\le j} x_{v_{i-1}v_{i}} \le j-1. \end{aligned}$$

(44)

We use a different approach for time uncertainty. For the cardinality-constrained and single knapsack uncertainty sets we initialize the model with only the deterministic time flow propagation constraints and dynamically insert the robust constraints (16) and (17) whenever they are violated. For the two-knapsack uncertainty set, preliminary results showed that the introduction of the robust constraints slowed down the model significantly, as a considerable number of constraints are usually introduced into the model on each cut, and thus we decided to use feasibility cuts (44) instead. This proved to be more effective for this particular uncertainty set. To efficiently check the feasibility of a solution, we use DP algorithms based on equations (1) and (23) to compute the worst-case elapsed times and then identify whether time windows are violated in the route. These algorithms have complexity $\mathcal {O}(|N|\Gamma ^t)$ for the cardinality-constrained uncertainty set and $\mathcal {O}(|N|\prod _{l \in L}\Delta _l^t)$ for the knapsack set.

5 Computational experiments

In this section, we present the results of extensive computational experiments performed to assess the proposed compact models and BC algorithms for the cardinality-constrained and knapsack uncertainty sets, using benchmark instances from the literature. We consider two versions of the knapsack uncertainty set, one with a single knapsack and the other with two knapsacks. We compare the computational performance of these approaches against the MTZ-based formulation of Munari et al. (2019) for the cardinality-constrained set, which is the state-of-the-art compact model for the RVRPTW. Additionally, we analyze the impact of robustness regarding the different uncertainty sets.

All models and algorithms were coded in C++ using the Concert library of IBM CPLEX Optimization Studio version 20.1 with default parameters. The computational experiments were conducted on a computer cluster with 2 x AMD Rome 7532 @ 2.40 GHz processor and 64GB of RAM. We set a time limit of 3600 s for each run.

We use the same benchmark instances of the RVRPTW with 25 customers introduced by Munari et al. (2019), who adapted the VRPTW instances of Solomon (1987) to include uncertainty in demands and travel times. Each uncertain parameter is defined in terms of its nominal value and maximum deviation. The maximum deviations for demand ($Dev^d$) and travel time ($Dev^t$) are defined as 10%, 25%, and 50% of the nominal value, truncated to the first decimal place. In the experiments with the cardinality-constrained uncertainty set, the budgets for demand ($\Gamma ^d$) and travel time ($\Gamma ^t$) assume the values of 0, 1, 5, and 10, where 0 is the deterministic case. We run experiments with three different configurations of these parameters: uncertainty on demand only ($\Gamma ^d>0, \Gamma ^t=0$), uncertainty on travel time only ($\Gamma ^d=0, \Gamma ^t>0$), and uncertainty on both demand and travel times ($\Gamma ^d>0, \Gamma ^t>0$). For the latter, the budgets for both parameters are the same, i.e., $\Gamma ^d=\Gamma ^t$. Similar configurations are used for the single and two-knapsack uncertainty sets, with budgets $\Delta ^d, \Delta ^t \in \{0,20,40,60\}$. For the two-knapsack uncertainty set we assume that $\Delta ^d=\Delta ^d_1=\Delta ^d_2$ and $\Delta ^t=\Delta ^t_1=\Delta ^t_2$ for any budget. The nodes were divided into two groups, namely north and south, based on their geographical position in relation to the depot. In all experiments, if the budget of uncertainty for a specific parameter (demand or travel time) in the instance is zero, the maximum deviation for that parameter ($Dev^d$ or $Dev^t$) will also be zero. These combinations of budget and deviations result in 56 instances for the deterministic cases (i.e., when $\Gamma ^d=\Gamma ^t=0$ and $\Delta ^d=\Delta ^t=0$) and 168 instances for each configuration of budgets with positive values. However, for experiments with the cardinality-constrained RVRPTW having positive $\Gamma ^t$, five instances became infeasible and were discarded (hence, we have 163 instances in experiments with configurations in which $\Gamma ^t > 0$). The detailed results are available online at www.dep.ufscar.br/munari/rvrptw.

5.1 Computational performance of the compact formulations

5.1.1 Cardinality-constrained uncertainty set

Table 1 summarizes the results obtained with the MTZ-based and the CF formulations for the cardinality-constrained RVRPTW. We performed two experiments with both models: solving their LP relaxations only and solving them using the general-purpose MIP solver. For the first experiment, the table presents the average objective value (Obj), the quality of the LP relaxation as a percentage (QLR), and the average computation time in seconds (T). QLR is the percentage of the LP relaxation value relative to the obtained integer solution value. For the MIP solver results, in addition to the average objective values and computation times, the table shows the average optimality gap as a percentage (Gap), as provided by the solver at the end of the execution, and the number of instances solved to optimality (Opt). The results are grouped according to different configurations of $\Gamma ^d$ and $\Gamma ^t$.

Table 1 Results of the MTZ-based and CF formulations for the cardinality-constrained RVRPTW, considering different configurations of budgets

Regarding the LP relaxation of the formulations, we observe that CPLEX was considerably faster with the MTZ model, whereas the CF model resulted in stronger LP bounds. On average, the value of the LP relaxation for the CF model is 78.3% of the integer solution against 65.1% for the MTZ formulation. This behavior was expected since the CF formulations in the literature are known for having tighter LP relaxations than those based on big-M parameters (Letchford and Salazar-González 2015).

For the MIP formulations, while the MTZ model yielded shorter run times and 13 more instances solved to optimality, the CF presented lower average optimality gaps in all combinations of $\Gamma ^d$ and $\Gamma ^t$, better ensuring the quality of the solution obtained. Hence, when the use of the MTZ model does not lead to proven optimality, the gaps are considerably larger than those of the CF formulation, which is usually closer to proving optimality given its stronger LP relaxation. Furthermore, with the CF formulation, CPLEX solved more instances to optimality in the deterministic case ($\Gamma ^d=\Gamma ^t=0$) in about half the time on average. The CF model was also superior in terms of computation times and number of optimal solutions in instances where the uncertainty budgets ($\Gamma ^d$ and $\Gamma ^t$) are less than or equal to 1. Moreover, using the CF model resulted in more instances solved to optimality than the MTZ model in instances with $\Gamma ^d=5$ and $\Gamma ^t=0$ and in all instances under uncertainty exclusively on travel time ($\Gamma ^d=0$ and $\Gamma ^t>0$). These results suggest that the CF formulation should be the preferred choice for solving instances involving travel time uncertainty and for instances with demand uncertainty when the budget is sufficiently small.

We also identified the traditional behavior found in the RO literature (Ordonez 2010; Agra et al. 2013; Munari et al. 2019) where increasing the budget also tends to increase the time it takes to solve the problem for both formulations. This is expected since the budget directly impacts the number of variables and constraints of the formulations. This behavior is noticeable in both formulations and for any combination of $\Gamma ^t$ and $\Gamma ^d$.

5.1.2 Knapsack uncertainty set

Table 2 follows a similar structure to Table 1, but for different configurations of the knapsack set budgets $\Delta ^d$ and $\Delta ^t$. Similar conclusions as with the previous uncertainty set can be drawn from Table 2 regarding the quality of the LP relaxation and computational performance of the models. Particularly, the CF formulation presented stronger LP relaxations overall, with a QLR of 77.8%, but as a MIP model it resulted in fewer instances solved to optimality (461) than the MTZ-based model (1013), in longer running times (2576.13 seconds against 1494.33 seconds from the MTZ model, on average), and in larger average gaps (38.7% versus 10.1%). This is a consequence of the CF model requiring longer running times when solving the LP relaxation for instances with larger $\Delta$ values (e.g., 1558.49 seconds for $\Delta ^d=0$ and $\Delta ^t=60$, and 1909.10 seconds for $\Delta ^d=\Delta ^t=60$, on average), hindering the solver efficiency. Notably, instances with positive travel time deviation were harder to solve than those with deviation exclusively on demand, which is a consequence of the models having more constraints related to time flow propagation, as we cannot apply the constraint reduction strategy used for the demand uncertainty.

Table 2 Results of the MTZ-based and CF formulations for the single knapsack-constrained RVRPTW, considering different configurations of budgets

5.1.3 Two-knapsack uncertainty set

We now present the results of experiments conducted using the two-knapsack uncertainty set. We note that the models designed for this set were particularly challenging to solve. This is because they contain considerably more decision variables and constraints than the models based on the single knapsack uncertainty set, as the load variables are indexed based on the budgets of the two knapsacks. Consequently, the solver tends to use more memory to store and process the model and branch-and-bound tree.

The results obtained with the CF and MTZ-based compact formulations using the two-knapsack uncertainty set are summarized in Table 3. Similarly to other uncertainty sets, we performed experiments based on the LP relaxations and the full MIP formulations. The table has the same structure as Tables 1 and 2. The QLR values were computed based on the best results obtained by the BC algorithm presented in the next section.

Table 3 Results of the MTZ-based and CF formulations for the two-knapsack RVRPTW, considering different configurations of budgets

The first conclusion we can draw from these results is the increased difficulty in solving the formulations, as the solver presented considerably larger optimality gaps and longer computation times when compared to the use of other uncertainty sets. Additionally, fewer instances were solved to optimality overall. This is intensified in instances with larger uncertainty budgets, as the size of the problem significantly increases with the increase in budget.

Comparing the formulation based on MTZ constraints to that based on CF constraints, we get similar conclusions to the single knapsack uncertainty set. The MTZ formulation performed generally better, with lower average gaps. However, the LP relaxation of the model based on the MTZ constraints is generally weaker than that obtained with the model based on CF constraints. Notably, the CF-based formulation was particularly affected by the increase in problem size, where in some configurations, namely $\Delta ^d=0$ and $\Delta ^t=60$, and $\Delta ^d=60$ and $\Delta ^t=60$, the solver was unable to even find an optimal solution for the LP relaxation of the model, for any instance in these groups.

5.2 Computational performance of the BC algorithms

5.2.1 Cardinality-constrained uncertainty set

In this section, we analyze the results of the BC algorithms developed in Sect. 4, considering the cardinality-constrained uncertainty set. Table 4 summarizes the results using a similar structure to that of Table 1. We do not show results for the LP relaxation, as they are similar to those presented in Table 1.

Table 4 Average objective values and computation times of the BC algorithm for the cardinality-constrained RVRPTW

As expected, the BC algorithms outperformed their corresponding compact models as they start with a model having considerably fewer constraints and add cuts to ensure robustness as they are needed. The average solution times and gaps decreased, while the number of optimal solutions increased in all budget configurations. For example, the average solution time for the MTZ-based model decreased from 694.93 seconds to 277.13 seconds, the average gap reduced from 4.8% to 0.8%, and the number of instances solved to optimality increased from 1306 to 1449. Similarly, the average time for solving the CF model was almost halved, decreasing from 790.87 to 430.88 seconds. The average gap decreased from 2.1% to 0.8%, and 114 more instances were solved to optimality compared to solving the compact formulation.

The BC method with the MTZ-based formulation performed better than that with the CF formulation, taking less computation time to solve the instances (277.13 seconds against 430.88) and finding more optimal solutions (1449 against 1407). Additionally, this method was slightly superior even when solving most instances where the compact formulation had some advantage, namely the instances under uncertainty exclusively on travel time. The CF model had a better performance in terms of optimality gaps in instances under uncertainty exclusively on demand and $\Gamma ^d\le 5$, but both formulations solved the same number of instances to optimality in these configurations.

There are two main reasons for these superior results of the MTZ-based BC algorithm. The RCI generated using the CVRPSep package strengthen the LP relaxation of the model, which is still quicker to solve than the LP relaxation of the CF model. Indeed, strengthening the LP relaxation is particularly more helpful to the MTZ-based formulation, as it has a weak LP relaxation. Consequently, this reduces one advantage of the CF model over the MTZ-based model. Moreover, since the solver usually obtains the optimal solution of the LP relaxation faster with the MTZ-based formulation, the search tree explores more nodes quicker and, hence, finds an optimal solution before the BC algorithm based on the CF model. Even when the BC algorithms do not prove optimality within the time limit, the MTZ-based BC algorithm usually shows a superior performance, as it tends to explore more nodes.

5.2.2 Knapsack uncertainty set

Table 5 summarizes the results of the BC algorithms for the knapsack-constrained RVRPTW for different budget configurations. Most of the inferred conclusions for the cardinality-constrained uncertainty set also hold for the single knapsack set. The BC algorithms improved the computational performance compared to solving the compact models, indicated by the lower average running times and the larger number of solved instances. More specifically, the BC algorithm with MTZ-based formulation solved 1456 instances compared to only 1013 solved by the general-purpose MIP solver with the compact formulation, and the BC with the CF formulation solved 1318 instances to optimality compared to 461 instances with the compact model. Additionally, the better performance of the BC algorithm with the MTZ-based model is noticeable regarding computation times, number of instances solved to optimality, and optimality gaps. This behavior is a consequence of the strengthening of the LP relaxation in the BC algorithms, further assisted by the reduced size of the MTZ-based model compared to the CF model.

Table 5 Average objective values and computation times of the BC algorithm for the single knapsack-constrained RVRPTW

While algorithms with the knapsack uncertainty set proved to be more challenging to solve than their deterministic counterparts, their performance was comparable to those with the cardinality-constrained uncertainty set. Notably, the best-performing configuration with the knapsack uncertainty set, which is the BC algorithm based on an MTZ formulation, solved more instances than the best configuration of the BC algorithm for the cardinality-constrained uncertainty set. To help visualize this behavior, Fig. 1 shows the number of instances solved to optimality for each pair of demand and travel time deviations $(Dev^d,Dev^t)$, base models (MTZ and CF), and uncertainty sets (Card: cardinality-constrained; or Knap: single knapsack). The horizontal green line over the bars shows the number of instances for that combination of $Dev^d$ and $Dev^t$. As the chart suggests, the BC algorithms with the cardinality-constrained uncertainty set solved a similar number of instances to optimality to the knapsack uncertainty set. Thus, the strategy of relaxing the RO constraints and reintroducing them only if violated proved to be beneficial for both uncertainty sets.

Fig. 1

Number of instances solved to optimality by the BC algorithms for each pair of demand and travel time budgets ($Dev^d$,$Dev^t$) for the cardinality- and knapsack-constrained RVRPTW

5.2.3 Two-knapsack uncertainty set

Table 6 summarizes the results of the computational experiments with the BC algorithm using the two-knapsack uncertainty set. This table follows a similar structure to that of Tables 4 and 5. The results indicate that the BC algorithm vastly outperforms the compact formulations in terms of optimality gap, the number of instances solved to optimality, and the average computation times for this uncertainty set. This improvement is mainly because the base model of the BC algorithm is considerably smaller in terms of decision variables and constraints when compared to the compact formulations. Notably, the algorithm based on the CF formulations solves nearly 19 times more instances than its respective compact formulation.

Table 6 Average objective values and computation times of the BC algorithm for the two-knapsack RVRPTW

One interesting observation is that the results of the two-knapsack uncertainty set show a notable discrepancy compared to the other sets studied: the BC algorithm based on the CF formulation consistently outperformed the algorithm based on the MTZ formulation, on average. This discrepancy can be attributed to the absence of (a large number of) robust time flow constraints, as they were replaced by feasibility cuts, in instances under travel time uncertainty. Additionally, this formulation has a stronger LP relaxation and generally better performance in the deterministic case compared to the MTZ-based formulation. This stronger LP relaxation helped the BC method to lift the lower bound more quickly, thus reducing the average optimality gap compared to the method with the MTZ-based formulation.

5.3 Robustness analysis

We analyze the impact of the proposed RO approach regarding the objective function value and robustness of the solutions. The robustness of a solution is an important information in the decision-making process, as it can be used to evaluate the trade-off between cost and its risk, which is represented by the chance of a solution becoming infeasible in practice. To estimate this, we applied a Monte Carlo simulation with 1000 scenarios in which the uncertain parameters follow a continuous uniform distribution from their nominal value to their maximum realization for a given $Dev^d$ (or $Dev^t$).

5.3.1 Cardinality-constrained uncertainty set

Table 7 shows the average results for each budget configuration of the cardinality-constrained set, considering maximum deviations of 10%, 25%, and 50%. For each combination of budgets ($\Gamma ^d$ and $\Gamma ^t$) and deviations (Dev), the table shows the average price of robustness (PoR), which constitutes the percentage increase in costs of the robust solution over the deterministic one, and the average percentage of infeasible scenarios in the Monte Carlo simulation (Risk). Furthermore, regarding the PoR, the table shows the minimum (Best) and maximum (Worst) values obtained among all instances under that combination, and the normalized standard deviation (SD). All values are presented as percentages. The SD values help us evaluate the solutions’ variability because, although the average robust solution among the instances might be good, there is a risk of the worst-case performance being considerably more expensive.

Table 7 Average probability of constraint violation (Risk) and average price of robustness (PoR) of the solutions obtained for the cardinality-constrained RVRPTW considering different deviations. For each combination of budgets and deviation, columns Best, Worst, and SD give the minimum, maximum, and normalized standard deviation regarding PoR. All values are presented as percentages

We note that, by construction, greater budgets ($\Gamma ^d$ and $\Gamma ^t$) enlarge the uncertainty sets, and therefore, the probability of infeasibility decreases, but the cost increases accordingly. This can be identified by comparing the PoR and the Risk values between solutions with same deviation but different budgets. The probability of constraint violation, on the other hand, tends to decrease for large uncertainty budgets $\Gamma$. It is up to the decision-maker to select the most appropriate level of robustness. Regarding the impact of the deviations (Dev), we observe an increase on the PoR as they increase (positive budgets only), as the robust solutions become more conservative to account for these additional deviations. Furthermore, the deviation strongly impacts the Risk, especially when considering smaller budgets, as the solutions are more likely to violate the capacity or time windows constraints.

Interestingly enough, the SD values of the cost increase for the robust solutions are relatively small. Hence, the differences in terms of PoR among solutions within an instance class are not particularly large. From a decision-maker’s standpoint, this means that using the RO approach usually results in solutions with similar cost increment over the deterministic solution, with relatively low chances of large variability. This is particularly good for planning because, once the appropriate uncertainty budgets are set, there is little need to test different RO parameters for the new data when working with a given cost target.

Figure 2 shows the plots of the PoR versus the Risk for instances in classes C1, R1, and RC1, considering different deviations (0, 10, and 25%) and uncertainty budgets ($\Gamma \in \{0,1,5,10\}$ and $\Delta \in \{0,20,40,60\}$) for both uncertainty sets. The more convex the curve is, the better the trade-off between PoR and Risk is because the robust solution effectively reduces the risks with a slight cost increase. Thus, some of the solutions with the most expensive trade-off are those from instance class RC1 in Fig. 2c and f, where an increase of more than 30% in the costs is needed to neutralize the risks. We also note that in some configurations, namely in class C1 in Fig. 2a, c, d, and f; in class R1 in 2(b); and class RC1 in 2(c), increasing the budget also increases the solution costs with no impact in the risks. These cases occur when the solution with a smaller budget already had a null risk, and thus using a more conservative choice only increases the cost of the solution. From a decision-maker perspective, there is no reason to use these over-conservative solutions over the ones with zero risk and lower costs. On the other hand, some robust solutions, particularly those with deviation in time, greatly improve the robustness with an excellent trade-off, voiding all risks with a worst-case deviation of 10% with an increase in costs of as little as 0.5%.

Fig. 2

Trade-off between price of robustness (PoR) and probability of constraint violation (Risk) for the instances in classes C1, R1, and RC1

In summary, the results of the cardinality-constrained RVRPTW suggest that the RO approach can provide relevant solutions to support the decision-making process of choosing vehicle routes. The decision-maker can obtain solutions with different trade-offs regarding risks and costs. With this data, they can make an informed choice and opt for a more robust solution, which deteriorates the costs but ensures a better service level, or take a cheaper solution but accept more risks.

5.3.2 Knapsack uncertainty set

Table 8 summarizes the PoR and Risk values for the single knapsack-constrained RVRPTW according to each combination of budgets ($\Delta ^d$ and $\Delta ^t$) and deviations (Dev). Similarly to the previous uncertainty set, as the budgets $\Delta ^d$ and $\Delta ^t$ increase, the solutions become more conservative, and thus the PoR tends to increase while the risks tend to lower. The increase in the deviation values (Dev) also significantly affects the PoR and Risk. For a given combination of Dev and $\Delta$, the robust solutions have a similar increment in the PoR for all instances of the group. This is a positive behavior, as the decision-maker can have prior insight into the cost of the solution for that combination before running a new instance, allowing them to better direct computational efforts.

Table 8 Average probability of constraint violation (Risk) and average price of robustness (PoR) of the solutions obtained for the single knapsack-constrained RVRPTW considering different deviations. For each combination of budgets and deviation, columns Best, Worst and SD give the minimum, maximum and normalized standard deviation regarding PoR. All values are presented as percentages

The results indicate that the solutions obtained for the single knapsack-constrained uncertainty set resemble those obtained for the cardinality-constrained uncertainty set, when considering the same deviation level (Dev), particularly for those under with smaller deviation levels (10% or 25%). This is confirmed in the charts presented in Fig. 3, which show the average Risk and PoR for each combination of ($Dev^d$, $Dev^t$) of the solutions obtained considering the cardinality-constrained and the knapsack uncertainty sets. In particular, there are some configurations where both uncertainty sets yield similar solutions in terms of cost and risk, such as $\Gamma ^d=5, \ \Gamma ^t=0$ and $\Delta ^d=40, \ \Delta ^t=0$ with $Dev=10\%$; $\Gamma ^d=1, \ \Gamma ^t=0$ and $\Delta ^d=20, \ \Delta ^t=0$ with $Dev=50\%$; and $\Gamma ^d=10, \ \Gamma ^t=0$ and $\Delta ^d=60, \ \Delta ^t=0$ with $Dev=50\%$.

It is worth noting, however, that several configurations provided unique solutions that could not be achieved by the other uncertainty sets. Some of these solutions offer interesting trade-offs or a strictly superior performance in terms of cost and risk to those offered by the other sets. For example, the solutions using the knapsack uncertainty set with $\Delta ^d=0$ and $\Delta ^t=20$ with $Dev=10\%$ are on average strictly better than those obtained with the cardinality-constrained set with $\Gamma ^d=0$ and $\Gamma ^t=1$, as they have lower risk and cost. A similar behavior can be observed in the solutions with $Dev=25\%$ with $\Delta ^d=40$ and $\Delta ^t=0$, which have the same zero risk but a slightly lower cost compared to the solutions obtained with the cardinality-constrained uncertainty set with $\Gamma ^d=10$ and $\Gamma ^t=0$. Conversely, there are some solutions where the cardinality-constrained set presents more competitive solutions, such as instances under demand and travel time uncertainty with $Dev=50\%$, where solutions with $\Gamma ^d=\Gamma ^t=1$ are superior to those obtained with $\Delta ^d=\Delta ^t=40$.

Fig. 3

Average Risk and PoR for different budget values and deviation levels

A particularity of the knapsack uncertainty set is that the robustness of the solution does not increase as much as the cardinality-constrained uncertainty set for instances with larger deviations. For example, for instances with travel time uncertainties of $Dev=25\%$ and $Dev=50\%$, we were unable to obtain null-risk solutions using the chosen budgets for the knapsack uncertainty set. This is because, unlike the cardinality-constrained set, the budget of the knapsack set is independent of the deviation, and once the knapsack is completely filled, the solution may not change even in scenarios with larger deviations. Nevertheless, these results show that the knapsack uncertainty set might be useful from the decision-maker’s point of view, as it can provide different and competitive solutions that may outperform solutions related to the cardinality-constrained uncertainty set in some configurations. Moreover, this uncertainty set is often more intuitive to design in real-world systems as estimating the total deviation in a route is easier than the number of arcs/nodes attaining their worst-case value.

5.3.3 Two-knapsack uncertainty set

Table 9 Average probability of constraint violation (Risk) and average price of robustness (PoR) of the solutions obtained for the two-knapsack RVRPTW considering different deviations. For each combination of budgets and deviation, columns Best, Worst and SD give the minimum, maximum and normalized standard deviation regarding PoR. All values are presented as percentages

Table 9 summarizes the PoR and risk of the solutions obtained for the two-knapsack uncertainty set for each combination of budgets ($\Delta ^d$ and $\Delta ^t$) and deviation (Dev). We also present the best, worst, and standard deviation (SD) values for the PoR. The solution behavior for this uncertainty set is similar to the others. The risk decreases and the cost increases as higher budgets of uncertainty are considered. Conversely, the risks and costs tend to increase for scenarios with larger deviations. Regardless, the solutions obtained with this set were unique compared to the other sets in terms of risk and cost, presenting distinct trade-offs not achievable by other uncertainty sets. For example, this is the only uncertainty set able to provide solutions that offer trade-offs with non-zero risks of less than 5% in instances with 10% deviation ($\Delta ^d=0$ and $\Delta ^t=20$; $\Delta ^d=0$ and $\Delta ^t=40$; $\Delta ^d=20$ and $\Delta ^t=20$; and $\Delta ^d=40$ and $\Delta ^t=40$). This type of solution may appeal to decision-makers who accept the relatively low risk of infeasibility in exchange for a small reduction in cost.

In the experiments, the two-knapsack uncertainty set was, by construction, more conservative than the knapsack uncertainty set with the same budget $\Delta ^d$ and $\Delta ^t$. This is because the least conservative scenario for a route in the two-knapsack uncertainty set, where each customer visited in the route is in the same knapsack, is equivalent to the single knapsack uncertainty set with the same budget. Moreover, in the cases where customers from different knapsacks are visited on the route, the total budget in the route increases because the deviation of a node in one knapsack can be considered even if the other knapsack is completely filled.

5.4 Solution characteristics and managerial insights

Finally, we analyze the behavior of robust solutions and provide some managerial insights related to different uncertainty sets. For this purpose, we define and compute the customer-per-route ratio metric that can be used to describe the characteristics of the solutions for different configurations in terms of deviation and budget. The table showing the average value for this parameter, considering each budget configuration and deviation level, is presented in “Appendix 3”.

The customer-per-route ratio is calculated by finding the average number of customers visited in each route for a given solution. It can provide a general understanding of the structure of the routes and help assess the number of vehicles used in a solution. Figure 4 presents three charts showing the average customer-per-route ratio for each budget configuration, considering the three studied uncertainty sets. The blue lines represent results with the cardinality-constrained set (Card), gray lines represent results with the single-knapsack uncertainty set (Sing Knap), and orange lines represent the results with the two-knapsack set (Two-Knap). Each chart represents the average results for each deviation level (10%, 25%, and 50%). The budgets are displayed on horizontal axes in format $[\Gamma ^d,\Gamma ^t]$ or $[\Delta ^d,\Delta ^t]$ according to the uncertainty set.

Fig. 4

Average number of customers per route for each budget configuration and uncertainty set

The charts show that as the deviation increases, there is a tendency to reduce the number of customers visited per route. This trend is more pronounced for larger deviations (25% and 50%). With all instances having 25 customers, it also means an increase in the number of vehicles. When comparing the individual behavior of uncertainty sets, we observe that scenarios with larger deviation lead to more intense changes in solutions based on the cardinality-constrained set with budget increases. However, this behavior reflects the tendency of this set to provide zero risk at a higher cost compared to both knapsack sets in instances with small deviation levels, and to be the only set capable of finding risk-free solutions in instances with larger deviation parameters. In several cases, the knapsack sets were able to provide solutions with similar risk levels at lower costs and smaller changes from the deterministic solution in terms of customer-per-route ratio. Therefore, from a decision-maker’s perspective, it may be advantageous to evaluate and implement solutions based on a knapsack uncertainty set over a cardinality-constrained set. Additionally, even when solutions provided by a knapsack uncertainty are not strictly superior to those obtained using a cardinality-constrained set they often offer interesting trade-offs better matching the decision maker’s strategy.

Figure 4 also illustrates the generally more conservative results of the two-knapsack uncertainty set compared to the single knapsack set, when they are defined using the same budget values. This can be seen from the consistently lower customer-per-route ratio of the two-knapsack uncertainty set in most configurations. The reason for this is that for a given budget $\Delta ^d/\Delta ^t$, the total deviation on a route in the single knapsack set is limited by this budget, while in the two-knapsack set it may be limited by twice that value because each knapsack has its own budget $\Delta ^d/\Delta ^t$. Regarding the difference in behavior patterns between the cardinality-constrained and knapsack uncertainty sets, it is because the budgets for both knapsack sets are fixed amounts that do not depend on the deviations; whereas, with cardinality-constrained sets, the total deviation absorbed depends on both budget size and deviation level.

6 Conclusions

We proposed new compact models for the RVRPTW with variability in demand and travel time by considering the cardinality-constrained and knapsack uncertainty sets. We are not aware of any other compact model that considers a knapsack uncertainty set. The compact models were formulated using MTZ-based and CF constraints, and we exploited the linearization technique to model uncertainty. Additionally, we proposed tailored branch-and-cut algorithms based on these formulations, resulting in more efficient approaches.

Computational results with the proposed compact models using benchmark instances from the literature suggest that the MTZ-based formulation yields the best overall performance for both uncertainty sets, even though the CF model exhibits stronger LP relaxations and promotes a better performance of the solver on the deterministic case. An exception to this behavior is the solution of instances under uncertainty exclusively on travel times considering the cardinality-constrained uncertainty set, in which the CF leads to a better performance in terms of number of instances solved to optimality and optimality gaps, thus its use is recommended in this case.

The tailored branch-and-cut algorithms considerably improve the computational results of the proposed models, especially the one that relies on the MTZ-based formulation. When comparing the results of the two types of uncertainty sets, we observe that the use of a knapsack uncertainty set provides interesting solutions that can present a robustness level similar to the cardinality-constrained set, traditionally used in literature, but with lower costs. Based on our experiments, this uncertainty set may be easier to use in a practical setting, since it requires only the estimation of the maximum expected deviation, a more realistic requirement than the number of parameters attaining their worst-case value.

There are interesting directions for future work. One would be to develop branch-price-and-cut algorithms for the knapsack-constrained RVRPTW, which would allow us to solve larger instances of the problem. These algorithms may be combined with heuristic approaches, leading to an effective exact hybrid method for this variant. Another interesting topic would be to extend the proposed compact models and branch-and-cut algorithms to other types of uncertainty sets used in the RO literature, such as the ellipsoidal and factor models, which may show more suitable features in a decision-making process.

Appendices

Appendix 1: MTZ-based formulation for the RVRPTW under a multiple knapsack uncertainty set

To adapt the previous MTZ-based model to the multiple knapsack uncertainty set, we need new load and time variables and budget parameters. Each knapsack has a budget $\Delta ^d_l$ (demand) or $\Delta ^t_l$ (time). We provide the model for two knapsacks, and the extension to more knapsacks is trivial. The variables are now $u_{i\delta _{1}\delta _{2}}$ to represent accumulated load of the vehicle up to node i, with a total deviation $\delta _{1}$ over the demand’s nominal value for the first knapsack and $\delta _{2}$ for the second one; likewise, time variables are now $w_{i\delta _{1}\delta _{2}}$ representing the earliest possible time to start the service at node i, considering a total deviation of $\delta _{1}$ over the travel time’s nominal value for the first knapsack and $\delta _{2}$ for the second one. The model is then:

$$\begin{aligned}&\text{ min } \displaystyle \sum _{(i,j) \in A} c_{ij} x_{ij}, \end{aligned}$$

(45)

$$\begin{aligned}&\text{ s.t. } \text{(6), } \text{(7), } \text{(12), } \text{ and } \text{ to } \nonumber \\&\displaystyle u_{j \delta _{1}\delta _{2}} \ge u_{i\delta _{1}\delta _{2}}+\bar{d}_j+Q(x_{ij}-1), \ (i,j) \in A, 0\le \delta _{1}\le \Delta _1^d,0\le \delta _{2}\le \Delta _2^d, \end{aligned}$$

(46)

$$\begin{aligned}&\displaystyle u_{j \delta _{1}\delta _{2}} \ge u_{i(\delta _{1}-\hat{d}_j)\delta _{2}}+\bar{d}_j +\hat{d}_j+Q(x_{ij}-1), \ (i,j) \in A, j\in {S}^{d}_{1},j \not \in {S}^{d}_{2}, \hat{d}_j\le \delta _{1} \le \Delta _1^d, 0\le \delta _{2}\le \Delta _2^d, \end{aligned}$$

(47)

$$\begin{aligned}&\displaystyle u_{j \delta _{1}\delta _{2}} \ge u_{i\delta _{1}(\delta _{2}-\hat{d}_j)}+\bar{d}_j +\hat{d}_j+Q(x_{ij}-1), \ (i,j) \in A, j\not \in {S}^{d}_{1}, j \in {S}^{d}_{2}, 0\le \delta _{1} \le \Delta _1^d, \hat{d}_j\le \delta _{2}\le \Delta _2^d, \end{aligned}$$

(48)

$$\begin{aligned}&\displaystyle u_{j \delta _{1}\delta _{2}} \ge u_{i(\delta _{1}-\hat{d}_j)(\delta _{2}-\hat{d}_j)}+\bar{d}_j +\hat{d}_j+Q(x_{ij}-1), \ (i,j) \in A, j\in {S}^{d}_{1},j \in {S}^{d}_{2}, \hat{d}_j\le \delta _{1} \le \Delta _1^d, \hat{d}_j\le \delta _{2}\le \Delta _2^d, \end{aligned}$$

(49)

$$\begin{aligned}&\displaystyle u_{j \Delta _1^d\delta _{2}} \ge u_{i(\Delta _1^d-\lambda )\delta _{2}}+\bar{d}_j +\lambda +Q(x_{ij}-1), \ (i,j) \in A, j\in {S}^{d}_{1}, j \not \in {S}^{d}_{2}, 0\le \lambda \le \hat{d}_j, 0\le \delta _{2}\le \Delta _2^d, \end{aligned}$$

(50)

$$\begin{aligned}&\displaystyle u_{j \delta _{1}\Delta _2^d} \ge u_{i\delta _{1}(\Delta _2^d-\lambda )}+\bar{d}_j +\lambda +Q(x_{ij}-1), \ (i,j) \in A, j\not \in {S}^{d}_{1}, j \in {S}^{d}_{2}, 0\le \lambda \le \hat{d}_j, 0\le \delta _{1}\le \Delta _1^d, \end{aligned}$$

(51)

$$\begin{aligned}&\displaystyle u_{j \delta _{1}\Delta _2^d} \ge u_{i(\delta _{1}-\lambda )(\Delta _2^d-\lambda )}+\bar{d}_j +\lambda +Q(x_{ij}-1), \ (i,j) \in A, j\in {S}^{d}_{1}, j \in {S}^{d}_{2}, \lambda \le \hat{d}_j, \end{aligned}$$

(52)

$$\begin{aligned}&\displaystyle u_{j\Delta _1^d\Delta _2^d} \le Q, \ j\in N, \end{aligned}$$

(53)

$$\begin{aligned}&\displaystyle w_{j \delta _{1}\delta _{2}} \ge w_{i(\delta _{1}-\lambda )\delta _{2}}+\bar{t}_{ij}+s_i +\lambda +b_{n+1}(x_{ij}-1), \ (i,j) \in A, (i,j)\in {S}^{t}_{1}, (i,j) \not \in {S}^{t}_{2}, 0\le \lambda \le \min \{\hat{t}_{ij}, \delta _{1}\}\le \Delta _1^t, 0\le \delta _{2}\le \Delta _2^t, \end{aligned}$$

(54)

$$\begin{aligned}&\displaystyle w_{j \delta _{1}\delta _{2}} \ge w_{i\delta _{1}(\delta _{2}-\lambda )}+\bar{t}_{ij}+s_i +\lambda +b_{n+1}(x_{ij}-1), \ (i,j) \in A, (i,j)\not \in {S}^{t}_{1}, (i,j) \in {S}^{t}_{2}, 0\le \delta _{1}\le \Delta _1^t, \lambda \le \min \{\hat{t}_{ij},\delta _{2}\}\le \Delta _2^t, \end{aligned}$$

(55)

$$\begin{aligned}&\displaystyle w_{j \delta _{1}\delta _{2}} \ge w_{i(\delta _{1}-\lambda )(\delta _{2}-\lambda )}+\bar{t}_{ij}+s_i +\lambda +b_{n+1}(x_{ij}-1), \ (i,j) \in A, (i,j)\in {S}^{t}_{1}, (i,j) \in {S}^{t}_{2}, 0\le \lambda \le \hat{t}_{ij},\lambda \le \delta _{1}\le \Delta _1^t, \lambda \le \delta _{2}\le \Delta _2^t, \end{aligned}$$

(56)

$$\begin{aligned}&\displaystyle a_j\le w_{j \delta _{1}\delta _{2}}\le b_j, \ (i,j) \in A, 0\le \delta _{1} \le \Delta ^t_1, 0\le \delta _{2} \le \Delta ^t_2, \end{aligned}$$

(57)

$$\begin{aligned}&u_{i\delta _{1}\delta _{2}} \ge 0, \ i\in N, 0\le \delta _{1} \le \Delta ^d_1, 0\le \delta _{2} \le \Delta ^d_2, \end{aligned}$$

(58)

$$\begin{aligned}&w_{i\delta _{1}\delta _{2}} \ge 0, \ i\in N, 0 \le \delta _{1} \le \Delta ^t_1, 0 \le \delta _{2} \le \Delta ^t_2. \end{aligned}$$

(59)

Similarly to the previous models, the objective function (45) seeks to minimize the total traveling costs. Constraints (46)–(52) compute the demand for the worst case and forbid subtours. The vehicle capacity is ensured by constraints (53). Constraints (54)–(56) are similar to (50)–(52), but for the travel time. The time windows constraints are imposed by (57) and the domains of the variables are defined in (58)–(59). Note that we can easily extend this model for k knapsacks by adding indices from $\delta _1$ to $\delta _k$.

Appendix 2: Commodity-flow formulation for the RVRPTW under a multiple knapsack uncertainty set

Similarly to how it was done for the MTZ-based model, we extend formulation (32)–(38) to consider multiple knapsacks. Again, we present a formulation containing two knapsacks as the extension to k knapsacks is trivial, but the number of constraints grows quickly. This formulation uses the same sets and parameters as the MTZ-based model, while the load and time variables are now $f_{ij\delta _{1}\delta _{2}}$ and $g_{ij\delta _{1}\delta _{2}}$ with similar interpretations. The resulting model is given by:

$$\begin{aligned}&\text{ min } \displaystyle \sum _{(i,j) \in A} c_{ij} x_{ij}, \end{aligned}$$

(60)

$$\begin{aligned}&\text{ s.t. } \text{(6), } \text{(7), } \text{(12), } \text{ and } \text{ to } \nonumber \\&\displaystyle \sum _{j:(i,j) \in A}f_{ij\delta _{1}\delta _{2}} \ge \bar{d}_i+\sum _{h:(h,i) \in A}f_{hi\delta _{1}\delta _{2}}, \ i \in N, 0\le \delta _{1}\le \Delta _1^d, 0\le \delta _{2}\le \Delta _2^d, \end{aligned}$$

(61)

$$\begin{aligned}&\displaystyle \sum _{j:(i,j) \in A}f_{ij\delta _{1}\delta _{2}} \ge \bar{d}_i+\hat{d}_i +\sum _{h:(h,i) \in A}f_{hi(\delta _{1}-\hat{d}_i)\delta _{2}}, \ i \in N, i\in S^{d}_{1},i \not \in S^{d}_{2}, \hat{d}_i\le \delta _{1}\le \Delta _1^d, 0\le \delta _{2}\le \Delta _2^d, \end{aligned}$$

(62)

$$\begin{aligned}&\displaystyle \sum _{j:(i,j) \in A}f_{ij\delta _{1}\delta _{2}} \ge \bar{d}_i+\hat{d}_i+\sum _{h:(h,i) \in A}f_{hi\delta _{1}(\delta _{2}-\hat{d}_i)}, \ i \in N, i\not \in S^{d}_{1},i \in S^{d}_{2}, 0\le \delta _{1}\le \Delta _1^d, \hat{d}_i\le \delta _{2}\le \Delta _2^d, \end{aligned}$$

(63)

$$\begin{aligned}&\displaystyle \sum _{j:(i,j) \in A}f_{ij\delta _{1}\delta _{2}} \ge \bar{d}_i+\hat{d}_i+\sum _{h:(h,i) \in A}f_{hi(\delta _{1}-\hat{d}_i)(\delta _{2}-\hat{d}_i)}, \ i \in N, i\in S^{d}_{1},i \in S^{d}_{2}, 0\le \delta _{1}\le \Delta _1^d, \hat{d}_i\le \delta _{2}\le \Delta _2^d, \end{aligned}$$

(64)

$$\begin{aligned}&\displaystyle \sum _{j:(i,j) \in A}f_{ij\Delta _1^d\delta _{2}} \ge \bar{d}_i+\lambda +\sum _{h:(h,i) \in A}f_{hi(\Delta _1^d-\lambda )\delta _{2}}, \ i \in N, i\in S^{d}_{1},i \not \in S^{d}_{2}, 0\le \delta _{2}\le \Delta _2^d, 0\le \lambda <\hat{d}_i, \end{aligned}$$

(65)

$$\begin{aligned}&\displaystyle \sum _{j:(i,j) \in A}f_{ij\delta 1\Delta _2^d} \ge \bar{d}_i+\lambda +\sum _{h:(h,i) \in A}f_{hi\delta _{1}(\Delta _2^d-\lambda )}, \ i \in N, i\not \in S^{d}_{1},i \in S^{d}_{2}, 0\le \delta _{1}\le \Delta _1^d, 0\le \lambda <\hat{d}_i, \end{aligned}$$

(66)

$$\begin{aligned}&\displaystyle \sum _{j:(i,j) \in A}f_{ij\Delta _1^d\Delta _2^d} \ge \bar{d}_i+\lambda +\sum _{h:(h,i) \in A}f_{hi(\Delta _1^d-\lambda )(\Delta _2^d-\lambda )}, \ i \in N, i\in S^{d}_{1},i \in S^{d}_{2},0\le \lambda <\hat{d}_i, \end{aligned}$$

(67)

$$\begin{aligned}&\displaystyle d_ix_{ij} \le f_{ij\delta _1\delta _2} \le (Q-d_j) x_{ij}, \ (i,j) \in A, 0\le \delta _{1}\le \Delta _1^d,0\le \delta _{2}\le \Delta _2^d, \end{aligned}$$

(68)

$$\begin{aligned}&\displaystyle \sum _{j:(i,j) \in A}g_{ij\delta _{1}\delta _{2}} \ge \sum _{\begin{array}{c} h:(h,i) \in A\\ \lambda \le \hat{t}_{hi} \end{array}} (g_{hi(\delta _{1}-\lambda )\delta _{2}}+(\bar{t}_{hi}+\lambda )x_{hi})+s_i, \ i \in N,(i,j)\in S^{t}_{1},(i,j) \not \in S^{t}_{2}, 0\le \lambda \le \delta _{1} \le \Delta _1^t, 0\le \delta _{2} \le \Delta _2^t, \end{aligned}$$

(69)

$$\begin{aligned}&\displaystyle \sum _{j:(i,j) \in A}g_{ij\delta _{1}\delta _{2}} \ge \sum _{\begin{array}{c} h:(h,i) \in A\\ \lambda \le \hat{t}_{hi} \end{array}} (g_{hi\delta _{1}(\delta _{2}-\lambda )}+(\bar{t}_{hi}+\lambda )x_{hi})+s_i, \ i \in N,(i,j)\not \in S^{t}_{1},(i,j) \in S^{t}_{2}, 0\le \delta _{1} \le \Delta _1^t, 0\le \lambda \le \delta _{2} \le \Delta _2^t, \end{aligned}$$

(70)

$$\begin{aligned}&\displaystyle \sum _{j:(i,j) \in A}g_{ij\delta _{1}\delta _{2}} \ge \sum _{\begin{array}{c} h:(h,i) \in A\\ \lambda \le \hat{t}_{hi} \end{array}} (g_{hi(\delta _{1}-\lambda )(\delta _{2}-\lambda )}+(\bar{t}_{hi}+\lambda )x_{hi})+s_i, \ i \in N,(i,j)\in S^{t}_{1},(i,j) \in S^{t}_{2}, 0\le \lambda \le \delta _{1} \le \Delta _1^t, 0\le \lambda \le \delta _{2} \le \Delta _2^t, \end{aligned}$$

(71)

$$\begin{aligned}&\displaystyle (a_j+s_j)x_{ij}\le g_{ij\delta _{1}\delta _{2}}\le (b_j+s_j)x_{ij}, \ (i,j) \in A, 0\le \delta _{1} \le \Delta _1^t, 0\le \delta _{2} \le \Delta _2^t \end{aligned}$$

(72)

$$\begin{aligned}&x_{ij} \in \{0, 1\}, \ (i,j) \in A, \end{aligned}$$

(73)

$$\begin{aligned}&f_{ij\delta _{1}\delta _{2}} \ge 0, \ (i,j) \in A, 0\le \delta _{1}\le \Delta _1^d, 0\le \delta _{2}\le \Delta _2^d, \end{aligned}$$

(74)

$$\begin{aligned}&g_{ij\delta _{1}\delta _{2}} \ge 0, \ (i,j) \in A, 0\le \delta _{1}\le \Delta _1^t, 0\le \delta _{2}\le \Delta _2^t. \end{aligned}$$

(75)

The interpretation of this model is similar to the previous one, but the variables are related to the arcs and not the nodes.

Appendix 3: Results for customer-per-route ratio

In this section, we present the average results for the customer-per-route ratio discussed in Sect. 5.4. The results are summarized in Table 10, which shows the average ratio for each budget and deviation (Dev) configuration for each uncertainty set. The budgets are displayed in the format $[\Gamma ^d,\Gamma ^t]$ / $[\Delta ^d,\Delta ^t]$ according to the uncertainty set.

Table 10 Average customer-per-route ratio for each budget and deviation level