Table des matières
Introduction générale
I Problème de transport sélectif
Introduction
1 Problème de tournée de véhicules sélectif
1.1 Définition du problème
1.2 Quelques variantes du TOP
1.2.1 Le problème de tournées sélectif multipériodiques-mTOP
1.2.2 Le problème de tournées sélectif avec fenêtres de temps-TOPTW
1.2.3 Le problème de tournées sélectif avec avec profits et contraintes de capacité-CTOP
1.3 Terminologie et propriétés
1.3.1 Terminologie
1.3.2 Propriétés
1.4 Formulation linéaire
1.4.1 Modélisation du TOP à deux dépôts sous forme d’un problème sur un graphe
1.4.2 Modélisation sous forme d’un programme linéaire en nombres entiers
1.5 Conclusion
2 La résolution du problème de tournées de véhicules sélectif
2.1 Une approche basée sur un algorithme de cutting-plane
2.1.1 Élimination des sous-tours
2.1.2 Propriétés de dominance
2.1.3 Les inégalités valides basées sur les incompatibilités
2.1.4 Algorithme de cutting-plane
2.2 La résolution de TOP grâce à l’algorithme génétique
2.2.1 Codage utilisé
2.2.2 Création de la population initiale
2.2.3 Sélection
2.2.4 Croisement
2.2.5 Mutation
2.2.6 Résultats Numériques
2.3 Conclusion
II Dimension des ordres bipartis
Introduction
3 Ensembles ordonnés
3.1 Relation d’ordre
3.1.1 Minorants, majorants, minimaux et maximaux
3.1.2 Diagramme de Hasse d’un ordre
3.1.3 Isomorphisme et dualité
3.1.4 Chaînes, Antichaînes et paramètres fondamentaux
3.2 Conclusion
4 Dimension des ordres bipartis
4.1 Le théorème de Dilworth
4.2 Extensions et générateurs
4.3 Dimension d’un ordre
4.3.1 Ordres de dimension deux
4.4 Ensemble ordonné biparti
4.5 Les algorithmes
4.5.1 Problèmes, algorithmes, complexité
4.5.2 Les problèmes P, NP, et NP-complets
4.6 Conclusion
Conclusion générale
Bibliographie
