Projet : bataille de la Marne

Un exercice de modélisation complexe.

On va optimiser l'arrivée des taxis à la bataille de la marne de 1914.

On a un ensemble $S$ de villes, et des routes reliant certaines villes entre elles (il peut exister plusieurs routes entre deux villes), décrites dans un graphe non orienté $G$.

• chaque ville $i$ est caractérisée par un nombre $p[i]$ de places de parking,
• chaque route $(i, j)$ est caractérisée par le temps $tv[(i, j)]$ qu'il faut pour aller de la ville $i$ à la ville $j$
• chaque route $(i, j)$ a une capacité $ct[(i, j)]$ qui correspond au nombre de véhicules qui peuvent l’emprunter par unité de temps

Au temps $t = 0$, on a un certain nombre de véhicules stationnés dans différentes villes et il faut qu’au temps $t = K$, le plus possible de véhicules soient arrivés à une ville donnée (la Marne).

Il est possible que des véhicules arrivent avant cette date butoir, mais après la date K, c’est trop tard.

Modélisation

On va modéliser ce problème comme un problème de flots. Le problème est :

• qu'une route possède à la fois une capacité et une longueur, qui sont des caractéristiques très différentes
• qu'il faut gérer le temps

On considère le temps comme étant une valeur discrète prenant 0, 1, 2, ..., K comme valeur.

On peut alors représenter chaque ville par $K+1$ sommets représentant chacun la ville à un temps donné. La ville $v$ sera ainsi représentée par les sommets $(v, 0)$, ..., $(v, K)$, le sommet $(v, i)$ représentant la ville au temps $i$.

De là, une route de temps 5 (et de capacité $ct[(v1, v2)]$) de v1 vers v2 va être représentée par :

• un arc de $(v1, 0)$ vers $(v2, 5)$ de capacité $ct[(v1, v2)]$
• un arc de $(v1, 1)$ vers $(v2, 6)$ de capacité $ct[(v1, v2)]$
• ...
• un arc de $(v1, K-5)$ vers $(v2, K)$ de capacité $ct[(v1, v2)]$

Une voiture qui reste dans la ville $v1$ au temps $i$ emprunte un arc de $(v1, i)$ vers $(v1, i+1)$ dont la capacité est le nombre de places de parking $p[v1]$ de la ville v1.

Le sommets spéciaux sont :

• le puits est la Marne au temps K: $(Marne, K)$
• la source est un sommet fictif que l'on relie aux sommets $(v, 0)$ correspondant aux villes où il y a des taxis au temps 0. La capacité de ses arcs est le nombre de taxis disponibles.

Données

On reprend le graphe des villes de plus de 10000 habitants en France métropolitaine, déjà utilisé lors du projet : chemin de poids minimum.

Il nous reste à placer les différents paramètres du problèmes :

• les villes de départ, disons $T = 5$ prisent au hasard TAXI_DÉPART = random.sample(list(france), T) (on utilise lma fonction sample du module random)
• nombre de taxis par villes : une constante valant NOMBRE_TAXI
• la ville de destination, nommé LA_MARNE qu'on a qu'à dire que c'est la ville de Reims
• temps final : $K = 20$
• capacité des routes (nombre de taxis par unité de temps) : dictionnaire ct
• le nombre de places de parking par villes : dictionnaire p
• le temps de parcours de chaque route : dictionnaire tv

Capacité des routes

On va donner une capacité aléatoire de taxi par route. On borne cependant ce nombre par MAX_TAXI_ROUTE, disons égal à 20.

Places de parking

Comme les capacités des routes, on va prendre un entier aléatoire entre 1 et MAX_PARKING.

Temps de parcours des routes

Pour homogénéiser les temps de parcours, on aimerait faire en sorte qu'ils soient compris entre 1 et MAX_DIST (disons 5) et soit dépendant de la distance GPS entre les deux villes.

Nous allons créer cette distance en plusieurs temps

Enfin :

Modèle

Il faut transformer les données du problème en une instance de notre modélisation.

Résolution

Nombre de Taxis à un instant donné

A un instant donné, un taxi peut être dans une ville donnée ou sur la route.

Nombre de taxi en transit sur une route

Représentation graphique

Le code suivant représente la carte de France avec les différentes données du problème représentées :

import matplotlib.pyplot as plt
import matplotlib.lines as mlines


fig, ax = plt.subplots(figsize=(10, 10))

for u in france:
    ax.text(villes[u]["longitude"], villes[u]["latitude"], u)
    for v in france[u]:
        if v > u:  # évite de tracer 2 fois le même arc
            continue

        ax.add_line(
            mlines.Line2D(
                (villes[u]["longitude"], villes[v]["longitude"]),
                (villes[u]["latitude"], villes[v]["latitude"]),
            )
        )

ax.plot(
    [villes[x]["longitude"] for x in france],
    [villes[x]["latitude"] for x in france],
    "o",
    color="black",
    markersize=2,
)
ax.plot(
    [villes[LA_MARNE]["longitude"]],
    [villes[LA_MARNE]["latitude"]],
    "*",
    color="red",
    markersize=20,
)
ax.plot(
    [villes[x]["longitude"] for x in TAXI_DÉPART],
    [villes[x]["latitude"] for x in TAXI_DÉPART],
    "o",
    color="red",
    markersize=10,
)

circle = plt.Circle((x, y), r)
ax.add_patch(circle)