Optimisation de la localisation et la configuration d'infrastructures de recharge pour une flotte de taxis électriques

Les enjeux actuels autour de l'écologie et du développement de nouveaux modes de transport moins polluants nous amènent à aborder de nouvelles problématiques. Celles traitées dans ce mémoire ont été initiées par le lancement du projet pilote de l'entreprise Taxelco : Téo Taxi, qui a introduit une flotte de taxis électriques à Montréal en novembre 2015. La mise en place et le fonctionnement d'une telle flotte conduit à diverses interrogations, dont notamment celle de la localisation des infrastructures de recharge. Nous proposons de traiter cette problématique en trois étapes : la localisation des infrastructures de recharge, l'attribution des courses aux véhicules et la configuration des stations. Ces trois problèmes sont formulés en programmes linéaires, dont les objectifs sont de minimiser les distances d'accès aux sites de recharge, pour les modèles de localisation et de configuration et de minimiser le nombre de véhicules en service, pour le modèle d'attribution des courses. Les modèles de localisation et de configuration prennent en compte en entrée un ensemble de données de courses représenté par une matrice de déplacements interzones. L'objectif de ces modèles est de localiser les sites de recharge à proximité des zones les plus visitées (zones accueillant le plus d'extrémités de courses). Chacune des zones est alors associée à un et un seul site de recharge. La configuration vise à répartir un nombre de bornes donné sur les différents sites localisés, en tenant compte alors du nombre de déplacements associés à chaque site. Le modèle d'attribution des courses consiste en un modèle de flux dans un réseau, pour lequel on souhaite satisfaire la totalité des courses en entrée avec un minimum de véhicules, nous prenons également en compte le problème de la recharge des taxis et la localisation des stations déterminée préalablement. Les modèles mathématiques mentionnés sont développés sous AIMMS ou AMPL et résolus par le solveur CPLEX. Les différentes expériences présentées dans ce mémoire sont appliquées au projet Téo Taxi et traitent donc de cas spécifiques rencontrés sur le développement de cette flotte de taxis électriques. Nous prenons en compte l'état actuel de leur réseau de recharge, ainsi que des diverses améliorations et modifications envisagées. Ces expériences sont possibles et pertinentes grâce à l'ensemble des données fournies par Téo Taxi. Nous élaborons donc une série d'expériences, compte tenu de l'état du réseau de recharge de Téo Taxi en mars 2017 : trois sites répartis sur l'île de Montréal et un quatrième site envisagé. Ces expériences ont pour but de localiser optimalement trois sites de recharge puis quatre sites sur le territoire d'étude et enfin de considérer les trois sites de recharge de Téo Taxi afin de localiser optimalement uniquement un quatrième site. Nous utilisons alors le modèle d'attribution comme outil de simulation pour évaluer les différentes localisations et déterminer la sollicitation des différentes stations, sur le cas d'une journée de service. Enfin, pour l'étape de configuration des stations, nous répartissons, tout d'abord, 50 bornes entre les stations de recharge pour tous les cas de localisation, puis nous nous appuyons sur les résultats précédents concernant la sollicitation des stations pour établir des comparaisons. Une seconde série d'expériences est ensuite réalisée selon la même approche, en tenant compte des évolutions du réseau de recharge de Téo Taxi en avril 2017 : quatre sites Téo et deux sites supplémentaires envisagés. Les résultats mis en évidence par la résolution du modèle de localisation révèlent les gains potentiels des localisations optimisées des stations. En effet, sur la première série d'expériences, les gains sur le temps total d'accès aux stations de recharge sont évalués entre 20 et 30%, pour les localisations optimisées par rapport aux localisations de Téo Taxi. L'importance d'une répartition optimale de bornes de recharge aux stations est, quant à elle, prouvée par le modèle de configuration. Les résultats présentés démontrent que toutes les stations ne sont pas sollicitées de la même manière et que certaines se doivent de proposer plus de bornes de recharge, car elles sont susceptibles d'accueillir plus de véhicules. Les simulations réalisées sur le seul exemple du 10 octobre 2016 ne permettent pas de conforter ces résultats car l'échantillon est trop restreint. Cependant, le modèle d'attribution, en tant qu'outil de simulation, devrait permettre une validation de ces résultats avec un plan d'expérience plus étendu.

Abstract

The current challenges concerning ecology and the development of less polluting transportation, lead us to address new issues. With this master thesis in collaboration with Taxelco, we discuss some of them. Indeed, Taxelco launched, in November 2015, an electric taxis fleet in Montreal, named Teo Taxi. This project brings new questions, nonetheless our work focuses mainly on charging station location. We address this problem in a three-step approach: charging facilities location, trip allocation to vehicles and stations configuration. These three problems are formulated using linear programming. With the location and configuration models, we seek to minimize the access distance to charging stations, while with the allocation model, we seek to minimize the number of taxis working. The location and configuration models use as input the trip data, represented by a from-to matrix, to locate the charging facilities close to the most visited areas. Then each area is linked with only one charging station. Looking at the trips matrix, the configuration model is used to allocate chargers to stations. The allocation model is formulated as a flow network and aims at satisfying the entire demand with a minimum of taxis. This model includes the locations determined by the charging problem. These three models are developed under AIMMS or AMPL and solved by the solver CPLEX. We use the Teo Taxi case and the specificities of this electric taxis fleet to make different experiments. With those experiments we considered Teo Taxi strategic decisions and development. Thanks to the data provided by Teo Taxi, we present relevant tests. So, we planned experiments based on the existing charging network in March 2017: three Teo stations and a fourth potential one. With those experiments we looked at optimal locations: three optimal stations, four optimal stations and a fourth optimal station with the three current ones. Then with the allocation model, used as a simulation tool, we evaluated the different locations and showed the demand at each station. Finally, we allocated 50 chargers to the stations, with the configuration model, and used the previous results on stations use for comparisons. Then, we repeated the same approach on the charging network updated in April 2017: four Teo stations and two other potential stations. The results provided by the location model show potential gains with the optimized stations locations. Indeed, on the first experiment, we show gains on total access time of around 20 and 30%, with an optimal location against Teo's one. The configuration model results show how the optimal distribution of chargers at stations is significant. In fact, the charging demand is different at each station, so some has to provide more chargers than others. Finally, we use the case of one day (10 October 2016) to simulate different locations, but with this single day we were not able to confirm previous results, because of the restricted sample. However, we can use the allocation model as a simulation tool to validate those results with more elaborate tests.