Due à l’augmentation de la force des changements climatiques, il devient critique d’éliminer les combustibles fossiles. Les véhicules électriques sont un bon moyen de réduire notre dépendance à ces matières polluantes, mais leur adoption est généralement limitée par le manque d’accessibilité à des stations de recharge. Dans cet article, notre but est d’agrandir l’infrastrucure liée aux stations de recharge pour fournir une meilleure qualité de service aux usagers (et une meilleure accessibilité aux stations). Nous nous attaquons spéficiquement au context urbain. Nous proposons de représenter un modèle d’assignation de demande de recharge à des stations sous la forme d’un problème de flux maximum. Ce modèle nous sert de base pour évaluer la satisfaction des usagers étant donné l’infrastruture disponible. Par la suite, nous incorporons le model de flux maximum à un programme en nombre entier mixte qui a pour but d’évaluer l’installation de nouvelles stations et d’étendre leur disponibilité en ajoutant plus de bornes de recharge. Nous présentons notre méthodologie dans le cas de la ville de Montréal et montrons que notre approche est en mesure résoudre des instances réalistes. Nous concluons en montrant l’importance de la variation dans le temps et l’espace de la demande de recharge lorsque l’on résout des instances de taille réelle. / With the increasing effects of climate change, the urgency to step away from fossil fuels is greater than ever before. Electric vehicles (EVs) are one way to diminish these effects, but their widespread adoption is often limited by the insufficient availability of charging stations. In this work, our goal is to expand the infrastructure of EV charging stations, in order to provide a better quality of service in terms of user satisfaction (and availability of charging stations). Specifically, our focus is directed towards urban areas. We first propose a model for the assignment of EV charging demand to stations, framing it as a maximum flow problem. This model is the basis for the evaluation of the user satisfaction by a given charging infrastructure. Secondly, we incorporate the maximum flow model into a mixedinteger linear program, where decisions on the opening of new stations and on the expansion of their capacity through additional outlets is accounted for. We showcase our methodology for the city of Montreal, demonstrating the scalability of our approach to handle real-world scenarios. We conclude that considering both spacial and temporal variations in charging demand is meaningful when solving realistic instances.

Dans les chaînes d’approvisionnement, les producteurs font souvent appel à des entreprises de transport pour livrer leurs marchandises. Cela peut entraîner une concurrence entre les transporteurs qui cherchent à maximiser leurs revenus individuels en desservant un produc- teur. Dans ce travail, nous considérons de telles situations où aucun transporteur ne peut garantir la livraison de la source à la destination en raison de son activité dans une région restreinte (par exemple, une province) ou de la flotte de transport disponible (par exemple, uniquement le transport aérien), pour ne citer que quelques exemples. La concurrence est donc liée à l’expansion de la capacité de transport des transporteurs. Le problème décrit ci-dessus motive l’étude du jeu d’expansion de réseau multi-agent joué sur un réseau appartenant à de multiples transporteurs qui choisissent la capacité de leurs arcs. Simultanément, un client cherche à maximiser le flux qui passe par le réseau en décidant de la politique de partage qui récompense chacun des transporteurs. Le but est de déterminer un équilibre de Nash pour le jeu, en d’autres termes, la strategie d’extension de capacité et de partage la plus rationnelle pour les transporteurs et le client, respectivement. Nous rappelons la formulation basée sur les arcs proposée dans la littérature, dont la solution est l’équilibre de Nash avec le plus grand flux, et nous identifions ses limites. Ensuite, nous formalisons le concept de chemin profitable croissant et nous montrons son utilisation pour établir les conditions nécessaires et suffisantes pour qu’un vecteur de stratégies soit un équilibre de Nash. Ceci nous conduit à la nouvelle formulation basée sur le chemin. Enfin, nous proposons un renforcement du modèle basé sur les arcs et une formulation hybride arc- chemin. Nos résultats expérimentaux soutiennent la valeur des nouvelles inégalités valides obtenues à partir de notre caractérisation des équilibres de Nash avec des chemins croissants rentables. Nous concluons ce travail avec les futures directions de recherche pavées par les contributions de cette thèse. / In supply chains, manufacturers often use transportation companies to deliver their goods. This can lead to competition among carriers seeking to maximize their individual revenues by serving a manufacturer. In this work, we consider such situations where no single carrier can guarantee delivery from source to destination due to its operation in a restricted region (e.g., a province) or the available transportation fleet (e.g., only air transportation), to name a few examples. Therefore, competition is linked to the expansion of transportation capacity by carriers. The problem described above motivates the study of the multi-agent network expansion game played over a network owned by multiple transporters who choose their arcs’ capacity. Simultaneously, a customer seeks to maximize the flow that goes through the network by deciding the sharing policy rewarding each of the transporters. The goal is to determine a Nash equilibrium for the game, in simple words, the most rational capacity expansion and sharing policy for the transporters and the customer, respectively. We recap the arc-based formulation proposed in literature, whose solution is the Nash equilibirum with the largest flow, and we identify its limitations. Then, we formalize the concept of profitable increasing path and we show its use to establish necessary and sufficient conditions for a vector of strategies to be a Nash equilibrium. This lead us to the first path-based formulation. Finally, we propose a strengthening for the arc-based model and a hybrid arc-path formulation. Our experimental results support the value of the new valid inequalities obtained from our characterization of Nash equilibria with profitable increasing paths. We conclude this work with the future research directions paved by the contributions of this thesis.