**Solving the Travelling Salesman Problem by Using Artificial Bee Colony Algorithm**
\*\*This is a Double-blind review, please do not include authors information in this version \*\*
Received Date: \*date
Accepted Date: \*date
Published Date: \*date
**HIGHLIGHTS**
- The aim of finding the minimum cost of time or distance for Travelling Salesman Problem (TSP)
- Use of arificial bee colony algorithm to determine the minimum cost of time or distance
- Use of secondary data which consist of 29 cities in Bavaria in order to implement the algorithm
- The shortest distance obtained was 3974km
ABSTRACT
*Travelling Salesman Problem (TSP) is defined as a list of cities that must visit all cities that start and end in the same city with the aim of finding the minimum cost of time or distance. In this study, the Artificial Bee Colony (ABC) algorithm was used to resolve the TSP. ABC algorithms is an optimisation technique that simulates the foraging behaviour of honey bees and has been successfully applied to various practical issues. ABC algorithm has three types of bees that are used by bees, onlooker bees, and scout bees. In Bavaria from Library of Traveling Salesman Problem with the distance from a city to another city has been used to find the best solution of the shortest distance. The result shows that the best solution for the shortest distance that traveller have to travel all the 29 cities in Bavaria is 3974km.*
*Keywords: Travelling Salesman Problem, Artificial Bee Colony Algorithm, Optimisation*
# INTRODUCTION
Irish and British mathematicians, W. R. Hamilton and Thomas Kirkman have introduced Traveling Salesman Problem (TSP). TSP is the classic algorithmic which is mathematical problem that focused on optimization in the field of computer sciences and operations research in order to find a better solution for the problem that is the shortest, fastest and cheapest. The easiest way to convey the TSP is by describing the location as a set of nodes.
From the previous research, there are many definitions of TSP from each author. The first definition is stems from Kaspi, Zofi and Teller (2019). TSP is defined as a list of cities that a salesperson has to visit all the cities which are starting and ending in the same city with the goal of finding the minimum cost which is time or distance. Basically, the traveling salesman problem is defined as containing n for cities (vertices) and m for edges between 2 vertices is a weight as traveling time or distance.
Moreover, the generalized TSP is to cover all variants TSP which is a set of cities that includes depot and a subset. It is to cover some of the customers’ satisfactions and the main objective is to find the shortest total distance travelled by the salesman (Pandiri & Singh, 2019). However, the article that emanated by Khan and Maiti (2019) said that TSP is the standard combinatorial discrete optimization problem that consist of a set of N cities (vertices). So the objective of the problem is to find the shortest path that starting and visiting all the vertices once and return to the starting vertex.
There are several solutions to solve the TSP but the result is approximate and not always optimal. The TSP can uses the optimisation algorithm method to solve the problem faced by the salesman experiencing the problem, where the route distance that the salesman has to use to distribute the product from the original place and visited all the cities before going back to the original place. Besides that, the salesman also has to consider the cost of travel while distributing the product. In conclusion, the salesman need to find the shortest distance to travel all the city once and back to origin place.
The TSP can be formulated as an integer linear program. Miller-Tuckerm-Zemlin (MTZ) and Dantzig-Fulkerson-Johnson (DFJ) have proposed the formulation for TSP. The MTZ formulation is still useful in certain settings even though MTZ formulation is not stronger than DFJ formulation. Hence, in this study, DFJ formulation is used. The formulation can defined as follows:
(1)
Subject to:
(2)
(3)
(4)
where is the path goes from city i to city j, is the distance from city i to city j and Q is number of edges between the nodes.
Based on the above equation, the shortest distance will be determined for traveller to travel all the city once and back to origin place.
# RELATED WORKS
On the report by O'Neil and Hoffman (2019), TSP investigates the shortest path for pickup and delivery such as meal delivery and ride-sharing is meaningful in on-demand last-mile logistic. By using low-width decision diagrams in assignment problem assumptions duals as primal heuristic can find a good result within scrupulous time budgets.
In expert opinions of Akhand, Ayon, Shahriyar Siddique and Adeli (2019), TSP represents by all spider monkey wherever Swap Operator (SO) and Swap Sequence (SS) primarily based operations are utilized in separate spider monkey optimization that allows interaction among monkeys is getting the best result of TSP. The example of SOs is a global leader, local leader or randomly choose from the group of a spider monkey that conveyance regarding the exploitation of the involvement of other members. The result of the experiment exposes the effectiveness of discrete optimization of spider monkey for solving TSP.
Based on a basic genetic algorithm, combining crossover and dynamic mutation is an improved strategy that has been proposed to optimize mutation characters and gain population diversity. The convergence rate and best solution of the advanced algorithm show that it is superior to the standard, prepared selection and adaptive crossover probability of genetic algorithm and a new method for TSP are provided (Xu, Pei & Zhu, 2018).
Based on the random method, to overcome the optimized locations of the exit door for a safer emergency evacuation, ABC algorithm was proposed by Khamis et al. (2019) and as a result of ABC has fewer control parameters to be tuned to find the foremost optimal locations of the exit door. In representing the group of dynamics, it used a crowd evacuation model supported the Social Force Model (SFM) and becomes the premise for the optimizer of cost functions. By minimizing crowd evacuation times and increasing the amount of individuals being evacuated, the optimum locations of exit doors for a multi-room situation can improve the evacuation potency. It is additionally clearly incontestable that the optimized style of design is impressive in rising the evacuation efficiency underneath the various desired speeds of the group to evacuate.
# ARTIFICIAL BEE COLONY ALGORITHM
Based on the research done by Zuloaga and Moser (2017), Artificial Bee Colony (ABC) algorithm is one of the groups of "swarm intelligence" which refer to the collective behaviour of the decentralized and self-organized system, commonly composed by agents that follow uncomplicated rules where the communications lead to the evolution of intelligent behaviours.
In 2005, based on the intelligent foraging behaviour of the honey bee swarm, Dervis Karaboğa was introduced the ABC algorithm. As claimed by Mridula, Rahman and Ameer (2018), the colony of bees is divided into three types with a different method that approaches to the food which are the employed bees, onlooker bees and scout bees. Employed bees have visited food beforehand and moved the honey bees to the source of food while onlooker bees are waiting at the area to make a decision for choosing the food source and scout bees move arbitrarily inside the chosen area.
All employed bees produced the initial sources of food. The steps have to be repeated until met all the requirement. In the first step, employed bees have to find and determine the closet source of food in memory. After that, the food source has to evaluate because the employed bees should dance in the hive to tell the onlooker bees about the food source. Then, depending on the dance by employed bees, onlooker bees will choose one of their sources. The bees evaluated its nectar amount after choosing a neighbour around that. Determined and replaced the sources of food with the new sources of food that discovered by scout bees. The best sources of food are found (Guo, Li, Tang & Li, 2017).
Food sources, employed bees and unemployed bees are the parts of bee honey destructive behaviour which the behaviour patterns are unification and abandonment source of food (Lvshan, Dongzhi & Weiyu, 2017). The distance between honeycomb and the sources of food, the element of honey and the complication of takeout honey are the factors that affect the value of food source. Each employed bees has a one-to-one concurrence with its matching food source where it can share information obtained with other bees. To scrutinize and utilize the source of food is the main task for unemployed bees. Following bees make a decision whether to recruit or give up and detecting bees have to analyze the new food source.
The four phases that consist in ABC algorithm are illustrated in Figure 1.
Figure 1: Flowchart of the ABC Algorithm
(Source: Guo, Li, Tang & Li, 2017)
Based on Figure 1, there are four phases in the standard ABC algorithm. The phases are initialization of the parameters and population phase, employed bees phase, onlooker bees phase and scout bees phase. All the flow will repeat until all requirements met. The elaboration of these phases for ABC are described below:
**Initialization of The Parameters and Population**
is representing possible solution that randomly produced by a group of food sources *SN/2* where *SN* is the colony’s population size. The following equation is:
(5)
where and *D* denoted the number of problem dimension, rand(0,1) is a uniform random number in the range \[0,1\] and and are respectively to the upper and lower bounds for the dimension *jth*.
Then, the solution is calculated by the following equation:
(6)
where is the value of fitness, is the objective value of the solution and is the absolute value of .
**Employed Bee Phase**
In this phase, the employed bees will search for the food sources throughout the whole space. Every sources of food, is allocated to one and only employed bee and a new food source, is generated for each employed bees in the neighbourhood of the food sources and its present position as follows:
(7)
where *k* is different with *i*, , are randomly chosen indexes and is a uniformly distributed real number between \[-1,1\]. A greedy selection is performed according to their fitness values between and . Employed bees will share the information with onlooker bees about the nectar amount of food sources after complete the search.
**Onlooker Bee Phase**
Onlooker bees will evaluate the information of food sourced from employed bees and choose a source of food, based on its probability value as calculated in Eq(8):
(8)
where is the fitness value of the *ith* source of food, . The higher , the largest chance source of food to be selected. When the source of food, have been selected, one onlooker bee updates by using Eq. (7) and if the new source of food has equal or better fitness value than , a new member in the population is replaces by . Similar with employed bees phase, a greedy selection is performed according to their fitness values between and .
**Scout Bee Phase**
The number of scout bees is not defined beforehand in the colony. If the source of food, cannot be improved through a predetermined number of trial “limit”, the source of food, is to be abandoned and the corresponding employed bee becomes a scout. A new source of food, produced by the scout randomly as follows:
(9)
where *i* is the index of the employed bees whose “trail” values reaches the “limit” value firstly, , rand(0,1) is a uniform random number in the range \[0,1\] and and are respectively to the upper and lower bounds for the dimension *jth*.
The phase from 3.2 to 3.4 will be repeating until the termination criterion is satisfied.
# RESULTS AND DISSCUSSION
To solve the TSP, the secondary data is used to implement. The data is adopted from Library of Traveling Salesman Problem (TSPLIB) which is from Zuse Institute Berlin. The data set consists of 29 cities in Bavaria with a distance from a city to another city as shown in Table 1.
Table 1: The Nodes of 29 Cities
| **City** | **Node** | |
| -------- | -------- | ----- |
| | **X** | **Y** |
| 1 | 1150 | 1760 |
| 2 | 630 | 1660 |
| 3 | 40 | 2090 |
| 4 | 750 | 1100 |
| 5 | 750 | 2030 |
| 6 | 1030 | 2070 |
| 7 | 1650 | 650 |
| 8 | 1490 | 1630 |
| 9 | 790 | 2260 |
| 10 | 710 | 1310 |
| 11 | 840 | 550 |
| 12 | 1170 | 2300 |
| 13 | 970 | 1340 |
| 14 | 510 | 700 |
| 15 | 750 | 900 |
| 16 | 1280 | 1200 |
| 17 | 230 | 590 |
| 18 | 460 | 860 |
| 19 | 1040 | 950 |
| 20 | 590 | 1390 |
| 21 | 830 | 1770 |
| 22 | 490 | 500 |
| 23 | 1840 | 1240 |
| 24 | 1260 | 1500 |
| 25 | 1280 | 790 |
| 26 | 490 | 2130 |
| 27 | 1460 | 1420 |
| 28 | 1260 | 1910 |
| 29 | 360 | 1980 |
Meanwhile, Figure 2 shows the result of shortest distance obtained for traveller travel all the 29 cities in Bavaria. Based on the figure, form Iteration 1 until Iteration 5, the best or shortest distance is 4504km. Then, the distance decrease at 4473km from Iteration 6 to Iteration 8. From Iteration 9 until Iteration 23, the distance be more short which is remains constant at 4393km. For next iteration, the distance also decrease and remains constant at 4231km from Iteration 24 until Iteration 79. The shortest distance is 4151km at Iteration 80 to Iteration 191. The next iteration until last iteration which is Iteration 200, the shortest distance is 3974km. So, it can be concluded that, with the maximum iteration is 200, the shortest distance for travel all the cities on is 3974km.
Figure 1: The Shortest Distance for 200 Iteration
Table 2 below shows the optimum route of 29 cities with distance of 3974km. The traveller have to visit all 29 cities once and back to city 1. The route of all 29 cities are illustrated as in Figure 3.
Table 2: The Optimum Route of 29 Cities
| **City** | **Node** | |
| -------- | -------- | ----- |
| | **X** | **Y** |
| 1 | 1150 | 1760 |
| 8 | 1490 | 1630 |
| 4 | 750 | 1100 |
| 17 | 230 | 590 |
| 18 | 460 | 860 |
| 9 | 790 | 2260 |
| 3 | 40 | 2090 |
| 5 | 750 | 2030 |
| 12 | 1170 | 2300 |
| 26 | 490 | 2130 |
| 29 | 360 | 1980 |
| 28 | 1260 | 1910 |
| 25 | 1280 | 790 |
| 14 | 510 | 700 |
| 22 | 490 | 500 |
| 20 | 590 | 1390 |
| 15 | 750 | 900 |
| 10 | 710 | 1310 |
| 6 | 1030 | 2070 |
| 2 | 630 | 1660 |
| 13 | 970 | 1340 |
| 21 | 830 | 1770 |
| 27 | 1460 | 1420 |
| 7 | 1650 | 650 |
| 23 | 1840 | 1240 |
| 16 | 1280 | 1200 |
| 24 | 1260 | 1500 |
| 19 | 1040 | 950 |
| 11 | 840 | 550 |
| 1 | 1150 | 1760 |
Figure 3: Route of 29 Cities
# CONCLUSION
Artificial Bee Colony (ABC) algorithms is a technique of optimization that simulates honey bees’ foraging behaviour and has been successfully applied to various practical issues. A set of honey bees are able to perform tasks successfully through social cooperation that called swarm. In the ABC algorithm, there are three types of bees which are employed bees, onlooker bees, and scout bees. The employed bees will search food around the sources of food in the memory and all the collected information will be share to the onlooker bees. The onlooker bees tend to select the good sources of food that was found by the employed bees. The sources of food that has higher quality which is the best fitness value will have more chance for the onlooker bees to select the good source of food than the lower quality. The scout bees are translated from a few employed bees, which abandon their food sources and search new ones.
In this study, ABC algorithm have been used to solve the Travelling Salesman Problem (TSP) for the data that was collected from Library of Traveling Salesman Problem (TSPLIB) which is from Zuse Institute Berlin. The data set consists of 29 cities in Bavaria with the nodes for every city and a distance from a city to another city. MATLAB software version R2015a is used to solve the TSP Traveller has to visit all the 29 cities and back to the first city which is City 1. The result shows that the best solution for the shortest distance that traveller have to travel all the 29 cities is 3974km.
**REFERENCES**
Akhand, M. A. H., Ayon, S. I., Shahriyar, S. A., Siddique, N., & Adeli, H. (2019). Discrete Spider Monkey Optimization for Traveling Salesman Problem. *Applied Soft Computing*, 105887.
Guo, Y., Li, X., Tang, Y., & Li, J. (2017). Heuristic artificial bee colony algorithm for uncovering community in complex networks. *Mathematical Problems in Engineering*, *2017*.
Kaspi, M., Zofi, M., & Teller, R. (2019). Maximizing the Profit per Unit Time for the Travelling Salesman Problem. *Computers & Industrial Engineering*.
Khamis, N., Selamat, H., Ismail, F. S., Lutfy, O. F., Haniff, M. F., & Nordin, I. N. A. M. (2019). Optimized exit door locations for a safer emergency evacuation using crowd evacuation model and artificial bee colony optimization. *Chaos, Solitons & Fractals*, 109505.
Khan, I., & Maiti, M. K. (2019). A swap sequence based artificial bee colony algorithm for traveling salesman problem. *Swarm and evolutionary computation*, *44*, 428-438.
Lvshan, Y., Dongzhi, Y., & Weiyu, Y. (2017, November). Artificial bee colony algorithm with genetic algorithm for job shop scheduling problem. In *2017 International Symposium on Intelligent Signal Processing and Communication Systems (ISPACS)* (pp. 433-438). IEEE.
Mridula, K. M., Rahman, N., & Ameer, P. M. (2018). Sound velocity profile estimation using ray tracing and nature inspired meta-heuristic algorithms in underwater sensor networks. *IET Communications*, *13*(5), 528-538.
O’Neil, R. J., & Hoffman, K. (2019). Decision diagrams for solving traveling salesman problems with pickup and delivery in real time. *Operations Research Letters*, *47*(3), 197-201.
Pandiri, V., & Singh, A. (2018). A hyper-heuristic based artificial bee colony algorithm for k-Interconnected multi-depot multi-traveling salesman problem. *Information Sciences*, *463*, 261-281.
Xu, J., Pei, L., & Zhu, R. Z. (2018). Application of a genetic algorithm with random crossover and dynamic mutation on the travelling salesman problem. *Procedia computer science*, *131*, 937-945.
Zuloaga, M. S., & Moser, B. R. (2017, July). Optimizing resource allocation in a portfolio of projects related to technology infusion using heuristic and meta-heuristic methods. In *2017 Portland International Conference on Management of Engineering and Technology (PICMET)* (pp. 1-23). IEEE.