odd_nodes = [
    node for node in G1.nodes
    if G1.degree(node) % 2 == 1
]

for (u, v), dist in sorted_pairs:
    if u not in used and v not in used:
        matching.add((u, v))
        used.add(u)
        used.add(v)

euler_circuit = list(nx.eulerian_circuit(G_aug))
S6 - 2025 3 semaines 5 étudiants

ERO1

Prototype d'aide à la décision pour préparer le survol de Montréal par des drones et comparer des plans de déneigement à partir du réseau routier réel.

Python NetworkX OSMnx NumPy Scikit-learn Recherche tabou

Le projet en quelques mots

ERO1 applique la recherche opérationnelle à un cas concret : organiser une reconnaissance aérienne, puis répartir les rues à déneiger en tenant compte des distances, du temps et du coût des véhicules.

Le rendu comporte deux études complémentaires. La première prépare des circuits de drones couvrant le réseau routier de Montréal. La seconde construit et compare des tournées de déneigeuses sur cinq arrondissements : Outremont, Verdun, Anjou, Rivière-des-Prairies–Pointe-aux-Trembles et Le Plateau-Mont-Royal.

De la carte aux scénarios

Le réseau routier est chargé depuis OpenStreetMap avec OSMnx, puis représenté sous forme de graphe. Les deux études réutilisent cette base pour produire des parcours et des indicateurs destinés à comparer plusieurs configurations.

Données routières

OpenStreetMap et graphes

Reconnaissance

Zones et circuits de drones

Déneigement

Tournées, temps et coûts

Étude du survol par drones

Le programme découpe le graphe de Montréal en zones géographiques avec K-means. Lorsqu'une zone n'est pas connexe, il recherche des liaisons pour réunir ses composantes avant de calculer un circuit de couverture.

Partition du réseau

Le nombre de zones correspond au nombre de drones étudié. Le code contient des scénarios allant d'un à quarante-cinq drones et permet de filtrer les propositions par coût ou durée de mission.

Circuit de couverture

Pour chaque zone, les sommets de degré impair sont appariés par une méthode gloutonne. Le graphe augmenté est ensuite parcouru avec un circuit eulérien afin de couvrir toutes ses rues.

Résultats produits

Le programme génère des cartes intermédiaires, le circuit obtenu, les distances par drone et un fichier récapitulatif des scénarios.

Étude des tournées de déneigeuses

Dans ce second volet, une rue est considérée comme une unité de travail. Le programme calcule les plus courts chemins entre les extrémités des rues et conserve ces distances en cache pour éviter de répéter les calculs les plus coûteux.

  • Solution initiale : les rues sont réparties entre les véhicules avant le départ et le retour à un même point de référence.
  • Recherche tabou : des échanges de rues entre les tournées créent des solutions voisines ; une liste tabou évite de revenir immédiatement sur des configurations déjà explorées.
  • Comparaison : plusieurs nombres de véhicules et les deux types définis dans le sujet sont évalués selon leur distance, leur durée et leur coût journalier.
  • Exécution parallèle : plusieurs recherches sont lancées avec le module multiprocessing, puis leurs résultats sont regroupés pour retenir une configuration.

Choix et limites du modèle

Les méthodes employées sont des heuristiques : elles cherchent rapidement une solution exploitable, mais ne garantissent pas l'optimum global. Pour le drone, le partitionnement géographique peut produire des zones déséquilibrées et l'appariement glouton reste approximatif. Les liaisons ajoutées utilisent aussi des distances directes sans modéliser les contraintes réelles de vol.

Pour le déneigement, chaque exécution compare des flottes homogènes d'un seul type de véhicule. Le rapport final identifie donc la gestion d'une flotte hétérogène comme une amélioration à apporter au prototype.

Synthèse du projet

Un travail collectif

Le rendu est signé par une équipe de cinq étudiants. La répartition détaillée des tâches n'étant pas documentée, je présente les études du drone et des déneigeuses comme un travail collectif, sans m'attribuer un module particulier.

Ce que le projet m'a apporté

Ce projet m'a permis de relier un problème concret à une modélisation en graphe, puis de comparer des scénarios plutôt que de chercher une réponse unique. Il m'a également familiarisé avec les compromis entre qualité d'une solution, temps de calcul et limites d'un modèle.