Présentation générale

Pendant les derniers jeux olympiques et paralympiques l'accessibilité du métro a été critiquée. Pour remédier à cela, nous vous demandons de sélectionner un ensemble de stations de métro à aménager en priorité afin de pouvoir accéder à tous les sites olympiques. L'objectif est de minimiser le nombre de stations à aménager afin de pouvoir répondre rapidement au besoin.

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

Dans un premier temps on vous propose le problème suivant: Trouvez le plus petit ensemble de stations à aménager qui permettent que tous les sites olympiques soient à au plus x minutes de marche d'une station de métro accessible. (x étant un paramètre)

On vous suggère dans un second temps d'autres problèmes en bonus: trouvez les stations à aménager de sorte que dans le nouveau réseau comprenant les stations accessibles le chemin le plus court entre deux sites olympiques comprenne au plus x minutes de marche. (en tenant compte des changements de lignes)

Vous pourrez également proposer vos propres variantes du problèmes en justifiant pourquoi elles sont pertinentes.

Vous présenterez vos résultats de manière graphique afin de faciliter la compréhension de ce que vous proposez.

Données

Pour réaliser ce projet, vous aurez besoin de la localisation des sites olympiques et des stations de métro qui sont disponibles en opendata.

Vous aurez aussi besoin du graphes du réseau routier/pétitionner de Paris, vous pouvez utiliser par exemple osmnx si vous choisissez de faire votre projet en python ou n'importe quel autre bibliothèque utilisant openstreetmap.

Premier rendu - 10/10

  1. Implémentez une réduction vers Ensemble Dominant (Dominating Set) ou une variante ;
  2. Implémentez un algorithme bruteforce pour résoudre le problème.

Pensez à commencer un rapport pour les prochains rendus.

Algorithme Branch-and-Bound pour ED

ensemble_dominant(graphe G, dominant partiel S, entier k)
    si k = 0 :
        tester si S est un dominant 
    sinon :
        u <- sommet de degré min parmi les sommets non dominés par S
        pour tout v dans N[u] :
            ensemble_dominant(G, S U {v}, k-1)

Second rendu 14/11

Pour ce rendu un petit rapport vous est demandé (txt ou pdf selon votre choix).

  1. Implémentez un algorithme de type Branch-and-Bound.
  2. Implémentez l'algo progressif.

Pour chaque algo vous réaliserez des tests sur différentes instances afin de déterminer leur performances.

Rendu final et soutenance

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

Ce rendu reprend tous les points des précédents rendu, dans le rapport vous penserez bien à préciser les détails de vos implémentations, votre méthode de travail et d'évaluation des algorithmes (tests et benchmarks), vos optimisations des algorithmes demandés et les limites de votre projet.

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 23/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.