International Journal of Emerging Technology and Advanced Engineering

Website: www.ijetae.com (ISSN 2250-2459, Volume 2, Issue 5, May 2012)

A Survey Paper on Solving Travelling Salesman

problem Using Bee colony optimization
Lalit Kumar Bansal
M.Tech Student, SUS College of Engineering and Technology, Tangori (Mohali) India
[email protected]

Abstract Traveling Salesman Problem (TSP) is about

finding a Hamiltonian path with minimum cost. Travelling II. TRAVELLING SALESMAN PROBLEM
salesman problem (TSP) finds its application in many real Assume that a salesman is given a set of cities along
world industrial applications including the areas such as with traveling distances (or costs) from one city to
logistics, transportation, and semiconductor industries. few
potential applications of TSP includes finding an optimized
another city. The salesman is obligatory to explore each
scan chains route in integrated chip testing, parcels city (while traveling the salesman must visit every city
collection and sending in logistics companies, and only once and then return to the starting city) with least
transportation routing problem. This paper gives a brief distances (or costs). The outcome of TSP is to conclude a
overview of the various approaches that have been Hamiltonian tour with minimum cost. Generally, TSP can
implemented to solve TSP and specifically bee colony be denoted via graph notations as follows:
optimization (BCO) for solving TSP. The BCO model is Let G = (V, E) be a graph. V is a set of x cities, V = {v1,
constructed algorithmically based on the collective , vx}. E is a set of arcs or edges, E = {(p,q ): p, q V}.
intelligence shown in bee foraging behavior. E is usually coupled with a distance (or cost) matrix,
which is defined as D = (d). If d p, q = dq, p, the problem is
Keywords- bee colony optimization, foraging
a symmetric TSP (STSP) else it belongs to asymmetric
behavior, heuristic search, travelling salesman problem,
TSP (ATSP). In TSP, the purpose is to establish the
waggle dance
permutation of set V that minimizes the total roundtrip
distance as shown in Equation (1). Overview and
I. INTRODUCTION
fundamental concepts about TSP can be referred from
[5], [6].
Animals such as ant, bee, fish, and cockroach show
a-1
many interesting collective behaviors. A colony of honey
C()= d(j),(j+1) + d(a),(1) (1)
bees can extend itself over long distances and in multiple j=1
directions simultaneously to exploit a large number of
food sources. An example will be the highly coordinated
Various techniques used to solve TSP.
pattern shown in their foraging and aggregation
In general, these techniques are classified into two broad
behaviors. The individuals in the beehive usually perform
categories:
their actions locally with limited knowledge about the
First are Exact and the other one is Approximation
entire system. However, when their local actions are
algorithms [2].
combined, they emerge to produce global effects.
A. Exact algorithms
This paper describes the work in applying the Bee
Exact algorithms are methods which make use of
Colony Optimization (BCO) model, which is based on
mathematical models while approximation algorithms
foraging behavior in bee colony, to Traveling Salesman
make use of heuristics and iterative improvements for
Problem (TSP). This research is inspired by [1], on using
problem solving process. Some examples of exact
a new honey bee algorithm for dynamic allocation of
methods category are Lagrangian Relaxation, Branch and
Internet servers. The paper starts with a discussion on
Bound, Integer Linear Programming etc.
TSP in Section II. Literature survey has been shown in
B. approximation algorithms
section II. A discussion on BCO model is presented in
The approximation algorithms are of two types:
Section IV. Finally, this paper ends with conclusions and
1) Constructive heuristics
future works.
constructive heuristics includes instances such as, Greedy
Heuristics, Nearest Neighborhood, Insertion Heuristics
[3], Christofides Heuristics [4] etc.

309
 International Journal of Emerging Technology and Advanced Engineering
