All Title Author
Keywords Abstract

Parallel Methods of Solving of Supply Problem Using Ant Colony Optimization

Keywords: ant colony optimization , metaheuristics , parallel algorithm , multi-core architecture , combinatorial optimization , vehicle routing problem , very large scale vehicle routing problem

Full-Text   Cite this paper   Add to My Lib


Presented work focuses on solving of the vehicle routingproblem, which is considered as a basic supply problem.The main motivation is to achieve high quality solutions ofthe vehicle routing problem in the shortest possible time.It tries to achieve this goal via parallelization of the antcolony optimization metaheuristics, which is suitable forcalculating of combinatorial problems. The vehicle rout-ing problem is an NP-complete problem, therefore usageof heuristics is the only way to solve it on large instances.The author proposes and compares dierent settings andsolving methods of the vehicle routing problem using theant colony optimization in sequence and parallel execu-tion. He determines appropriate application of the lo-cal search methods, which improves solution quality andapplies the elite approach. On selected communicationtopology, he proposes and compares several synchroniza-tion and communication strategies, all from achieved qual-ity and speedup point of view, on dierent number ofmulti-core processors.The author presents his own optimization tool, which isbased on execution of the ant colony optimization in a pa-rallel environment. The author applies proposed parallelmethod to the very large scale vehicle routing probleminstances with as many as 1200 customers.


comments powered by Disqus