Exploiting Grid Computation for Solving the Vehicle Routing Problem

[en] 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.

Disciplines :

Computer science
Mathematics

Author, co-author :

Lecron, Fabian ; Université de Mons > Faculté Polytechnique > Informatique, Logiciel et Intelligence artificielle

Manneback, Pierre ; Université de Mons > Faculté Polytechnique > Informatique, Logiciel et Intelligence artificielle

Tuyttens, Daniel ; Université de Mons > Faculté Polytechnique > Mathématique et Recherche opérationnelle

Language :

English

Title :

Exploiting Grid Computation for Solving the Vehicle Routing Problem

Publication date :

16 May 2010

Event name :

ACS/IEEE International Conference on Computer Systems and Applications

Event place :

Hammamet, Tunisia

Event date :

2010

Research unit :

F114 - Informatique, Logiciel et Intelligence artificielle
F151 - Mathématique et Recherche opérationnelle

Research institute :

R300 - Institut de Recherche en Technologies de l'Information et Sciences de l'Informatique

Available on ORBi UMONS :

since 09 December 2010

Statistics

Number of views

17 (0 by UMONS)

Number of downloads

0 (0 by UMONS)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

Bibliography

(2009) Grid5000. [Online]. Available: https://www.grid5000.fr/ mediawiki/index.php/Grid5000:Home
E. Alba and B. Dorronsoro, "Solving the vehicle routing problem by using cellular genetic algorithms," in Evolutionary Computation in Combinatorial Optimization, 2004.
B. Baker and M. Ayechew, "A genetic algorithm for the vehicle routing problem," Computers & Operations Research 30, pp. 787-800, 2003.
J. Berger and M. Barkaoui, "A hybrid genetic algorithm for the capacitated vehicle routing problem," Genetic and Evolutionary Computation, vol. 2723, pp. 646-656, 2003.
S. Cahon, "Paradiseo : Une plate-forme pour la conception et le déploiement de métaheuristiques parallèles hybrides sur clusters et grilles," Ph.D. dissertation, Université des Sciences et Technologies de Lille, 2005.
S. Cahon, N. Melab, and E.-G. Talbi, "Paradiseo: A framework for the reusable design of parallel and distributed metaheuristics," Journal of Heuristics 10, pp. 357-380, 2004.
G. Clarke and J. W. Wright, "Scheduling of vehicles from a central depot to a number of delivery points," Operations Research, vol. 12, no. 4, pp. 568-581, 1964.
J.-F. Cordeau, G. Desaulniers, J. Desrosiers, M. M. Solomon, and F. Soumis, VRP with time windows. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 2002, pp. 157-193.
J.-F. Cordeau, M. Gendreau, and G. Laporte, "A tabu search heuristic for periodic and multi-depot vehicle routing problems," Networks, vol. 30, no. 2, pp. 105-119, 1997.
G. B. Dantzig and J. H. Ramser, "The truck dispatching problem," Management Science, vol. 6, no. 1, pp. 80-91, 1959.
K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, "A fast and elitist multi-objective genetic algorithm: Nsga-ii," IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, 2002.
B. Dorronsor, D. Arias, F. Luna, A. J. Nebro, and E. Alba, "A grid-based hybrid cellular genetic algorithm for very large scale instances of the cvrp," in 2007 High Performance Computing & Simulation Conference (HPCS 2007), W. W. Smari, Ed., 2007, pp. 759-765.
J. Dréo, A. Pétrowski, P. Siarry, and E. Taillard, Métaheuristiques pour l'optimisation difficile, Eyrolles, Ed. 356 pages, 2003.
B. E. Gillett and L. R. Miller, "A heuristic algorithm for the vehicle-dispatch problem," Operations Research, vol. 22, no. 2, pp. 340-349, 1974.
J. Homberger and H. Gehring. (1999) Extended solomon's vrptw instances. [Online]. Available: http://www.fernuni-hagen.de/WINF/ touren/inhalte/probinst. htm
G. Laporte and F. Semet, Classical heuristics for the capacitated VRP. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 2002, pp. 109-128.
F. Lecron, "Résolution de problèmes d'optimisation combinatoire sur grille informatique: évaluation de la plate-forme paradiseo," Master's thesis, Faculté Polytechnique de Mons, 2008, promoteurs: D. Tuyttens et P. Manneback.
J. K. Lenstra and A. H. G. R. Kan, "Complexity of vehicle routing and scheduling problems," Networks, vol. 11, pp. 221-227, 1981.
C. Lima, M. Goldbarg, and E. Goldbarg, "A memetic algorithm for the heterogeneous fleet vehicle routing problem," Electronic Notes in Discrete Mathematics, vol. 18, pp. 171-176, 2004, latin-American Conference on Combinatorics, Graphs and Applications.
E.-G. Talbi, Parallel Combinatorial Optimization. Wiley-Interscience, 2006.
-, Metaheuristics: From Design to Implementation. Wiley-Interscience, 2009.
D. Tuyttens, J. Teghem, and N. El-Sherbeny, "A particular multi-objective vehicle routing problem solved by simulated annealing," Economics and Mathematical Social Sciences 48, pp. 133-152, 2004.