Website: www.ijetae.com (ISSN 2250-2459, Volume 2, Issue 5, May 2012)
A greedy algorithm is an algorithm that follows the improved solution. Local search methods have a tendency
problem solving heuristic of making the locally optimal to become stuck in suboptimal regions or on plateaus
choice at each stage with the hope of finding a global where many solutions are equally fit. Tabu search
optimum. On some problems, a greedy strategy need not enhances the performance of these techniques by using
produce an optimal solution, but nonetheless a greedy memory structures that describe the visited solutions or
heuristic may yield locally optimal solutions that user-provided sets of rules. If a potential solution has
approximate a global optimal solution. been previously visited within a certain short-term period
The nearest neighbor algorithm was one of the first or if it has violated a rule, it is marked as "taboo" so that
algorithms used to determine a solution to the travelling the algorithm does not consider that possibility
salesman problem. In it, the salesman starts at a random repeatedly.
city and repeatedly visits the nearest city until all cities The ant colony optimization algorithm (ACO) is a
have been visited. It quickly yields a short tour, but probabilistic technique for solving computational
usually not the optimal one. problems which can be reduced to finding good paths
The insertion heuristic algorithm gradually builds a route through graphs. The algorithm aims to search for an
by inserting at each step a vertex in its neighborhood on optimal path in a graph, based on the behavior of ants
the current route, and performing a local reoptimization. seeking a path between their colony and a source of food.
This is done while checking the feasibility of the Researchers focus on TSP from various disciplines
remaining part of the route. Backtracking is sometimes because of its easy initiation, complicated to solve but
necessary. Once a feasible route has been determined, an possess numerous applications.
attempt is made to improve it by applying a post-
optimization phase based on the successive removal and III. LITERATURE SURVEY
reinsertion of all vertices. Because of many similarities between server and
The goal of the Christofides heuristic algorithm (named honey bee colony forager allotment, [1] proposed a new
after Nicos Christofides) is to find a solution to the decentralized honey bee algorithm which with dynamism
instances of the traveling salesman problem where the allocates servers to give surety of request loads. The work
edge weights satisfy the triangle inequality. is compared in opposition to an omniscient optimality
2) Improvement heuristics. algorithm, a conventional greedy algorithm, and an
Instances in improvement heuristic include k-opt [5], Lin- algorithm that computes omnisciently the optimal static
Kernighan Heuristics [6] [7] [23], Simulated Annealing allocation. They evaluated performance on simulated
[8], Tabu Search [9], Evolutionary Algorithms [10] [11] request streams and commercial trace data. The algorithm
[12], Ant Colony Optimization [13] [14], Bee System shows better result than static or greedy for highly
[15] etc. variable request loads, but greedy can outperform the
In combinatorial optimization, LinKernighan is one of method under low changeability.
the best heuristics for solving the Euclidean traveling A number of results were developed, by Chandra and
salesman problem. It briefly involves swapping pairs of Tovey [5] some worst-case and some probabilistic, on the
sub-tours to make a new tour. It is a generalization of 2- performance of 2- and k-opt local search for the TSP,
opt and 3-opt. 2-opt and 3-opt work by switching two or with respect to both the quality of the solution and the
three paths to make the tour shorter. LinKernighan is speed with which it is obtained.
adaptive and at each step decides how many paths An implementation of the Lin-Kernighan heuristic, one of
between cities need to be switched to find a shorter tour . the most effective methods for giving optimal or near
Simulated annealing (SA) is a generic probabilistic optimal solutions for the symmetric TSP is described [7],
metaheuristic for the global optimization problem of [13] Computational tests show that the implementation is
locating a good approximation to the global optimum of a highly valuable.
given function in a large search space. It is often used Vanlaarhoven [8] offered a quantitative study of the
when the search space is discrete (e.g., all tours that visit typical behavior of the simulated annealing algorithm
a given set of cities). For certain problems, simulated based on a cooling schedule obtainable previously by the
annealing may be more efficient than exhaustive authors. The study is based on the analysis of numerical
enumeration provided that the goal is merely to find results obtained by systematically applying the algorithm
an acceptably good solution in a fixed amount of time, to a 100-city TSP. The prospect and the variance of the
rather than the best possible solution. cost are analyzed as a function of the control parameter of
Tabu search is a local search method used for the cooling schedule
mathematical optimization. Local searches take a Even though K-OPT are not the fastest TSP solution
potential solution to a problem and check its immediate method, it is widely recognized as a performance
neighbors (that is, solutions that are similar except for benchmark.
one or two minor details) in the hope of finding an
310
 International Journal of Emerging Technology and Advanced Engineering
