Planification basée sur des scénarios pour le routage de véhicules partiellement dynamique avec des clients stochastiques

Le problème de routage de véhicules multiples avec fenêtres temporelles (VRPTW) est un problème d'optimisation combinatoire difficile et largement étudié. Cet article considère un VRPTW dynamique avec des clients stochastiques, où l'objectif est de maximiser le nombre de clients servis. Il présente une approche à plusieurs scénarios (MSA) qui génère continuellement des plans de routage pour des scénarios incluant des demandes connues et futures. Les décisions durant l'exécution utilisent un plan distingué choisi, à chaque décision, par une fonction de consensus. L'approche a été évaluée sur des problèmes de routage de véhicules adaptés des références de Solomon avec un degré de dynamisme variant entre 30 % et 80 %. Les résultats indiquent que MSA présente des améliorations dramatiques par rapport aux approches ne tirant pas parti de l'information stochastique, que l'utilisation d'une fonction de consensus améliore significativement la qualité des solutions, et que les bénéfices de MSA augmentent avec le degré de dynamisme (effectif).