Keywords

1 Introduction

Ant colony optimisation (ACO) is a bioinspired mechanism used in genetic programming to solve complex probabilistic problems. ACO was invented in 1992 by Marco Dorigo in his PhD thesis [1]. The ant colony optimisation algorithm is widely used because of the use of positive feedback mechanism, heuristic probability, computing distributed numeric information, and other characteristics. The ACO algorithms are used for solving the different problems of discrete mathematics and operation search such as the quadratic assignment problem and travelling salesman problem (TSP). In the ACO, we use a mixture of some advance and run-time knowledge for making decisions in the formula. TSP is a NP-hard problem which can be developed to be an admissible solution for any other problem that belongs to the NP-hard class [2]. In this paper roulette wheel selection is used, which is the most democratic selection method where the selection of parents is based upon their fitness. The better chromosomes are selected so that they can give feasible results. The algorithm generates random numbers in the initial phase of tour construction to select the city randomly based on probability of finding the city in the search area [3]. The other sections of this paper are as follows; Sect. 2 gives the background detail of TSP and explains the algorithm. Section 3 explains the roulette selection which is used in the ACO framework and Sect. 4 describes the implementation part with the test and results.

2 Ant Colony Optimisation for TSP

2.1 TSP

The problem of finding an optimal path between n number cities is known as TSP. The TSP is a most significant problem first posed by the Irish mathematician W. R. Hamilton in the nineteenth century [4]. This problem has also been intensely studied in operations research and other areas since 1930. Formally, TSP can be represented by a complete weighted graph, G = (V, E), in which V represents a set of n vertices and E represents a set of bidirectional edges between V i , V j € V, and minimize the vertices ∑n i  = 0 W i,j , where W i,j is used to represent an edge weight between two vertices V i and V j .

2.2 Ant Colony Optimisation

The ant colony meta-heuristic is an advanced approach for finding the solution of difficult problems with the help of a bioinspired approach from the behaviour of natural ants [5]. In ACO we use artificial ants which work similarly to natural ants for searching a good solution of the optimisation problem, whereas applying the ACO optimisation problem converts it into a weighted graph problem for finding the best feasible path [6]. The ACO algorithm is divided into three main parts as follows.

Tour Construction

We start constructing our tour by placing ants at random places (vertices) in our graph where each ant will decide which is the best path to reach the next vertex by taking the next move based on the formula

