1 Introduction

Metaheuristics and especially nature-inspired ones have been the most applicable algorithms in combinatorial optimization problems over the last three decades; this is due to the importance of combinatorial optimization in the scientific world as well as the industrial world; to that end, several scientific studies are conducted about the most successful processes in nature, including biological systems, physical, and chemical processes such as natural evolution, swarm intelligence, annealing process, in a numerical algorithm [1–5]. Most combinatorial optimization problems are NP-hard [6–8], and the optimal or even suboptimal solution is typically difficult to be found. The metaheuristic method provides many advantages over an exact method. In some practical applications, the search of an optimal solution can be completely inappropriate due to many factors: the size of problem, the dynamic of work environment, the lack of precision in data collection, the difficulty in formulating some constraints or the presence of conflicting objectives, and sometimes a large number of real problems are not optimizable effectively by purely mathematical approaches. In this case, using an exact method has been often much slower than metaheuristic, which can cause additional costs in computation time. Nevertheless, nature-inspired algorithms still pose a real challenge in the sense to solve realistically large problem instances in reasonable computation time, such as ant colony optimization (ACO) [9], particle swarm optimization (PSO) [10, 11], bee colony optimization [12], firefly algorithm (FA) [13], cuckoo search (CS) [14], and very recently, bat algorithm (BA) [15]; it is, mainly, applied in continuous optimization problems [16], that is inspired by echolocation behavior of bats in searching for the optimum.

The travelling salesman problem (TSP) is one of the well-known and extensively studied problems in discrete or classical combinatorial optimization. The goal of this problem is to find the shortest tour that visits each city in a given list exactly once and then returns to the starting city. TSP is known to be a NP-hard problem [17], it is easy to describe but very difficult to solve. For a symmetric TSP with n cities, there are (n − 1)!/2 possible tours, the easiest way to find a solution is to seek the possibility of all existing paths then choose the shortest one, as a result the computational time complexity of this algorithm will be exponential to the size of n given cities in factorial time O(n!). Table 1 shows the time required to calculate tours if one tour evaluated in 1 ns (10−9 s).

Table 1 The computation time estimated if one tour requires 1 ns
Full size table

The TSP has wide applicability in many industrial applications [18–21] such as analysis of the structure of crystals in X-ray crystallography, computer wiring and connecting components on a computer board, overhauling gas turbine engines, the order-picking problem in warehouses, the vehicle routing problem and scheduling problems, and many others. In real life, the process of finding a solution for this kind of problems is already in progress and attracts many researchers to investigate great efforts in developing novel methods.

Many studies have been devoted to solve TSP such as Tabu search (TS) [22], simulated annealing (SA) [23], genetic algorithms (GA) [24, 25], and greedy randomized adaptive search procedure (GRASP) [26]. Recently, in the last 15 years, several studies based on nature-inspired algorithms or swarm intelligence methods have been proposed for the solution of the TSP, such as ACO [27–30], PSO [31–33], CS [34], and many more metaheuristic algorithms. BA is a new metaheuristic developed by Yang in 2010: It is inspired from bats echolocation system used to find their prey. This novel algorithm was originally developed for solving continuous optimization problems, and typically, BA has proven to be effective in solving this field of optimization. The main aim of this paper is to introduce a new discrete variant of bat algorithm (DBA) to solve symmetric travelling salesman problem (STSP) and to test its efficiency compared to other nature-inspired and classic metaheuristic algorithms.

The remaining part of this paper is organized as follows: Sect. 2 provides a brief literature review of swarm intelligence algorithms and especially of BA. Section 3 introduces the standard BA. Section 4 describes briefly the TSP. Section 5 proposes a discrete bat algorithm (DBA) to solve STSP. Section 6 presents a set of experimental results of symmetric TSP benchmarks from TSPLIB library [35]. Finally, Sect. 7 concludes and gives some perspectives of research.

2 Literature review

