A distributed evolutionary algorithm with a superlinear speedup for solving the vehicle routing problem
Krunoslav Puljić; Department of Mathematics, University of Zagreb, Bijenička cesta 30, 10000 Zagreb ; Robert Manger; Department of Mathematics, University of Zagreb, Bijenička cesta 30, 10000 Zagreb
Computing and Informatics, Tome 28 (2012) no. 1, / Harvested from Computing and Informatics
Text on Computing and Informatics
In this paper we present a distributed evolutionary algorithm for solving the capacitated vehicle routing problem. Our algorithm consists of autonomous processes that create heterogeneous evolutionary environments, perform evolution on separate populations of chromosomes, and communicate asynchronously through occasional migrations of chromosomes. The paper also presents experiments where the algorithm has been tested on some benchmark problem instances. By measuring the effects of distribution on solution quality and on computing time, the experiments confirm that the algorithm achieves a superlinear speedup.
Publié le : 2012-08-10
Classification:  Vehicle routing problem, evolutionary algorithms, distributed algorithms, superlinear speedup, experiments,  90C27, 90C35, 90C59, 68W15, 68W40 
@article{cai1014,
     author = {Krunoslav Pulji\'c; Department of Mathematics, University of Zagreb, Bijeni\v cka cesta 30, 10000 Zagreb and Robert Manger; Department of Mathematics, University of Zagreb, Bijeni\v cka cesta 30, 10000 Zagreb},
     title = {A distributed evolutionary algorithm with a superlinear speedup for solving the vehicle routing problem},
     journal = {Computing and Informatics},
     volume = {28},
     number = {1},
     year = {2012},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai1014}
}

Krunoslav Puljić; Department of Mathematics, University of Zagreb, Bijenička cesta 30, 10000 Zagreb; Robert Manger; Department of Mathematics, University of Zagreb, Bijenička cesta 30, 10000 Zagreb. A distributed evolutionary algorithm with a superlinear speedup for solving the vehicle routing problem. Computing and Informatics, Tome 28 (2012) no. 1, . http://gdmltest.u-ga.fr/item/cai1014/