Le parlement européen a récemment adopté une nouvelle règle sur le placement de stations de recharge pour voitures électriques sur les autoroutes. D’ici 2026, toutes les autoroutes devront être équipées d’au moins une station de recharge tous les 60km.
Pour répondre à ce besoin, il faudra être capable de donner la localisation des stations de recharges à installer de sorte que pour tout plus court chemin d’au moins 60km sur autoroute, il y ait au moins une station de recharge accessible. L’objectif est alors de minimiser le nombre de stations installées.
Le projet se déroulera en plusieurs étapes :
Concernant l’organisation :
Le problème consiste donc à placer un minimum de stations sur les autoroutes. Ces stations devront être placées de sorte à satisfaire des contraintes. Tout chemin de plus de 60km devra être couvert par une station. Les stations de recharge ne peuvent être placées qu’aux endroits où l’infrastructure le permet, sur les aires de repos et stations existantes.
L’entrée sera donc le réseau autoroutier, les aires de repos et le nombre de km maximal. En sortie, la liste des aires de repos sera retournée.
Vous fournirez une visualisation des résultats comprenant les autoroutes et les stations équipées.
Pour résoudre ce problème, on vous suggère d’utiliser les données d’openstreetmap. Vous pouvez les récupérer au format json en écrivant des requêtes sur overpass-turbo.eu.
La requête suivante permet de récupérer les autoroutes en France :
[out:json];
area[name = "France"];
(way(area)["highway"~"^(motorway|trunk)$"];>;);
out;
Les highway=services
et highway=rest_area
correspondent aux stations services et aires de repos existantes. Vous vous référerez au wiki d’openstreetmap afin de récupérer les autres informations nécessaires.
Vous créerez des instances de différentes tailles pour pouvoir également tester les algorithmes les plus lents.
Vous construirez de manière automatique à partir de ces données les instances du problème.
Ce rendu est facultatif (mais conseillé).
Ce qui est attendu par priorité :
Un petit rapport sera fourni pour expliquer votre avancement et vos difficultés.
Ensemble Dominant Annoté:
À partir du point 3 du premier rendu, codez une réduction (polynomiale) du problème vers Ensemble Dominant ou Ensemble Dominant Annoté. (Que concluez vous de la complexité du problème ?)
Pour les algorithmes d’Ensemble Dominant, vous permettrez l’appel de ceux-ci sur des graphes au format texte. (.dot par exemple)
exemple d’appel:
./mon_programme.py -SAT -g mon_graphe_à_20_sommets.dot -k 10
Vous fournirez un rapport détaillant le travail réalisé et les difficultés rencontrées. Le rapport étudiera la complexité aussi bien théorique que pratique (mesure du temps d’exécution) des algorithmes implémentés.
Le rendu final devra être envoyé au plus tard le 12/01.
Vous fournirez un rapport reprenant les points suivants:
Vous décrirez de manière précise comment exécuter votre projet sur les machines du CREMI avec des exemples. Le projet sera principalement évalué sur le rapport, tout ce qui n’est pas expliqué dans le rapport ne sera pas considéré
La soutenance aura lieu le 16/01 au CREMI (A28 salle 203). Celles-ci dureront 20 à 25 minutes.
Voici les horaires de passage pour chaque groupe :
Nous vous demandons d’entrer discrètement dans la salle 10 minutes avant votre horaire et de vous installer sur un ordinateur afin d’éviter toute perte de temps. Vous devrez présenter rapidement ce que vous avez fait, puis nous vous poserons des questions à propos de votre projet. Vous pouvez utiliser des slides, mais ce n’est pas obligatoire.