Une heuristique de recherche à voisinage variable pour le problème du voyageur de commerce avec fenêtres de temps
Thesis or Dissertation
2016-04 (degree granted: 2016-09-28)
Author(s)
Level
Master'sDiscipline
InformatiqueKeywords
- Recherche à voisinage variable
- Problème de voyageur de commerce
- Fenêtres de temps
- Minimisation du temps d'arrivée au dépôt
- Réalisabilité d'un mouvement
- Rentabilité d'un mouvement
- Réduction de l'espace de recherche
- General variable neighborhood search
- Traveling salesman problem
- Time windows
- Completion time minimization
- Feasibility
- Profitability
- Search space reduction
- Applied Sciences - Operations Research / Sciences appliqués et technologie - Recherche opérationnelle (UMI : 0796)
Abstract(s)
Nous adaptons une heuristique de recherche à voisinage variable pour traiter le problème du voyageur de commerce avec fenêtres de temps (TSPTW) lorsque l'objectif est la minimisation du temps d'arrivée au dépôt de destination. Nous utilisons des méthodes efficientes pour la vérification de la réalisabilité et de la rentabilité d'un mouvement. Nous explorons les voisinages dans des ordres permettant de réduire l'espace de recherche. La méthode résultante est compétitive avec l'état de l'art. Nous améliorons les meilleures solutions connues pour deux classes d'instances et nous fournissons les résultats de plusieurs instances du TSPTW pour la première fois. We adapt a general variable neighborhood search heuristic to solve the traveling salesman problem with time windows (TSPTW) where the objective is to minimize the completion time. We use efficient methods to check the feasibility and the profitability of a movement. We use a specific order to reduce the search space while exploring the neighborhoods. The resulting method is competitive with the state-of-the-art. We improve the best known solutions for two classes of instances and provide the results of multiple instances of TSPTW for the first time.
This document disseminated on Papyrus is the exclusive property of the copyright holders and is protected by the Copyright Act (R.S.C. 1985, c. C-42). It may be used for fair dealing and non-commercial purposes, for private study or research, criticism and review as provided by law. For any other use, written authorization from the copyright holders is required.