La résolution du problème de tournées de véhicules sélectif

Problème de tournée de véhicules sélectif

Dans ce chapitre, nous présentons la définition du problème de tournée de Véhicule Sélectif avec ses variantes. Ensuite, nous présentons les caractéristiques du TOP ainsi que la terminologie utilisée lors de sa description. Et en fin, nous décrivons un modèle pour le problème de tournée de Véhicule Sélectif sous forme d’un programme linéaire en nombres entiers ainsi qu’un autre sous forme d’un problème sur un graphe.

Le problème de tournée de Véhicule Sélectif est une variante de VRP où à priori il n’est pas possible de servir tous les clients. En TOP un nombre limité de véhicule est disponible pour visiter un ensemble potentiel des clients, où chaque véhicule doit partir d’un dépote et revenir en un autre après avoir visité un ensemble de clients. Sa solution consiste à construire un ensemble de m tournées associes a m véhicules contenant chaqune les points d et a comme point de départ et point d’arrivée. Les m tournées sont identifiées de telle sort à respecter le temps de trajet limite L et le profit total récolté par l’ensemble des m tournées soit maximisé. Dans notre cas la capacité des véhicules n’est pas prise en considération vu que l’on considère que l’on fournit un service aux clients. Chaque client ne peut être desservi qu’une seul fois et par au plus un seul véhicule.

Pour cette raison, ces problèmes sont les plus utilisés dans les domaines industriels où les ressources humaines et matérielles ont souvent certaines limites par rapport à la demande des clients à un moment donné, à savoir le nombre d’employés, le temps de travail de chaque employé, etc. tout en respectant ces limites. L’une des caractéristiques du TOP est qu’une solution peut avoir des clients non desservis qui le seront éventuellement ultérieurement (voir figure (1.1)). Cette caractéristique est due d’une part à la limitation du nombre de véhicules et d’autre part à la limitation de chaque tournée par une longueur maximale. Le TOP peut être défini avec un dépôt unique, c’est à dire que chaque véhicule part du dépôt et y revient après la visite d’un ensemble de clients. La variante du TOP à un seul dépôt est un cas particulier de la variante à deux dépôts. En effet, il suffit de mettre une distance nulle entre les deux dépôts (voir figure (1.2)). Un autre cas particulier du problème correspond au cas où nous considérons qu’un seul véhicule et un seul dépôt, cette variante revient à résoudre un problème connu sous le nom du Problème du Voyageur de Commerce Sélectif PVCS ([7], [17] et [25]).

Le problème de tournées sélectif multi périodiques-mTOP

Le problème de tournées de véhicules sélectif multi périodique (mTOP) a été récemment présenté par Zhang et al. [16] comme une nouvelle variante du problème de tournées sélectif (TOP). Dans le cas de mTOP, toutes les caractéristiques de TOP mentionnes dans la section précédente sont prises en compte, avec quelques contraintes supplémentaires à respecter. De même, tous les clients ne doivent être visités. Un nombre limité de véhicules identiques est disponible pour visiter ces clients. Chaque véhicule est associé à un temps de trajet limite prédéfinie et deux dépôts particuliers au cours de laquelle la visite doit commencer et terminer. Chaque client est associé à un profit qui est recueillie au plus une fois par la flotte de véhicules. De plus, chaque circuit est divisé en un certain nombre de périodes ayant chacune son propre délai de trajet maximal. Chaque période doit se terminer à un certain client, à partir de laquelle la période suivante commence. Par exception, la première période de chaque tournée doit commencer à partir du dépôt et le dernier doit se terminer à l’autre dépôt. Ainsi, le but de mTOP est de maximiser les profits recueillis auprès des clients servis dans les périodes sans dépasser la limite de temps de trajet de chaque période.

Le problème de tournées sélectif avec fenêtres de temps- TOPTW

Le problème de tournées sélectives avec fenêtres de temps (Team Orienteering Problem with Time Windows-TOPTW), est une variante bien connue de TOP. Afin de respecter la disponibilité de certains clients, Kantor et Rosenwein [9] ont présenté cette variante de TOP pour résoudre ce problème. Dans cette variante, la flotte de véhicules est disponible pour visiter un ensemble de clients, tout en respectant le temps de trajet limite L imposé pour chaque véhicule. De même que le TOP, le profit de chaque client peut être recueillie au plus une fois par la flotte, où La disponibilité de chaque client i est représentée par une fenêtre de temps définie par la date de service au plus tôt ei et celle au plus tard li. Un véhicule arrivant au client i avant la date ei doit attendre jusqu’à l’ouverture de la fenêtre de temps, alors qu’une arrivée tardive après li n’est pas permise et rend la solution irréalisable. La résolution du TOPTW consiste à organiser les visites pour tous les véhicules afin de maximiser la somme des profits collectés tout en respectant les fenêtres de temps des clients servis et le temps de trajet limite L imposé pour chaque véhicule.

Création de la population initiale :

Cette phase permet de générer une population d’individus qui servira de base pour les générations futures. Le choix de la population initiale est important car il peut rendre plus ou moins rapide la convergence vers l’optimum global. Pour construire la population initiale, nous avons développé une heuristique qui construit progressivement chaque chromosome de la manière suivante : à une itération donnée, le chromosome comporte plusieurs tournées dont le dernier tournées est en cours de construction, et son dernier gène est appelé sommet courant. L’algorithme doit choisir le prochain sommet à ajouter dans la tournée parmi les successeurs possibles du sommet courant dans le graphe. La sélection parmi les candidats se fait aléatoirement mais en favorisant les sommets ayant le plus grand profit. Elle repose sur un principe de roulette, où chaque sommet occupe un secteur proportionnel à son profit.

Lorsqu’un sommet est sélectionné, il faut vérifier qu’il peut être visité en respectant les contraintes. Si ce n’est pas le cas, l’algorithme retire ce sommet de la roulette puis réitère la procédure pour tester un autre successeur. Si aucun successeur ne permet de vérifier les contraintes, la tournée s’achève et l’algorithme tente d’en créer une nouvelle. Au fur et à mesure de la construction, la liste des sommets déjà insérés dans le chromosome est tenue à jour pour éviter de les tester une seconde fois. De plus, à chaque ajout d’un sommet dans une tournée, les caractéristiques de celle-ci (le temps de trajet parcourue, profit collecté) sont mises à jour. Deux évènements peuvent achever la construction d’un chromosome. Soit le nombre de tournées déjà construites est égal au nombre de véhicules disponibles. Soit il ne reste aucun successeur qui vérifie les contraintes.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela rapport gratuit propose le téléchargement des modèles gratuits de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

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