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.