Table des matières 497

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 l'histoire 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 l'industrie 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 L'approche 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 ( L'ordinateur et les problèmes de transport (
L'entreprise 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 d'un graphe ( Algorithme de calcul des
composantes connexes ( Exemple : Circulation de l'information dans
une firme ( Graphe des composantes connexes d'un 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 d'un graphe économe de l'espace 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 d'un réseau connexe de coût minimal (
Définitions d'un arbre
3.2 Un algorithme efficace pour trouver un arbre générateur de
poids minimal 105
3.3 L'arbre 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 l'algorithme de Kruskal (
Validité de l'algorithme pour déterminer un itinéraire permettant une
charge maximale ( Modèle linéaire pour l'arbre 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 d'un CLPC ( Certificat
d'optimalité 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 d'augmentation du flot 195
5.4 Chaîne d'augmentation 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 d'une 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 d'un arc hors base et construction de
la solution de base no 1 251
6.6 Description de l'algorithme du simplexe réseau 258
6.7 Algorithme du simplexe réseau : résolution de l'exemple de base
262
Initialisation (Itération 0) ( Itération 1 ( Itération 2 ( Itération 3
6.8 Exemples d'applications 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 d'un PFCM ( Présentation d'un problème multisource
et multipuits comme un PFCM ( Présentation d'un 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 d'une 1re solution admissible : la méthode du coin nord-
ouest 306
4. Une 2e heuristique de calcul d'une solution initiale : la méthode des
coûts minimaux 310
5. Vérification de l'optimalité d'une solution 312
6. L'algorithme du transport 321
7. 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 d'affectation 353

8.1 Quelques exemples d'application dans le monde du transport
353
Appariements d'allers et de retours ( L'affectation de conducteurs à
des cueillettes ( Affectation de conducteurs à des voyages (
Affectation d'équipes à des réparations d'urgence ( Interdire ou
forcer des affectations
8.2 La nécessité d'un algorithme efficient 366
8.3 Le principe de base de l'algorithme 368
8.4 La notion de zéros indépendants 369
8.5 Un algorithme pour résoudre les problèmes d'affectation : 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 d'affectation ( 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 d'un 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 d'un 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 d'une 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 d'une 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 d'une
tournée hamiltonienne initiale 459
Pénalités d'insertion et notion de proximité d'un sommet à une
tournée partielle ( La notion de distance d'un sommet non visité à
une tournée partielle ( Les méthodes d'insertion
10.4 Heuristiques pour un PVC symét