Modélisation TIMES

Le Canada vise la cible zéro émission nette de gaz à effet de serre (GES) d'ici 2050. Mais comment atteindre cet ambitieux objectif de carboneutralité? Principalement en prenant des mesures sur le plan de la production et de la consommation d'énergie, deux aspects qui peuvent être évalués à l'aide de modèles énergétiques dits « technico-économiques ». Ces derniers détaillent l'ensemble du secteur énergétique avec ses différentes formes d'énergie (pétrole, bioénergies, électricité, etc.) et de technologies associées, afin d'identifier des stratégies qui permettraient d'éviter ou de séquestrer les émissions de GES.

Au fil du temps, des membres du GERAD ont développé plusieurs versions de tels modèles, en suivant, en particulier, l'approche TIMES élaborée au sein de l'Agence internationale de l'énergie. TIMES correspond à un programme mathématique de grande taille – constitué de millions de variables et d'équations – qui, une fois résolu, permet de cibler les scénarios de réduction des GES les plus efficaces sur le plan économique et le moment optimal pour les mettre en œuvre.

TIMES correspond à un programme mathématique qui permet de cibler les scénarios de réduction des GES les plus efficaces.

Le GERAD a notamment conçu un premier TIMES adapté au contexte canadien (TIMES Canada), que la société ESMIA Consultants – fondée par Kathleen Vaillancourt, une entrepreneure formée au GERAD – a ensuite repris pour en faire une version nord-américaine appelée NATEM. ESMIA l'utilise pour conseiller des entreprises et le gouvernement; par exemple, en collaboration avec l'Institut de l'énergie Trottier et Olivier Bahn, professeur au Département de sciences de la décision de HEC Montréal et directeur du GERAD, elle exploite le modèle pour élaborer des perspectives énergétiques canadiennes. Ainsi, le dernier rapport, publié en 2018, souligne l'importance de l'électrification et du déploiement des bioénergies pour atteindre des cibles ambitieuses de réduction des GES au Canada.

ESMIA et Olivier Bahn utilisent également NATEM dans le milieu universitaire, par exemple pour évaluer la pertinence économique et écologique d'un nouveau matériau de construction élaboré à l'Université McGill pour remplacer le ciment.

Planification des opérations en transport public

Toutes les grandes villes possèdent un réseau de transport urbain qui comprend, entre autres, un service d'autobus. Cette infrastructure offre à la population la possibilité de se déplacer entre les différents quartiers de la ville de façon économique et écoresponsable. Les sociétés de transport public étant, en grande majorité, subventionnées par les gouvernements, elles se doivent d'offrir un service de bonne qualité tout en évitant des coûts de fonctionnement excessifs. Ainsi, afin d'optimiser la planification de leurs opérations, elles font appel à des logiciels de prise de décision.

Étant donné la complexité de la tâche (par exemple, la Société de transport de Montréal offre plus de 17 000 voyages d'autobus par jour répartis sur 225 lignes), la planification d'un réseau d'autobus se fait généralement par étapes. Elle comprend la détermination des : i) lignes d'autobus; ii) horaires des voyages pour chaque ligne; iii) horaires d'autobus indiquant la suite des voyages à effectuer pour chaque autobus; iv) journées de travail spécifiant les suites des voyages à couvrir par des chauffeurs anonymes; et v) horaires des chauffeurs affectant des journées de travail et des jours de congé à chaque chauffeur pour le prochain mois. Les problèmes des étapes i) et ii) sont de niveau stratégique/tactique, et visent à maximiser la qualité du service tout en respectant certaines contraintes globales sur les ressources disponibles. Les problèmes des étapes iii) à v), quant à eux, sont de niveau opérationnel et cherchent à offrir à moindre coût le service déterminé dans les étapes précédentes, tout en prenant en compte de nombreuses contraintes pratiques telles que celles issues de la convention collective des chauffeurs.

