Projet d’Algorithmique Appliquée M2 (2023-2024)

english version

Présentation générale

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 :

  1. modélisation du problème ;
  2. implémentations des algorithmes (force brute, etc…) ;
  3. ajout d’extensions.

Concernant l’organisation :

Problème

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.

Donné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 autoroutes en France sur openstreetmap

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.

Premier rendu pour le 15/10

Ce rendu est facultatif (mais conseillé).

Ce qui est attendu par priorité :

  1. Simplification du graphe ;
  2. Utiliser sur le graphe une implémentation de Floyd-Warshall ou implémenter votre version modifiée de l’algorithme qui s’arrête pour les chemins déjà couverts ;
  3. Pour chaque chemin le plus court, lister les stations qui le couvrent.

Un petit rapport sera fourni pour expliquer votre avancement et vos difficultés.

Réduction vers Ensemble Dominant

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 ?)

Second rendu pour le 29/10

  1. Tous les points du premier rendu;
  2. Réduction du problème de couverture des autoroutes vers Ensemble Dominant (ED)
  3. Implémentez un vérificateur pour ED ;
  4. Implémentez une solution pour ED type brute-force et/ou une réduction vers SAT et/ou PLNE.
  5. Bonus: d’autres algorithmes, ex: approximation, glouton, etc… (selon vos envies)

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.

Rendu final et soutenance

Le rendu final devra être envoyé au plus tard le 12/01.

Vous fournirez un rapport reprenant les points suivants:

  1. Tous les points des précédents rendus;
  2. l’algorithme progressif;
  3. les autres algorithmes que vous aurez implémentés.

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.