In the last decade, the swarm intelligence algorithms have been emerged as a powerful method to solve various engineering optimization problems [6]. The vast majority of algorithms have been suggested depending on different intelligent behaviors of swarms or by mimicking the behaviors of biological systems in nature. Day after day, the number of researchers interested in swarm intelligence algorithms increases rapidly. This is a subject on which there is an ample literature. Dorigo et al. [27] proposed ACO by inspiration from the natural behavior of ant species. Karaboga and Basturk [36] developed artificial bee colony (ABC) by simulating the intelligent foraging behavior of honeybee swarm. Kennedy and Eberhart [37] proposed PSO by inspiration from the social behavior of bird flocking when searching for food. Yang proposed FA based on the flashing patterns of tropical fireflies. Passino [38] introduced bacterial foraging optimization algorithm (BFO) by observing the social foraging behaviors of E. coli bacterial swarm. Krishnan and Ghose [39] proposed glowworm swarm optimization algorithm (GSO) inspired by the luminescence capability of glowworms. Chu et al. [40] developed cat swarm optimization algorithm (CSO) by observing the seeking and tracing mode of cats. Gandomi and Alavi [41] proposed Krill Herd (KH) based on the simulation of the herding behavior of krill individuals. Gheraibia and Moussaoui [42] proposed penguins search optimization algorithm (PeSOA) based on collaborative hunting strategy of penguins. Meng et al. [43] inspired by the hierarchal order in the chicken swarm and the behaviors of the chicken swarm, introduced Chicken swarm optimization algorithm (CSOa). Bansal et al. [44] proposed a new swarm approach named spider monkey optimization algorithm (SMO) by modeling the foraging behavior of spider monkeys.

The BA is one of the newest swarm-intelligence-based algorithms proposed by Yang in 2010 [15], based on the intelligent echolocation behavior of bats when catching their prey. In recent years, the BA has become a popular bio-inspired algorithm and one can easily understand that the BA is applied to solve a large variety of optimization problems, while many researchers have provide a wide range of contributions to the literature. Gandomi et al. [45] focused on solving constrained optimization tasks by using BA. Khan et al. [46] proposed a fuzzy modification of BA for clustering of company workplaces. Tamiru and Hashim [47] used fuzzy systems for modeling energy destructions in the components of an industrial gas turbine. Yılmaz and küçüksille [48] suggested three different methods to enhance the local and global search of BA, and they employed both standard test functions and constrained real-world problems to validate the performance of their approaches. Nguyen et al. [49] hybridized BA with ABC algorithm and four benchmark functions are used to test the convergence of the proposed method. Pan et al. [50] applied the concepts of parallel processing and communication strategy to hybrid PSO with BA and six benchmark functions are tested to validate the approached method. Wang et al. [51] employed a Gaussian walk with BA to improve the local search capability, and they modified the velocity equation to assure a good exploitation. Gandomi and Yang [52] introduced chaos mechanism into BA to improve the global search mobility of BA and optimized a set of benchmark problems with different chaotic maps. Mirjalili el al. [53] proposed a binary BA for unimodal, multimodal, and composite functions. Besides that, BA was applied to solve many other optimization problems which more detailed in [54]. However, the application of the standard BA algorithm to solve discrete problems remains limited until 2012, when Nakamura et al. [55] introduced the first binary version of BA to solve feature selection problems. A few years ago, some recent research focused on BA in combinatorial optimization problems, such as Xie et al. [56] introduced a differential Lévy-flights BA to minimize the permutation flow shop problem. Sabba and Chikhi [57] used the sigmoid function to propose a discrete binary BA for solving the multidimensional knapsack problem. Büyüksaatçı [58] used BA to solve the single-row facility layout problem. Fister et al. [59] proposed a modified BA for planning the sports training sessions, etc.

3 Bat-inspired algorithm

