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 staion 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 chose suivante : des navettes électriques pouvant chacune transporter 300 vélos d’une station à l’autre. On peut mettre une navette en place entre 2 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, vous pouvez utiliser les données de Open Data Paris. La table dont vous avez besoin est 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.

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 fourni 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)
        
    OUPUT : 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 mondre aussi les scripts suivants qui permettent de faire un affichage graphique avec mathplotlib. (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()

A 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 foncion navette et remplissage définie 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 wikiedia.

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

# YOUR CODE HERE
raise NotImplementedError()
# YOUR CODE HERE
raise NotImplementedError()
# YOUR CODE HERE
raise NotImplementedError()
# YOUR CODE HERE
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
    """
    # à compléter
    # YOUR CODE HERE
    raise NotImplementedError()
# par exemple...
navette(F, "David Weill - Parc Montsouris-14124", "Jourdan - Cité Universitaire-14135") # pour mes calculs 300 vélos
# vérifons 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érifons 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
    # YOUR CODE HERE
    raise NotImplementedError()
# par exemple...
remplissage(F, "Jourdan - Stade Charléty-14014") # pour mes calculs 48
# vérifons 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érifons 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 affiche la réponse en se basant sur vos calculs.

# YOUR CODE HERE
raise NotImplementedError()

Combien de navettes avez-vous utilisé ?

# YOUR CODE HERE
raise NotImplementedError()

Combien de stations n’ont-elles reçu aucun vélos ?

# YOUR CODE HERE
raise NotImplementedError()

Un peu de dessin ?

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

# YOUR CODE HERE
raise NotImplementedError()