On the stochastic vehicle routing problem with time windows, correlated travel times, and time dependency

Vehicle Routing Problems (VRP) were and still are subject of countless studies in the literature of operational research. These problems consist in finding a set of vehicle routes serving certain customer requests with the minimum total travel cost. The term VRP in general refers to the deterministic problem, in which all the data are known and not subject to uncertainty. However, in practice, due to a variety of influences such as traffic jams, weather, customer availability etc., the real situation is often unpredictable, so that a solution of the deterministic problem in most cases produces solutions that are far from optimal in reality. To deal with this problem, specific approaches for addressing these uncertainties are needed.

The aim of this paper is to devise a new approach to check the feasibility of routes in the VRP with time windows (VRPTW) assuming stochastic travel times which can be used in branch-and-price algorithms as well as in many heuristic frameworks. Uncertainty is taken into account in several ways: firstly, the cost of a route depends on its expected travel times and is hence a random variable itself. Secondly, if a driver arrives too early at a customer’s location, the resulting waiting time has to be taken into account. Our model allows to calculate different costs for waiting and driving. Thirdly, and most importantly, a route may turn out to be infeasible under certain realizations of the travel times, due to the risk of missing some time window.

Unlike many other approaches presented in the literature, we explicitly deal with dependent travel times in our approach, assuming a joint normal distribution. In practice, neighboring streets often have highly correlated travel times, so that taking into account the dependency of travel times is important in order to obtain feasible solutions. This is also confirmed by our computational study: considering such dependencies improves the precision of the solutions significantly. The importance of correlations between travel times has also been underlined in Park and Laurence (1999).

Our approach can be used in any context where single routes are considered separately. This is the case, e.g., in the well-known set partitioning model, where the variables correspond to potential routes that are either enumerated in a first phase or are generated on the fly in a column generation approach. Also many heuristic approaches produce potential routes that have to be checked individually for feasibility and therefore our proposed feasibility check can be integrated easily.

The solution method proposed in this paper is based on the chance constraint approach, where a route is accepted if the risk of a failure stays below a given threshold. We distinguish between two application scenarios. In the first scenario, the route is considered infeasible if for any of the customers on this route, the probability of missing her time window is too high. This means that the infeasibility for every customer is checked independently. Such a scenario occurs in applications that consist of only deliveries, e.g., post delivery, or only pickups, e.g., garbage disposal. We present a (single) chance constraint formulation for this scenario. In the second scenario, missing a customer’s time window may render the entire route infeasible. Therefore, we aggregate the risk of failure for all customers and reject a route if the cumulated risk of failure is too high. The latter approach applies to variants of the VRP where pickups and deliveries are performed by the same vehicles, so that missing a customer might imply that some following customers cannot be served any more, e.g., due to lack of space in the vehicle. Another example for this is drayage, in which missing a customer can lead to a lack of empty containers at a later stop. In this situation, we are interested in the (joint) probability that at least one of the time windows is missed. For this setting, we present a joint chance constraint formulation. Moreover, for obtaining a more accurate stochastic model, we propose to consider truncated probability distributions in this case.

In both cases, we use and extend an idea of Ehmke et al. (2015). It addresses the fact that, due to possible waiting times, the arrival times at subsequent customers are not normally distributed any more. It is proposed in Ehmke et al. (2015) to approximate these travel times, which can be defined as maxima between two normally distributed variables, again by normally distributed travel times, with the same expected values and variances. In this context, we also refer the reader to Clark (1961), Nadarajah and Kotz (2008) and Sinha et al. (2007). We extend this approximation to the correlated case by also considering and updating the covariances between travel times. Additionally, we consider a situation where travel times change over the day, meaning that the time needed to travel an arc depends on when the arc is traversed.

It turns out that these extensions, though being computationally more expensive, lead to much more precise assessments of the feasibility of a route in realistic situations. In fact, our experiments on a set of instances with realistic travel times show that ignoring covariances leads to the creation of routes that are actually infeasible, when validated by sampling. The number of infeasible routes is decreased significantly when including covariance information in our algorithm. When travel times vary over the day, the difference between our approach taking this into account and an approach based on average travel times, is even larger, with many infeasible routes produced in the latter approach and, at the same time, objective values being better for our new algorithm.

The main purpose of our experiments is to show that considering covariances is crucial for an accurate feasibility check when instances with realistic travel times are solved. Additionally, we show that our proposed algorithms are a reliable feasibility check. As long as we do not consider time-dependent travel times (as in Section 4.2), the feasibility check could as well be performed by sampling, which would even be faster than our approach. However, we ultimately aim at combining correlations and time dependency, in which case sampling will not be a practicable approach any more; see our discussion in Sect. 4.2.2.

We aim at solving Vehicle Routing Problems with Time Windows subject to uncertain travel times. Extending the terminology of Toth and Vigo (2002) for the deterministic version of the problem, we will refer to this class of stochastic problems as SVRPTW. Every customer is visited exactly once by exactly one vehicle and all vehicle routes start and end at a single depot.