Recently, a new metaheuristic search algorithm is presented by Yang in 2010 [15], called the bat-inspired algorithm or BA [60]. The bat-inspired search is based on the echolocation behavior of bats to find the prey and discriminate different types of insects even in complete darkness with varying pulse rates of emission and loudness. They achieve this by emitting calls out to the environment and listening to the echoes that bounce back from them. They are able to identify location of other objects and to measure the distance from the targets by following delay of the returning sound. These emitting calls are very loud sound pulses that vary in properties according to their hunting strategies and depend on the species. The echolocation pulses are characterized by three features: pulse frequency, pulse emission rate, and loudness or intensity. The bats emit echolocation pulses with varying frequencies between 25 and 150 kHz depending on proximity of the target [15]. The pulse rate corresponds to the number of pulses emitted per second, and it can also be adapted by bats according to how far they are away from the target object and this pulse rate can be sped up to 200 pulses per second when approaching a target. Finally, bats decrease the intensity (loudness) of pulse from 120 (loudest) to 50 dB (quietest) as they come closer to their prey. Yang in [15] idealized echolocation behavior of bats and its associated parameters in a numerical optimization algorithm. The BA algorithm has been empirically tested and compared with other existing algorithms using some single and multiobjective standard functions of unconstrained optimization in [15, 60]. Furthermore, Yang and Gandomi [16, 45] validated the performance of BA in benchmark problems of constrained engineering optimization. These studies have clearly demonstrated a better efficiency of the bat-inspired algorithm over other methods.

The basic BA developed by Xin-She Yang [15] is described in following steps:

  1. 1.

    All bats use echolocation to sense distance, and they also “know” the difference between food/prey and background barriers in some magical way;

  2. 2.

    Bats fly randomly with velocity v i at position x i with a fixed frequency f min, varying wavelength λ and loudness A 0 to search for prey. They can automatically adjust the wavelength (or frequency) of their emitted pulses and adjust the rate of pulse emission r in the range of [0, 1], depending on the proximity of their target

  3. 3.

    Although the loudness can vary in many ways, we assume that the loudness varies from a large (positive) A 0 to a minimum constant value A min.

figure a

First, initializing bat population: position x i , velocity v i and frequency f i . The movement of the virtual bats is given by updating their velocities v t i and positions x t i at time step t using Eqs. 1–3, as follows:

$$f_{i} = \, f_{\hbox{min} } + \left( {f_{\hbox{max} } {-}f_{\hbox{min} } } \right)\beta ,$$
(1)
$$v_{i}^{t} = v_{i}^{t - 1} + \left( {x_{i}^{t - 1} - x_{*} } \right) f_{i} ,$$
(2)
$$x_{i}^{t} = x_{i}^{t - 1} + v_{i}^{t} ,$$
(3)

where β ∈ [0, 1] denotes a randomly generated vector from uniform distribution.

The variable x * denotes the current global best location (solution), which is located after comparing all the solutions provided by the m bats.

Second, a random number is applied; if this random number verifies the condition in Line 8 of Algorithm 1 and after selection of one solution among the current best solutions of bat, a new solution will be accepted around the current best solutions; it can be represented by:

$$x_{\text{new}} = x_{\text{old}} + \varepsilon A^{t} ,$$
(4)

where ε ∈ [−1, 1] is a random number, while A t = <A t i > is the average loudness of all the bats at current generation.

Third, the loudness A i and the pulse emission rate r i will be updated, and a solution will be accepted if a random number is less than loudness A i and \(f\left( {x_{i} } \right) < f(x_{ * } )\). A i and r i are updated by:

$$A_{i}^{t + 1} = \alpha A_{i}^{t} ,$$
(5)
$$r_{i}^{t + 1} = r_{i}^{0} \left[ {1 - \exp \left( { - \gamma t} \right)} \right],$$
(6)

where α, γ are constants and f(·) is fitness function. The algorithm repeats until maximal number of cycles is reached.

4 The travelling salesman problem

