In this talk, we present a novel branch-price-and-cut (BP&C) algorithm for solving an electric VRP with stochastic travel-times and energy consumption. Instead of working on the customer-based graph, we model and solve the problem directly on the road network graph. This is motivated mainly due to (i) the difficulty of properly dealing with stochastic travel times in the customer-based graph, as pointed out recently in the literature, and (ii) the possibility, in the road network, of representing all the relevant attributes that can affect energy consumption when traveling along a road link.

The first contribution is a method for generating time- and space-correlated speed scenarios. This technique makes use of speed average and speed variance profiles defined on each link, which are then used to generate a multivariate normal distribution that represents the traveling speed on every link and time period. In addition to space- and time-correlation, the technique also enables time-dependency, much common in urban scenarios due to e.g. peak traffic hours.

Next, we introduce a BP&C algorithm to solve the target problem. The main difficulty when designing such algorithm is to develop an efficient procedure for checking the feasibility of routes, since the battery consumption constraint is probabilistic. By drawing and evaluating scenarios, we are able to statistically infer the feasibility (or infeasibility) of routes. This procedure is incorporated into the pricing algorithm. Other components of the algorithm include capacity-based completion bounds and the separation of rounded capacity cuts. Preliminary results are reported.