Table des matières
1. Le monde du transport
- 1.1 Des outils qui ont révolutionné le monde du transport
- La palettisation
- La conteneurisation
- Le GPS et ses prédécesseurs
- Le routage des navires
- 1.2 Quelques anecdotes de l’histoire des transports
- 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
- Le camion
- Le transport aérien
- Øresund
- Arabie Saoudite
- Guinée
- Chili
- 1.4 Modes non conventionnels de transport
- 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
- Les voies du passé et du présent
- Le camionnage
- Des problèmes à résoudre dans l’industrie du camionnage
- La recherche en transport au Québec
- Le Centre de recherche sur les transports (CRT)
- Le Groupe d’études et de recherche en analyse des décisions (GÉRAD)
- Giro
- Technologies Ad Opt Inc.
- INRO
- 1.6 L’approche pédagogique de ce manuel – la famille Simard
- 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
2. Réseaux et graphes : vocabulaire et exemples
- 2.1 Les précurseurs
- 2.2 Sommets, arcs et arêtes : les atomes des graphes et des réseaux
- 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
- 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
- Incidence et degrés
- Chaînes et composantes connexes
- Accessibilité
- Composantes connexes et connexité
- 2.5 Compléments
- Représentation d’un graphe économe de l’espace en mémoire
- Graphe biparti
- Graphe planaire
- 2.6 Exercices
- 1. Exemples de réseaux concrets
- 2. Répertoire d’un ordinateur
- 3. Notions élémentaires des réseaux orientés
- 4. Degrés des sommets dans un réseau orienté
- 5. Accessibilité dans un réseau orienté
- 6. Composantes connexes d’un réseau orienté
- 7. Ajout d’arcs dans un réseau orienté
- 8. Arcs reliant deux composantes connexes
- 9. Nombre minimal d’arcs
- 10. Notions élémentaires des réseaux non orientés
- 11. Degrés des sommets dans un réseau non orienté
- 12. Accessibilité dans un réseau non orienté
- 13. Composantes connexes d’un réseau non orienté
- 14. Ajout d’arcs dans un réseau non orienté
- 15. Nombre minimal d’arêtes
- 16. Graphes orientés avec contraintes sur les degrés
- 17. Sens uniques
- 18. Chemins simples
- 19. Échange de camions
3. Arbres
- 3.1 Une propriété de base des réseaux non orientés : la connexité
- 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
- 3.3 L’arbre générateur de poids maximal
- 3.4 Arbre de poids minimal dans un réseau cartésien
- 3.5 Compléments
- 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
- 1. Pertinence de la structure d’arbre
- 2. La crise du verglas
- 3. Nombre de sommets
- 4. Arbres générateurs d’un graphe complet
- 5. Arbre générateur de poids minimal
- 6. Arbres générateurs de poids minimal
- 7. Arbres générateurs de poids extrêmes
- 8. Arbres générateurs de poids maximal
- 9. Arbre dans un réseau cartésien
- 10. Martinique
- 11. Voies ferrées
- 12. Économie routière
- 13. Une condition nécessaire pour la connexité
- 14. Définitions d’un arbre
- 15. Méditations sur un arbre
- 16. Rameau de feuilles de pin
- 17. Liste des degrés d’un graphe
- 18. Arbres de décision
- 19. Arbres de décision et décisions séquentielles
4. Le calcul du chemin le plus court dans un réseau
- 4.1 Le CLPC, une donnée essentielle dans le monde du transport
- 4.2 Un algorithme efficace pour le calcul des CLPC : la méthode de Dijkstra
- 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é
- 4.4 Compléments
- Un modèle mathématique pour le calcul d’un CLPC
- Certificat d’optimalité pour les longueurs des CLPC
- Preuve
- Méthode de correction d’étiquettes pour le calcul des CLPC
- 4.5 Exercices
- 1. Refus paradoxaux
- 2. Calcul d’un CLPC
- 3. Calcul de CLPC de un à tous
- 4. Arborescence des CLPC
- 5. Nombre de chemins
- 6. Tableau d’accessibilité
- 7. Calcul d’une chaîne de longueur minimale
- 8. Calcul de CLPC de un à tous dans un réseau non orienté
- 9. CLPC et arbre générateur de poids minimal
- 10. CLPC dans un réseau mixte
- 11. Livraison de pizzas
- 12. Le défilé du père Noël
- 13. Ajout, retrait ou modification d’un arc
- 14. Pose d’étiquettes
- 15. Modèles linéaires
- 16. Baltimore-Montréal
- 17. Soudure de pièces en aluminium
- 18. Le chanteur d’opéra et le taxi
- 19. L’homme d’affaires pressé et le taxi
- 20. Barrières de pluie
5. Le flot maximal
- 5.1 Le rééquilibrage des palettes
- 5.2 Terminologie et définition du problème de flot maximal
- Classification des sommets
- Le problème de flot maximal
- 5.3 Chemin d’augmentation du flot
- 5.4 Chaîne d’augmentation
- 5.5 La notion de coupe dans un réseau
- 5.6 La pose d’étiquettes pour le calcul du flot maximal
- 5.7 Compléments
- Le réseau résiduel et la pose d’étiquettes dans 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
- 1. Exemples d’applications
- 2. Arcs avant et arcs arrière
- 3. Calcul d’une solution optimale
- 4. Calcul du flot maximum
- 5. Amélioration d’une solution admissible
- 6. Coupes dans un réseau
- 7. Vérification de l’optimalité
- 8. Flot maximal et coupe de capacité minimale
- 9. Coupe de capacité minimale
- 10. Expédition à Bornéo
- 11. Un réseau de métro
- 12. Lavage de camions
- 13. Transport de palettes
- 14. Le maître passeur
- 15. Barrages routiers
- 16. Trouver les erreurs
- 17. Recherche systématique d’un chemin d’augmentation
- 18. Modèle linéaire
- 19. Modèle linéaire et coupes
6. Le problème de flot à coût minimal
- 6.1 Définition du problème
- 6.2 Le calcul d’une solution admissible initiale
- 6.3 Classification des arcs dans une solution admissible
- 6.4 Solution admissible de base
- 6.5 Calcul du coût marginal d’un arc hors base et construction d’une solution de base no 1
- 6.6 Description de l’algorithme du simplexe réseau
- 6.7 Algorithme du simplexe réseau : résolution de l’exemple de base
- Initialisation (Itération 0)
- Itération 1
- Itération 2
- Itération 3
- 6.8 Exemples d’applications de PFCM
- Le transport à charges partielles
- La localisation des entrepôts
- Les PFCM et le transport aérien
- 6.9 Compléments
- 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
- 1. Solutions admissibles
- 2. Solution optimale
- 3. Vérification de la non-optimalité
- 4. Optimalité et coût marginal
- 5. Optimal ou non, voilà la question
- 6. L’algorithme du simplexe réseau
- 7. Cas particuliers de PFCM
- 8. PFCM et le problème d’affectation
- 9. PFCM et le problème de transport classique
- 10. Le PFCM, de a à z
- 11. Modèle linéaire associé à un PFCM
- 12. Un problème multisource et multipuits
- 13. Un PFCM avec une borne inférieure
- 14. L’affectation de tracteurs à des remorques
- 15. L’heure de pointe dans un dédale urbain
- 16. Le problème de transbordement
- 17. Les cannettes de Canul
7. Le problème de transport classique
- 7.1 Définition du problème
- 7.2 Rééquilibrage des palettes entre divers terminus
- 7.3 Calcul d’une première solution admissible : la méthode du coin nord-ouest
- 7.4 Une deuxième heuristique de calcul d’une solution initiale : la méthode des coûts minimaux
- 7.5 Vérification de l’optimalité d’une solution
- 7.6 L’algorithme du transport
- 7.7 Compléments
- 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
- 1. La méthode du coin nord-ouest
- 2. La méthode des coûts minimaux
- 3. Choix des cases entrante et sortante
- 4. Construction des cycles de changement
- 5. Une itération de l’algorithme du transport
- 6. Résolution de problèmes de transport
- 7. Le transport des palettes
- 8. Un problème admettant plusieurs solutions optimales
- 9. Une solution initiale qui est optimale
- 10. Modification d’un coût unitaire
- 11. Problèmes non équilibrés
- 12. Modèle linéaire
- 13. La méthode des pénalités
- 14. Construction d’une solution initiale : comparaison des trois méthodes
- 15. Problème dégénéré et méthode du coin nord-ouest
- 16. Problème dégénéré et méthode des coûts minimaux
- 17. Problème dégénéré et itération
- 18. Bières Témiscouata Inc.
- 19. Livraisons anticipées et en retard
8. Le problème d’affectation
- 8.1 Quelques exemples d’application dans le monde du transporta
- Appariement d’allers et de retours
- L’affectation de conducteurs à des cueillettes
- Affectation de conducteurs à des voyages
- 1. Journée et heure de départ
- 2. Voyages avec ou sans arrêts
- 3. Voyages avec ou sans manutention
- 4. La région du voyage
- Affectation d’équipes à des réparations d’urgence
- Interdire ou forcer des affectations
- 8.2 La nécessité d’un algorithme efficient
- 8.3 Le principe de base de l’algorithme
- 8.4 La notion de zéros indépendants
- 8.5 Un algorithme pour résoudre les problèmes d’affectation : la méthode hongroise
- 8.6 Un exemple de problème non équilibré avec un objectif de maximisation
- 8.7 Compléments
- 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
- 1. Utilisations pratiques du modèle d’affectation
- 2. Le modèle d’affectation et les hôpitaux
- 3. La compagnie US-LTL
- 4. Réduction-ligne et réduction-colonne pour un PA3
- 5. Réduction-ligne et réduction-colonne pour un PA4
- 6. La méthode hongroise
- 7. Affectation d’employés à des tâches
- 8. Solution gourmande et solution optimale
- 9. Camionneurs en quête de voyages
- 10. Réparations urgentes
- 11. Cocktails
- 12. Rallye
- 13. Le vieillissement du whisky
- 14. Des employés qui peuvent accomplir plusieurs tâches
- 15. Problème avec conditions sur les affectations
- 16. Modèle linéaire
9. Le problème du postier chinois non orienté
- 9.1 La tournée d’un camelot
- La leçon de Jacques : préliminaires
- 9.2 La suite de la leçon de Jacques : un appariement optimal des sommets impairs
- 9.3 La séquence de visite des arêtes d’un multigraphe eulérien
- 9.4 Le problème du postier chinois orienté
- 9.5 Compléments
- 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.7 Exercices
- 1. Service sur les liens d’un graphe et gestion d’une municipalité
- 2. Modèle linéaire des appariements
- 3. Tournée optimale ou non optimale ?
- 4. Tournées eulériennes optimales dans un réseau non orienté
- 5. Recherche du nid familial
- 6. Artificier
- 7. Parcomètres
- 8. Inspection d’un système de canalisations souterraines
- 9. Distribution d’échantillons
- 10. Modèle linéaire du PCNO
- 11. Un réseau orienté non eulérien
- 12. Tournée eulérienne dans un réseau orienté
10. Le problème du voyageur de commerce
- 10.1 Typologie, historique et applications
- 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
- 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
- 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étrique : amélioration d’une tournée hamiltonienne
- La méthode 2-OPT
- 10.5 Résoudre un PVC asymétrique
- 10.6 Compléments
- Absence de croisements dans une tournée optimale d’un réseau cartésien
- Le modèle linéaire d’un PVC symétrique : un exemple
- 10.7 Exercices
- 1. La perceuse robotisée
- 2. Chez Transport HenriD
- 3. Les quincailleries
- 4. Un premier problème asymétrique
- 5. Un second problème asymétrique
- 6. La méthode 2-OPT
- 7. Cycle complet
- 8. Chaîne hamiltonienne
- 9. Sonars
- 10. La tournée d’un orchestre de chambre
- 11. Un jeu de piste
- 12. Leïla, agente d’immeubles
- 13. La course aux débiteurs
- 14. La ronde du vigile
- 15. La maison d’été des Simard
