CALENDRIER

mai 2018
L M M J V S D
  01 02 03 04 05 06
07 08 09 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31      

Partager cet événement

Enregistrer cet événement

Séminaire : The vehicle routing problem with stochastic and correlated travel times

Date
Mardi 13 mars 2018
Débute à 15:30

Prix
gratuit

Contact
Marilyne Lavoie
Site Web

Lieu
4488
2920, chemin de la Tour
Montréal, QC Canada
H3T 1N8

514 343-6111
Site Web | Itinéraire et carte

Catégories


Consulté 1924 fois
Séminaire : The vehicle routing problem with stochastic and correlated travel times

Séminaire 'Un chercheur du GERAD vous parle!'

Titre : The vehicle routing problem with stochastic and correlated travel times

Conférencier : Borzou Rostami – Polytechnique Montréal, Canada

In this paper we consider a version of the capacitated vehicle routing problem (CVRP) where travel times are assumed to be uncertain and statistically correlated (CVRP-SCT). In particular we suppose that travel times follow a multivariate probability distribution whose first and second moments are known. The main purpose of the CVRP-CST is to plan vehicle routes whose travel times are reliable, in the sense that observed travel times are not excessively dispersed with respect to their expected value. To this scope we adopt a mean-variance approach, where routes with high travel time variability are penalized. This leads to a parametric binary quadratic program for which we propose two alternative set partitioning reformulations and show how to exploit certain special structure in the correlation matrix when there is correlation only between adjacent links. For each model, we develop an exact branch-price-and-cut algorithm, where the quadratic component is dealt with either in the column generation master problem or in its subproblem. We tested our algorithms on a rich collection of instances derived from well-known datasets. Computational results show that our algorithms can efficiently solve problem instances with up to 75 customers. Furthermore, the obtained solutions significantly reduce the time variability when compared with standard CVRP solutions.


---

Du café et des biscuits seront offerts au début du séminaire.
Bienvenue à tous!

© École Polytechnique de Montréal
Bottin | Plan du site | Recherche | Conditions | Besoin d'aide?