The Traveling Salesman Problem (TSP) consists of, given a set of n cities with distances between each pair, starting from an initial point, finding the shortest path to visit all the cities exactly once, and returning to the starting point.
The idea behind the Artificial Bee Colony algorithm is to generate food sources, where each source represents a solution to the TSP, and then attempt to improve this solution through local searches. Whenever a food source is exhausted, meaning it can no longer be improved, it is replaced by a new food source (a new solution).
Each solution found is compared with the best solution obtained so far, ensuring that the final solution will be the best among all iterations.
The search space contains only feasible solutions, and the neighborhood structure uses a local search with two possible moves:
- 2-opt move
- Vertex swap
For parallelization, the mpicc library was used, which enables the use of MPI (Message Passing Interface) with C++.
The parallel algorithm works as follows: after a set number of processes are created, each one generates an initial solution (food sources), and from there, the evaluations of solutions are carried out in parallel.
The TSP implemented here is the symmetric TSP.
The instancias folder contains the test instances for execution.
The instances are also available in TSPLIB, but the ones used here include some modifications.
The accepted instance format is:
<numberOfVertices>
<vertex0> <coordinateX0> <coordinateY0>
<vertex1> <coordinateX1> <coordinateY1>
...
and continues up to vertex <numberOfVertices - 1>.
After running make in the terminal:
1. Execute lamboot (if not already running).
2. Run:
mpirun -np n ./main i
Where:
- n = number of processes
- i = name of the instance
At the end of execution, the following results are printed in the terminal:
- Route
- Total sum of the route’s edges
- Execution time in seconds
Copyright (c) 2019 Felipe Ferreira Carvalho Silva, Iagho Cristian Chagas, Lorena Kerollen Botelho Tavares, Rodrigo Pinto Herculano, William Davi Coelho