Calcul d’itinéraires grâce à la théorie des Graphes

GRAPHES

Groupe A
Calcul d’itinéraires sans et avec contraintes pour la société MonTrajetElectrique.com

Introduction

Chaque litre de gazole consomme l’oxygène de l’air et charge, inexorablement, l’atmosphère en gaz carbonique, oxyde d’azote, particules toxiques… qui accroissent sans cesse l’effet de serre. C’est pourquoi il a fallu, afin de préserver notre belle planète bleue, se tourner vers des véhicules moins polluants tels que les véhicules électriques. Un bon nombre de stations ont donc du répondre à cette nouvelle demande, notamment en permettant la recharge ou l’échange de batteries pour les usagers car, malheureusement, les batteries ont une autonomie limitée et ne permettent que de courts trajets inférieur à 150km.

Ce marché émergent et en nette croissance a permis à des sociétés tel que MonTrajetElectrique.com de proposer des solutions adaptées aux utilisateurs de véhicule électriques afin de répondre à leurs attentes en leur proposant des trajets adaptées à leurs contraintes et, notamment, leur permettant de ne plus jamais tomber en panne de batteries.

Ce projet a pu être mené à bien par une équipe de 4 jeunes étudiants ingénieurs qui ont su répondre au cahier des charges en implémentant des algorithmes optimisés. Algorithmes permettant de calculer les itinéraires les plus courts sans ou avec contraintes telle que la gestion des batteries du véhicule afin d’indiquer une station de ravitaillement. Ils ont aussi pu implémenter un programme pour la représentation graphique des cartes s’appuyant sur les utilitaires graphviz et neato. Ceci pour le plus grand bonheur des clients de MonTrajetElectrique.com !

Ce rapport décrit le fruit de leur travail avec les différentes difficultés auxquelles ils ont pu être confrontés ainsi que la manière dont elles ont été résolues.