Optimisation d’un service d’autopartage de véhicules électriques Amine Ait-Ouahmed 1 , Fen Zhou 1 , Didier Josselin 2,1 1. Laboratoire Informatique d’Avignon, Université d’Avignon, (S)FR Agor@ntic mohammed-amine.ait-ouahmed@univ-avignon.fr,fen.zhou@univ-avignon.fr 2. UMR ESPACE 7300 CNRS, Université d’Avignon, UNSA, (S)FR Agor@ntic didier.josselin@univ-avignon.fr RÉSUMÉ. Dans un système d’autopartage dit «à un seul sens», les utilisateurs peuvent prendre une voiture dans une station et la laisser ensuite à une autre station. Ce com- portement conduit généralement à une situation pour laquelle certaines stations sont pleines et d’autres vides. Le système est d’autant plus contraint que les véhicules sont électriques et qu’un temps de recharge minimal est nécessaire. Dans ce travail, nous proposons des heuristiques qui optimisent la redistribution des voitures et la gestion du service. Ces heuristiques permettent de calculer le nombre de voitures électriques, le nombre d’agents nécessaire et les différentes opérations de redistribution à réaliser pour une journée donnée. Les algorithmes proposés sont appliqués sur le réseau Auto Bleue de la ville de Nice et une cartographie est réalisée sur QuantumGIS à partir des demandes estimées. ABSTRACT. In the so called "one way" electric carsharing system, users can take a car at a station, use and leave it at another station. This process usually leads to a si- tuation where some stations are full while others are empty. The system is especially compelling because vehicles are electrical and a minimal charging time is required. Therefore, a balanced system requires the optimal distribution of the vehicles. In this work, we propose a heuristics algorithm that optimizes the redistribution of cars and their service management. This algorithm calculates the number of electric cars, the number of agents required and the redistribution operations to perform in a given day. The algorithms are applied to the Auto Bleue network in the surrounding of Nice (France) and a map is provided within QuantumGIS using estimated demands. MOTS-CLÉS : autopartage de véhicules électriques, redistribution de voitures, algo- rithme génétique, QuantumGIS, Auto Bleue à Nice KEYWORDS: electric carsharing, car redistribution, genetic algorithm, QuantumGIS Copyright © by the paper’s authors. Copying permitted for private and academic purposes. Proceedings of the Spatial Analysis and GEOmatics conference, SAGEO 2015. 2 SAGEO’2015 1. Introduction L’autopartage est le partage d’une flotte de voitures entre abonnés. Der- rière cette définition se cache un principe simple : l’utilisation occasionnelle en libre service d’une voiture sans en être le propriétaire. Selon une enquête natio- nale française (Louvet, Godillon, 2013), l’autopartage représente une solution de substitution à la voiture privée. Avant d’être abonnés, environ un tiers des ménages ne possède pas leur propre voiture, tandis que 75 % d’entre eux ne possèdent plus de voiture après la souscription. En outre, une grande propor- tion des répondants de l’enquête a déclaré que l’autopartage leur a permis de renoncer à l’achat d’une première voiture (34,4 % des répondants) ou d’une voiture supplémentaire de (8,8 %). La voiture est moins possédée, mais aussi moins utilisée : le nombre de kilomètres parcourus en voiture par an diminue de 41 %, suite à l’adhésion à l’autopartage. En ce qui concerne l’autopartage ex- ploité par les autorités locales ou par des entreprises privées, nous distinguons deux catégories : – l’autopartage "en boucle" : cette forme de partage de voiture est la plus classique car à ses débuts, l’autopartage a utilisé un système de boucle où les utilisateurs étaient obligés de restituer leur voiture à la station de départ ; – l’autopartage " à un seul sens" : il est différent du système en boucle dans la mesure où l’utilisateur peut restituer sa voiture dans toutes les stations et pas nécessairement à la station de départ. Ce système présente des avantages pour les clients, car la restitution de la voiture est beaucoup moins contraignante et peut être effectuée dans une station proche de la destination du client. C’est ce système que nous étudions dans cet article. Bien que l’autopartage dans un seul sens ait plusieurs avantages, il génère un problème majeur de relocalisation des véhicules. En effet, le fait que l’uti- lisateur ne ramène pas le véhicule dans sa station d’origine peut générer un déséquilibre dans la distribution des véhicules à travers la ville. Les opérateurs d’autopartage résolvent ce problème par l’introduction d’agents mobiles qui déplacent les véhicules entre les stations afin d’équilibrer leur répartition. Ce type de problème apparaît également dans des services similaires comme le par- tage de vélos (bike-sharing) (Schuijbroek et al., 2013). Ces opérations peuvent représenter un coût important, d’où le besoin de les optimiser. Au cours de ces dernières années, plusieurs études ont traité des plans de déploiement du service d’autopartage et de sa gestion. (Jorge, Correia, 2013) proposent notam- ment une revue de la littérature assez complète à ce sujet. Les décisions concernant le nombre de stations d’autopartage, leur localisa- tion et la taille de la flotte des voitures représentent des éléments stratégiques du problème. Parmi les travaux d’optimisation qui se sont intéressés à ce ni- veau de décision, nous pouvons citer les modèles de Programmation Linéaire en Nombres Entiers (PLNE) avec deux niveaux de décision (Correia et al., 2012) ou la localisation des dépôts et la sélection des tournées pour maximiser les bé- Copyright © by the paper’s authors. Copying permitted for private and academic purposes. Proceedings of the Spatial Analysis and GEOmatics conference, SAGEO 2015. Optimisation d’un service d’autopartage 3 néfices de l’organisation de l’autopartage dans un seul sens (cas de Lisbonne). D’autres auteurs (George, Xia, 2011) traitent le problème de la détermination de la taille optimale de la flotte. (Ion et al., 2009) utilisent un algorithme flou basé sur un ensemble de règles pour sélectionner les stations électriques. En ce qui concerne le niveau de décision tactique et opérationnelle, (Jorge et al., 2012) testent un modèle de PLNE pour résoudre le problème de relo- calisation des voitures. (Kek et al., 2009) présentent un algorithme d’aide à la décision pour les opérateurs d’autopartage de Singapour. (Jorge et al., 2014) comparent les relocalisations optimales calculées avec un modèle PLNE, avec deux politiques de relocalisation simulée. Dans le domaine de l’optimisation et de l’aide à la décision pour l’autopar- tage à un seul sens, (Boyaci et al., 2013) ont tenu compte des contraintes de recharge électrique des voitures. Dans ce travail, le problème de relocalisation des véhicules a été traité comme un problème d’échange de flux de voitures entre les stations. Les auteurs supposent qu’après chaque utilisation, les véhi- cules doivent se recharger pendant la même durée (2 heures) indépendamment de la distance parcourue. Dans le cadre de notre étude, nous proposons une prise en compte plus réa- liste des contraintes de recharge électrique et modélisons le problème comme un problème de routage des véhicules au lieu d’un problème de flux général, ce qui nous permet de suivre les véhicules et leurs affecter des temps de recharge correspondants aux distances parcourus. Nous tenons également compte du temps d’utilisation du véhicule par un client, d’où découle un temps de re- charge proportionnel. La demande est également estimée à partir de données géographiques de densité de population et de bassins de chalandise des stations. Après cette introduction, le reste de l’article est organisé comme suit. Nous présentons le problème d’autopartage de véhicules électriques dans un seul sens dans la section 2. Ensuite, une heuristique ainsi qu’un algorithme génétique sont proposés pour l’optimisation du problème dans la section 3. Une hypothèse pour la génération d’instances sur le site de Nice est fixée dans la section 4 et des simulations sont menées dans la section 5 pour comparer les différents algorithmes et illustrer l’effet de la relocalisation des voitures sur les coûts. Enfin, le papier est conclu dans la section 6. 2. Le modèle : définition du problème et notations Pour définir plus formellement la relocalisation et le routage dans l’autopar- tage de voitures électriques dans un seul sens, nous allons préciser les données manipulées, les règles, les contraintes et les objectifs. Nous présentons aussi un petit exemple pour faciliter la compréhension du problème. Copyright © by the paper’s authors. Copying permitted for private and academic purposes. Proceedings of the Spatial Analysis and GEOmatics conference, SAGEO 2015. 4 SAGEO’2015 2.1. Les données Les données sont composées d’un ensemble N = {1, 2, ..., nbStat } de stations pour le stationnement et la recharge électrique des véhicules, chaque station i ∈ N ayant une capacité Qi maximale de places. L’ensemble T = {1, 2, ..., nbT } des périodes de temps divise le temps d’une journée de service en des périodes de temps t ∈ T de même durée. Le temps du trajet entre les stations k et i 0 est donné par tki . L’ensemble des demandes des clients est D = {d(kt )(it) } où 0 d(kt )(it) représente un départ de la station k à t0 vers la station i à t. L’ensemble F = {1, 2, ..., nbV eh } réunit les véhicules électriques. Chaque voiture doit se recharger au minimum pendant une durée T rdki après un trajet de la station k vers i. On dispose également d’un ensemble d’agents (salariés de l’opérateur du service) E = {1, 2, ..., nbAgt } capables de déplacer un véhicule à la fois entre les stations. 2.2. Les règles et les contraintes du système Le problème est soumis à des contraintes de temps et de ressources : – Un client peut demander une location de voiture, caractérisée par la sta- tion et la date de départ, conjointement avec la station et la date d’arrivée ; – Une voiture peut satisfaire des clients, être déplacée par un agent ou bien être garée dans une station de recharge ; – Un agent peut déplacer une voiture d’une station à une autre ; – Chaque voiture ou chaque agent peut commencer la journée dans une station et la terminer dans une autre ; – Le nombre de voitures garées dans une station ne doit pas dépasser la capacité de la station ; – Aucun trajet ne dois dépasser 100 km, distance qui correspond approxi- mativement à l’autonomie des voitures électriques – Chaque voiture doit être rechargée après chaque voyage. Le temps de recharge est proportionnel à la durée du trajet effectué (pour chaque 15 km effectué, 30 min de recharge sont nécessaires). Une implémentation de ces contraintes avec un programme linéaire en nombres entiers est utilisée pour une résolution exacte de petites instances du problème, mais cette implémentation n’est pas détaillée dans cet article. 2.3. Objectif Nous minimisons un coût global C obtenu par la somme pondérée de 4 objectifs. Copyright © by the paper’s authors. Copying permitted for private and academic purposes. Proceedings of the Spatial Analysis and GEOmatics conference, SAGEO 2015. Optimisation d’un service d’autopartage 5 min {C = α · CC + β · CV + γ · CA + δ · CD } où : – CC est le nombre de demandes de clients non satisfaites ; – CV est le nombre de voitures utilisées; – CA est le nombre d’agents utilisés; – CD est la somme des distances parcourus. Dans cet article, nous n’introduisons pas encore d’optimisation multi-critère. La pondération des quatre critères nous permettrait en effet d’adapter la fonc- tion d’objectifs selon les besoins. Présentement, les poids α, β, γ et δ ont été respectivement fixés à : 1000, 200, 100 et 10. Les valeurs des poids correspondent à l’importance des différents objectifs dans notre problème d’optimisation. Cet article présentant la méthode dans son ensemble, nous fixons ici arbitrairement un gradient net d’importance entre les critères : la principale priorité est la satisfaction du plus grand nombre de clients, puis vient la minimisation du nombre de voitures, du nombre d’agents et enfin de la somme des distances parcourues. D’autres scénarios de fonctions objectif orientées davantage vers l’optimisation des ressources seraient envisageables, mais ici nous nous foca- lisons sur une fonction objectif résolument orientée vers la qualité de service, premier critère d’un service public. 2.4. Exemple A1,v1 v6 A1,v3 A1 A1 A1 A1,v2 (v6,c1) (v3,c11) (v2,c10) (v1,A1) (A1,v3) (v6,c8) v2,v3 v2,v3 v4 v5 v5 v1 v1,v3 v1,v3 v1,v3 1 (v4,c4) (v3,c2) (v5,c9) (v5,c5) (v1,c7) v4,v5,v6 v4,v5,v6 A1,v1 A1,v3 v2 v2,v4 v2,v4,v6 v4,v5,v6 v4,v5,v6 v4,v5,v6 (v2,c3) (v4,c6) 1 2 3 4 5 6 7 8 9 10 Figure 1. Exemple d’autopartage avec 6 véhicules et 3 stations distinctes (v = véhicule, A = agent et c = client) ; par exemple, (v1, A1) indique que l’agent A1 a déplacé la voiture 1, (v6, c1) indique que le client 1 a utilisé la voiture 6. La Figure 1 décrit un schéma logistique simplifié associé à un scénario pos- sible pour une journée de service. Dans ce scénario, le service d’autopartage est Copyright © by the paper’s authors. Copying permitted for private and academic purposes. Proceedings of the Spatial Analysis and GEOmatics conference, SAGEO 2015. 6 SAGEO’2015 Table 1. Exemple de onze instances de demandes d’utilisateurs Départ Arrivée Clients Station Période de Temps Station Période de Temps client 1 (c1) 3 2 1 4 client 2 (c2) 2 2 3 3 client 3 (c3) 2 2 3 4 client 4 (c4) 3 2 2 3 client 5 (c5) 3 2 2 4 client 6 (c6) 2 4 3 5 client 7 (c7) 3 3 2 6 client 8 (c8) 1 5 3 6 client 9 (c9) 2 6 3 7 client 10 (c10) 3 7 1 9 client 11 (c11) 1 6 2 7 basé sur 6 voitures électriques et 3 stations : la station 1 (1 place de parking et 1 place de recharge), la station 2 (2 parkings et 2 recharges) et la station 3 (3 parkings, 3 recharges). La journée de service est divisée en dix périodes de temps. Le temps nécessaire pour recharger une voiture après un voyage est égal à 1 période de temps et le temps du trajet entre toutes les stations est égal à 1 période de temps également. Onze demandes de clients sont caractérisées par des couples (station, période de temps) de départ et d’arrivée indiquées dans la Table 1. On peut observer que grâce aux relocalisations opérées par l’agent (A1), les 11 clients ont pu être satisfaits dans l’exemple de la Figure 1. 3. Solutions approchées et algorithmes heuristiques Les techniques heuristiques permettent un compromis entre vitesse d’exé- cution et qualité de solution. Dans un premier temps, nous introduisons une nouvelle Heuristique Gloutonne (HG) permettant la construction rapide d’une solution réalisable pour le problème d’autopartage traité. En utilisant cette HG, nous définissons ensuite un Algorithme Génétique (AG). 3.1. Heuristique gloutonne Nous développons une heuristique spécifique à notre problème, de com- plexité polynomiale, qui prend en compte les objectifs, les règles et les contraintes évoquées précédemment. Vue la complexité du problème traité, les expérimen- tations que nous avons réalisées (cf Table 2) montrent qu’il est impossible de trouver une solution exacte dans un temps raisonnable pour des instances de taille réelle (soit environ 30). Nous nous tournons donc vers des solutions ap- prochées et efficaces. On utilise pour cela une fonction de routage pour les véhicules et les agents, dans un graphe qui permet de modéliser et d’optimiser le partage des ressources (capacité d’accueil des stations). Copyright © by the paper’s authors. Copying permitted for private and academic purposes. Proceedings of the Spatial Analysis and GEOmatics conference, SAGEO 2015. Optimisation d’un service d’autopartage 7 Chaque véhicule est ainsi associé à un chemin qui commence au début d’une journée de service dans une station et visite d’autres stations jusqu’à la fin du service. Un tel chemin est fondamentalement caractérisé par ses traces dans deux dimensions : l’espace et le temps. Il est donc naturel d’utiliser un graphe spatio-temporel G(V, A, C, R) composé comme suit : – L’ensemble des sommets V = {vti : t ∈ T, i ∈ N } ∪ {vs , vd } est composé de tous les nœuds vti où i représente une station et t une période de temps, les nœuds vs et vd représentant respectivement le début et la fin de la journée de service ; – L’ensemble des arcs est A = A1 ∪ A2 ∪ A3 où : - A1 = {(vti , vt+1 i ), (vs , vi1 ), (vinbT , vd ) : i ∈ N, t ∈ T }. Chaque arc (vti , vt+1 i ) représente un lien au sein de la même station entre deux périodes de temps consécutives. - A2 = {(vtk0 , vti ) : i ∈ N, k ∈ N, t ∈ T, t0 ∈ T, (t = t0 + dki + T rdki ∧ i 6= k)}. Chaque arc (vtk0 , vti ) représente un lien entre deux stations différentes i et k à deux moments différents t0 et t ; t = t0 + dki + T rdki assure que les voitures respectent le temps du trajet dki entre les deux stations, ainsi que le temps de recharge T rdki nécessaire après le trajet. 0 - A3 = {(vtk0 , vti ) : i ∈ N, k ∈ N, t ∈ T, t0 ∈ T, d(kt )(i(t−T rdik )) ∈ D}. Chaque arc (vtk0 , vti ) représente une demande de location de voiture à partir de la station k à t0 vers la station i à t − T rdik . – L’ensemble des coûts est C 0 = C1 ∪ C2 ∪ C3 où : - C1 = {ca : a ∈ A1 } ; cet ensemble modélise les coûts d’immobilisation des véhicules dans une station pendant une période de temps. La valeur de chaque ca ∈ C1 a été fixée à 0 ; une valeur plus grande inciterait l’algorithme à déplacer les véhicules par les agents sans réel intérêt (sans augmentation du nombre de clients satisfaits). - C2 = {ca : a ∈ A2 }; cet ensemble modélise les coûts de relocalisation des véhicules entre les stations. La valeur de chaque c(vk0 ,vti ) ∈ C2 a été fixée à t la valeur de distance dki séparant les stations k et i. - C3 = {ca : a ∈ A3 } ; cet ensemble de coûts négatifs permet de rendre attractifs certains liens dans le processus de calcul des plus courts chemins pour satisfaire les clients ; effectivement, plus un parcours de véhicule satisfait des clients, plus son coût décroît grâce aux arcs de coût négatif. Dans un premier temps, la valeur de tous les ca ∈ C3 a été fixée de manière homogène à −100 ; cette valeur permet de faire prévaloir l’importance de satisfaction des clients par rapport aux autres coûts. Dans la deuxième partie de cette section, la méta- heuristique se basera sur des valeurs hétérogènes de l’ensemble C3 générées par l’heuristique gloutonne HG. i – L’ensemble des ressources (parking et lieux de recharge) est R = {rt,t+1 : i i rt,t+1 = Qi , t ∈ T, i ∈ N } ; ici, chaque ressource rt,t+1 représente le nombre de Copyright © by the paper’s authors. Copying permitted for private and academic purposes. Proceedings of the Spatial Analysis and GEOmatics conference, SAGEO 2015. 8 SAGEO’2015 places disponibles dans la station i entre t et t + 1. Nous associons à chaque i ressource rt,t+1 un ensemble d’arcs : Urt,t+1 i = {(vti , vt+1 i ), (vtk0 , vti00 ) : (vti , vt+1 i )∈ A1 , (vtk0 , vti00 ) ∈ A2 ∪A3 , (t ≤ t00 )∧(t00 −T rdki ≤ t)}, qui utilisent cette ressource. Le principe de la méthode proposée consiste à chercher à chaque itération le meilleur chemin de véhicule qui peut être ajouté à la solution partielle sans violer les contraintes de capacités des stations. Après le calcul d’un tel chemin, on calcule un graphe résiduel en supprimant les ressources utilisées par le véhi- cule. Plus précisément, pour chaque véhicule, nous calculons le meilleur chemin P athj à partir du nœud source vs vers le nœud destination vd , en utilisant l’al- gorithme de Dijkstra. Une fois le chemin P athj calculé, nous mettons à jour l’ensemble A3 par la suppression des arcs représentant les demandes des utili- sateurs desservis par la voiture j. Si P athj traverse un arc appartenant à l’en- i semble Urt,t+1 i , une unité de ressource est soustraite à partir de rt,t+1 . Une fois i Rt,t+1 égal à zéro, nous supprimons l’ensemble des arcs Urt,t+1 i . L’heuristique est décrite dans l’Algorithme 1. Dans cet algorithme, la fonction routeAgents prend comme entrée les opérations de relocalisation des voitures et calcule le nombre d’agents nécessaire pour les effectuer. Les trajets des agents durant la journée de service sont tracés de manière itérative en utilisant l’algorithme de plus court chemin de Dijkstra. 3.2. Meta-heuristique Les algorithmes génétiques (Fonseca, Fleming, 1993) représentent une mé- thode d’optimisation intelligente qui exploite des solutions générées aléatoire- ment dans l’espace de recherche et utilise des informations historiques sur les solutions générées pour diriger la recherche dans l’espace des solutions possibles. Une adaptation adéquate de l’algorithme génétique est proposée. Le fonction- nement général est introduit dans l’Algorithme 2 et ses différentes étapes sont détaillées dans le reste de cette section. Voici les principales étapes de la méta-heuristique développée : – Modélisation du chromosome (solution) : toute instance d’un problème traité est associé à un ensemble fini de solutions réalisables, dont chacune peut être caractérisée par une modélisation sous forme de chromosome, ce qui per- met la distinction entre les différentes solutions. Dans l’algorithme génétique proposé, nous construisons toutes les solutions utilisant l’algorithme HG. Pour obtenir les différentes solutions, nous associons à chaque solution s l’ensemble des coûts négatifs C3S généré aléatoirement entre 0 et −100, au lieu de l’en- semble de valeurs homogènes C3 présenté dans la section précédente. En effet, l’ensemble de valeurs hétérogènes C3S permet de donner un ordre d’importance entre les différentes demandes des clients, ce qui donne des solutions différentes selon les ordres générés. Une modélisation sous forme de chromosomes de la solution s est une représentation vectorielle de l’ensemble C3S . Copyright © by the paper’s authors. Copying permitted for private and academic purposes. Proceedings of the Spatial Analysis and GEOmatics conference, SAGEO 2015. Optimisation d’un service d’autopartage 9 Algorithme 1 : Algorithme de l’heuristique gloutonne Data : G(V, A, C, R, U ) ; /* Le graphique spatio-temporel modélisant le problème */ Result : P athsCars , Relocation, Satisf iedDemands, P athsAgents 1 initialization; 2 P athsCars ← ∅ /* l’ensemble de chemins qui constituent les trajectoires des voitures */ ; 3 Satisf iedDemands ← ∅ /* l’ensemble de demandes satisfaites*/ ; Relocation ← ∅ /*l’ensemble de relocalisation des voitures */ ; 4 P athsAgents ← ∅ /* l’ensemble de chemins qui constituent les trajectoires des agents */ ; 5 j ←1 ; 6 costP athj ← 0 ; 7 while (j ≤ nbV eh ) ∧ (costP athj ≤ 0) do 8 pathj ← Dijkstra(G(V, A, C, R)) ; 9 costP athj ← Cost(pathj ) ; 10 forall (vtk0 , vti ) ∈ path do 11 if (vtk0 , vti ) ∈ A3 then 12 A3 ← (vtk0 , vti ) ; 13 Satisf iedDemands ← Satisf iedDemands ∪ (vtk0 , vti ) ; 14 forall Uri00 00 do t ,t +1 15 if (vtk0 , vti ) ∈ Uri00 00 then t ,t +1 16 rti00 ,t00 +1 ← rti00 ,t00 +1 − 1 ; 17 if rti00 ,t00 +1 = 0 then 18 A ← A \ Uri00 00 ; t ,t +1 19 if (vtk0 , vti ) ∈ A2 then 20 /* (vtk0 , vti ) est un arc de relocalisation */ Relocation ← Relocation ∪ (vtk0 , vti )j ; 21 P athsCars ← P athsCars ∪ pathj ; 22 j ←j+1 ; 23 P athsAgents ← routeAgents(Relocation); – Fonction fitness : cette fonction d’évaluation permet la sélection ou le rejet d’un individu, pour ne garder que les individus ayant les plus bas coûts dans la population actuelle. Cette méthode garantit que les individus formant l’élite de la population seront conservés, tandis que les individus mal adaptés seront éliminés de la population. Pour calculer la valeur fitness d’une solution, nous utilisons la fonction objectif C définie dans la section 2. Copyright © by the paper’s authors. Copying permitted for private and academic purposes. Proceedings of the Spatial Analysis and GEOmatics conference, SAGEO 2015. 10 SAGEO’2015 Algorithme 2 : Algorithme génétique Générer des solutions aléatoires pour la population initiale : – créer des ensembles de coûts négatifs différents (voir 3.2-Modélisation S du chromosome) : C3S0 , C3S1 , C3S2 , ..., C3 tailleP opulation (taillePpopulation= 50 individus) – construire les solutions initiales avec HG Évaluer la population initiale (fonction fitness) REPEAT – sélectionner les parents de la population précédente – croisement des parents pour créer une nouvelle génération (taux=70%) – effectuer la mutation sur la nouvelle population (taux de 1%) – construire les solutions de la nouvelle population avec HG – évaluer la nouvelle population (fonction fitness) JUSQU’À un critère d’arrêt (temps limite = 30 min) – Sélection : elle consiste à choisir des solutions parents pour la reproduction de la population. Dans cette procédure, les meilleures solutions sont favorisées en utilisant une sélection stochastique par roulette. Dans ce schéma de sélection, la probabilité de sélectionner un individu est proportionnelle à la valeur de sa fonction fitness. – Opérateurs de croisement et de mutation : la création d’un nouvel indi- vidu (fils) est le produit du croisement de deux chromosomes parents via un processus d’échange de parties de chromosomes choisies aléatoirement entre les deux parents. Ce processus permet une intensification dans l’espace de re- cherche grâce à l’échange d’informations entre les chromosomes (individus). Pour assurer une large diversification de la population, on utilise un opérateur de mutation simple qui consiste à modifier aléatoirement la valeur d’une section du chromosome. Les taux de croisement et de mutation ont été fixés respecti- vement à 70 % et 1 % par rapport à la taille de la population, fixée elle à 50 individus. 4. Simulation d’autopartage : instances pour le site de Nice (Auto Bleue) L’autopartage de la métropole de Nice (AVEM, 2015) permet de louer des véhicules en libre service à Nice et dans ses environs proches. Tous les véhicules sont électriques et disposent donc d’une autonomie limitée et nécessitent des re- chargements fréquents. 64 stations sont actuellement localisées sur ce territoire par le service Auto Bleue, accessible à 4000 clients inscrits. Copyright © by the paper’s authors. Copying permitted for private and academic purposes. Proceedings of the Spatial Analysis and GEOmatics conference, SAGEO 2015. Optimisation d’un service d’autopartage 11 Figure 2. Données géographiques utilisées pour la création des instances Il nous est actuellement impossible de disposer des informations clients sur le service Auto Bleue. De ce fait, et également afin d’étalonner et d’évaluer la méthode proposée, nous avons généré des instances aléatoires pour simuler les flux origines-destinations (Figure 2). Pour ce faire, nous avons tout d’abord créé une partition à partir de polygones de Voronoï, où chaque station possède une aire de chalandise bornée par celles de ses voisines. Un autre intérêt est l’obtention d’une partition spatiale où ne persiste aucun trou, ni aucune su- perposition d’aires de chalandise contiguës. Considérant ensuite deux distances d’accès aux stations à pied (300 et 500 mètres), nous avons réalisé des zones tampons à vol d’oiseau autour des stations, qui nous donnent une estimation suffisante des distances relatives, même si l’usage de distances sur le réseau aurait été plus précis dans ce contexte. Avec cette approche, nous simulons seulement un accès de proximité du service, faisant abstraction d’un éventuel usage de modes intermodaux (véhicule personnel, bus, etc.) pour rejoindre les stations. L’intersection des zones tampons avec les polygones de Voronoï nous fournit une zone de chalandise théorique par station. Chacune de ces aires est alors croisée avec les données de population issues du carroyage de l’INSEE (côté de 200 m). Finalement, par une requête spatiale à chaque station, nous calculons la somme des populations incluses dans l’aire de chalandise. Cette Copyright © by the paper’s authors. Copying permitted for private and academic purposes. Proceedings of the Spatial Analysis and GEOmatics conference, SAGEO 2015. 12 SAGEO’2015 valeur permet d’estimer une probabilité de départ et d’arrivée de véhicules d’autopartage pour une station donnée et sert de base à la création des ins- tances simulées. 5. Résultats Les simulations ont été effectuées sur un PC Intel Core équipé d’un CPU de 3.3GHz et 8GBytes de RAM. Les algorithmes ont été implémentés en Java. 5.1. Comparaison des différentes méthodes en fonction de la montée en charge Pour comparer nos solutions avec les solutions optimales, nous avons utilisé le solveur CPLEX 12.2 qui se base sur une Programation Linéaire en Nombres Entiers (PLNE) du problème. Comme la capacité de résolution du solveur se restreint à de petites instances, nous avons effectué les comparaisons sur des instances générées aléatoirement avec moins de 20 stations. En effet, nous avons pu constater que l’obtention d’une solution exacte est impossible pour des instances de plus de 30 stations simulées et 60 clients, ou 20 stations et 150 clients. Dans la Table 2 des résultats, on constate que l’heuristique gloutonne HG permet de trouver des solutions avec un gap (écart) maximal d’environ 20 % par rapport à la solution optimale et que l’algorithme génétique permet de réduire encore cet écart. 5.2. Apport de la relocalisation des véhicules sur le site de Nice Nous avons également utilisé l’algorithme génétique pour la relocalisation des véhicules et nous l’avons comparé sur les mêmes instances à un service d’autopartage sans relocalisation sur le site de Nice (64 stations). La Figure 3 compare les performances des deux types de service sur des demandes de clients générées selon l’hypothèse fixée dans la section précédente. On commence avec une demande faible (50 clients) et on augmente la demande jusqu’à la satu- ration du service (700 clients). Chaque résultat est représenté dans la figure sous forme de l’intervalle de confiance autour de la moyenne au risque de 5% avec un échantillon de 10 simulations pour une instance avec la même quantité de demandes. On constate que les résultats sont dans leur ensemble discrimi- nants. 3(a) montre l’amélioration du pourcentage de satisfaction des clients avec la relocalisation des véhicules. 3(b) montre une diminution du nombre de voitures utilisées quand la demande est faible et leur augmentation quand le service est proche de la saturation, car la relocalisation permet une plus grande exploitation de la capacité des stations. 3(c) montre une nette augmentation de la fréquence d’utilisation de chaque véhicule en cas de relocalisation. 3(d) fournit le nombre d’agents nécessaire pour effectuer les relocalisations dans les différentes instances ; ce nombre s’amortit lors de la montée en charge. Copyright © by the paper’s authors. Copying permitted for private and academic purposes. Proceedings of the Spatial Analysis and GEOmatics conference, SAGEO 2015. Optimisation d’un service d’autopartage 13 Table 2. Résultats des simulations (NbS = nombre de stations, NbD = nombre de demandes, HG = Heuristique Gloutonne, AG = Algorithme Génétique) Instances Comparaison des algorithmes Coût Nb clients Nb de Nb d’ Gap Temps NbS NbD Algo total non voitures agents par rapport de C satisfaits utilisées utilisés à l’optimal calcul CPLEX 4140 0 19 3 0% 6.1h 30 HG 4250 0 19 4 2.17% 0.1s AG 4140 0 19 3 0% 22s CPLEX 7840 3 22 4 0% 6.3h 5 40 HG 9430 5 20 3 20% 0.1 s AG 7950 3 22 5 1.4% 30s CPLEX 16570 11 25 5 0% 6.7h 60 HG 16770 11 25 7 1.2% 0.1s AG 16720 11 25 6 1.026% 36s CPLEX 5750 0 27 3 0% +10h 40 HG 6550 1 26 3 13.91% 0.3s AG 5760 0 27 3 0.001% 2.6m CPLEX 10350 2 35 12 0% +10h 10 60 HG 12810 5 34 9 21,6% 0.3s AG 11340 3 35 12 9.5% 2.7m CPLEX 27110 16 50 9 0% +10h 100 HG 30430 19 50 12 12.2% 0.4s AG 30170 19 47 15 11.2% 3.7m CPLEX 8330 0 38 11 0% +10h 60 HG 9230 0 39 13 10.8% 1.1s AG 9230 0 39 13 10.8% 10.8m CPLEX 14900 1 65 8 0% +10h 20 100 HG 18420 4 63 17 23.6% 1.2s AG 16240 1 65 12 8.9% 11.5m CPLEX 17310 0 72 26 0% +10h 150 HG 20340 3 69 32 17.5% 1.2s AG 19820 1 74 30 14.5% 12.5m CPLEX Out of memory 30 60 HG 8790 0 37 13 - 2s AG 8660 0 37 12 - 27 min 6. Conclusion et perspectives Un algorithme génétique basé sur une heuristique gloutonne efficace est pro- posé pour optimiser une journée de service d’autopartage de voitures électriques dans un seul sens. Notre objectif est de maximiser le nombre d’utilisateurs et de réduire au minimum le coût logistique (nombre d’agents, nombre de voitures). La pondération de chacun de ces critères est modifiable dans la fonction d’ob- jectif et permet ainsi d’explorer potentiellement plusieurs types de solutions. Dans notre approche, nous traçons le chemin de chaque véhicule à l’aide d’un graphe spatio-temporel qui permet de modéliser toute une journée de service. À titre de comparaison, nous utilisons un solveur exact qui ne résout que de petites instances. Les résultats des simulations confirment que notre heuris- tique permet d’obtenir une solution proche de l’optimale dans des temps de calcul tout à fait raisonnables et parfaitement compatibles avec des systèmes d’autopartage de villes moyennnes comme Nice. Cette méthode nous permet Copyright © by the paper’s authors. Copying permitted for private and academic purposes. Proceedings of the Spatial Analysis and GEOmatics conference, SAGEO 2015. 14 SAGEO’2015 100 200 sans relocalisation sans relocalisation pourcentage de clients satisfaits avec relocalisation avec relocalisation nombre de voitures utilisées 150 80 100 60 50 40 100 200 300 400 500 600 700 100 200 300 400 500 600 700 nombre de demandes des clients nombre de demandes des clients (a) Pourcentage de clients satisfaits (b) Nombre de voitures utilisées nombre de clients / nombre de voitures 3 15 sans relocalisation sans relocalisation avec relocalisation avec relocalisation nombre d’agents sollicités 2.5 10 2 5 1.5 0 1 100 200 300 400 500 600 700 100 200 300 400 500 600 700 nombre de demandes des clients nombre de demandes des clients (c) Taux d’utilisation d’une voiture (d) Nombre d’agents sollicités Figure 3. Comparaison d’autopartages avec relocalisation et sans relocalisation des véhicules sur le site de Nice ; les valeurs sont représentées avec leur intervalle de confiance au risque α de 5% également de valider l’apport de la relocalisation des voitures sur le service d’auto partage à Nice. En termes de perspectives, un raffinement de la fonction d’objectif pour l’obtention d’un coût uniformisé, une approche multi-critère permettant de viser l’un ou l’autre des objectifs ou de rechercher des compromis, ainsi que des simulations sur des instances de taille supérieure (jusqu’à 100 demandes ou plus) afin de tester la résistance à la montée en charge des algorithmes développés, constituent des pistes intéressantes de recherche. Par ailleurs, une montée en charge jusqu’à 700 clients journaliers constitue un plafond maximal (actuellement, Auto Bleue compte environ 4000 abonnés avec une flotte de 200 voitures réparties sur une soixantaine de stations). Toutefois, la méthode proposée possède une capacité importante de scalabilité qui est actuellement testée dans un travail complémentaire. Copyright © by the paper’s authors. Copying permitted for private and academic purposes. Proceedings of the Spatial Analysis and GEOmatics conference, SAGEO 2015. Optimisation d’un service d’autopartage 15 Bibliographie AVEM. (2015). La voiture électrique en libre-service et en autopartage. Consulté sur http://www.avem.fr/index.php?page=libre_service_ve&cat=appli_det&id=1 Boyaci B., Geroliminis N., Zografos K. (2013). An optimization framework for the de- velopment of efficient one-way car-sharing systems. 13th Swiss Transport Research Conference, vol. 240, p. 718–733. Correia G., Homem De Almeida G., Antunes A. P. (2012). Optimization approach to depot location and trip selection in one-way carsharing systems. Transportation Research Part E: Logistics and Transportation Review, vol. 48, no 1, p. 233–247. Fonseca M. C., Fleming J. P. (1993, July). Genetic algorithms for multiobjective optimization: formulation, discussion and generalization. in Genetic Algorithms: Proceeding of the Fifth International Conferencen, San Mateo, CA: Morgan Kauf- mann. George D. K., Xia C. H. (2011). Fleet-sizing and service availability for a vehicle rental system via closed queueing networks. European Journal of Operational Research, vol. 211, no 1, p. 198–207. Consulté sur http://dx.doi.org/10.1016/ j.ejor.2010.12.015 Ion L., Cucu T., Boussier J., Teng F., Breuil D. (2009). Site selection for electric cars of a car-sharing service. World Electric Vehicle Journal, vol. 3, no 1, p. 1–10. Jorge D., Correia G. (2013). Carsharing systems demand estimation and defined operations: A literature review. European Journal of Transport and Infrastructure Research, vol. 13, no 3, p. 201–220. Jorge D., Correia G., Barnhart C. (2012). Testing the Validity of the MIP Approach for Locating Carsharing Stations in One-way Systems. Procedia - Social and Behavioral Sciences, vol. 54, p. 138–148. Consulté sur http://dx.doi.org/10.1016/ j.sbspro.2012.09.733 Jorge D., Correia G., Barnhart C. (2014). With Simulated Relocation Policies in One- Way Carsharing Systems. Transactions on Intelligent Transportation Systems, vol. 15, no 4, p. 1667–1675. Kek A. G. H., Cheu R. L., Meng Q., Fung C. H. (2009). A decision support system for vehicle relocation operations in carsharing systems. Transportation Research Part E: Logistics and Transportation Review, vol. 45, no 1, p. 149–158. Consulté sur http://dx.doi.org/10.1016/j.tre.2008.02.008 Louvet N., Godillon S. (2013). Enquête nationale sur l’autopartage. 6t bureau de recherche. Schuijbroek J., Hampshire R., Hoeve W.-J. van. (2013). Inventory Rebalancing and Vehicle Routing in Bike Sharing Systems. , no 1491. Consulté sur http:// repository.cmu.edu/tepper/1491 Copyright © by the paper’s authors. Copying permitted for private and academic purposes. Proceedings of the Spatial Analysis and GEOmatics conference, SAGEO 2015.