A Fast Electric Vehicle Path-Planner Using Clustering
lundi, 26 août 2019·
,,
Jaël Champagne Gareau
Éric Beaudry
Vladimir Makarenkov
Résumé
Over the past few years, several studies have considered the problem of
Electric Vehicle Path Planning with intermediate recharge (EVPP-R) that
consists of finding the shortest path between two given points by traveling
through one or many charging stations, without exceeding the vehicle’s range.
Unfortunately, the exact solution to this problem has a high computational
cost. Therefore, speedup techniques are generally necessary (e.g., contraction
hierarchies). In this paper, we propose and evaluate a new fast and intuitive
graph clustering technique, which is applied on a real map with charging
station data. We show that by grouping nearby stations, we can reduce the
number of stations considered by a factor of 13 and increase the speed of
computation by a factor of 35, while having a very limited trade-off increase,
of less than 1%, on the average journey duration time.
Type
Publication
Proceedings of the International Federation of Classification Societies Conference
Auteurs
Chercheur postdoctoral en informatique
Je suis actuellement chercheur postdoctoral en informatique à l’Université
TÉLUQ, où mes travaux portent sur l’accélération de la conversion de nombres
entiers et flottants en chaînes de caractères décimales. Au cours de mon
doctorat, j’ai conçu des algorithmes et des structures de données exploitant
l’architecture moderne des ordinateurs afin de résoudre de grandes instances
de processus décisionnels de Markov (MDP). Durant ma maîtrise, j’ai développé
des algorithmes de planification d’itinéraires pour véhicules électriques,
visant à déterminer le chemin optimal entre deux points tout en minimisant
le temps total du trajet (déplacement, recharge et attente aux bornes).
Auteurs
Auteurs