|
Édition du: 15/02/2026 |
|
INDEX |
GRAPHES |
||
|
Minimiser la voirie (Steiner) |
|||
Faites
un double-clic pour un retour en haut de
page
|
Réseaux et Chemins
On connaît les jeux comme relier trois maisons sans
croisement ou traverser les ponts de
Königsberg. Mais derrière ces défis ludiques se cachent de vrais problèmes
mathématiques, utiles pour organiser les tournées d’un facteur ou construire
des réseaux entre villes. Comment parcourir toutes les rues sans gaspiller de
temps ? Comment relier des lieux avec le moins de câbles possible ?
Ces questions sont au cœur du travail des ingénieurs et des urbanistes. Cette page vous propose de découvrir ces problèmes, de les comprendre
et de les classer pour mieux les résoudre. |
||
|
|
Sommaire de cette page >>> Optimisation de
réseaux et de chemins >>> Deux grands
types de problèmes >>>
Comparaison entre ARP et VRP >>>
Variantes de types de livraisons >>> Classification
des problèmes de réseaux et de tournées |
Débutants Glossaire |
Anglais: Network and
Path Optimization Problems / Network and Routing Optimization Problems
|
Problème Les problèmes d’optimisation de réseaux et de
chemins cherchent à organiser au mieux des liaisons entre points ou à planifier
des déplacements pour réduire un coût, gagner du temps ou économiser des
ressources. Variété de problèmes Imaginez une ville où il faut poser des câbles
pour relier des écoles, des hôpitaux et des bureaux : il s’agit de choisir
quels tronçons creuser pour que tous les lieux soient connectés en dépensant
le moins possible. Parfois on peut ajouter des points
intermédiaires pour raccourcir les liaisons, comme poser un petit relais
entre deux quartiers, et c’est alors un problème de type arbre de Steiner. Le
cas se pose notamment pour une disposition de points en grille ou en sommets
de polygones réguliers. Dans d’autres situations, l’enjeu n’est pas de
construire mais de parcourir : un facteur doit passer sur certaines rues pour
distribuer le courrier, il faut alors planifier une tournée qui couvre toutes
les rues nécessaires en minimisant la distance parcourue, ce qui relève des
problèmes de postier. Parfois encore, on veut visiter une liste
d’adresses une seule fois et revenir au point de départ, comme pour une
tournée commerciale, et l’on cherche l’ordre de visite le plus court
possible. Solution de ces problèmes Chaque situation impose des contraintes
différentes : capacité d’un véhicule, fenêtres horaires, sens de circulation,
ou coût d’installation d’un équipement. Les méthodes pour résoudre ces problèmes vont de
recettes simples et rapides qui donnent une bonne solution en peu de temps à
des techniques plus lourdes qui garantissent l’optimalité mais demandent
beaucoup de calculs. Dans la pratique, on combine souvent une solution
rapide pour démarrer et des améliorations locales pour l’affiner. |
Quelques exemples
Fameux problème des trois maisons
Relier chaque maison aux
trois réseaux sans croisements |
|
|
ARP – Arc Routing
Problems Problèmes d’acheminement sur arcs Problèmes de tournées sur arêtes Problèmes de routage d’arcs |
VRP – Vehicle
Routing Problems Problèmes de tournées de véhicules |
|
|
Couvrir tous les chemins |
Desservir toutes les villes |
|
|
|
|
|
|
Les problèmes d’acheminement sur arcs (arc
routing) s’intéressent à la couverture de segments du réseau, comme des rues ou
des routes, sans que la visite de sommets particuliers soit un objectif en
soi. Par
exemple, dans un problème de déneigement urbain, l’objectif est de parcourir
toutes les rues à traiter, quel que soit l’ordre dans lequel les carrefours
sont traversés. |
À l’inverse, les problèmes de tournées de
véhicules (vehicle routing) mettent l’accent sur la desserte de sommets
spécifiques, généralement associés à des clients. Dans un contexte de livraison, il s’agit de
déterminer des tournées permettant de visiter chaque client tout en
respectant des contraintes de capacité ou de temps. |
|
|
Bien que ces deux familles de problèmes
poursuivent un objectif commun d’optimisation des parcours, elles se
distinguent fondamentalement par ce qui doit être couvert sur le graphe
représentatif :
|
||
|
Critères |
ARP – Arc Routing Problems |
VRP – Vehicle Routing Problems |
|
|
Objet
principal |
Arêtes (segments, rues, arcs). |
Sommets (clients, points de demande). |
|
|
Question |
Où faut-il passer ? |
Qui faut-il visiter ? |
|
|
But |
Couvrir un ensemble d’arêtes requises. |
Desservir un ensemble de sommets. |
|
|
Difficultés |
Atteindre les bonnes arêtes, peu importe les
sommets intermédiaires. |
Organiser les visites des points de demande sous
contraintes logistiques. |
|
|
Structure
du graphe |
Graphe avec arêtes requises ou non. |
Graphe complet ou métrique entre sommets. |
|
|
Type de
couverture |
Couverture exhaustive ou partielle des arêtes. |
Visite de tous les sommets (au moins une fois). |
|
|
Répétition
autorisée |
Sommets et arêtes peuvent être répétés. |
Sommets généralement visités une seule fois. |
|
|
Nature des
tournées |
Souvent une ou plusieurs tournées fermées. |
Plusieurs tournées, souvent depuis un dépôt. |
|
|
Contraintes
typiques |
Sens des arcs, coûts asymétriques, connexité. |
Capacités, fenêtres de temps, flotte. |
|
|
Complexité |
Polynomial pour certains cas, NP-difficile en général. |
NP-difficile dès les variantes de base |
|
|
Applications
typiques |
Tournée du postier; Déneigement, balayage de routes. |
Livraison et collecte de marchandises. |
|
Variantes de types de livraisons
|
VRP — Vehicle
Routing Problem |
Problème
de tournées de véhicules. Il s’agit de planifier les trajets d’une flotte de
véhicules pour desservir un ensemble de clients tout en minimisant le coût
(distance, temps, etc.). |
|
CVRP — Capacitated
Vehicle Routing Problem |
Problème
de tournées de véhicules avec capacité. Chaque véhicule a une limite de
chargement, et les clients ont des demandes spécifiques. L’objectif est de
respecter ces contraintes tout en optimisant les trajets. |
|
VRPTW — Vehicle
Routing Problem with Time Windows |
Problème
de tournées de véhicules avec fenêtres temporelles. Chaque client doit être
servi dans un créneau horaire donné, ce qui ajoute une contrainte de
planification à la tournée. |
Voir Énigme du chameau et des
bananes
Taxonomie des réseaux et des chemins
|
Genèse
du tableau de classement présenté ci-dessous Dans
les ouvrages de référence (Ahuja–Magnanti–Orlin, Gutin–Punnen, Mitchell,
etc.), les problèmes d’optimisation de réseaux se répartissent en 5 à 7
grandes familles, selon les auteurs. J'ai choisis de décrire les sept familles. |
|
|
Tout problème d’optimisation de
réseau peut être
classé selon :
|
Les problèmes modernes (réseaux
sans fil, réseaux distribués, graphes géométriques, réseaux sociaux) se
rangent dans ces sept familles:
|
|
Ci-dessous:
|
|
|
Exemples - Optimisation de réseaux
et de chemins |
|||
|
Nom du problème |
Définition simple |
Exemple concret |
|
|
Postier chinois |
Trouver un trajet qui passe au moins
une fois par toutes les rues. |
Un facteur doit parcourir toutes
les rues d’un quartier pour distribuer le courrier. |
|
|
Postier rural |
Parcourir seulement certaines rues
obligatoires, pas toutes. |
Une équipe doit inspecter uniquement
les rues endommagées après une tempête. |
|
|
Tournées de véhicules (VRP) |
Organiser les tournées de plusieurs
véhicules pour desservir des clients. |
Trois camions doivent livrer tous
les magasins d’une ville sans dépasser leur capacité. |
|
|
Tournées de véhicules avec contrainte |
Même chose, mais chaque client doit
être visité dans un créneau horaire. |
Le camion doit livrer un supermarché entre
8h et 10h, pas avant ni après. |
|
|
Voyageur de commerce (TSP) |
Trouver un tour unique
visitant chaque ville une seule fois. |
Un commercial doit visiter toutes
ses agences et revenir au point de départ. |
|
|
Voyageur de commerce à récompenses |
On peut sauter certaines
villes, mais cela coûte une pénalité. |
Un livreur peut ignorer des clients peu
importants pour gagner du temps. |
|
|
Arbre couvrant minimal MST |
Relier toutes les villes avec le
moins de routes possibles. |
Construire un réseau électrique le
moins cher reliant tous les villages. |
|
|
Plus court chemin |
Trouver le chemin le plus rapide
entre deux points. |
Aller de chez soi à l’aéroport en minimisant
le temps de trajet. |
|
|
Minimisation du diamètre |
Construire un réseau où le trajet
le plus long entre deux villes est le plus court possible. |
Concevoir un réseau informatique où un
message met le minimum de temps pour circuler. |
|
|
Arbre à diamètre borné |
Relier toutes les villes en
garantissant que personne n’est trop loin des autres. |
Un réseau d’urgence où toutes les
stations doivent être accessibles en ≤ 3 sauts. |
|
|
Réseaux épars (Spanners) |
Garder seulement quelques routes,
tout en conservant des trajets presque aussi courts qu’avant. |
Réduire le nombre de câbles dans un
réseau sans trop rallonger les distances. |
|
|
Steiner à minimisation de longueur |
Relier des villes en ajoutant des points
intermédiaires pour réduire la longueur totale. |
Ajouter des “jonctions” pour
construire un réseau de fibre plus court et moins cher. |
|
|
Steiner à diamètre borné |
Ajouter des points intermédiaires
pour réduire le pire trajet, pas la longueur totale. |
Placer un hub central pour que
toutes les villes soient à 2 sauts maximum. |
|
|
Problèmes de visibilité / géométriques |
Construire des segments ou réseaux
qui couvrent ou bloquent une région. |
Placer des capteurs pour que toute
la zone soit surveillée. |
|
|
Présentation de la taxonomie
complète des problèmes de réseaux et de chemins Ce chapitre présente une classification unifiée
des principaux problèmes d’optimisation combinatoire liés à la conception de
réseaux, à la couverture et aux tournées. Ces problèmes apparaissent dans de
nombreux domaines tels que la recherche opérationnelle, l’informatique
théorique, la géométrie algorithmique, les télécommunications et la
logistique. On distingue deux classes de problèmes: Classe 1
: Problèmes de tournées et d’acheminement Ce groupe regroupe les problèmes où l’on doit
parcourir des lieux ou des segments selon un itinéraire optimisé. Il inclut :
Classe 2
: Problèmes de conception et de connectivité Ce groupe concerne les problèmes où l’on cherche
à relier des points ou concevoir un réseau, souvent sans parcours dynamique.
Il inclut :
|
|
|
Nomenclature Problèmes
d’acheminement sur arcs (ARP) Les problèmes
d’acheminement sur arcs (Arc Routing Problems – ARP) consistent
à déterminer un ou plusieurs parcours couvrant un sous-ensemble d’arêtes,
tout en minimisant le coût total. Ces modèles apparaissent dans l’inspection de
routes, le déneigement, le balayage urbain ou la maintenance des
infrastructures. Problèmes
du postier Problème du postier chinois (Chinese
Postman Problem) : trouver une tournée couvrant toutes les arêtes d’un
graphe au moins une fois. Problème du postier rural (Rural
Postman Problem) : couvrir uniquement certaines arêtes requises,
généralement non connexes. Problèmes du postier venteux et mixte (Windy
/ Mixed Postman Problems) : intégrer des coûts asymétriques ou des
graphes combinant arêtes orientées et non orientées. Problèmes
de tournées de véhicules (VRP) Le problème
de tournées de véhicules (Vehicle Routing Problem – VRP) vise à
planifier les tournées d’une flotte de véhicules pour desservir un ensemble
de clients sous diverses contraintes. Ils modélisent la logistique, la distribution, la
collecte, le transport sanitaire ou industriel. Parmi les principales variantes figurent : le VRP capacitaire (Capacitated VRP), le VRP avec fenêtres de temps (VRP with
Time Windows), et de nombreuses extensions intégrant des
contraintes opérationnelles spécifiques. Problèmes
de tournée de sommets (TSP) Les problèmes de tournée de sommets visent à
déterminer un parcours optimisé permettant de visiter un ensemble de sommets,
généralement sans répétition.
Le problème
du voyageur de commerce (Traveling Salesman Problem – TSP)
consiste à trouver le cycle de coût minimal passant exactement une fois par
chaque sommet. >>>
Certaines variantes relâchent ou modifient les
contraintes classiques : TSP à récompenses (Prize-collecting
TSP), autorisant l’exclusion de sommets moyennant pénalité. Variantes avec sommets de Steiner (Steiner
TSP variants), permettant l’ajout de sommets auxiliaires ou
l’enrichissement du graphe. Problèmes
de recouvrement et d’arborescence Ces problèmes cherchent à relier ou atteindre des
sommets dans un graphe sans autoriser l’ajout de sommets auxiliaires.
Le problème
de l’arbre couvrant de poids minimal (Minimum Spanning Tree – MST)
consiste à relier tous les sommets d’un graphe pondéré en minimisant le coût
total des arêtes.
Le problème
du plus court chemin (Shortest Path Problem) vise à déterminer
un chemin de coût minimal entre deux sommets, ou entre une source et
l’ensemble des autres sommets du graphe. Il constitue un problème fondamental
de la théorie des graphes. Problèmes
de Steiner et conception de réseaux Les problèmes de Steiner visent à construire un
réseau de coût minimal reliant un ensemble de sommets dits terminaux.
Contrairement aux arbres couvrants classiques, ils autorisent l’ajout de
sommets auxiliaires, appelés sommets (ou points) de Steiner, afin de
réduire le coût global.
Le problème
de l’arbre de Steiner dans les graphes (Steiner Tree in Graphs)
consiste à relier un sous-ensemble de sommets terminaux dans un graphe
pondéré, en autorisant l’ajout de sommets intermédiaires, de manière à
minimiser la somme des poids des arêtes. >>>
Le problème
de l’arbre de Steiner euclidien (Euclidean Steiner Tree)
considère des points dans le plan euclidien. Les points de Steiner peuvent
être placés librement dans le plan afin de minimiser la longueur totale du
réseau.
Le problème
de l’arbre de Steiner rectiligne (Rectilinear Steiner Tree)
impose que les connexions suivent uniquement des segments horizontaux et
verticaux (métrique L1). Il est particulièrement utilisé en conception de
circuits intégrés (VLSI).
Plusieurs extensions intègrent des contraintes ou
objectifs supplémentaires : Arbre de Steiner à récompenses (Prize-collecting
Steiner Tree), où certains terminaux peuvent être ignorés moyennant une
pénalité. Forêt de Steiner (Steiner
Forest), qui vise à relier plusieurs groupes de terminaux indépendamment. Arbre de Steiner avec contraintes de sauts ou de
diamètre (Hop-constrained / Bounded-diameter Steiner Tree), limitant la
longueur des chemins. Arbre de Steiner orienté ou capacitaire (Directed
/ Capacitated Steiner Tree), intégrant des contraintes de direction ou de
flux. Problèmes
de conception structurelle des réseaux (diamètre, sauts, spanners, réseaux épars) Cette famille optimise
non pas un parcours, mais la
structure même du réseau.
Construire un réseau connexe
minimisant la plus grande distance entre deux sommets.
Bounded-Diameter
Spanning Tree Hop-Constrained
Spanning Tree Ces modèles limitent la
longueur maximale des trajets ou le nombre de relais. >>>
Construire un
sous-graphe approchant les distances du graphe complet tout en utilisant peu
d’arêtes. Exemples : t‑spanners, Yao
graphs, Theta graphs. Applications : réseaux
sans fil, géométrie algorithmique, graphes distribués.
Contrairement aux
Steiner classiques (minimisation de longueur), ces variantes optimisent : le diamètre, le nombre de sauts, ou le stretch. Exemples : Bounded-Diameter
Steiner Tree, Hop-Constrained
Steiner Tree, Low-Stretch
Steiner Networks. Cette famille inclut
notamment les réseaux “étoile” optimaux pour les polygones réguliers lorsque
l’on autorise des points de Steiner. Problèmes
géométriques connexes et de visibilité Ces problèmes étendent les notions de couverture,
de connectivité et de tournée à des contextes géométriques continus ou à des
contraintes physiques.
Les ensembles
opaques (Opaque Sets) et les problèmes de type Kakeya consistent à construire un ensemble de
segments ou de courbes intersectant toute droite traversant une région
donnée, afin d’en bloquer la visibilité.
Les problèmes
de conception de réseaux géométriques (Geometric Network Design)
visent à construire des réseaux efficaces minimisant le nombre de liens ou le
facteur d’allongement des chemins, comme dans les réseaux épars géométriques (geometric spanners) ou les *chemins
à nombre minimal de segments.
Ces modèles sont centraux dans la conception de
réseaux de télécommunications, de circuits VLSI et plus généralement dans
l’optimisation de réseaux physiques soumis à des contraintes géométriques et
technologiques. |
|
|
Retour |
|
|
Suite |
|
|
Voir |
|
|
Sites |
|
|
Cette page |
