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 situation 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, algorithme génétique, QuantumGIS, Auto Bleue à Nice
Copyright © by the paper’s authors. Copying permitted for private and academic purposes. Proceedings of the Spatial Analysis and GEOmatics conference, SAGEO 2015.
L’autopartage est le partage d’une flotte de voitures entre abonnés.
Derriè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
nationale française
– 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’utilisateur 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
partage de vélos (bike-sharing)
Les décisions concernant le nombre de stations d’autopartage, leur
localisation 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
niveau de décision, nous pouvons citer les modèles de Programmation Linéaire en
Nombres Entiers (PLNE) avec deux niveaux de décision
En ce qui concerne le niveau de décision tactique et opérationnelle,
Dans le domaine de l’optimisation et de l’aide à la décision pour
l’autopartage à un seul sens,
Dans le cadre de notre étude, nous proposons une prise en compte plus réaliste 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 recharge 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.
Pour définir plus formellement la relocalisation et le routage dans l’autopartage 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.
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 est donné par tki. L’ensemble des demandes des clients est D = {d(kt0)(it)} où d(kt0)(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.
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 station 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 approximativement à 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.
Nous minimisons un coût global C obtenu par la somme pondérée de 4 objectifs. 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 fonction 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 focalisons sur une fonction objectif résolument orientée vers la qualité de service, premier critère d’un service public.
A1,v1 (v1,A1) v2,v3
v2,v3 (v3,c2) (v6,c1)
(A1,v3) v4 (v4,c4) (v2,c3) 4 v6
La Figure 1 décrit un schéma logistique simplifié associé à un scénario possible 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. 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.
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).
Nous développons une heuristique spécifique à notre problème, de complexité 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érimentations 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 approché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.
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 noeuds vti où i représente une station et t une période de temps, les noeuds 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, vti+1), (vs, vi1), (vinbT , vd) : i ∈ N, t ∈ T }. Chaque arc (vti, vti+1) 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 , vi) représente un lien entre deux stations différentes i et k)}. Chaque arc (vt0 t 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.
- A3 = {(vtk0 , vti) : i ∈ N, k ∈ N, t ∈ T, t0 ∈ T, d(kt0)(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 C0 = 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(vtk0 ,vti) ∈ C2 a été fixée à 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étaheuristique 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 : rt,t+1 = Qi, t ∈ T, i ∈ N } ; ici, chaque ressource rti,t+1 représente le nombre de i places disponibles dans la station i entre t et t + 1. Nous associons à chaque ressource rti,t+1 un ensemble d’arcs : Urti,t+1 = {(vti, vti+1), (vtk0 , vti00 ) : (vti, vti+1) ∈ 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éhicule. Plus précisément, pour chaque véhicule, nous calculons le meilleur chemin P athj à partir du noeud source vs vers le noeud destination vd, en utilisant l’algorithme 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 utilisateurs desservis par la voiture j. Si P athj traverse un arc appartenant à l’ensemble Urti,t+1 , une unité de ressource est soustraite à partir de rti,t+1. Une fois Rti,t+1 égal à zéro, nous supprimons l’ensemble des arcs Urti,t+1 . 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.
Les algorithmes génétiques
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 permet 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’ensemble 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 . 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 15 16 if (vtk0 , vti) ∈ A2 then /* (vtk0 , vti) est un arc de relocalisation */
Relocation ← Relocation ∪ (vtk0 , vti)j ;
P athsCars ← P athsCars ∪ pathj ; 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. 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 du chromosome) : C3S0 , C3S1 , C3S2 , ..., C3StailleP 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 individu (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 recherche 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 respectivement à 70 % et 1 % par rapport à la taille de la population, fixée elle à 50 individus.
L’autopartage de la métropole de Nice
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 instances simulées.
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.
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.
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 saturation 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 discriminants. 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.
10 20 30 30 40 60 40 60 100 60 100 150 60
HG AG Génétique) Gap par rapport à l’optimal
0% 2.17% 0% 0% 20% 1.4% 0% 1.2% 1.026%
0% 13.91% 0.001%
0% 21,6% 9.5% 0% 12.2% 11.2%
0% 10.8% 10.8%
0% 23.6% 8.9% 0% 17.5% 14.5%
Un algorithme génétique basé sur une heuristique gloutonne efficace est proposé 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’objectif 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 heuristique 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 sans relocalisation avec relocalisation sans relocalisation avec relocalisation 200 s e é s i iltu 150 s e r u t iov 100 e d e r b om 50 n
15 s é t i c llio 10 s s t n e g a ’d 5 e r b m o n
0 100 200 300 400 500 600 700 nombre de demandes des clients 100 200 300 400 500 600 700 nombre de demandes des clients (a) Pourcentage de clients satisfaits (b) Nombre de voitures utilisées sans relocalisation avec relocalisation sans relocalisation avec relocalisation 100 200 300 400 500 600 700 nombre de demandes des clients 100 200 300 400 500 600 700 nombre de demandes des clients (c) Taux d’utilisation d’une voiture (d) Nombre d’agents sollicités é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.