The travelling salesman problem was introduced in 1800s by the Irish mathematician W.R. Hamilton and the British mathematician Thomas Kirkman; it can be stated as a permutation problem with the objective of finding a shortest closed tour which visits all the cities in a given set; TSP can be modeled as completely connected graph in a D-dimensional Euclidean space (D is size of the problem), which cities are the graph’s vertices, paths are the graph’s edges, and a path’s distance is the edge’s length. Mathematically, it can be defined as given a set of n cities, named {c 1, c 2,…, c n }, and permutations π 1,…, π n , the goal is to find a number of permutation π i  = {c 1, c 2, …, c n }, such that minimizes f(π) the sum of all Euclidean distances d between each city from the same path π and it is given as follows:

$$f\left( \pi \right) = \sum\limits_{i = 1}^{n - 1} {d_{\pi (i)\pi (i + 1)} + d_{\pi (n)\pi (1)} }$$
(7)

The Euclidean distance d, between any two cities with coordinate (x 1, y 1) and (x 2, y 2) is calculated by:

$$d = \sqrt {\left( {x_{1} - x_{2} } \right)^{2} + \left( {y_{1} - y_{2} } \right)^{2} }$$
(8)

Broadly, the TSP is classified as STSP. In this symmetric TSP variation, all of the edge costs are symmetric. This means that, for all vertices in the graph, the cost incurred, when moving from vertex i to vertex j, is the same as the cost incurred when moving from vertex j to vertex i, i.e., d ij  = d ji .

5 Discrete bat algorithm for STSP

Generally, the optimization problems can be divided into two main classes, continuous and discrete [61, 62]. An optimization problem with real decision variables is known as a continuous optimization problem, whereas it is called discrete optimization problem if decision variables take discrete (usually integer) values. Moreover, in discrete problems, the set of feasible solutions is discrete or can be reduced to a discrete one by the discretization of the continuous space. Basically, the BA has been developed to optimize continuous nonlinear functions [15, 16] in which, each bat moves in search space toward continuous valued position, but many problems are, however, defined for discrete valued spaces where the domain of the variables is finite. Typically, many bio-inspired population-based algorithms have been shown a good efficiency in solving continuous problems as well as to solve discrete problem like BA [15], CS [14], and PSO [37]. In the original versions of these algorithms, it is impossible to exploit them directly to solve discrete problems; So many researchers have modified these last algorithms to deal with discrete problems and we can cite some of them: binary bat algorithm (BBA) [55], discrete cuckoo search (DCS) [34], and discrete binary particle swarm optimization (DBPSO) [63].

In this paper, we propose a novel DBA to solve especially the symmetric TSP problem. The DBA saves the original concept and the same steps of the basic BA algorithm, but modifies some equations to shift to discrete space. So the following subsections describe briefly the various steps of extending version of BA to solve TSP.

5.1 Position and velocity representation

In the literature, there are many representations to define a TSP position (solution) in search space, i.e., path representation, adjacency representation, ordinal representation, matrix representation, and binary representation [64]. In basic BA, the position x i of each virtual bat defines a potential solution to problem; to find the best solution, each bat adjusts its velocity by randomly selecting frequency f i of sonic wave. On the other hand, each bat uses the pulse emission rate r i and loudness A i to control the intensive local search that is processed to generate a new individual around the current global best solution. So, in this study, the solution of n cities found by the ith bat is represented by a n-dimensional vector x i  = (x i1, x i2,…, x in ). The velocity v i is viewed as a set of permutation π i  = {c 1, c 2, …, c n }, which allows being close to the global best solution x * = (x *1, x *2,…, x *n ).

5.2 Position updating equation

In continuous BA, the bats’ movement is calculated by the three previous Eqs. 1–3. By using Eqs. 1 and 2, each bat updates its velocity. The resulting value is applied in Eq. 3 to calculate the next position of each individual. However, in order to apply BA to solve TSP, these equations cannot be used directly and must be adapted to the problem.

In the same way as the standard BA, each bat selects a frequency f i in the range of frequency [f min, f max], where f min and f max are two integers in the range [1, n], n denotes the number of cities. The frequency f i denotes the number of cities of sub-tour saved from the current solution x t i when this last one crosses with the current global best solution x t* . The velocity v t i consists of a set of permutations that allow crossing two solutions x t i and x t* , while respecting 2-exchange crossover heuristic algorithm as described in [65].