$$\rho_{xy}^{k} = \left\{ {\begin{array}{*{20}l} {\frac{{\left[ {\tau_{xy} (t)} \right]^{\alpha } \left[ {\eta_{xy} } \right]^{\beta } }}{{\sum\nolimits_{{\mu \in J_{k(x)} }} {\left[ {\tau_{x\mu } (t)} \right]^{\alpha } \left[ {\eta_{x\mu } } \right]^{\beta } } }}} \hfill & {{\text{if}}\,y \in J_{k(x)} } \hfill \\ 0 \hfill & {\text{otherwise}} \hfill \\ \end{array} } \right.$$
(1)

where ρ is the probability of the ant to move from one vertex to another. The variable τ is used to represent the quantity of pheromone while searching for food, and α is a heuristic constant which is used for finding the paths due to its greedy approach [7]. This is the case where the inverted distance is 1/distance between the city x and y and raised to the power of β is also a heuristic constant which describes the speed of selecting paths by ants and everything calculated until it is divided by the summations of every solution. The record of cities where the ant k passes is kept in the tabu list (tabuk) [8].

Pheromone Update

After construction of the tour, updating of residual information is performed when all the ants finish their traversing. This is the formula:

$$\tau_{xy} (t + n) = ( 1{-}\rho ) \times \tau_{xy} (t) +\Delta \tau_{xy} (t)$$
(2)

where

$$\Delta \tau_{xy} (t) = \sum_{k = 1} m\Delta \tau_{xy}^{k} (t)$$
(3)

τ is the absolute pheromone amount which gets deposited for worker (ant) k on the edge xy. ρ refers to the pheromone volatisation coefficient and (1 − ρ) represents the delay of pheromone ranges 0–1 [9].

Terminating Condition

If the terminating condition is satisfied (i.e., all the cities are visited and no city is repeated), the circulation will stop. Compare all the best solutions previously updated in the tabu list (tabuk) in every iteration and find the optimal solution; otherwise empty the tabu list and continue the iteration.

2.3 Genetic Algorithm

A genetic algorithm approach is inspired from the chromosomes which are used to solve complex problems [10]. They are used to handle the population of possible solutions where each solution represents a chromosome containing an abstract representation [11]. The genetic algorithm iteration has these phases:

  • Selection phase The selection process defines the fitness of randomly selected individuals.

  • Reproduction This process uses both recombination and mutation for producing new chromosomes.

  • Evaluation In this process evaluation is done on the basis of fitness of new chromosomes.

  • Replacement In this process, old chromosomes are replaced by the new ones.

3 Roulette Wheel Selection

In the roulette wheel selection method [12], we use the random number generation mechanism for selecting the best path. In the roulette wheel selection mechanism the spinning of each segment is according to the probabilities of selecting parent values with the most fitness having more probability to be chosen. The largest segment is occupied by the fittest individual whereas in correspondence the smaller segment is occupied by the least fit within the roulette wheel [13]. The circumference of the roulette wheel is considered as the sum of all segments on the surface of the wheel [14]. In this selection mechanism, selection is done by finding the probability of individual K, P(Choice zK) as defined with the equation as

$$P\left( {\text{Choice zK}} \right) = \frac{{{\text{def fitness }}\left( K \right) }}{{\sum {n_{jz} } ,{\text{fitness }}\left( j \right)}}$$
(4)

Here’s some pseudo-code of the roulette wheel selection for computing fitness of the individual.

4 Experiments and Results

4.1 Problem Formulation

The aim of this paper is to solve the TSP problem which is a NP-hard problem by using the ACO meta-heuristic. NP problems are nondeterministic polynomial time problems; the NP-complete problems are hard once whose solutions can deal with any other NP problem in polynomial time. We can also find suboptimal solutions of NP problems which may be found in polynomial time.

4.2 Experimental Setup

While going for the implementation part, we solve the NP problem taking an example of a travelling salesman problem in which a travelling salesman wants to visit 100 different cities by driving through roads, starting and ending his trip at home. This algorithm is performed in MATLAB®. The results show the graphical output of 100 cities of different states in India and generate the optimal solution with respect to iterative time and iterative best cost.

4.3 Experimental Results

While performing the experiment to solve TSP we have to define the starting and ending nodes of our round trip so that we can easily calculate the distance of the round trip. In this real-life example we collect the data of 100 cities which a travelling salesman has to visit by defining “Saharanpur” as the starting and ending node of our round trip as shown in Table 1. In the table we describe the number of cities [15] and their respective names [16]. As defined in our problem the salesperson has to visit 100 cities for delivering products following a shortest route where the salesperson has to visit each city exactly once. In our results the salesperson visits all 100 cities defined in the table with the optimal distance of 6435.302 km.

Table 1 100 cities on which optimisation is performed
Full size table

In the ant colony algorithm we take these parameters’ values as α = 1, β = 5, Q = 10, C = 100, ρ = 0.65, and λ = 0.15. In this TSP problem we take 100 different locations with their geocoordinate values in the input file and set input type as geo. Figure 1 shows the output path of the optimised route which is then drawn on the map of India. Figure 2 shows the states it covers and Fig. 3 shows the graph of the number of iterations with respect to the cost of the optimal path calculated.

Fig. 1
figure 1

The output path of the optimised route which is then drawn on the map of India

Full size image
Fig. 2
figure 2

The states it covers

Full size image
Fig. 3
figure 3

The graph of the number of iterations with respect to the cost of the optimal path calculated

Full size image

5 Conclusion

We concluded from the proposed work that the roulette wheel selection method is an efficient selection method which is used in the ant colony optimisation (ACO) algorithm for finding the optimal route of the travelling salesman problem. The results also revealed that the roulette-based selection explores the search space and visits the 100 cities with the lowest iterative cost with respect to iterative time for the defined tour. Future work could be evaluated by using the variable neighbourhood search heuristic in the ACO framework with the combination of different selection strategies such as the tournament-based selection strategy and rank-based selection strategy for the travelling salesman problem and its variants.