Restriction du jeu de données pour la phase de test

Restriction du jeu de données pour la phase de test

Construction de routes

La première idée qui vient à l’esprit dans ce genre de problème est de relier tous les points en choisissant à chaque fois le plus proche de celui où l’on se trouve. Il s’agit de la méthode relativement myopique du plus proche voisin, de difficulté en ( ) 2 O n . Cette méthode a été étudiée par Rosenkrantz et al. (1977) qui ont aussi étudié les algorithmes d’insertion. L’insertion consiste à créer une route avec seulement deux (2) points, puis on va insérer de nouveaux points à cette route en respectant un critère prédéfini. Ce critère peut être le point qui fait varier le moins la longueur totale de la route, le point qui se trouve le plus près d’une route existante, etc. Le choix du critère est ce qui va déterminer la difficulté de la résolution. Il existe aussi la méthode de rapiéçage qui consiste à résoudre le TSP sans éliminer les souschemins puis de relier tous les sous-chemins entre eux en trouvant les arcs de moindre coûts jusqu’à n’avoir plus qu’une seule route. 1.2.2.2 Amélioration de routes Chacun des algorithmes présentés ici prennent comme base un tour obtenu d’une manière quelconque et vont l’améliorer. L’algorithme r-opt (Lin, 1965) consiste à retirer r arcs à une solution existante et les réinsérer de toutes les manières possibles puis de choisir celle qui offre la plus grande réduction de coût. On répète ensuite cette opération sur r autres arcs jusqu’à ce qu’il n’y ait plus de gain. Une méthode utilisant une analogie avec la science des matériaux est celle du recuit simulé (Simulated Annealing ou SA) par Kirkpatrick et al. (1983). En effet, pour arriver à un état stable de la matière, il faut refroidir graduellement un matériau pour ne pas qu’il se fige dans un minimum local. Il en est de même pour une solution au TSP, il faut le contraindre graduellement afin qu’il trouve un état quasi optimal. 31 La recherche avec liste de tabous (Glover, 1990) est une méthode qui permet comme le recuit simulé de détériorer la solution afin d’éviter les minima locaux mais on utilise aussi une liste tabou de solutions déjà testées que l’on s’interdit de réessayer en vue de trouver toujours une solution qui tende vers l’optimal. 1.3 Le problème de tournée de véhicule Le problème de tournée de véhicule (Vehicle Routing Problem ou VRP) découle directement du problème de voyageur de commerce. La formulation la plus basique du problème est la suivante : Un ensemble de clients doit être servi par une flotte de camions identiques partant d’un dépôt unique. Par la suite, de nombreuses contraintes peuvent êtres ajoutées complexifiant d’avantage le problème. La relation avec le TSP est triviale, il s’agit donc aussi d’un problème NP-Difficile. Parmi les différents types de VRP fréquemment rencontrés, citons le CVRP lorsqu’on ajoute une contrainte de capacité au camions, le DVRP lorsqu’on limite la distance parcourable par les camions, le VRPTW lorsqu’on spécifie des fenêtres de temps pour visiter les clients, le VRPPD lorsque les camions peuvent effectuer des cueillettes et des livraisons sur leur chemin. Mais il en existe encore bien d’autres et on peut aussi les associer entre eux. De par les similitudes entre les deux problèmes de TSP et de VRP, on peut aussi répartir les méthodes de résolution du VRP en méthodes exactes et heuristiques (Laporte, 1992b). 1.3.1 Méthodes exactes Une des premières méthodes exactes étudiée utilise la notion qu’on peut résoudre un CVRP ou un DVRP en résolvant un m-TSP (Laporte et al., 1986), c’est-à-dire en créant m routes correspondant au nombre de camions de la flotte et satisfaisant les contraintes du problème de voyageur de commerce : chaque point n’est visité qu’une fois. On utilise ensuite les algorithmes classiques de branch-and-bound. On peut ainsi en relaxant suffisamment le problème réussir à résoudre des problèmes de quelques centaines de clients. 32 On peut aussi considérer la méthode k-degree center tree (Christofides et al., 1981) qui formule le problème de manière à répartir tous les arcs en quatre (4) catégories auxquelles ont peut associer des coûts respectifs, puis on minimise le coût total en trouvant la meilleure association entre les arcs et les catégories. Une autre méthode utilise la programmation dynamique pour résoudre ce problème (Eilon et al., 1971). Mais comme toutes les méthodes exactes, les problèmes deviennent rapidement impossibles à résoudre dans un temps raisonnable et demandent à réaliser de nombreuses relaxations qui dénaturent la qualité de la solution. Les problèmes au dessus d’une centaine de clients sont déjà trop grands.

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 chatpfe.com propose le téléchargement des modèles complet 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
CHAPITRE 1 REVUE DE LITTÉRATURE
1.1 La collecte d’huile au Québec
1.1.1 Historique
1.1.2 Types d’huiles
1.1.3 Principe de la collecte
1.2 Le Problème de voyageur de commerce
1.2.1 Les méthodes exactes
1.2.2 Les méthodes heuristiques
1.2.2.1 Construction de routes
1.2.2.2 Amélioration de routes
1.3 Le problème de tournée de véhicule
1.3.1 Méthodes exactes
1.3.2 Méthodes heuristiques
1.3.2.1 L’algorithme de Clarke et Wright
1.3.2.2 L’algorithme de balayage
1.4 Problème de tournée de véhicule avec gestion de stock
1.4.1 Origines
1.4.2 Définition
1.4.3 Caractérisation des problèmes
1.4.3.1 Le temps
1.4.3.2 Le produit
1.4.3.3 La topologie
1.4.3.4 La demande
1.4.3.5 Les coûts
1.4.3.6 Les contraintes
1.4.3.7 La stratégie de tournée
1.4.4 Méthodes de résolution
1.4.4.1 Séparation du problème
1.4.4.2 Horizon de planification
1.4.4.3 Méthodes exactes et heuristiques
1.5 Conclusion
CHAPITRE 2 MÉTHODOLOGIE
2.1 Données d’entrée
2.1.1 Jeu de données test
2.1.2 Données réelles
2.1.2.1 Mise en forme
2.1.2.2 Réception
2.1.2.3 Analyse des données
2.1.2.4 Prévision pour l’année 2011
2.1.2.5 Restriction du jeu de données pour la phase de test
2.2 Modélisation
2.2.1 Classification des clients
2.2.2 Méthode graphique
2.2.3 Tri par fonction coût
2.2.4 Programmation entière
2.2.4.1 Logique générale
2.2.4.2 Le modèle initial – Phase 1
2.2.4.3 Le modèle lissé – Phase 1
2.2.4.4 Phase 2
2.2.4.5 Le modèle utilisé
2.3 Automatisation de la résolution des modèles développés
2.3.1 Procédure pour les modèles initiaux
2.3.2 Résolution sur un an pour les modèles initiaux
2.3.3 Procédure pour le modèle utilisé
2.4 Conclusion
CHAPITRE 3 EXPÉRIMENTATIONS
3.1 Introduction des indicateurs de performance
3.2 Le modèle initial
3.3 Le modèle lissé
3.3.1 Première optimisation
3.3.2 Deuxième optimisation
3.3.3 Troisième optimisation – NbVis variable
3.3.4 Quatrième optimisation – Augmentation de la durée de calcul
3.4 Le modèle utilisé
3.5 Phase 2
3.6 Temps de calcul
3.7 Implantation chez le client
3.8 Conclusion
CONCLUSION
ANNEXE I MODÉLISATION ET AUTOMATISATION DU MODÈLE
RÉFÉRENCES