The 2-exchange crossover mechanism can be illustrated by an example in Fig. 1. In this example, we take the frequency f = 2 and the distance matrix D defined as below. For this example, we consider two solutions x 1, x 2 and we want to cross them together to get a new solution. In the beginning, we start by saving the f first cities from x 1 and mark it as already assigned in x 2. Next, the new solution is initialized by the cities saving in x 1. After this, we continue to concatenate the last city of the new solution by the closest city either from x 1 or x 2. During the construction process of the new solution, it is necessary to ensure that the two candidate cities chosen from x 1 and x 2 not be already marked in the new solution.

Fig. 1
figure 1

An example of 2-exchange crossover heuristic for TSP

Full size image
$$D = \left( {\begin{array}{*{20}c} {\begin{array}{*{20}c} {\begin{array}{*{20}c} {\begin{array}{*{20}c} {\begin{array}{*{20}c} {\begin{array}{*{20}c} 0 \\ 5 \\ . \\ {\begin{array}{*{20}c} 9 \\ {\begin{array}{*{20}c} . \\ 4 \\ \end{array} } \\ \end{array} } \\ \end{array} } & {\begin{array}{*{20}c} {\begin{array}{*{20}c} {\begin{array}{*{20}c} . \\ 0 \\ \end{array} } \\ 3 \\ \end{array} } \\ {12} \\ . \\ . \\ \end{array} } \\ \end{array} } & {\begin{array}{*{20}c} {\begin{array}{*{20}c} 11 \\ . \\ 0 \\ \end{array} } \\ . \\ 1 \\ 2 \\ \end{array} } \\ \end{array} } & {\begin{array}{*{20}c} {\begin{array}{*{20}c} . \\ . \\ {11} \\ \end{array} } \\ 0 \\ . \\ 5 \\ \end{array} } \\ \end{array} } & {\begin{array}{*{20}c} {\begin{array}{*{20}c} 4 \\ 12 \\ . \\ \end{array} } \\ 7 \\ 0 \\ . \\ \end{array} } \\ \end{array} } & {\begin{array}{*{20}c} {\begin{array}{*{20}c} {.} \\ 1 \\ . \\ \end{array} } \\ . \\ 8 \\ 0 \\ \end{array} } \\ \end{array} } \right)$$

5.3 The neighborhood search

The definition of a neighborhood is important for combinatorial problems as well as continuous problems. Typically, neighborhood search or local search procedure is frequently used for iteratively improving a solution. In the context of the TSP, that means to search the better solution in the neighborhood of the existing solution by making the minimum changes on the last one. The most popularly local search procedure is 2-opt, where two edges are exchanged iteratively until no further improvement is possible as showing in Fig. 2, in which (A) represents initial tour and (B) new tour. The tour (B) is created by taking two pairs of consecutive nodes, pairs (c, d) and (a, b) from the tour (A) and checking if the distance (cd + ab) is higher than (cb + ad), if that is the case, then exchange nodes a and c in pairs (c, d) and (a, b).

Fig. 2
figure 2

2-Opt move: a original tour and b resulting tour

Full size image

5.4 Discrete bat algorithm

This subsection describes briefly the various steps of extending version of BA to solve TSP and recalls the basic terminology used in the previous subsections. Steps of the proposed algorithm DBA are presented below, and the DBA algorithm is summarized in Algorithm 2.

Step 1: Initialize the size of bat population. Generate a random starting position x i for each bat. Initialize the emission rates r i  ∈ [0.0, 1.0] and the loudness A i  ∈ [0.0, 1.0]. Define pulse frequency f min and f max in range [1, n].

Step 2: Calculate the global best solution.

Step 3: For each bat, generate new solutions by adjusting frequency Eq. 1, and updating velocities and locations/solutions, by using the following equations:

