Hybrid Evolutionary Resolution Approches for static and dynamic 1-PDPTW

Autor: Kammarti, Ryan
Přispěvatelé: Laboratoire d'Automatique, Génie Informatique et Signal (LAGIS), Université de Lille, Sciences et Technologies-Centrale Lille-Centre National de la Recherche Scientifique (CNRS), Laboratoire Modélisation, Analyse et Commande des Systèmes [Tunis] (ACS), Ecole Nationale d'Ingénieurs de Tunis (ENIT), Université de Tunis El Manar (UTM)-Université de Tunis El Manar (UTM), Ecole Centrale de Lille, Pierre BORNE, Mekki KSOURI, Slim HAMMADI
Jazyk: francouzština
Rok vydání: 2006
Předmět:
Zdroj: Autre. Ecole Centrale de Lille, 2006. Français
Popis: Nowadays, goods and people transportation take an important place in all societies daily life and business. The single pickup and delivery problem is one of the most faced problems. Having a set of request to satisfy the transportation vehicle will carry goods from providers to respective customers respecting their each time windows and its self-transportation capacity. In this work, we present a review of the scientific literature on the 1-PDPTW and we present some new approaches to resolve the static and the dynamic cases of this problem. Our approaches use mainly evolutionary algorithms based on the use of special genetic operators conceived in to improve the solutions quality and to decrease the computation time. They are also based on the use of the Pareto optimality approach to provide to the decision maker a set of good feasible solutions. Some of our approaches use distance end tardiness lower bounds to evaluate the obtained solutions. A hybridization stage, consisting on a special Tabu search, can be applied to improve the solutions given by the evolutionary algorithms. Finally, we present some simulations and results elaborated with benchmarks especially conceived for the 1-PDPTW and other benchmarks issued from the literature.; De nos jours, le transport de marchandise occupe une place importante dans la vie économique des sociétés modernes. Le problème de collecte et de distribution avec fenêtres de temps à un seul véhicule est un des problèmes les plus rencontrés. Ayant un ensemble de demandes à satisfaire, le véhicule doit transporter des biens de fournisseurs à leurs clients respectifs en respectant les fenêtres de temps et sa capacité. Dans ce travail, nous présentons un état de l'art du 1-PDPTW et nous proposons plusieurs approches évolutionnistes pour traiter ses deux cas : statique et dynamique. Nos approches utilisent principalement des algorithmes évolutionnistes basés sur l'utilisation d'opérateurs génétiques spéciaux conçus dans le but d'améliorer la qualité des solutions et de diminuer le temps de calcul. Elles sont aussi basées sur la Pareto optimalité pour fournir un ensemble de solutions viables. Quelques unes de nos approches utilisent des bornes inférieures de distance et de retard dans le but d'évaluer les résultats obtenus. Une recherche Tabou, constituant un étage d'hybridation, peut être appliquée pour l'amélioration des solutions obtenues par les algorithmes évolutionnistes. Enfin nous présentons quelques simulations et résultats élaborés à partir de benchmarks spécialement conçus pour le 1-PDPTW ainsi que d'autres provenant de la littérature.
Databáze: OpenAIRE
Externí odkaz: