Скачать или смотреть Vehicle Routing with Stochastic Supply of Crowd Vehicles and Time Windows

(28 septembre 2021 / September 28, 2021) Atelier Optimisation sous incertitude / Workshop: Optimization under uncertainty

Michel Gendreau (École Polytechnique de Montréal, Canada)
Vehicle Routing with Stochastic Supply of Crowd Vehicles and Time Windows

Résumé / Abstract: We study a setting where a crowd-shipping platform sells heterogeneous products of different sizes from a central depot. Delivery requests are fulfilled by a fleet of professional drivers and a pool of crowd drivers. The crowd-shipping platform standardizes crowd-drivers’ capacities and compensates them to return undelivered packages back to the depot. We assume that crowd driver availability is uncertain and formulate a two-stage stochastic model to optimize the routes planned for professional drivers and crowd drivers. We propose a branch and price algorithm to solve the problem exactly and a column generation heuristic to solve larger instances quickly. We further develop an analytical method to calculate upper bounds on the supply of vehicles and an innovative cohesive pricing problem to generate columns for the pool of crowd drivers. Computational experiments are carried out on modified Solomon instances with a pool of 100 crowd vehicles. The branch and price algorithm is able to solve instances with up to 100 customers. We show that the value of the stochastic solution can be as high as 18% when compared with the solution obtained from a deterministic simplification of the model.