$$v_{i}^{t} = \chi \left( {x_{i}^{t - 1} ,x_{*} ,f_{i} } \right),$$
(9)
$$x_{i}^{t} = \phi \left( {x_{i}^{t - 1} ,v_{i}^{t} } \right),$$
(10)

where the function χ(cross) takes three input arguments (two solutions and one integer) and returns a set of permutations reached by applying 2-exchange crossover mechanism described in Sect. 5.2. The function ϕ(sort) returns a new solution obtained by sorting the elements of x t−1 i according to the permutations v t i .

Step 4: A random number is applied; if it is upper to r i , then select a solution among the best solutions. Generate a local solution by exchanging two arcs from the selected best solution.

Step 5: Evaluate the new solution according to the Eqs. 7, 8.

Step 6: Generate a new solution by flying randomly.

Step 7: Generate a random number, if this number is less than loudness A i and the last evaluated solution is better than the best solution so accept the new solutions.

Step 8: Stop the algorithm if the maximal number of iterations is reached. Return to Step 3 otherwise.

figure b

6 Numerical results and performance comparisons

To validate its performances, the proposed algorithm has been tested on 41 symmetric benchmarks of TSP taken from TSPLIB library [35], ranging from 51 to 1379 cities and each instance is run independently for 30 times. The DBA is coded in MATLAB R2010a, and the experiment has been made on a PC with processor Intel(R) Core(TM) 2 Duo CPU T4300@ 2.1 GHZ 800 MHz and 2.00 GB of RAM. Table 2 summarizes the simulation parameter values used for the experiments of DBA algorithm. Table 3 shows the numerical results of DBA algorithm (A number shown in bold in Table 3 indicates that DBA reaches the optimal solution of the tested instance). These results are obtained by calculating the Euclidean distances between all edges. The first column indicates the instance name ended by the number of cities, the second column stands for the best known from TSPLIB, the third column indicates the best results obtained by DBA, the fourth one represents the worst results obtained, the fifth column indicates the average solutions length found, the sixth column denotes the standard deviation of solutions obtained by the DBA algorithm over 30 independent runs, and the seventh and the eighth columns show, respectively, the percentage deviation of the average solution length over the optimal length of 30 runs “PDav(%),” and the percentage deviation of the best solution length found over the optimal solution length of 30 runs “PDbest(%)”. In the ninth column, C1% is the number of solutions (over 30 runs) for which the deviation from the optimal solution is less than or equal to 1 and “Copt” is the number of the optimal solutions. The last column gives the average elapsed time in second during 30 runs.

Table 2 The parameters of the problem
Full size table
Table 3 Results of the DBA algorithm for symmetric instances from TSPLIB
Full size table

The percentage deviation of a solution to the optimal solution is calculated by the following formula:

$$\begin{aligned}&{\text{PDsolution}}(\% ) \\ &\quad = \frac{{({\text{solution}}\;{\text{length}} - {\text{optimal}}\;{\text{solution}}\;{\text{length}})}}{{{\text{optimal}}\;{\text{solution}}\;{\text{length}}}} \times 100 \end{aligned}$$

Furthermore, the pulse emission rate and loudness are used to control the intensive local search, which allows generating new solutions around the current global best solution. The choice of these parameters values has a critical role in the performance of the algorithm, and the quality of solutions found. The preliminary experiments in Fig. 3 show that a larger emission rate value as well as small loudness value can provide a premature convergence toward undesirable solutions. Therefore, as shown from Fig. 4, it is preferred to use a small value of emission rate and loudness, typically equal to 0.5, to provide a trade-off between emission rate and loudness and give good solutions.

Fig. 3
figure 3

The best lengths found of eil51, st70 eil76, eil101, kroA100, kroB100, kroC100, kroD100, kroE100 and d198 when r i and A i varying between 0 and 1

Full size image
Fig. 4
figure 4

The best lengths found of eil51, st70 eil76, eil101, kroA100, kroB100, kroC100, kroD100, kroE100 and d198 when r i  = 0.5 and A i  = 0.5

Full size image

