Le défi des vélos#

Le problème à résoudre#

Vous avez été embauché comme consultant chez Schmurfvengo qui vient d’obtenir de façon inespérée la gestion des vélibs à Paris. Le problème est le suivant : pour cause de soucis techniques, il faut régulièrement remplacer l’ensemble de la flotte (30 000 vélos) en une nuit.

Pour cela, vous disposez de plusieurs gros camions qui peuvent déposer chacun 2000 vélos dans un ensemble de stations en périphérie de la ville. Il y a 1396 stations en fonctionnement dans la capitale. Il faut donc ensuite distribuer les vélos aux autres stations. On cherche une solution.

La société propose de mettre en place la stratégie suivante : des navettes électriques pouvant chacune transporter 300 vélos d’une station à l’autre. On peut mettre une navette en place entre deux stations \(v_1\) et \(v_2\) : si elles sont éloignées de 500m à vol d’oiseau ou moins, ou si \(v_2\) est la station la plus proche de \(v_1\) (cela permet de relier au réseau les stations « isolées » qui sont à plus de 500m de toutes les autres stations).

Cette solution est-elle viable :

  • Pourra-t-on livrer tous les vélos ?

  • De combien de navettes aurons-nous besoin ?

  • Toutes les stations recevront-elles des vélos ?

Les données#

Pour résoudre ce problème, nous avons pris les données de Open Data Paris et plus spécifiquement de la table Stations Velibs : emplacement des stations. Le fichier json est disponible dans ce dossier, les données sont directement interprétables en Python de cette façon.

(les tests ont été effectué sur les données json proposées, qui datent d’un export de 2021)

import json
data = json.load(open("media/velib-emplacement-des-stations.json"))

La variable data est une liste dont chaque élément est un dictionnaire python contenant les informations d’une station vélib.

len(data)

Voilà par exemple, le premier élément de la liste, la station Bois de Vincennes - Gare

data[0]

Voici l’ensemble des stations périphériques où les camions pourront livrer à chacune 2000 vélos.

entry_points = {"David Weill - Parc Montsouris", "Vanne - Saussaies", "Bruneseau - Quai d'Ivry", "Gare RER - Canadiens", "Porte de Vincennes", "Champeaux - Gallieni", "Romainville - Vaillant-Couturier", "Frères Flavien - Porte des Lilas", "Grands Moulins de Pantin", "Emile Reynaud - Porte de la Villette", "Wilson - Landy", "Fragonard - Porte de Clichy", "Gare d'Asnières sur Seine", "Reims - Porte d'Asnières", "Porte Maillot - Pereire", "Charles de Gaulle - Madrid", "Porte de la Muette", "Transvaal - Charles de Gaulle", "Rond-Point Rhin et Danube", "Murat - Porte de Saint-Cloud", "Porte de Vanves", "Porte d'Orléans", "Bois de Vincennes - Gare"}

Remarque : ici on a identifié les stations par leurs noms. MAIS ! Il existe des stations qui portent le même nom. De façon générale, on utilisera donc un identifiant comportant à la fois le nom et l’id de la station (pour que cela reste lisible et unique). La fonction suivante pourra être utile.

def name(d):
    return d['fields']['name'] + "-" + str(d['fields']["stationcode"])

Exemple :

name(data[0])

On vous fournit aussi la fonction suivante qui permet de calculer la distance en mètres entre deux points données sous forme (latitude, longitude).

import math
def toRad(angle):
    """
    Converti un angle donné en degré en un angle donné en radian.
    
    INPUT:
        
        - angle, un angle en degré
        
    OUTPUT : la valeur en radian
    """
    return angle*2*math.pi/360

def distance(p1, p2):
    """
    Renvoie la distance en mètres entre les points `p1` et `p2` données en coordonnées géographique
    
    INPUT:
    
        - p1, un tuple (latitude, longitude)
        - p2, un tuple (latitude, longitude)
        
    OUTPUT : la distance à vol d'oiseau en mètres entre p1 et p2
    """
    lat1, lon1 = p1
    lat2, lon2 = p2
    R = 6371e3
    phi1 = toRad(lat1)
    phi2 = toRad(lat2)
    dphi = toRad(lat2 - lat1)
    dlam = toRad(lon2 - lon1)

    a = math.sin(dphi/2)**2 + math.cos(phi1)*math.cos(phi2)*math.sin(dlam/2)**2
    c = 2*math.atan2(math.sqrt(a), math.sqrt(1-a))
    return R*c

Par exemple, la distance entre la première station de la liste Bois de Vincennes - Gare et la seconde, Morillons - Dantzig est environ de 12.5km.

distance(data[0]["fields"]["coordonnees_geo"],data[1]["fields"]["coordonnees_geo"]) 

On vous montre aussi les scripts suivants qui permettent de faire un affichage graphique avec matplotlib. (Le premier affiche des points et le second des lignes)

