Lavoie, Marc-André
(2022).
« Planification coopérative en temps réel d'itinéraires d'une flotte de véhicules électriques partageant des bornes de recharge » Mémoire.
Montréal (Québec), Université du Québec à Montréal, Maîtrise en informatique.
Fichier(s) associé(s) à ce document :
Résumé
Ce mémoire aborde le problème de planification coopérative d’itinéraires pour une flotte de véhicules électriques (VÉ) utilisant un réseau de bornes de recharge. Les réseaux de bornes actuels n’ont généralement pas de système de réservation de bornes. Dans les outils d’aide la planification d’itinéraire de VÉ, chaque VÉ est planifié de façon indépendante. Au mieux, le temps d’attente espéré, basé sur l’historique d’utilisation des bornes, peut être intégré. Planifier chaque VÉ de façon indépendante peut être qualifié de planification non coopérative puisque chaque VÉ utilise les bornes permettant le meilleur itinéraire. Lorsque plusieurs VÉ coexistent, cela peut mener à une utilisation non optimale des bornes. Par exemple, deux VÉ partant en même temps d’une même origine vers une même destination voudront utiliser les mêmes bornes en même temps. Dans ce mémoire, nous proposons des algorithmes de planification coopérative d’itinéraire de VÉ. Ces algorithmes ont pour objectif d’optimiser l’usage global des bornes. Une propriété de ces solutions est que certains VÉ peuvent emprunter des itinéraires légèrement plus coûteux en temps. Par exemple, des VÉ peuvent faire de petits détours pour éviter les conflits ou la surutilisation de certaines bornes. Les travaux réalisés s’inspirent de travaux réalisés en planification coopérative de chemins pour des groupes d’agents dans des jeux vidéo. Les planificateurs coopératifs les plus simples exécutent un planificateur individuel pour chaque VÉ mais dans des ordres différents. Chaque ordre d’exécution peut générer un plan global différent. Une modification de cette approche est de calculer successivement les plans par morceau : le planificateur coopératif simple trouve meilleur plan dans un intervalle de temps compris entre 0 et T (T étant l’horizon temporel). Ensuite, le meilleur plan dans l’intervalle T à 2T est calculé et ainsi de suite jusqu’à ce que tous les VÉ soient à destination. Cet algorithme élargit l’espace de plan exploré tout en rendant le planificateur utilisable en temps réel. Finalement, des méthodes originales avec réparation locale de solutions existantes sont proposées. Ces derniers éliminent les pires attentes aux bornes de recharge (en tenant compte des détours) en explorant récursivement des solutions voisines. Les algorithmes ont été évalués sur des scénarios artificiels générés avec des données réelles comme la carte routière du Québec extraite d’OpenStreetMap et du réseau de bornes du Circuit électrique.
| Type: |
Mémoire accepté
|
| Informations complémentaires: |
Fichier numérique reçu et enrichi en format PDF/A. |
|
Directeur de thèse: |
Beaudry, Éric |
| Mots-clés ou Sujets: |
Planification automatique / Itinéraires / Véhicules électriques / Bornes de recharge |
| Unité d'appartenance: |
Faculté des sciences > Département d'informatique |
| Déposé par: |
Service des bibliothèques
|
| Date de dépôt: |
30 août 2023 08:10 |
| Dernière modification: |
30 août 2023 08:10 |
| Adresse URL : |
http://archipel.uqam.ca/id/eprint/16829 |
RECHERCHER
PARCOURIR
LIBRE ACCÈS