Website: www.ijetae.com (ISSN 2250-2459, Volume 2, Issue 5, May 2012)
Tabu search and its application to the symmetric TSP, Algorithm (PS-EA) have been compared. The results
which is a classic combinatorial optimization problem is showed that ABC outperforms the other algorithms.
shown by Knox [9]The results of Tabu search is Traditionally, chess has been called the "fruit fly of
compared to the K-OPT procedure using six test Artificial Intelligence". In recent years, however, the
problems drawn from the literature focus of game playing research has gradually shifted
The combination of local search heuristics and genetic away from chess towards games that offer new
algorithms is a capable approach for finding near- challenges highlighted by Rijswijk [20]. These challenges
optimum solutions to the traveling salesman problem consist of large branching factors and imperfect
(TSP). An approach is offered in which local search information. The key ideas about Queen Bee are
techniques are used to find local optima in a given TSP presented in the approach.
search space, and genetic algorithms are used to search Chong and Gay [21] presented a novel approach that
the space of local optima in order to find the global uses the honey bees foraging model to solve the job shop
optimum. In this Merz utilized[10] new genetic operators scheduling problem.
for realizing the proposed approach are described, and the Chong and Gay proposed a population-based approach
quality and efficiency of the solutions obtained for a set that uses a honey bees foraging model to solve job shop
of symmetric and asymmetric TSP instances are scheduling problems. [22]The algorithm uses an efficient
discussed. neighborhood structure to search for reasonable solutions
White and yen give details the development of a and iteratively progress on prior solutions. The primary
Hybrid Evolutionary Algorithm for solving the Traveling solutions are generated using a set of priority dispatching
Salesman Problem (TSP).[12] The stratagem of the rules. Experimental results comparing the proposed
algorithm is to broaden the successful results of a genetic honey bee colony approach with existing approaches
algorithm (GA) using a distance preserving crossover such as tabu search, ant colony and shifting bottleneck
(DPX) by including memory in the form of ant procedure on a set of job shop problems are presented.
pheromone during the city selection process. The .
synergistic combination of the DPX-GA with city IV. THE BCO MODEL FOR TSP
selection based on probability found out by both distance
and previous success adds additional information into the Various bees models have been attempted in different
search mechanism. This combination into a Hybrid GA domains ranging from dynamic server allocation for
facilitates finding quality solutions for TSP problems internet hosting center [1], numerical function
with lower computation complexity. optimization[19], hex game playing program [20], job
MAX --MIN Ant System, an enhanced version of shop scheduling [21] [22], to TSP.
basic Ant System, and report the results for its application
to symmetric and asymmetric instances of Traveling
Salesman Problem. Hoos [14] show how MAX --MIN
Ant System can be significantly refined extending it with
local search heuristics. The results show that MAX --
MIN Ant System has the property of effectively guiding
the local search heuristics towards promising regions of
the search space by generating good initial tours.
Seeley et al. [18] studied the extent to which scout
honey bees gain information from waggle dances the
whole time their careers as foragers.
Swarm intelligence is a research branch that models
the population of interacting agents or swarms that are
able to self-organize. An ant colony, a flock of birds or an
immune system is a typical example of a swarm system.
Bees swarming around their hive is also an example of
swarm intelligence. Artificial Bee Colony (ABC) The
approach proposed by Karaboga and Basturk [19] is an
optimization algorithm based on the intellectual behavior
of honey bee swarm.
In this work, ABC algorithm is used for optimizing
multivariable functions and the results produced by ABC, Figure1. Flow chart for foraging process of honey bees
Genetic Algorithm (GA), Particle Swarm Algorithm
(PSO) and Particle Swarm Inspired Evolutionary

311
 International Journal of Emerging Technology and Advanced Engineering