import matplotlib.pyplot as plt

x = [d["fields"]["coordonnees_geo"][1] for d in data]
y = [d["fields"]["coordonnees_geo"][0] for d in data]


plt.scatter(x,y,s=5)

plt.title('Les stations velibs dans Paris')
plt.xlabel('longitude')
plt.ylabel('latitude')
plt.savefig('StationsVelib.png')
plt.show()
import matplotlib.pyplot as plt


station_names = set(name(d) for d in data)
station_dict = {name(d):d for d in data}
station = station_names.pop()

while len(station_names) > 0:
    next_station = min(station_names, key = lambda n: distance(station_dict[n]["fields"]["coordonnees_geo"], station_dict[station]["fields"]["coordonnees_geo"]))
    station_names.remove(next_station)
    plt.plot([station_dict[station]["fields"]["coordonnees_geo"][1], station_dict[next_station]["fields"]["coordonnees_geo"][1]], [station_dict[station]["fields"]["coordonnees_geo"][0], station_dict[next_station]["fields"]["coordonnees_geo"][0]], 'k-', lw=1)
    station = next_station

plt.title('Un chemin reliant toutes les stations')
plt.xlabel('longitude')
plt.ylabel('latitude')
plt.savefig('CheminsStations.png')
plt.show()

À vous de jouer !#

Vous avez maintenant tous les éléments pour résoudre le problème. Petit résumé.

Le but : acheminer le maximum de vélos sur les 30000.

Les contraintes :

  • respecter la capacité de chaque station (pas plus de 80% de remplissage)

  • respecter les contraintes de l’énoncé sur les camions de départ et les navettes.

Le résultat : votre résultat doit être facilement utilisable. En particulier vous devez implanter les fonctions navette et remplissage définies en bas de la fiche et donner les lignes de codes affichant les réponses aux questions.

Un peu de dessin ? Donnez une illustration de votre résultat en utilisant matplotlib.

Comment faire ? Aidez-vous des fiches précédentes, discutez avec votre groupe, posez des questions, lisez wikipedia.

Remarque : Le calcul final prend du temps ! (quelques minutes environ)

# VOTRE CODE ICI
raise NotImplementedError()
# VOTRE CODE ICI
raise NotImplementedError()
# VOTRE CODE ICI
raise NotImplementedError()
def navette(flot, station1, station2):
    """
    S'il existe une navette entre `station1` et `station2`, renvoie le nombre de vélos qui seront transportés par cette navette durant la nuit. Sinon, renvoie 0.
    
    INPUT:
    
        - flot, l'objet contenant le résultat de vos calculs
        - station1, le nom-id d'une station Velib
        - station2, le nom-id d'une seconde station Vélib
    """
    # VOTRE CODE ICI
    raise NotImplementedError()
# par exemple...
navette(F, "David Weill - Parc Montsouris-14124", "Jourdan - Cité Universitaire-14135") # pour mes calculs 300 vélos
# vérifions qu'on ne dépasse pas la capacité des navettes
assert all( navette(F, name(d1), name(d2)) <= 300 for d1 in data for d2 in data)
# vérifions qu'on n'a pas de navettes entre une station et elle-même
assert all( navette(F, name(d), name(d)) == 0 for d in data)
def remplissage(flot, station):
    """
    Renvoie le nombre de vélos qu'on aura installé à `station` à la fin de la nuit.
    
    INPUT :
    
        - flot, l'objet contenant le résultat de vos calculs
        - station, le nom d'une station velib
    """
    # à compléter
    # VOTRE CODE ICI
    raise NotImplementedError()
# par exemple...
remplissage(F, "Jourdan - Stade Charléty-14014") # pour mes calculs 48
# vérifions qu'on ne dépasse pas la capacité des stations
assert all( remplissage(F, name(d)) <= 0.8 * d["fields"]["capacity"] for d in data)
# vérifions qu'on ne distribue pas des "demi-vélos"
assert all( remplissage(F, name(d)) == int(remplissage(F, name(d))) for d in data)

Combien de vélos avez-vous livré ?

Répondez par une ligne de code qui affecte la réponse à la variable vélos_livrés en se basant sur vos calculs.

# VOTRE CODE ICI
raise NotImplementedError()
vélos_livrés
import hashlib
assert hashlib.md5(bytes(vélos_livrés)).hexdigest() == 'd5390b9819d739049c5e8dbc3e2f14c2'

Combien de navettes avez-vous utilisées ?

# VOTRE CODE ICI
raise NotImplementedError()

Combien de stations n’ont reçu aucun vélo ?

# VOTRE CODE ICI
raise NotImplementedError()

Un peu de dessin ?#

On voudrait se faire une idée du réseau de navettes, pouvez-vous le représenter graphiquement ?

# VOTRE CODE ICI
raise NotImplementedError()