Additionally, in order to evaluate the performance and to give more credibility of our results, Tables 4, 5 and 6 make respectively a fair comparison of the DBA results with those of the both algorithms discrete particle swarm optimization (DPSO) [33], genetic simulated annealing ant colony system with particle swarm optimization techniques (GSA-ACS-PSOT) [66] and improved DCS [34] as presented in their original papers.

Table 4 Comparison of computational results of DBA algorithm and DPSO [33]
Full size table
Table 5 Comparison of computational results of DBA algorithm and GSA-ACS-PSOT [66]
Full size table
Table 6 Comparison of computational results of DBA algorithm and improved DCS [34]
Full size table

According to the values displayed in Table 3, we can see that the DBA can reach the optimal solutions of 73.17 % from all tested instances and 92.68 % of the values of PDbest(%) are less than 0.4 %, which means that the solutions found by the proposed DBA algorithm over 30 runs, are very close to the optimal solutions known. Furthermore, the average error rate PDav(%) of 0.00 % value indicates that all the solutions found over 30 runs are the same as the optimal solutions known. Indeed, the experimental results presented in Table 3 have shown that the DBA is very efficient for solving small-size as well as large-size instances of TSP problem in a reasonable time.

Tables 4, 5 and 6 present the test results for 41 instances over 30 runs of DBA compared, respectively, to DPSO [33], GSA-ACS-PSOT [66], and improved DCS [34] (the optimal solutions found by these algorithms are presented as bold). For the five compared instances in Table 4, the DBA algorithm can find the best solutions of all instances with a success rate of 100 % and it is clearly seen that DBA outperforms DPSO. Moreover, the Table 5 reports the best and the average solutions found by the DBA algorithm and the GSA-ACS-PSOT algorithms, respectively. For 18 tested instances, the DBA finds 16 optimal solutions in front of 11 optimal solutions found by GSA-ACS-PSOT and the average of all standard deviations of DBA/GSA-ACS-PSOT is equal to 34.61/161.55. Also, the DBA reaches the optimal solution over 30 trails for five times; however, GSA-ACS-PSOT does not exceed one instance. Figure 5 shows evidently that the curve associated with DBA is better in terms of solutions quality compared to GSA-ACS-PSOT. Furthermore, Table 6 indicates experimental results found by DBA and improved DCS for 21 instances of the TSPLIB ranging from 107 to 1379 cities. For these instances, the DBA algorithm finds the best solutions for 12 instances over the 21 tested instances, while improved DCS finds the best solutions only for nine instances and the average of all standard deviations of DBA/improved DCS is equal to 61.16/121.20. The displayed results in Fig. 6 show that the solutions of the DBA and the improved DCS are very close in the eleventh first instances; however, DBA outperforms clearly improved DCS for the rest large-size instances.

Fig. 5
figure 5

PDav(%) (over 30 run) for 18 instances from TSPLIB

Full size image
Fig. 6
figure 6

PDav(%) (over 30 run) for 21 instances from TSPLIB

Full size image

7 Conclusion

This paper has proposed a DBA to solve the STSP. In this discrete version, we were based on basic bat algorithm as it is defined in inspiration sources, where we have extended some conventional BA operators to deal with a discrete optimization problem. The proposed discrete algorithm has been evaluated through its application to solve different instances of the STSP and its performance has been compared with DPSO [33], GSA-ACS-PSOT [66], and improved DCS [34]. The computational results revealed that our proposed DBA performs all compared algorithms to solve STSP. There are a number of directions that can be taken in our future research. The first one is to extend the DBA to solve other NP-hard combinatorial optimization problems, such as vehicle routing problem, scheduling problems, quadratic assignment problem, and many others. Another direction is to examine some discretization methods and encoding strategies used to switch between the continuous and the discrete search space, such as the smallest position value method, the random-key encoding scheme, the great value priority method, and the sigmoid function. Finally, it may also be interesting to hybrid the DBA with other heuristics or metaheuristics and to analyze the performance of each algorithm in solving TSP problem.