Back to search

Institutional Repository of Vilnius University

Dirbtinės bičių kolonijos algoritmo keliaujančio pirklio uždaviniui spręsti lygiagretinimas /

Abstract

dc:description

The Travelling Salesman Problem (TSP) is a well­-known problem in graph theory that is usually formulated as follows: the task is to find the shortest route by which the travelling salesman would visit all the required cities once and return to his starting city. Many exact and approximate algorithms have been devised to solve this problem. One category of approximate algorithms is called population ­based-algorithms. One of the best known population algorithms is called Ant Colony Optimization (ACO). It simulates the working of a real ant colony in search of the shortest route to food around obstacles. Several parallelization strategies have been considered for this algorithm. Artificial Bee Colony (ABC) algorithm is a newer and much less studied population­-based algorithm. It is decided to try to use one of the parallel versions of the ant colony optimization, called PACO, to parallelize two closely related versions of the ABC algorithm: Combinatorial Artificial Bee Colony (CABC) and quick Combinatorial Artificial Bee Colony (qCABC). In both versions each worker bee has its own route, which it repeatedly tries to improve using general subtour mutation (GSTM). The implemented algorithms are tested with several problem instances of different sizes from the TSP instance dataset “TSPLIB”. The results are compared with those of the PACO algorithm. Various combinations of the algorithms’ parameters are tested. Test results show that parallelization is beneficial for CABC and qCABC: good (but not optimal) tours are found after much less iterations with more cores.

Degree

thesis:*
Grantor dc:publisher
Institutional Repository of Vilnius University
Year dc:date
2023

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Pukšta, Andrius,

Rights

dc:rights
Statement dc:rights
  • info:eu-repo/semantics/openAccess
Language dc:language
lit

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Vilnius University
Base URL
epublications.vu.lt/oai
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Pukšta, Andrius,. Dirbtinės bičių kolonijos algoritmo keliaujančio pirklio uždaviniui spręsti lygiagretinimas /. Institutional Repository of Vilnius University, 2023. https://repository.vu.lt/VU:ELABAETD192847191&prefLang=en_US