A two-stage stochastic optimization model for synchronized two-echelon routing problems

Résumé Technique : Un Modèle d'Optimisation Stochastique à Deux Étages pour les Problèmes de Routage Synchronisés à Deux Échelons

Définition du Problème
Cette étude traite de la complexité de l'incertitude au sein de la logistique urbaine, en se concentrant spécifiquement sur les systèmes de transport intégrés terre-eau (IWLT - Integrated Water- and Land-based Transportation). Le problème central est le Problème de Routage de Véhicules à Multi-trajets et Deux Échelons avec Synchronisation de Satellites (2E-MVRP-SS). Dans ce système, des véhicules électriques légers (LEFV) opèrent sur le premier échelon (les rues) pour collecter des marchandises auprès des clients et les transférer vers des navires (second échelon) au niveau de nœuds satellites. Le système fonctionne sans options de stockage aux satellites, exigeant une synchronisation spatio-temporelle stricte entre les LEFV et les navires.

Le défi principal abordé est la propagation des retards causés par les délais de transbordement incertains aux satellites. Ces incertitudes, découlant de facteurs régionaux tels que la congestion routière ou les variations opérationnelles, peuvent perturber les opérations synchronisées, entraînant des retards de livraison aux clients, une augmentation des coûts opérationnels et une réduction de la fiabilité. L'étude cible spécifiquement les scénarios de logistique inverse (par exemple, la collecte de déchets, les retours) où la ponctualité du service est critique pour minimiser les coûts d'inventaire et les désagréments des clients.

Méthodologie
Les auteurs proposent un cadre d'optimisation stochastique à deux étapes avec un problème de recours à variables entières mixtes pour gérer ces incertitudes.

1. Formulation à deux étapes :

   • Première étape (Problème Maître) : Les décisions concernant les itinéraires des LEFV et l'assignation des tâches de transfert aux satellites sont prises avant la réalisation des retards. Cette étape donne la priorité à la fiabilité des temps de service pour les collectes. Le modèle suppose que les LEFV visitent le satellite le plus proche comme une approximation initiale.
   • Deuxième étape (Recours/Sous-problème) : Une fois des scénarios de retard spécifiques réalisés, des mesures correctives sont prises. Cela implique de réallouer les opérations de transbordement à différents satellites et de réorganiser les itinéraires des navires pour atténuer l'impact des retards. Les programmes des LEFV pour le service client restent fixes pour respecter les horaires promis, mais la logistique fluviale est ré-optimisée.

2. Approche Algorithmique :

   • Pour gérer la non-convexité de la fonction de coût de la deuxième étape et la nature d'entiers mixtes du problème, les auteurs emploient une méthode en L (L-shaped method) adaptée avec des coupes de Benders combinatoires.
   • L'algorithme itère entre un problème maître relaxé et des sous-problèmes pour chaque scénario.
   • Des coupes de faisabilité garantissent que les décisions de la première étape permettent des solutions faisables en seconde étape.
   • Des coupes d'optimalité approchent le coût attendu de la seconde étape.
   • Une approche d'échantillonnage basée sur les scénarios est utilisée pour représenter les incertitudes régionales. Les retards aux satellites sont modélisés comme des variables suivant une loi normale, discrétisées en un ensemble fini de scénarios ($N$) pour assurer la tractabilité computationnelle tout en maintenant la stabilité.

3. Configuration Expérimentale :

   • Le modèle a été testé sur de petites instances de réseaux (10 nœuds de collecte, 4 satellites) dérivées d'instances modifiées de Solomon VRPTW.
   • Deux conceptions de système ont été comparées : 2E-Flexible (les navires agissent comme des dépôts mobiles, synchronisés avec les LEFV) et 2E-Stationary (emplacements de navires fixes).
   • La performance a été évaluée par rapport à une base déterministe (sans retard) et une approche stochastique à deux étapes.

Contributions Clés

• Modélisation Novatrice de la Synchronisation : Il s'agit de la première étude traitant de l'impact des retards de satellites sur la synchronisation des véhicules dans un système à deux échelons sans capacité de stockage, un scénario exigeant une haute coordination spatio-temporelle.
• Cadre de Recours Stochastique : Le papier propose un modèle de programmation stochastique à deux étapes avec un recours à variables entières mixtes spécifiquement pour le 2E-MVRP-SS. Il utilise des coupes de Benders combinatoires au sein d'une méthode d'énumération pour gérer la non-convexité de la seconde étape.
• Analyse Comparative de la Flexibilité : L'étude fournit une comparaison quantitative entre les systèmes de transport flexibles (navires mobiles) et les systèmes stationnaires sous incertitude, démontrant la valeur de la flexibilité pour atténuer la propagation des retards.

Résultats

• Réduction des Coûts : Le modèle de programmation stochastique proposé a réduit les coûts totaux attendus de 37 % sur toutes les instances par rapport à une approche déterministe supposant l'absence de retards.
• Stabilité des Scénarios : L'approche de génération de scénarios a démontré une stabilité ; la variance des scénarios au sein de l'échantillon a diminué à mesure que le nombre de scénarios augmentait, se stabilisant autour de 30 scénarios.
• Impact de la Topologie du Réseau :
  • Pour les réseaux de demande Groupés (C), le système intégré maintient son efficacité avec une augmentation de coût minimale (proche de 0 %) sous l'effet de l'incertitude.
  • Pour les réseaux Aléatoires (R), l'approche stochastique a réalisé les économies les plus significatives par rapport aux stratégies déterministes, réduisant les coûts attendus jusqu'à 43 % dans certaines instances en localisant mieux les points de collecte sensibles aux retards.
• Performance du Système (Flexible vs Stationnaire) :
  • Le système 2E-Flexible a nettement surpassé le système 2E-Stationnaire en termes de fiabilité et de part modale.
    • Sous l'effet de l'incertitude, le système stationnaire a connu une augmentation brutale des temps de trajet routiers et des retards (par exemple, le retard est passé à 26 unités de temps dans les instances RC), tandis que le système flexible a maintenu un retard faible (9 unités de temps) et une part modale plus équilibrée entre la route et l'eau.
  • Le système flexible a efficacement atténué le risque d'augmentation des coûts de transport routier, démontrant que la relocalisation des unités de stockage (ou dans ce cas, des points de transbordement) ne peut égaler la performance des services de navigation flexibles en termes de congestion et de fiabilité.

Signification et Revendications
Le papier affirme que l'intégration de l'incertitude dans la planification hors ligne est essentielle pour la fiabilité et la rentabilité de la logistique urbaine multimodale, particulièrement dans les contextes où la compétition pour l'espace urbain limite les options de stockage. L'étude démontre que les systèmes flexibles, où les navires agissent comme des dépôts mobiles synchronisés avec les LEFV, offrent une résilience supérieure contre les retards de transbordement par rapport aux systèmes à emplacements fixes.

Les auteurs concluent que, bien que le modèle proposé soit exigeant en termes de calcul, les gains observés sur de petites instances suggèrent que l'optimisation stochastique peut améliorer considérablement la fiabilité du service et réduire la part modale « verte » (usage de la route) dans la logistique urbaine. Ils notent que les travaux futurs pourraient utiliser le cadre d'énumération et de tarification proposé pour développer des heuristiques pour des problèmes à grande échelle, mais la présente étude se concentre sur la validation du cadre théorique et des bénéfices de la flexibilité sur de petits réseaux solubles.