Groupe d’études et de recherche en analyse des décisions

G-2016-120

Robust solutions for the DARP with variations in transportation time

, , et

Le Problème de Transportà la Demande (PTAD) consiste à définir un ensemble de tournées pour acheminer des clients de leur point d'origine à leur point de destination tout en respectant des contraintes de capacité, de fenêtre de temps et de durée. Le PTAD Stochastique (PTADS) est une variante du PTAD dans laquelle le temps de trajet entre deux points est soumis à incertitude. Il est modélisé par une variable aléatoire pouvant représenter la variabilité des conditions de trafic (congestion due à un afflux, à des travaux de maintenance, à des conditions climatiques, etc.). La robustesse d'une solution peut être vue comme la probabilité de rester réalisable en tenant compte à la fois de la loi de distribution et de la politique du conducteur en réponse aux variations par rapport au planing initial. Trois politiques représentant des pratiques dans l'industrie sont considérées. Les principales approches pour les problèmes de transport stochastiques reposent sur l'estimation de la robustesse par simulation ou sur des méthodes analytiques. Toutes deux sont trop coûteuses pour être intégrées dans un schéma itératif de résolution. Nous proposons une approche indirecte pour estimer la robustesse. Elle repose sur la proposition d'un critère spécifique, corrélé avec la robustesse et qui peut être aisément calculé. Cette approche est intégrée dans une Evolutionary Local Search (ELS) et dans une métaheuristique multi-critère à base de population. Les solutions obtenues sont très robustes par rapport à ce critère et leur robustesse est confirmée par simulation. La robustesse des meilleures solutions du PTAD publiées dans la littérature est évaluée dans le contexte stochastique. La plupart est très sensible aux variations aléatoires. Les solutions fournies par l'ELS et l'algorithme à base de population sur les mêmes instances sont significativement plus robustes avec un impact modéré sur le coût de transport.

, 20 pages