Le défi des vélos#
Problème
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.
Attention
Les données fournies ont été téléchargées en 2021. Si vous les mettez à jour, les tests ne seront plus forcément cohérents.
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. Cependant il existe des stations qui portent le même nom. Pour évider les ambiguïtés, on utilisera donc un identifiant unique comportant à la fois le nom et l’id de la station (pour que cela reste lisible et unique). Pour cela, 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és 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)
### BEGIN SOLUTION
from network import Network
def addEdge(d1, d2):
return distance(d1['fields']["coordonnees_geo"], d2['fields']["coordonnees_geo"]) <= 500
def makeNetwork(data, entry_points):
N = Network(nodes = [name(d) for d in data], edges = [])
N.add_node("s1")
N.add_node("s")
N.set_edge_capacity("s", "s1", 30000)
for d1 in data:
isolated = True
closest = None
dmin = None
if d1['fields']['name'] in entry_points:
N.set_edge_capacity("s1", name(d1), 2000)
for d2 in data:
if d1 != d2:
dis = distance(d1['fields']["coordonnees_geo"], d2['fields']["coordonnees_geo"])
if dmin is None or dis < dmin:
closest = d2
dmin = dis
if addEdge(d1,d2):
isolated = False
N.set_edge_capacity(name(d1), name(d2), 300)
if isolated:
N.set_edge_capacity(name(d1), name(closest), 300)
N.add_node("t")
for d in data:
N.set_edge_capacity(name(d), "t", int(0.8 * d['fields']['capacity']))
return N
### END SOLUTION
### BEGIN SOLUTION
N = makeNetwork(data, entry_points)
### END SOLUTION
### BEGIN SOLUTION
from ford_fulkerson import maximal_flow
F = maximal_flow(N, "s", "t")
### END SOLUTION
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
"""
### BEGIN SOLUTION
return flot.flow(station1, station2)
### END SOLUTION
# 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
### BEGIN SOLUTION
return flot.flow(station,"t")
### END SOLUTION
# 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.
### BEGIN SOLUTION
vélos_livrés = F.global_value()
### END SOLUTION
vélos_livrés
import hashlib
assert hashlib.md5(bytes(vélos_livrés)).hexdigest() == 'd5390b9819d739049c5e8dbc3e2f14c2'
Combien de navettes avez-vous utilisées ?
### BEGIN SOLUTION
sum(1 for d1 in data for d2 in data if navette(F,name(d1),name(d2)) > 0)
### END SOLUTION
Combien de stations n’ont reçu aucun vélo ?
### BEGIN SOLUTION
sum(1 for d in data if remplissage(F, name(d)) == 0)
### END SOLUTION
Un peu de dessin ?#
On voudrait se faire une idée du réseau de navettes, pouvez-vous le représenter graphiquement ?
### BEGIN SOLUTION
import matplotlib.pyplot as plt
for d1 in data:
for d2 in data:
if navette(F, name(d1), name(d2)) > 0:
plt.plot([d1["fields"]["coordonnees_geo"][1], d2["fields"]["coordonnees_geo"][1]], [d1["fields"]["coordonnees_geo"][0], d2["fields"]["coordonnees_geo"][0]], 'k-', lw=1, color="red")
#elif N.capacity(name(d1), name(d2)) > 0:
# plt.plot([d1["fields"]["lon"], d2["fields"]["lon"]], [d1["fields"]["lat"], d2["fields"]["lat"]], 'k-', lw=1, color="blue")
plt.title('Les navettes de livraison')
plt.xlabel('longitude')
plt.ylabel('latitude')
plt.savefig('Livraison.png')
plt.show()
### END SOLUTION