More formally, we assume that a finite set C of nodes is given, where \(0\in C\) corresponds to the depot and the remaining nodes in \(C\setminus \{0\}\) correspond to customers to be served. Moreover, we assume that each pair of nodes \(i,j\in C\) is connected by a directed arc \((i,j)\in E\), we thus deal with a complete graph \(G=(C,E)\) throughout the paper. A route r in G is given by an ordered list of distinct customers \(c_{r_1},\dots ,c_{r_k}\), the set of its arcs is denoted by \(E_r:=\{(0,c_{r_1}),(c_{r_1},c_{r_2}), \dots ,(c_{r_{k-1}},c_{r_k}),(c_{r_{k}},0)\}\). In our problem, each customer is assigned a deterministic time window. It will be convenient to index the time windows by arcs, thus for an arc \(e=(i,j)\) we will denote by \(a_e\) (\(b_e\)) the earliest (latest) start time of service at customer j, so that the time window is defined by \([a_e,b_e]\).

All travel times are uncertain and thus modeled as random variables. More precisely, we make the assumption that the vector \(X\in {\mathbb R}^E\), which defines the travel time \(X_e\) for each arc e, is jointly normally distributed with means \(\mu \in {\mathbb R}^E_+\) and covariance matrix \(\Sigma \in {\mathbb R}^{E\times E}\), i.e., \(X\sim \mathcal {N}(\mu ,\Sigma )\); we will denote the entries of \(\Sigma \) by \(\sigma _{e,f}\) for \(e,f\in E\). For simplicity, we assume that \(\Sigma \) is positive definite.

In particular, the travel time of each single arc e is again normally distributed with \(X_e\sim \mathcal {N}(\mu _e,\sigma _{e}^2)\), where we set \(\sigma _{e}=\sqrt{\sigma _{e,e}}\). This also implies that the travel time of a route, given as the sum of travel times of the contained arcs, is normally distributed – however, this is only true as long as no time windows are considered. In Sect. 4.2 we additionally assume that travel times are day time dependent, e.g., at 8 a.m. we assume to have more traffic than at midnight. We model this by replacing the expected value and the variance of an arc by functions that depend on the day time. Finally, we will use \(\epsilon \in (0,1)\) throughout the paper to denote the threshold for the risk of a failure, i.e., we will accept a route if the probability that it is infeasible, with respect to the uncertain travel times, is at most \(\epsilon \). For the reader’s convenience, we summarize this notation in Table 1.

In this paper, we restrict ourselves to discussing the following two questions with respect to a fixed route r: This is motivated by the fact that many exact as well as heuristic approaches for solving vehicle routing problems can be reduced to the above tasks, in particular when the decision of (a) is a difficult problem in itself. An important example for this class of approaches is the set partitioning approach to the VRP, which is often combined with column generation. Assuming that the full set of feasible routes R is known, together with the corresponding cost \(c_r\) for each \(r\in R\), we can model the final optimization problem as follows:Here we choose a cheapest subset of all routes such that each customer is visited exactly once by these routes. Throughout the paper, we use this formulation in our experiments. Since all constraints that do not depend on the travel time, such as capacity constraints, can be checked easily in a deterministic preprocessing, we do not consider these constraints in the following. In particular, vehicles with infinite capacity are assumed.

In Sects. 4 and 5, we will concentrate on the above questions (a) and (b) in two different application scenarios. In the first one, a route becomes infeasible if we miss the time window of any of the customers with probability larger than \(1-\epsilon \); see Sect. 4. In the second scenario, a route is infeasible if the probability of missing at least one customer exceeds \(1-\epsilon \); see Sect. 5. Even if the difference between the two scenarios seems very subtle, the second approach is much more challenging from a mathematical (and complexity-theoretic) point of view, as it requires to deal with joint chance constraints. In fact, we can only deal with the latter case in an approximate way. In both cases, the expected costs have to take possible waiting times into account.

A standard approach for testing feasibility of a given route r would be to sample the distribution of the involved arc lengths and to check whether the given chance constraints hold with high enough probability. Clearly, the crucial question here is how many samples to compute. If the number is chosen too high, it takes too much time to compute them. If it is chosen too small, the result will be unreliable. However, in our context, we are not interested in the exact probabilities that a route is feasible or not. Instead, we only have to decide whether this probability is greater than the threshold \(1-\epsilon \). This can be exploited in order to adaptively choose the number of samples, using the following classical result due to Hoeffding (1963).

Here, a Bernoulli distribution is a probability distribution of an experiment with binary outcome. E.g., to be sure with probability 99% that the mean does not deviate more than 1% from the real expected value, at most 26492 samples are needed. Algorithm 1 exploits this result in order to reduce the number of samples, in situations where infeasibility can be decided early with a given probability \(1-\delta \).

