The Static and Stochastic VRP with Time Windows and both random Customers and Reveal Times - Laboratoire d’Excellence Intelligences des Mondes Urbains Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

The Static and Stochastic VRP with Time Windows and both random Customers and Reveal Times

Résumé

Static and stochastic vehicle routing problems (SS-VRP) aim at mod-eling and solving real life problems by considering uncertainty on the data. In particular, customer data may not be known with certainty. Before the beginning of the day, probability distributions on customer data are used to compute a first-stage solution that optimizes an expected cost. Customer data are revealed online, while the solution is executed, and a recourse strategy is applied on the first-stage solution to quickly adapt it. Existing SS-VRP variants usually make a strong assumption on the time at which a stochastic customer reveals its data (e.g., when a vehicle arrives at the corresponding location). We introduce a new SS-VRP where customer reveal times are stochastic. We define first-stage solutions and a recourse strategy for this new problem. A key point is to introduce waiting locations that are used in the first stage-solution to wait for the realization of customer stochastic data. We show how to compute the expected cost of a first-stage solution in pseudo polynomial time, in the particular case where the vehicles are not constrained by a maximal capacity. We also introduce a local search-based approach for optimizing the first-stage solution, and introduce a scale parameter to tune the precision and cost of the expected cost computation. Experimental results on small to large instances demonstrate its efficiency and flexibility.
Fichier principal
Vignette du fichier
version-finale.pdf (826.89 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01485434 , version 1 (08-03-2017)

Identifiants

  • HAL Id : hal-01485434 , version 1

Citer

Michael Saint-Guillain, Christine Solnon, Yves Deville. The Static and Stochastic VRP with Time Windows and both random Customers and Reveal Times. 20th European Conference on Applications of Evolutionary Computation (EvoApplications), Part {II}, Apr 2017, Amsterdam, Netherlands. pp.110-127. ⟨hal-01485434⟩
398 Consultations
529 Téléchargements

Partager

Gmail Facebook X LinkedIn More