DI-UMONS : Dépôt institutionnel de l’université de Mons

Recherche transversale
(titres de publication, de périodique et noms de colloque inclus)
2010-05-16 - Colloque/Article dans les actes avec comité de lecture - Anglais - 6 page(s)

Lecron Fabian , Manneback Pierre , Tuyttens Daniel , "Exploiting Grid Computation for Solving the Vehicle Routing Problem" in ACS/IEEE International Conference on Computer Systems and Applications, 10.1109/AICCSA, 1-6, Hammamet, Tunisie, 2010

  • Codes CREF : Recherche opérationnelle (DI1150), Informatique appliquée logiciel (DI2570), Analyse de systèmes informatiques (DI2572)
  • Unités de recherche UMONS : Informatique, Logiciel et Intelligence artificielle (F114), Mathématique et Recherche opérationnelle (F151)
  • Instituts UMONS : Institut de Recherche en Technologies de l’Information et Sciences de l’Informatique (InforTech)
Texte intégral :

Abstract(s) :

(Anglais) The purpose of this paper is to solve the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) on Grid'5000 using the ParadisEO framework. In this respect, four packages developed in ParadisEO are exploited. First, EO package (Evolving Objects) is used to create an evolutionary algorithm to solve the mono-objective CVRPTW. Then, a related multi-objective problem is solved with MOEO package (Multi-Objective Evolving Objects). The package PEO (Parallel Evolving Objects) permitted us to use a particular hybridization scheme: the cooperative island model. Exchanges were performed between three evolutionary algorithms. With this strategy, an improvement in the solutions has been noticed. The final part of the work is concerned with developing hybridization between an evolutionary algorithm and a simulated annealing (created with the Moving Objects Package MO). The goal is to take advantage of intensification by simulated annealing and diversification by evolutionary algorithm. One important feature is the exploitation of the Grid'5000 infrastructure which permits us to reduce the execution time by 50 compared to a sequential execution.