Depuis quelques décennies, des membres du GERAD ont réalisé des travaux de recherche sur les problèmes opérationnels des étapes iii) à v). La plupart de ces travaux ont été faits en collaboration avec l'entreprise GIRO qui est le leader mondial dans la commercialisation de logiciels d'optimisation pour le transport public. Pour résoudre le problème de création des journées de travail des chauffeurs, François Soumis et Jacques Desrosiers ont développé à la fin des années 1980 un algorithme de génération de colonnes, nommé Gencol, qui permet de sélectionner le meilleur ensemble de journées de travail à opérer parmi un nombre astronomique de journées de travail possibles sans avoir à toutes les énumérer. Cet algorithme, qui est toujours utilisé par GIRO, a été enrichi au fil des ans par de nouvelles avancées réalisées au GERAD, notamment la technique d'agrégation dynamique de contraintes conçue par Issmail El Hallaoui, François Soumis et Guy Desaulniers. Plus récemment, GIRO a décidé d'employer aussi la génération de colonnes pour résoudre le problème de création d'horaires des autobus afin de prendre en compte les contraintes de recharge des autobus électriques. À cet effet, une nouvelle collaboration avec Guy Desaulniers a permis d'étudier différentes variantes de ce problème, notamment celle considérant la possibilité de modifier très légèrement les heures de début des voyages. Finalement, Guy Desaulniers, Andrea Lodi et François Soumis font équipe pour intégrer des méthodes statistiques et d'apprentissage automatique dans les algorithmes d'optimisation pour le transport public.

Planification intégrée de la production et du transport

Dans une chaîne d'approvisionnement, différentes activités sont effectuées en séquence, depuis les fournisseurs initiaux jusqu'aux clients finaux. Parmi les activités les plus importantes figurent la production, la gestion des stocks et le transport. Dans de nombreux cas, ces différentes activités sont gérées de manière isolée. Cependant, des gains importants peuvent être obtenus en considérant explicitement l'interaction entre les différentes activités et donc en les optimisant simultanément.

Dans le contexte d'un système de gestion des stocks par le fournisseur (VMI), le fournisseur prend des décisions de réapprovisionnement pour ses clients. Cela conduit à des arbitrages complexes. Par exemple, lorsqu'il décide quand produire et livrer deux commandes différentes de clients, le fournisseur doit prendre en compte plusieurs éléments. Si les deux clients sont situés à proximité l'un de l'autre, des économies sur les coûts de transport peuvent être réalisées en livrant les commandes par le même itinéraire. Cependant, cette approche peut induire des coûts de stockage supplémentaires si ces commandes ont des dates d'échéance différentes. En outre, si le fournisseur produit également les marchandises, les décisions relatives à la production doivent être intégrées : existe-t-il des économies d'échelle possibles dans la production et la capacité disponible est-elle suffisante ?

Il est clair que la prise en compte de plusieurs étapes dans la chaîne d'approvisionnement rend le processus de planification beaucoup plus complexe, ce qui nécessite des outils plus sophistiqués. Les différentes activités ayant un impact les unes sur les autres, la planification nécessite une approche intégrée. Plusieurs membres du GERAD ont étudié des problèmes de planification intégrée de la chaîne logistique, tels que le problème de routage des stocks et le problème de routage de la production.

Il existe de nombreuses applications réelles dans lesquelles ces problèmes apparaissent. Guy Desaulniers a étudié une application pour une entreprise de restauration livrant des repas à différents clients. Dans ce cas, il fallait établir un horaire de travail des employés en plus du plan de production et de distribution. Jean-François Cordeau et Raf Jans ont étudié une autre application réelle de la planification intégrée de la production et du routage pour un producteur de viande qui doit livrer toute une gamme de produits à près de 200 détaillants ayant des fenêtres horaires différentes. Dans les deux cas, le problème est rendu plus difficile en raison de la courte durée de vie des produits. Jean-François Cordeau et Raf Jans ont examiné une autre application du problème de la logistique de production dans l'industrie du meuble. Guy Desaulniers, Jacques Desrosiers ont étudié le problème de la gestion des stocks dans un contexte maritime pour le gaz naturel liquéfié. Leandro Coelho et Gilbert Laporte ont résolu des variantes du problème d'acheminement des stocks dans diverses applications réelles : une pour un fabricant d'eau en bouteille et une autre pour le réapprovisionnement de guichets automatiques.

