Branch-price-and-cut for the electric vehicle routing problem with stochastic travel times and battery consumption chance-constraints
Alexandre Florio  1, 2@  , Nabil Absi  3, 4@  , Dominique Feillet  3, 4@  
1 : Ecole des Mines de Saint-Etienne  (EMSE)
Ecole des Mines de Saint-Etienne
2 : Laboratoire dÍnformatique, de Modélisation et dÓptimisation des Systèmes  (LIMOS)  -  Website
SIGMA Clermont, Université Clermont Auvergne : UMR6158, Centre National de la Recherche Scientifique : UMR6158
Bât ISIMA / Campus des Cézeaux BP 10025 / 63173 Aubière Cedex -  France
3 : Ecole des Mines de Saint-Etienne  (EMSE)  -  Website
Ecole des Mines de Saint-Etienne
Campus Georges Charpak Provence, F-13451 Gardanne, France -  France
4 : Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes  (LIMOS)  -  Website
CNRS : UMR6158
F-13541 Gardanne -  France

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.

Online user: 1 RSS Feed