Let \(s_{\max }\) be the number of samples that have to be performed. Building on Theorem 1, Algorithm 1 stops earlier when the probability of infeasibility of the given route can be proven to be higher than a given threshold \(1-\delta \). With this approach Algorithm 1 avoids a huge number of unnecessary samples compared to the standard sampling and is able to save a huge amount of running time. For routes that are feasible, \(s_{\max }\) samples are used to guarantee that the computed cost of the route is as accurate as in the case of standard sampling.

In the following sections, we will use this approach for comparison and validation. Our main objective is to develop methods not based on sampling.

In this section, we assume that all demands are deliveries, deterministic and known before the optimization process, and not split. A typical application for this scenario are deliveries from a post office. An important characteristic of this kind of problem is that if a customer in a route happens not to be served for some reason, the next customer in this route can still be served by the same vehicle. This is because the service failure at one customer does not undermine the service at the next customer. Therefore, in the chance constraint approach to be developed, a risk level of service failure is fixed for each customer independently. In other words, the feasibility of a route is determined considering the union of the single chance constraints in the route. In the following, we describe our approach in mathematical and algorithmic terms and show experimental results concerning solution quality and running times. We first address the issue of correlations in Sect. 4.1, then we consider time-dependent travel times in Sect. 4.2.

So far, we have assumed that feasibility of a route is determined by a high enough probability to reach each customer within its time window. An implicit assumption in our model was that the failure of serving a customer does not influence the feasibility of the rest of the route directly. We now consider the case where failing to serve a customer may directly imply the failure of serving one of the remaining customers on the route, motivated by problems where customer demands can be either deliveries or a pickups. We will refer to this problem as a Stochastic VRPTW with Backhauls (pickup) and Linehauls (deliveries), SVRPTW-BL. Note however that our problem differs from the classical VRP with Backhauls Toth and Vigo (2002), because no precedence constraints on the deliveries are assumed, and it differs from the VRP with Pickup and Delivery Toth and Vigo (2002), in that the latter assumes a delivery and a pickup for each customer.

Our investigation of this VRP variant is motivated by problems in intermodal freight transport, for example freight transportation in intermodal containers using trucks, which involves the distribution of loaded and empty containers between an intermodal facility or depot and fixed export and import customers. In these applications, a large number of different customer request types and container constraints may arise Bomboi and Pruente (2018). In particular, if a customer in a route is not served for some reason, the feasibility of the rest of the route is not guaranteed anymore, e.g., a failed pickup of an empty container leads to the failure in loading the freight at the next customer or a failed delivery leads to a lack of space in the truck for a subsequent pickup.

We thus have to guarantee a service level for the whole route and not for each single customer, that is, we need to consider joint chance constraints in the place of single chance constraints. In other words, we have to deal with the risk of infeasibility of the whole route rather that considering the risk of failing to serve any of the customers in the route independently. For simplicity, we assume here that failing to serve any customer within its time window makes the entire route infeasible. In the remainder of this section, an algorithm for this case, using joint chance constraints in an approximate way, is provided and computational results are presented. In principle, by a combination of our proposed algorithms for the single and the joint chance constraint case, our approach could be extended to the case where not all failures render the rest of the route infeasible. Besides having to deal with joint chance constraints now, another complication is that, after passing a customer, distributions have to be truncated, as we are only interested in travel times under the assumption that the customers visited so far have been served in time.

We devised several algorithms for checking the feasibility of a given route in the Stochastic Vehicle Routing Problem with time windows and with correlated and time-dependent travel times. They are either based on closed formulas or sampling. We consider either single or joint chance constraints depending on whether missing a customer’s time window makes the entire route infeasible or not. These algorithms can be embedded into most algorithms for solving the Vehicle Routing Problem with hard time windows and waiting times as a feasibility check. Due to the fact that the algorithms also compute expected waiting times, they can be easily adapted to variants of the problem with soft time windows and penalties. The experimental results obtained in our case study show that the algorithms assess the feasibility of a given route with a reasonable precision, in particular when correlations are taken into account. However, for a large number of samples, the latter approach is time consuming.

Considering the complementary strengths of the deterministic and the sampling approach, one could also investigate combinations of both approaches. E.g., one could check for a given route how likely it is to become infeasible, and if the result is very close to the value of acceptance, do a second check performing sampling with a high number of samples – possibly only for routes that were accepted, but very close to be not accepted, because adding an infeasible route is in general more problematic than missing a feasible one. Another hybrid approach would be to use sampling with a high number of samples just as a callback inside the optimization process: first compute an optimal solution using our approach, then check the feasibility of all routes used in this solution by sampling, and if some route turns out to be infeasible, remove it and re-optimize. The advantage of this approach is that the sampling has to be performed for a very small set of routes and can thus be performed with a large number of samples in reasonable time.