Avec les chercheurs susmentionnés, d'autres membres du GERAD, tels que Yossiri Adulyasak, se sont également concentrés sur le développement d'algorithmes d'optimisation efficaces pour divers problèmes intégrés de production, d'inventaire et de planification du transport, y compris des algorithmes efficaces pour le problème de routage d’inventaire, le problème de routage de la production et le problème intégré de planification du service des navires.

D'autres membres du GERAD se sont également penchés sur différents types de problèmes de planification logistique intégrée, comme l'intégration du routage des véhicules et de la planification du chargement par Marilène Cherkesly.

Références :

• Adulyasak, Y., Cordeau, J.F., Jans, R., Optimization-based adaptive large neighborhood search for the production routing problem. Transportation Science, 48(1), 20-45, 2014.

• Adulyasak, Y., Cordeau, J.F., Jans, R., Formulations and branch-and-cut algorithms for multivehicle production and inventory routing problems. INFORMS Journal on Computing, 26(1), 103-120, 2014.

• Bertazzi, L., Coelho, L.C., De Maio, A., Laganà, D., A matheuristic algorithm for the multi-depot inventory routing problem. Transportation Research Part E: Logistics and Transportation Review, 122, 524-544, 2019.

• Cherkesly, M., Desaulniers, G., Laporte, G., Branch-price-and-cut algorithms for the pickup and delivery problem with time windows and last-in-first-out loading. Transportation Science, 49(4), 752-766, 2015.

• Chitsaz, M., Cordeau, J.F., Jans, R., A unified decomposition matheuristic for assembly, production, and inventory routing. INFORMS Journal on Computing, 31(1), 134-152, 2019.

• Dayarian, I., Desaulniers, G., A branch-price-and-cut algorithm for a production-routing problem with short-life-span products. Transportation Science, 53(3), 829-849, 2019.

• Desaulniers, G., Rakke, J.G., Coelho, L.C., A branch-price-and-cut algorithm for the inventory-routing problem. Transportation Science, 50(3), 1060-1076, 2016.

• Grønhaug, R., Christiansen, M., Desaulniers, G., Desrosiers, J., A branch-and-price method for a liquefied natural gas inventory routing problem. Transportation Science, 44(3), 400-415, 2010.

• Guimarães, T. A., Coelho, L.C., Schenekemberg, C.M., Scarpin, C.T., The two-echelon multi-depot inventory-routing problem. Computers & Operations Research, 101, 220-233, 2019.

• Li, Y., Chu, F., Côté, J.F., Coelho, L.C., Chu, C., The multi-plant perishable food production routing with packaging consideration. International Journal of Production Economics, 221, 107472, 2020.

• Lmariouh, J., Coelho, L.C., Elhachemi, N., Laporte, G., Jamali, A., Bouami, D., Solving a vendor-managed inventory routing problem arising in the distribution of bottled water in Morocco. European Journal of Industrial Engineering, 11(2), 168-184, 2017.

• Neves-Moreira, F., Almada-Lobo, B., Cordeau, J.F., Guimarães, L., Jans, R., Solving a large multi-product production-routing problem with delivery time windows. Omega, 86, 154-172, 2019.

• Van Anholt, R.G., Coelho, L.C., Laporte, G., Vis, I.F., An inventory-routing problem with pickups and deliveries arising in the replenishment of automated teller machines. Transportation Science, 50(3), 1077-1091, 2016.

• Wu, L., Adulyasak, Y., Cordeau, J.-F., Wang, S., Vessel Service Planning in Seaports. Operations Research (Forthcoming), 2021.