Axe 3 : Aide à la décision prise sous incertitude
L'incertitude est inhérente à un grand nombre de problèmes de décision et d'optimisation pour diverses raisons : modèles imparfaits, entrées de nature aléatoire, mesures bruitées des variables, et connaissance imprécise des paramètres dynamiques. À cela s'ajoute la complexité fréquente des grands systèmes contemporains. Cet axe regroupe les méthodes de décision dans les systèmes complexes et incertains. Parmi celles-ci figurent l'estimation d'état, la commande optimale hiérarchisée, l'optimisation robuste et la théorie des jeux à champ moyen.
Membres
Cahiers du GERAD
This paper addresses the difficulties mining companies face in planning their digital transformation. Based on the literature on project portfolio manageme...
référence BibTeX
Pour les séquences de réseaux
plongés dans le cube unité \([0, 1]^m\)
,
il existe des limites de mesure (faibles) de séquences de mesures empiriques
...
This paper presents a partial outsourcing strategy for the vehicle routing problem with stochastic demands (VRPSD), and routing reoptimization is considered ...
référence BibTeXPublications
Activités
Amit Sinha – Université McGill Aditya Mahajan – Professeur titulaire, Département de génie électrique et informatique, Université McGill
Mathieu Boudreault – Professeur, Département de mathématiques, Université du Québec à Montréal
Yi Ren – Arizona State University
Exemple en énergie, environnement, ressources naturelles
Optimisation de la production hydroélectrique et de la maintenance
L'hydroélectricité est une énergie propre et renouvelable qui utilise la force de l'eau afin de produire de l'énergie. Au Canada, plus de 60 % de l'électricité est produite grâce à l'hydroélectricité, tandis qu'au Québec cette valeur grimpe à 97 %. Un système hydroélectrique est composé de centrales et de réservoirs. Des modèles d'optimisation sont utilisés pour gérer efficacement ces systèmes complexes en raison des dépendances spatiotemporelles entre les installations et des apports en eau incertains au moment de la planification. En effet, ces systèmes subissent les aléas des prévisions météorologiques et hydrologiques, en plus d'être composés de turbines ayant des efficacités différentes.
Le domaine de l'optimisation hydroélectrique s'intéresse au développement de modèles mathématiques pour résoudre ces systèmes. Sara Séguin, professeure au Département d'informatique et de mathématique à l'Université du Québec à Chicoutimi et membre du GERAD, travaille plus spécifiquement sur les modèles à court terme, lesquels visent à prendre des décisions sur des horizons courts (en heures ou en jours) sur des périodes d'une à quelques semaines. Sara Séguin travaille en collaboration avec Rio Tinto depuis 2013 afin de peaufiner et de développer de nouveaux modèles, et des projets sont en cours en collaboration avec Dominique Orban et Miguel F. Anjos, respectivement professeurs à Polytechnique Montréal et à l'Université d'Édimbourg. Les travaux de recherche visent à raffiner les modèles afin de produire plus d'énergie avec les mêmes installations. Des modélisations novatrices des fonctions de production ont permis de modéliser le problème et de le résoudre en un temps de calcul très court. La modélisation des fonctions de production est particulièrement importante, considérant qu'elles sont non linéaires et non convexes à la base. Pour la société, la résolution de ces modèles permet d'éviter les inondations en maintenant les niveaux des réservoirs à des valeurs sécuritaires, et permet la navigation sur les lacs l'été en maintenant le niveau suffisamment élevé. Pour tout producteur, produire plus d'énergie avec la même quantité d'eau permet aussi de réduire les coûts au consommateur.
Exemple en infrastructures intelligentes
Développer les services d'échange de batteries dans les villes
L'électrification des transports urbains est au cœur des transformations et de l'essor de la ville intelligente. Fonctionnant sur batteries et moteurs électriques, les véhicules électriques sont porteurs de promesses telles que la réduction des émissions de carbone. Ces avantages attendus ont poussé les gouvernements du monde entier à encourager de manière agressive l'adoption de véhicules électriques. Par exemple, le Royaume-Uni et la France prévoient d'interdire respectivement d'ici 2035 et 2040 – la vente de nouveaux véhicules à combustion interne. Les mégalopoles chinoises rationnent davantage les ventes de véhicules électriques que les ventes de voitures à combustibles fossiles en plafonnant le nombre de plaques d'immatriculation délivrées. Compte tenu de ces tendances, plus de 500 millions de véhicules de tourisme en circulation, soit 30 % de l'ensemble du parc automobile, devraient être électriques d'ici 2040.
Au fur et à mesure que les véhicules électriques prospèrent, l'échange de batteries reprend vie. Solution de rechange au branchement des voitures pour recharger la batterie, l'échange de batterie fait référence au mode de ravitaillement d'un véhicule électrique en remplaçant la batterie déchargée à bord par une batterie chargée. Le renouveau de cette approche est motivé par ses trois avantages par rapport à la charge par « plug-in » : 1) rapidité : le processus d'échange ne prend que 3 à 5 minutes, alors que même l'utilisation du compresseur de Tesla prend plus de 30 minutes pour charger une batterie à 80 %; 2) compacité : la courte durée de service permet à une station d'échange d'occuper beaucoup moins d'espace qu'une borne de recharge enfichable pour atteindre le même niveau de service; 3) sécurité : par rapport aux propriétaires de véhicules, les fournisseurs de services sont en mesure de charger et d'entretenir plus correctement les batteries. Par conséquent, on pense généralement que l'échange de batteries prévaut, en particulier dans les grandes villes.
Néanmoins, les entreprises de véhicules électriques et les municipalités sont désormais confrontées à des défis majeurs lorsqu'elles tentent d'étendre les services d'échange de batteries dans les villes :
- Incertitude de la demande et proximité du service : le déploiement de l'infrastructure doit être dense afin que les demandes d'échange aléatoires puissent accéder à une station d'échange sans trop de détours. Les réseaux de stations d'échange urbaines qui en résultent sont très décentralisés et donc difficiles à exploiter.
- Disponibilité des batteries : les stations d'échange doivent également assurer une haute disponibilité des batteries chargées en stock pour satisfaire les demandes d'échange et éviter les files d'attente. Ce défi opérationnel est exacerbé par la disposition décentralisée des stations d'échange, car les demandes d'échange sont plus variables lorsqu'elles sont désagrégées que lorsqu'elles sont mises en commun. Par conséquent, le prestataire doit constituer des stocks massifs de batteries, coûteuses et néfastes pour l'environnement.
- Accessibilité au réseau : enfin, le chargement de batteries épuisées dans les stations d'échange peut surcharger, voire déstabiliser les réseaux locaux de distribution d'électricité basse tension. Ces réseaux du « dernier kilomètre » ont souvent été construits sans allouer une capacité suffisante pour la recharge des véhicules électriques. La mise à niveau des réseaux de distribution existants serait prohibitive, voire irréalisable.
Depuis des années, des membres du GERAD travaillent sur des problèmes de recherche opérationnelle concernant le verdissement de nos systèmes de transport urbain dans l'incertitude. Par exemple, le professeur Wei Qi et ses collaborateurs – au sein et en dehors du GERAD – se sont efforcés de mieux comprendre comment étendre les services d'échange de batteries à l'échelle de la ville pour faire face aux défis susmentionnés. Ces derniers examinent, entre autres, une configuration de réseau « échanger localement, charger de manière centralisée », où les batteries sont échangées localement dans des stations d'échange décentralisées, et transportées et chargées dans des stations de recharge plus centralisées qui sont connectées aux réseaux de capacité suffisante (qui sont généralement de niveau de tension plus élevé ou à proximité d'une sous-station). Ils ont construit des modèles qui caractérisent analytiquement les opérations entrelacées et stochastiques de stockage, d'échange, de charge et de circulation des batteries entre une station de charge centralisée et des stations d'échange décentralisées. Ils ont également développé un nouveau cadre algorithmique combinant des techniques de génération de contraintes et de recherche de paramètres pour résoudre des problèmes complexes de planification et d'exploitation d'infrastructures conjointes.
Référence :
- Qi, W., Zhang, Y., Zhang, N., Scaling Up Battery Swapping Services in Cities (19 juin 2020).
Exemple en logistique intelligente
L'incertitude de la demande dans les décisions d'inventaire, de routage et de localisation
L'une des principales complexités de la planification de la chaîne d'approvisionnement provient des incertitudes inévitables auxquelles il faut faire face. Les membres du GERAD ont développé des méthodes basées sur l'optimisation robuste et stochastique pour prendre de meilleures décisions face à l'incertitude dans les applications pour la chaîne logistique. Ces problèmes vont des problèmes opérationnels et tactiques tels que le routage ou la planification de la production et des stocks, aux problèmes stratégiques tels que la localisation des installations.
La principale incertitude qui complique la planification de la chaîne logistique à tous les niveaux est l'incertitude de la demande. Lors de la prise de décisions concernant la production et les stocks, le stock de sécurité est utilisé pour se protéger contre ce type d’incertitude. Le planificateur doit trouver un équilibre entre le coût d'un stock insuffisant et le coût d'un stock trop important. Déterminer la bonne quantité de stock de sécurité est donc difficile et nécessite des approches d'optimisation sophistiquées. Yossiri Adulyasak, Jean-François Cordeau, Erick Delage, Raf Jans et Gilbert Laporte ont exploité la programmation stochastique et les approches robustes pour résoudre ces problèmes de production et de stock. D'autres incertitudes proviennent du processus de production lui-même, par exemple le temps de configuration stochastique, et doivent également être prises en compte pour établir des plans efficaces.
Le GERAD a une longue et riche tradition de recherche sur les problèmes de routage de véhicules. De nombreux membres du GERAD, dont Yossiri Adulyasak, Leandro Coelho, Jean-François Cordeau, Guy Desaulniers, Fausto Errico, Raf Jans, Gilbert Laporte et Andrea Lodi, ont étudié l'incorporation d'éléments stochastiques dans divers problèmes de routage de véhicules. Cela inclut non seulement la prise en compte de la demande stochastique, mais aussi des temps de déplacement ou de service stochastiques. En outre, les problèmes de planification intégrée prenant en compte les décisions de production, d'inventaire et de routage ont également été étudiés dans un environnement stochastique.
L'incertitude doit également être prise en compte pour des décisions plus tactiques et stratégiques. Une décision extrêmement importante de la chaîne d'approvisionnement concerne l'emplacement de nouvelles installations. Il s'agit de décisions d'investissement à long terme et elles doivent donc être prises lorsqu'il y a beaucoup d'incertitude quant à la demande future. Comme il est difficile d'avoir de bonnes informations sur cette demande à long terme, des approches robustes ont été utilisées par Erick Delage et Yossiri Adulyasak. D'autres types d'incertitude, comme la possibilité de perturbations d’une installation, ont également été intégrés dans ces modèles. Au niveau tactique, Errico Fausto a considéré l'incertitude de la demande dans un problème de planification logistique d'une ville à deux niveaux.
Références :
VRP stochastique
Adulyasak, Y., Jaillet, P., Models and algorithms for stochastic and robust vehicle routing with deadlines. Transportation Science, 50(2), 608-626, 2016.
Errico, F., Desaulniers, G., Gendreau, M., Rei, W., Rousseau, L.M., The vehicle routing problem with hard time windows and stochastic service times. EURO Journal on Transportation and Logistics, 7(3), 223-251, 2018.
Errico, F., Desaulniers, G., Gendreau, M., Rei, W., Rousseau, L.M., A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times. European Journal of Operational Research, 249(1), 55-66, 2016.
Gauvin, C., Desaulniers, G., Gendreau, M., A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands. Computers & Operations Research, 50, 141-153, 2014.
Hoogeboom, M., Adulyasak, Y., Dullaert, W., Jaillet, P., The robust vehicle routing problem with time window assignments. Transportation Science, 55(2). 275-552, 2021.
Markov, I., Bierlaire, M., Cordeau, J. F., Maknoon, Y., Varone, S., A unified framework for rich routing problems with stochastic demands. Transportation Research Part B: Methodological, 114, 213-240, 2018.
Rostami, B., Desaulniers, G., Errico, F., Lodi, A., Branch-price-and-cut algorithms for the vehicle routing problem with stochastic and correlated travel times. Operations Research, 69(2), 436-455, 2021.
Problèmes stochastiques intégrés de routage de véhicules et d'inventaire
Adulyasak, Y., Cordeau, J.F., Jans, R., Benders decomposition for production routing under demand uncertainty. Operations Research, 63(4), 851-867, 2015.
Alvarez, A., Cordeau, J.F., Jans, R., Munari, P., Morabito, R., Inventory routing under stochastic supply and demand. Omega, 102, 102304, 2021.
Coelho, L.C., Cordeau, J.F., Laporte, G., Heuristics for dynamic and stochastic inventory-routing. Computers & Operations Research, 52, 55-67, 2014.
Markov, I., Bierlaire, M., Cordeau, J.F., Maknoon, Y., Varone, S., Waste collection inventory routing with non-stationary stochastic demands. Computers & Operations Research, 113, 104798, 2020.
Roldán, R.F., Basagoiti, R., Coelho, L.C., Robustness of inventory replenishment and customer selection policies for the dynamic and stochastic inventory-routing problem. Computers & Operations Research, 74, 14-20, 2016.
Solyalı, O., Cordeau, J.F., Laporte, G., Robust inventory routing under demand uncertainty. Transportation Science, 46(3), 327-340, 2012.
Planification stochastique de la production et des stocks
Ardestani-Jaafari, A., Delage, E., Robust optimization of sums of piecewise linear functions with application to inventory problems. Operations research, 64(2), 474-494, 2016.
Rodrigues, F., Agra, A., Requejo, C., Delage, E., Lagrangian duality for robust problems with decomposable functions: the case of a robust inventory problem. INFORMS Journal on Computing, 33(2), 685-705, 2021.
Sereshti, N., Adulyasak, Y., Jans, R., The value of aggregate service levels in stochastic lot sizing problems. Omega, 102, 10233, 2021.
Solyalı, O., Cordeau, J.F., Laporte, G., The impact of modeling on robust inventory management under demand uncertainty. Management Science, 62(4), 1188-1201, 2016.
Taş, D., Gendreau, M., Jabali, O., Jans, R., A capacitated lot sizing problem with stochastic setup times and overtime. European Journal of Operational Research, 273(1), 146-159, 2019.
Thevenin, S., Adulyasak, Y., Cordeau, J.F., Material requirements planning under demand uncertainty using stochastic optimization. Production and Operations Management, 30(2), 475-493, 2021.
Problèmes stochastiques tactiques et stratégiques
Ardestani-Jaafari, A., Delage, E., The value of flexibility in robust location–transportation problems. Transportation Science, 52(1), 189-209, 2018.
Cheng, C., Adulyasak, Y., Rousseau, L.M., Robust facility location under disruptions. INFORMS Journal on Optimization, 2021.
Cheng, C., Adulyasak, Y., Rousseau, L.M., Robust facility location under demand uncertainty and facility disruptions. Omega, 103, 102429, 2021.
Crainic, T.G., Errico, F., Rei, W., Ricciardi, N., Modeling demand uncertainty in two-tier city logistics tactical planning. Transportation Science, 50(2), 559-578, 2016.
Saif, A., Delage, E., Data-driven distributionally robust capacitated facility location problem. European Journal of Operational Research, 291(3), 995-1007, 2021.