Algorithme exact basé sur la génération de colonnes pour la résolution du problème de tournées sélectives avec fenêtres de temps
| Autor: | El-Hajj, Racha, Moukrim, Aziz, Chebaro, Bilal, Kobeissi, Mohamed |
|---|---|
| Přispěvatelé: | Heuristique et Diagnostic des Systèmes Complexes [Compiègne] (Heudiasyc), Université de Technologie de Compiègne (UTC)-Centre National de la Recherche Scientifique (CNRS), UNIVERSITE LIBANAISE Faculté de Sciences II, Laboratoire d'Excellence 'Maîtrise des Systèmes de Systèmes Technologiques' (Labex MS2T), Lyes Benyoussef |
| Jazyk: | francouzština |
| Rok vydání: | 2015 |
| Předmět: | |
| Zdroj: | ROADEF2015 ROADEF2015, Lyes Benyoussef, Feb 2015, Marseille, France. pp.2 |
| Popis: | National audience; Cet article décrit un algorithme de résolution exacte du problème de tournées sélectives avec fenêtres de temps (Team Orienteering Problem with Time Windows - TOPTW). Il s'agit d'une variante du problème de tournées de véhicules dont le but est de maximiser la somme des profits collectés tout en respectant les fenêtres de temps des différents clients servis et un temps de trajet limite pour chaque véhicule. Notre algorithme est basé sur la génération de colonnes. Un algorithme de programmation dynamique est appliqué pour résoudre un sous-problème permettant de générer des colonnes supplémentaires pour les ajouter au problème maître à chaque itération. Les expérimentations réalisées sur le benchmark du TOPTW montrent l'efficacité de notre méthode. L’algorithme proposé permet de résoudre à l'optimalité plusieurs instances ouvertes. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|