Website: www.ijetae.com (ISSN 2250-2459, Volume 2, Issue 5, May 2012)
BCO model is a population based search algorithm The state transition rule from one city to another is based
mimics the food foraging behavior of swarms of honey on two parameters:
bees [16]. The algorithm performs a kind of Arc fitness
neighborhood search combined with random search. The Heuristic distance
basic approach behind the BCO is to produce the multi A higher fitness value is assigned for a path which is a
agent system (colony of artificial bees) skilled to part of preferred path. Because of heuristic distance
successfully solve difficult combinatorial optimization influence a bee tends to choose the next visiting city
problems. The artificial bee colony behaves partially which is nearest to current city. State transition
alike, and partially differently from bee colonies in probability gives the likelihood to move from city i to
nature. city j after n transitions. It is a function of the distance
between cities and of the arc fitness present on
When a honeybee scout finds food, she uses two known connecting edge.
tools to understand where it is. One is her solar compass,
which lets her remember where things are in relation to Pij (t) = [ij (t) . [1/dij]
the sun. [17][18]The bee's ability to see polarized light (2)
lets her determine where the sun is regardless of whether [ij(t)].[1/dij]
j Ai (t)
it is masked by clouds. The other tool is her internal
clock, which lets her keep track of how far she has flown. Where ij (t) is the arc fitness from city I to city j after n
transitions,
When she returns to the hive, the scout bee recruits her dij represents the distance between city i and city j,
sisters to carry the food back to the nest. They, like the represents a binary variable that turns on or off the arc
scout, are the oldest bees in the hive. The scout fitness influence in the model, and
distributes samples of the food, which will help her is to control the significant level of heuristic distance.
sisters find the food when they reach their destination. The general procedure that is followed by bee for solving
Then, she performs a dance on the vertical surface of the TSP is shown below:
combs in the hive. The area on which she performs the
dance is commonly known as the dance floor, and the Procedure BCO
worker bees who observe the dance are followers. Initialize_Population ( )
If the food is nearby, the bee performs a round dance by While stop criteria are not fulfilled do
traveling in loops in alternating directions. The round While all bees have not built a complete path do
dance doesn't convey much information about exactly Observe_Dance ( )
where the food is. However, it's generally close enough Forage_ByTransRule ( )
that the worker bees can smell it fairly quickly. Perform_Waggle_Dance ( )
End while
When the food is far away, the scout performs a waggle End while
dance. During the waggle dance, the scout runs in a End procedure BCO
straight line while waggling her abdomen, and then
returns to the starting point by running in a curve to the The waggle dance performed by bees can be illustrated as
left or right of the line [17] [18]. The straight line follows in figure:
indicates the direction of the food in relation to the sun. If
the bee runs straight up the hive wall, then the foragers
can find the food by flying toward the sun. If she runs
straight down the wall, then the foragers can find the food
by flying away from the sun. As the dance progresses, the
dancing bee adjusts the angle of the waggle run to match
the movement of the sun.
C. Path Construction in Bee

The scout bees after moving randomly generates two set

of paths namely preferred path and possible path.
Possible path set contains the cities that can be visited
from the current city. The preferred path set contains the
cities that results in more economic move in terms of cost
as well as distance. Figure2. Waggle dance performed by scout bees after finding
food source

312
 International Journal of Emerging Technology and Advanced Engineering
Website: www.ijetae.com (ISSN 2250-2459, Volume 2, Issue 5, May 2012)
In the above figure the bees communicate via the [7] K. Helsgaun, "An effective implementation of the
waggle dance, the dance gives the angle of the food Lin-Kernighan traveling salesman heuristic,"
source with respect to sun, here angle is denoted by , European Journal of Operational Research, vol.
and distance is shown by the long run which is 1 km here 126, no. 1, pp. 106-130, 2000.
in the figure. [8] J. H. M. K. E. H. L. Aarts and P. J. M.
V. CONCLUSION AND FUTURE WORK
Vanlaarhoven, "A quantitative analysis of the
simulated annealing algorithm- A case study for the
This paper presents a glance of various approaches traveling salesman problem," Journal of Statistical
being used to solve TSP. The Bee Colony Optimization is Physics, vol. 50, no. 1-2, pp. 187-206, 1988.
highlighted for Travelling Salesman problem with its [9] J. Knox, "Tabu search performance on the
basic mechanism of bees foraging behavior and its symmetric traveling salesman problem," Computers
efficiency in solving shortest path among various routes. & Operations Research, vol. 21, no. 8, pp. 867-876,
Among the future enhancements are incorporating 1994.
neighborhood search in the model. Neighborhood search [10] B. F. a. P. Merz, "A genetic local search algorithm
is useful when exploitation is desired. It can be applied for solving symmetric and asymmetric traveling
after every bee cycle to enhance the quality of solutions. salesman problem," in in Proceedings of
BCO can be combined with other heuristic techniques Internotional Conference on Evolutionary
such as k-opt local search, Tabu search to get more fine Computation, 1996.
results. Constructive heuristics can also be included in [11] P. M. a. B. Freisleben, "Genetic local search for the
preparing preliminary solutions. This helps the BCO TSP: New results," in in Proceedings of the 1997
algorithm to have a enhanced starting point in its search IEEE InternationalConference on Evolutionary
for finest solutions. More bees related features such as Computation, 1997.
the direction shown in waggle dance and scent sensing
can be included to make the model broader. [12] C. M. White and G. G. Yen, "A hybrid evolutionary
algorithm for traveling salesman problem," in in
REFERENCES Proceedings of Congress on Evolutionary
Computation, 2004.
[1] S. Nakrani and C. Tovey, "On honey bees and [13] L. M. Gambardella and M. Dorigo, "Solving
dynamic server allocation in Internet hosting symmetric and asymmetric TSPs by ant colonies," in
centers," Adaptive Behavior, vol. 12, no. 3-4, pp. in Proceedings of IEEE International Conference on
223-240, 2004. Evolutionary Computation, 1996.
[2] G. Laporte, "The traveling salesman problem: An [14] T. S. a. H. Hoos, "MAX-MIN ant system and local
overview of exact and approximate algorithms," search for the traveling salesman problem," in in
European Journal of Operational Research, vol. 59, Proceedings of ICEC'97 - 1997 IEEE 4th
no. 2, pp. 231-247, 1992. International Conference on evolutionary
Computation, 1997.
[3] R. E. S. D. J. Rosenkrantz and P. M. Lewis, "An
analysis of several heuristics for the traveling [15] P. L. a. D. Teodorovic, "Computing with Bees:
salesman problem," SIAM Journal on Computing, Attacking Complex Transportation Engineering
vol. 6, no. 3, pp. 563-581, 1977. Problems," International Journal on Artificial
Intelligence Tools, vol. 12, no. 3, pp. 375- 394,
[4] A. M. Frieze, "An extension of Christofides heuristic
2003.
to the kperson travelling salesman problem,"
Discrete Applied Mathematics, vol. 6, no. 1, pp. 79- [16] K. v. Frisch, "Decoding the language of the bee,"
83, 1983. Science, vol. 185, no. 4152, pp. 663-668, 1974.
[5] H. K. B. Chandra and C. Tovey, "New results on the [17] F. C. Dyer, "The biology of the dance language,"
old k-opt algorithm for the traveling salesman Annual Review of Entomology, vol. 47, pp. 917-949,
problem," SIAM journal of computing, vol. 28, no. 6, 2002.
pp. 1998-2029, 1999. [18] J. C. Biesmeijer and T. D. Seeley, "The use of
[6] S. Lin and B. W. Kerninghan, "An effective waggle dance information by honey bees throughout
heuristic algorithm for the traveling salesman their foraging careers," Behavioral Ecology and
problem," Operations Research, vol. 21, no. 2, pp. Sociobiology, vol. 59, no. 1, pp. 133-142, 2005.
498-516, 1973.

313
 International Journal of Emerging Technology and Advanced Engineering
Website: www.ijetae.com (ISSN 2250-2459, Volume 2, Issue 5, May 2012)
[19] D. Karaboga and B. Basturk, "A powerful and
efficient algorithm for numerical function
optimization: artificial bee colony (ABC)
algorithm," Journal of Global Optimization, vol. 39,
no. 3, pp. 459-471, 2007.
[20] J. V. Rijswijck, "Are bees better than fruitflies?
Experiments with a hex playing program," in in
Proceeding of 13th Biennial Conference of the
Canadian Society for Computational Studies of
Intelligence, 2000.
[21] Y. H. M. L. A. I. S. C. S. Chong and K. L. Gay, "A
bee colony optimization algorithm to job shop
scheduling," in in Proceedings of the 2006 Winter
Simulation Conference, 2006.
[22] Y. H. M. L. A. I. S. C. S. Chong and K. L.Gay,
"Using a bee colony Algorithm for neighborhood
search in job shop scheduling problems," in in
Proceeding of 21st European Conference on
Modeling and Simulation (ECMS 2007), 2007.
[23] K. Helsgaun, "An effective implementation of the
Lin- Kernighan traveling salesman heuristic," in
Roskilde University, 1998.

314