Chapitre 2 Réseaux et graphes : vocabulaire et exemples
2.2 Sommets, arcs et arêtes : les atomes des graphes et des réseaux 55 .... Une
modélisation linéaire du problème de transport classique ? La méthode des ...
part of the document
Méthodes de planification en transport
Avant-propos 1
1 Le monde du transport 8
1.1 Des outils qui révolutionnent le monde du transport 9
La palettisation ( La conteneurisation ( Le GPS et ses prédécesseurs ( Le routage des navires
1.2 Quelques anecdotes de lhistoire des transports 16
Le transport automobile ( Le transport militaire ( Le transport périurbain ( Les transports et les luttes syndicales ( Importance stratégique des équipements publics de transport
1.3 Les modes conventionnels de transport 20
Le camion ( Le transport aérien ( Øresund ( Arabie Saoudite ( Guinée ( Chili
1.4 Modes non conventionnels de transport 30
Rôle des pipelines ( Évacuations urgentes ( Acheminement du courriel ( Réseaux de communication ( Modes de transport chez les insectes, les oiseaux, les poissons
.
1.5 Le transport au Québec 35
Les voies du passé et du présent ( Le camionnage au Québec ( Des problèmes à résoudre dans lindustrie du camionnage ( La recherche en transport au Québec ( Le Centre de recherche sur les transports ( Le Groupe détudes et de recherche en analyse des décisions ( Giro ( Technologies Ad Opt Inc. ( INRO
1.6 Lapproche pédagogique de ce manuel - la famille Simard 41
La méthode pédagogique retenue ( La famille Simard ( Antoine de Saint-Exupéry ( La notion de réseau ( Caractères communs des réseaux ( Lordinateur et les problèmes de transport ( Lentreprise de transport innovatrice ( Les graphes
1.7 Exercices 49
2 Réseaux et graphes : vocabulaire et exemples 52
2.1 Les précurseurs 52
2.2 Sommets, arcs et arêtes : les atomes des graphes et des réseaux 55
Graphes orientés ( Graphes et réseaux orientés : un exemple ( Graphes et réseaux non orientés : un exemple ( Arcs ou arêtes ? ( Graphes mixtes ( Boucle
2.3 Les graphes orientés 67
La notion de graphe orienté ( Notations mathématiques et définitions de base ( Prédécesseurs, successeurs et degrés ( Chemins ( Accessibilité ( Composantes connexes et forte connexité ( Calcul des composantes connexes dun graphe ( Algorithme de calcul des composantes connexes ( Exemple : Circulation de linformation dans une firme ( Graphe des composantes connexes dun graphe
2.4 Les graphes non orientés 83
Incidence et degrés ( Chaînes et composantes connexes ( Accessibilité ( Composantes connexes et connexité
2.5 Compléments 88
Représentation dun graphe économe de lespace en mémoire ( Graphe biparti ( Graphe planaire
2.6 Exercices 91
3 Arbres 101
3.1 Une propriété de base des réseaux non orientés : la connexité 101
La famille Simard : design dun réseau connexe de coût minimal ( Définitions dun arbre
3.2 Un algorithme efficace pour trouver un arbre générateur de poids minimal 105
3.3 Larbre générateur de poids maximal 108
3.4 Arbre de poids minimal dans un réseau cartésien 110
3.5 Compléments 112
La logique gourmande ( Validité de lalgorithme de Kruskal ( Validité de lalgorithme pour déterminer un itinéraire permettant une charge maximale ( Modèle linéaire pour larbre de poids minimal
3.6 Exercices 121
4 Le calcul du chemin le plus court dans un réseau 139
4.1 Le CLPC, une donnée essentielle dans le monde du transport 139
4.2 Un algorithme efficace pour le calcul des CLPC : la méthode de Dijkstra 150
Historique du calcul des CLPC ( Présentation de la méthode de Dijkstra ( Deux propriétés des CLPC ( Commentaires concernant le calcul des CLPC
4.3 Méthode de Dijkstra pour un réseau non orienté 162
4.4 Compléments 165
Un modèle mathématique pour le calcul dun CLPC ( Certificat doptimalité pour les longueurs des CLPC ( Méthode de correction détiquettes pour le calcul des CLPC
4.5 Exercices 175
5 Le flot maximal 190
5.1 Le rééquilibrage des palettes 191
5.2 Terminologie et définition du problème de flot maximal 193
Classification des sommets ( Le problème de flot maximal
5.3 Chemin daugmentation du flot 195
5.4 Chaîne daugmentation 201
5.5 La notion de coupe dans un réseau 208
5.6 La pose détiquettes pour le calcul du flot maximal 215
5.7 Compléments 219
Le réseau résiduel et la pose détiquettes pour le calcul du flot maximal ( Modèle mathématique pour le problème de flot maximal ( Preuve de léquation (5.3) ( Preuves des théorèmes 5.2 et 5.3 ( Commentaires sur les théorèmes 5.1 et 5.4
5.8 Exercices 225
6 Le problème de flot à coût minimal 238
6.1 Définition du problème 238
6.2 Le calcul dune solution admissible initiale 241
6.3 Classification des arcs dans une solution admissible 243
6.4 Solution admissible de base 250
6.5 Calcul du coût marginal dun arc hors base et construction de la solution de base no 1 251
6.6 Description de lalgorithme du simplexe réseau 258
6.7 Algorithme du simplexe réseau : résolution de lexemple de base 262
Initialisation (Itération 0) ( Itération 1 ( Itération 2 ( Itération 3
6.8 Exemples dapplications de PFCM 268
Le transport à charges partielles ( La localisation des entrepôts ( Les PFCM et le transport aérien
6.9 Compléments 274
Un modèle linéaire dun PFCM ( Présentation dun problème multisource et multipuits comme un PFCM ( Présentation dun problème avec bornes inférieures comme un PFCM ( Solutions de base dégénérées ( Itérations dégénérées
6.10 Exercices 287
7 Le problème de transport classique 303
7.1 Définition du problème 303
7.2 Rééquilibrage des palettes entre divers terminus 305
7.3 Calcul dune 1re solution admissible : la méthode du coin nord-ouest 306
Une 2e heuristique de calcul dune solution initiale : la méthode des coûts minimaux 310
Vérification de loptimalité dune solution 312
Lalgorithme du transport 321
Compléments 324
Une modélisation linéaire du problème de transport classique ( La méthode des pénalités ( Le phénomène de la dégénérescence ( PTC non équilibré : cas où la somme des disponibilités est plus élevée ( PTC non équilibré : cas où la somme des demandes est plus élevée
7.8 Exercices 339
8 Le problème daffectation 353
8.1 Quelques exemples dapplication dans le monde du transport 353
Appariements dallers et de retours ( Laffectation de conducteurs à des cueillettes ( Affectation de conducteurs à des voyages ( Affectation déquipes à des réparations durgence ( Interdire ou forcer des affectations
8.2 La nécessité dun algorithme efficient 366
8.3 Le principe de base de lalgorithme 368
8.4 La notion de zéros indépendants 369
8.5 Un algorithme pour résoudre les problèmes daffectation : la méthode hongroise 371
8.6 Un exemple de problème non équilibré avec un objectif de maximisation 377
8.7 Compléments 380
Le modèle linéaire pour le problème daffectation ( Le principe des réductions-rangées ( Déterminer le nombre maximal de zéros indépendants
8.8 Exercices 386
9 Le problème du postier chinois 397
9.1 La tournée dun camelot 398
La leçon de Jacques : préliminaires
9.2 La suite de la leçon de Jacques : un appariement optimal des sommets impairs 405
9.3 La séquence de visite des arêtes dun multigraphe eulérien 411
9.4 Le problème du postier chinois orienté 414
9.5 Compléments 419
Pourquoi un multigraphe non orienté contient-il toujours un nombre pair de sommets impairs? ( Les chaînes de GA dune tournée optimale ne possèdent aucune arête en commun ( Un modèle linéaire du PCNO ( Le problème du postier chinois mixte
9.6 Exercices 430
10 Le problème du voyageur de commerce 442
10.1 Typologie, historique et applications 442
Définition et exemple euclidien ( Un exemple de PVC non euclidien ( Un exemple de PVC dans un réseau orienté ( Réseau hamiltonien ( Bref historique du PVC ( Complexité du PVC ( Applications et typologie
10.2 Heuristiques pour un PVC symétrique : principes généraux 455
Mesures de performance dune heuristique ( Une typologie des heuristiques pour le PVC ( La méthode du sommet le plus proche (SLPP)
10.3 Heuristiques pour un PVC symétrique : construction dune tournée hamiltonienne initiale 459
Pénalités dinsertion et notion de proximité dun sommet à une tournée partielle ( La notion de distance dun sommet non visité à une tournée partielle ( Les méthodes dinsertion
10.4 Heuristiques pour un PVC symétrique : amélioration dune tournée hamiltonienne 466
La méthode 2-OPT
10.5 Résoudre un PVC asymétrique 472
10.6 Compléments 477
Absence de croisements dans une tournée optimale dun réseau cartésien ( Le modèle linéaire dun PVC symétrique : un exemple
10.7 Exercices 481
Bibliographie 495
Table des matières 497