1 Introduction

The TSP is one of the NP-hard problems that many research types have been done on this issue. However, none of the research has been able to find a particular solution to this problem. This problem is discrete from the hybrid optimization problem, and the goal is to find the shortest Hamiltonian path. So, look for a route that first visits all the cities at most once and secondly returns to the city where the route started from that city and also this route is also the shortest possible route. Although this problem has a simple mathematical model and is very easy to understand, it is challenging to solve it. Due to the enlargement of the issue and the increase of cities, computational complexity increases and requires more resources and computational time. Since it is one of the NP-hard problems, it is not solvable, and all the presented solutions are relative, and a new solution can be presented that is more efficient than the previous solutions.

Nowadays, extensive and diverse research has been done by researchers to solve various problems [1,2,3,4,5]. Also, Various methods have been proposed to solve the TSP problem, which are accurate methods suitable for small and medium optimization problems. Because in solving large-scale problems, the computational time is very long in general, some of the exact methods are: branch and bound [6], branch and cut [7], branch and price [8], cutting planes [9], and Lagrangian dual [10]. Moreover, the need to find reasonable (not necessarily optimal) solutions to these problems have led to various approximation algorithms, such as metaheuristics. These methods have advantages such as simplicity and flexibility and generally produce quality solutions in a reasonable amount of time by creating shortcuts. However, in some models based on metaheuristic algorithms, they either have a high computational time, or do not produce an acceptable optimal answer, or are inefficient in the face of large-scale problems [11,12,13,14,15].

Different neighborhood search operators can be used to improve the performance of metaheuristic algorithms in metaheuristic algorithms. However, each of these operators has unique features that can have the necessary efficiency in different optimization operations stages. For this reason, hyper-heuristic modes of the Modified Choice Function can be used to select neighborhood search operators intelligently [16,17,18].

For the first time in [19], the term hyper-heuristic has been introduced, divided into two categories: selection hyper-heuristic and generation hyper-heuristic. Moreover, these two categories of selective and productive hyper-heuristics can be divided into two categories based on the nature of heuristics: perturbative and constructive, which is constructive hyper-heuristics [20] create a solution from the ground up gradually [21]. Moreover, in perturbative hyper-heuristics by performing disturbance mechanisms repeatedly in the solution improves the solution. Mechanisms that are generated or selected by hyper-heuristics are called low-level heuristics (LLHs). Selective-based hyper-heuristics have two general levels, low-level and high-level. The lower level includes evaluation function(s) and problem representation, and a set of LLHs.

Moreover, the high-level task of managing the LLH selection is used to generate a new solution and accept the new solution. The mechanism for selecting an LLH from a set of LLHs during the optimization process, in which this selected LLH performs better than other LLHs in this set, is called LLH selection, and several LLH selection methods include choice function [22,23,24], set of reinforcement learning variants [25, 26], backtracking search algorithm [27], harmony search [28], and Tabu search [29]. Moreover, how to decide to accept a new solution produced by LLH is called move acceptance. Some of the move acceptance methods are Late Acceptance [30], Simulated Annealing [31], Only Improvement [32].

In hyper-heuristics, there are two primary components called diversification and intensification. Due to the different capabilities of each LLH in different stages of the search process, these two components are essential hyper-heuristic elements. It is an intensification component to focus as much as possible on LLHs that perform better than other LLHs. On the other hand, it is a component of diversification to select LLHs that are rarely selected. Therefore, it is essential to strike a balance between diversification and intensification [27]. Furthermore, if an LLH performs well in one iteration step, it should not be used in subsequent steps alone to improve the solution, and if an LLH performs poorly in one iteration step, make this LLH not used permanently.

On the other hand, local search algorithms have been used in many studies to solve hybrid problems. Using two methods [29], Multi-start Local Search (MSLS) and Iterated Local Search (ILS) [30], the performance of local search algorithms is increasingly increasing. If these different mechanisms are combined, they can significantly increase metaheuristic algorithms' performance.

This paper presents a new method using the HHO algorithm [33]. This algorithm was developed to inspire the life, hunting practices, and mathematical modeling of Harris hawks' behaviors in the natural environment. This algorithm has been used in many studies despite being new, including Design and manufacturing problems, multi-level image thresholding problems [34], power flow problems [35], feature selection [11, 36,37,38], Satellite Image Segmentation [39], design of microchannel heat sinks [40], etc.

The proposed algorithm employs random-key encoding to generate a tour to maintain the core capabilities of the HHO algorithm, on the one hand, and utilizes the capabilities of active mechanisms in the continuous-valued problem space, on the other. Random-key encoding transfers solutions from continuous to discrete space. It motivated us to discretize the main mechanisms of the HHO algorithm operating in continuous space to solve the TSP, a discrete problem.

In this paper, to improve this algorithm's performance, two DE/best/2 mutation mechanisms have been used to increase the HHO algorithm's efficiency in the exploration phase. On the other hand, to improve the proposed algorithm's performance to solve the TSP, ten neighborhood search operators were used, four of which have been presented for the first time. Furthermore, the modified choice function (MCF) was utilized to increase efficiency and select neighborhood search operators. The proposed algorithm's capability and performance were then significantly increased using the Lin-Kernighan (LK) local search mechanism. Finally, the Metropolis acceptance strategy was employed to escape the local optima trap. The proposed algorithm's performance in solving problems with different dimensions was evaluated using the datasets available in TSPLIB [41], including small, medium, and large 100-85900 cities. The most important innovations and contributions of this paper are as follows:

  • This paper presents the HHO algorithm for the first time to solve the TSP.

  • The random-key encoding scheme is employed to adapt and solve the TSP using the HHO algorithm.

  • A DE/best/2 mutation operator mechanism is utilized to improve the HHO algorithm's performance in the exploration phase.

  • Ten neighborhood search operators are used for improving the proposed algorithm's performance, four of which are presented for the first time in this paper.

  • Modified choice function (MCF) is utilized to select neighborhood search operators at different optimization operations stages intelligently.

  • Lin-Kernighan (LK) local search is employed to increase the efficiency of the proposed algorithm.

  • The Metropolis acceptance strategy is utilized to escape the local optima trap.

  • The proposed algorithm's performance in solving TSP, which consists of 80 instances, has been tested using three criteria (i.e., the average tour length, average percent deviation, and average computation time). It is then compared with the previous seven models, indicating the acceptable performance of the proposed algorithm.

  • The proposed algorithm is also compared and evaluated with other models using the Wilcoxon signed-rank test.

The rest of this paper is structured as follows. Section 2 examines related works, Section 3 addresses the basic concepts, Section 4 presents the proposed algorithm, and Section 5 compares and evaluates the proposed algorithm with the other methods presented. Finally, Section 6 concludes the paper.

2 Related works

Various researchers have proposed various methods and algorithms over the years to solve the TSP. However, a definite method or algorithm cannot be proposed for TSP because it is an NP-hard problem. Therefore, researchers have always attempted to try some methods more efficiently than previous ones [42, 43].

In [44], a master-slave-based method is used to solve the TSP, with several colonies cooperating periodically in a distributed computing environment (DCE). This algorithm is hybrid with 3-Opt to improve performance. Each colony runs this algorithm separately and shares the results with other colonies. This method is evaluated with 21 instances. These methods either have a high computation time or do not provide an acceptable optimal solution, or are inefficient in dealing with large-scale problems.

In [45], a hybrid simulated annealing algorithm based on a Symbiotic Organism Search (SOS) is proposed to solve TSP. The purpose of this work is to evaluate the convergence behavior and scalability of this hybrid algorithm to solve TSPs with small- and large-scale traveling. In terms of average execution time, experiments on the solution convergence and percentage deviations were evaluated. The results of the experiments showed an improvement in results.

In [46], a discrete algorithm, i.e., a comprehensive learning Particle Swarm Optimization (PSO) algorithm with the Metropolis acceptance criterion, is proposed to solve the TSP. This algorithm employs two strategies, namely lazy velocity and eager evaluation, to improve performance. Additionally, the Metropolis acceptance criterion is utilized to avoid premature convergence. To solve this problem, hyper-heuristic methods, e.g., Modified Choice Function (MCF), can be employed. In [17], it is done automatically and intelligently by selecting neighborhood search heuristic by employed and onlooker bees.

In [47], the wolf colony search algorithm, which exploits siege strategy, is employed to solve the TSP to achieve several goals, including improving the mining ability, reducing the besiege range, and accelerating convergence time. The proposed algorithm showed better performance in terms of higher solving accuracy and faster convergence speed. Moreover, travel behavior and calling behavior strategies have been exploited to enhance wolf interaction and improve global optimization accuracy.

Additionally, the Lin-Kernighan local search is integrated with this algorithm. This algorithm is evaluated with 64 instances of TSP in TSPLIB. Hyper-heuristic is an automated methodology for selecting or generating a set of heuristics [21]. Moreover, travel behavior and calling behavior strategies have been exploited to enhance wolf interaction and improve global optimization accuracy. Also, in [48], the discrete pigeon-inspired optimization (PIO) (DPIO) algorithm is presented. The Metropolis acceptance criterion is utilized for discretization. A map operator and a new compass operator with comprehensive learning capability have been employed in this algorithm to increase the DPIO's exploration ability. A new landmark operator has also been utilized to increase the exploitation of this algorithm. Thirty-three large-scale instances of TSPLIB with 1000-85900 cities have been tested to evaluate the DPIO algorithm's performance. In [49], a combined wolf pack search and local search solution is presented to solve the TSP to balance exploration and exploitation and not get stuck in a local optimum. The results of experiments on TSPLIB indicate that the results obtained by this algorithm are better and closer compared to other algorithms. This algorithm could compare theoretical optimal values with higher robustness compared to the obtained values.

Moreover, In [50], a new algorithm called the Anglerfish algorithm is proposed to solve TSP. The search operation is performed randomly based on the initial population using the randomized incremental construction technique. It is performed using random sampling and without complicated procedural procedures. Also, in [51], a discrete algorithm, i.e., discrete SOS (DSOS), is enhanced using excellence coefficients self-escape to solve the TSP, called ECSDSOS. The self-escape strategy is utilized to avoid getting stuck in the local optimum. The excellence coefficients are used to choose shorter edges (routes) for generating better local paths. Instances in TSPLIB are used to evaluate this algorithm. The results show an improvement in the performance of the proposed algorithm relative to the compared algorithms.

In [52], the discrete sine-cosine algorithm (SCA) is presented using a local search to solve the TSP. The proposed algorithm employs two different mathematical models to update each generation's solutions to balance exploration and exploitation. It is also integrated with the 2-opt local search method to improve exploitation. This algorithm exploits a heuristic crossover to increase exploration ability. The experiments and evaluations indicate an improvement in this algorithm's performance from 41 different benchmarks in TSPLIB.

In [53], new versions of the ABC algorithm are introduced to solve the TSP, including the combinatorial version of the standard ABC, called combinatorial ABC (CABC), and an improved version of the CABC algorithm called the quick CABC (qCABC). The efficiency of these two versions of the ABC algorithm was evaluated using 15 TSP benchmarks. The results of evaluating these two algorithms' performance were then compared with eight different variables (GA variants).

In [54], a hybrid model is proposed using a genetic algorithm (GA) and remove-sharp and local-opt with ant colony optimization (ACO) to accelerate convergence and implement positive feedback to optimize the search space and create an efficient solution to solve complex problems. TSP was tested to evaluate the optimality accuracy and performance of the combinatorial model, indicating satisfactory performance. The results also showed better performance of the proposed algorithm relative to the compared models. This model can also solve various problems, such as network routing, scheduling, vehicle routing, etc. Also, in [55], an algorithm based on ACO and the partheno-genetic algorithm is proposed to solve the TSP. The primary purpose is to divide the variables into two parts. It uses the partheno-genetic algorithm to comprehensively search for the best value of the first section variables and then the ACO to precisely determine the best value of the second section variables. The comparative experiment results showed that the combinatorial algorithm effectively solved large-scale TSP and better performance than existing algorithms.

In [56], a new discrete differential evolution algorithm is used to solve TSP. The authors suggest a combination of the following: (1) an improved mapping mechanism for mapping continuous variables to discrete variables and vice versa, (2) a k-means clustering restoration method to increase the number of solutions in the initial population, and (3) a set of strategies mutation to increase the exploitation capability of the algorithm. Finally, two well-known local searches are presented to improve the local capability of the proposed algorithm. The experimental results showed a significant advantage of the proposed algorithm over many comparative methods in terms of the mean of known errors from known solutions; it achieves very competitive results with less computational time compared to other algorithms.

In [57], the ACO algorithm for solving TSP using a self-adaptive method to improve convergence and diversification called DEACO is proposed. It has been evaluated using the samples in TSPLIB, and the results of this work indicate the excellent performance of this model. And, In [58], a new discrete version of the Tree-Seed Algorithm (TSA) for solving TSP is presented. Three operators, swap, shift, and symmetry, have been used to provide the discrete version. This model has been evaluated and compared with several other discrete optimization algorithms, which indicate this model's acceptable performance.

In [59], the Genetic Algorithm is used to solve the multi-objective TSP problem. Numerous samples from TSPLIB with a different number of cities have been used for evaluation, and the results show the acceptable performance of this model. In [60], an improved PSO algorithm is used to solve the TSP, named MPSO. In this model, local search algorithms are also used to improve performance. Also, a new method has been used to move the particle towards the best particle for preventing premature convergence. The results obtained from this model have been compared with several other meta-heuristic algorithms, and the results obtained from this comparison have shown that it achieves better results than other optimization algorithms in most samples.

In [61], the authors present a discrete version of the shuffled frog-leaping algorithm based on heuristic information. In this model, a new operator called nearest neighbor information is designed. Also, four improved search strategies have been used to improve the performance of this model. Opposite roulette selection, on the other hand, is used to maintain population diversification. A large number of samples in TSPLIB have been used for evaluation. The results obtained from this work indicate the excellent performance of this model.

In [62], a new discrete version of the Crow Search Algorithm(CSA) for solving TSP is presented. Three discrete CSA are also proposed to improve performance. The algorithms presented in this paper are based on modular arithmetic, basic operators and dissimilar solutions techniques. One hundred eleven instances and several optimization algorithms have been used To evaluate and compare this model's performance, and the results have shown that it has a good performance in solving TSP. And, In [63], a discrete version of the Farmland Fertility Algorithm(FFA) is presented. In this research, three neighborhood search operators and a crossover operator are used. Also, to improve the performance of this model, the 2-OPT local search technique has been used. The roulette wheel technique has also been used to select local search operators. Examples from TSPLIB and several other optimization algorithms have been used to evaluate this model. The results show that this model performs well in other models.

Continuing previous research on the TSP solution, this paper offers a different approach to solving this problem by improving the HHO algorithm using various mechanisms that help balance the phases of exploration and exploitation, prevent premature convergence, and escape the local optima trap. It will be explained in detail in the section on the proposed algorithm (Table 1).

Table 1 Comparison of optimization algorithms used to solve TSP
Full size table

3 Fundamental research

3.1 Harris hawk optimization algorithm

The description of the HHO algorithm requires the symbols that are briefly described in Table 2. A brief description of this algorithm is given below.

Table 2 Explanations of symbols used in the mathematical model of HHO.
Full size table

The HHO algorithm uses two different strategies for search operations in the exploration phase. Each of these strategies is selected based on q; If q ≥ 0.5, the first strategy is used to search near one of the other hawks randomly, but if q < 0.5, the second strategy is used for the search operation, expressed in Eq. (1).

$$X\left(t + 1\right)=\left\{\begin{array}{c} {X}_{rand}(t) - {r}_{1} |{X}_{rand}(t) - {2}_{{r}_{2}}X(t)| q \ge 0.5\\ ({\rm {X}}_{\rm {rabbit}}(t) - {\rm {X}}_{\rm {m}}(t)) - {\rm {r}}_{3}(LB + {\rm {r}}_{4}(UB - LB)) q < 0.5\end{array}\right.$$
(1)

where \({X}_{m}(t)\) is calculated based on Eq. (2).

$${X}_{m}(t) = \frac{1 }{N} \sum_{i=1}^{N}{X}_{i}(t)$$
(2)

A different mechanism is used to move from the exploration phase to the exploitation phase. In optimization operations, the exploration operation is performed first, followed by the exploitation phase by increasing the iterations, finding the optimal solution, and promising solutions. Equation (3) is used for mathematical modeling.

$$E = 2{E}_{0}(1 -\frac{ t }{T} )$$
(3)

If \(|\rm {E}| \ge 1\), the algorithm enters the exploration phase, but if \(|\rm {E}|<1\), it enters the exploitation phase. The value of E has a decreasing trend during the increase of iterations. The HHO algorithm uses four different strategies to perform optimization operations in the exploitation phase. If E ≥ 0.5, two strategies, besiege and soft besiege with progressive rapid dives, are used. Conversely, if E < 0.5, two strategies, besiege and hard besiege with progressive rapid dives, are used. Each of these strategies will be explained below.

3.2 Soft besiege

If \(\rm {r }\ge 0.5\rm { and }|\rm {E}| \ge 0.5\), the HHO algorithm utilizes a soft besiege strategy for optimization operations. In this case, hawks cannot easily hunt rabbits because they have much energy to escape, described in Eqs. (4) and (5).

$$X(t + 1) = \left.\Delta X(t) - E \left|{ JX}_{rabbit}\right.(t) - X(t)\right|$$
(4)
$$\Delta X(t) = {X}_{rabbit}(t) - X(t)$$
(5)

In Eq. (4), \(\Delta X\), obtained using Eq. (5), represents the distance of the selected hawk to the rabbit, and \(E\) is obtained using Eq. (8). \(J\) is also the escape energy of the rabbit, which is obtained using the Eq. \(\rm {J}=2(1-{\rm {r}}_{5})\).

3.3 Hard besiege

If \(\rm {r}\ge 0.5\rm { and }|\rm {E}|<0.5\), the HHO algorithm uses a hard besiege strategy for optimization operations. In this case, hawks can hunt rabbits with rapid attacks because they no longer have enough energy to escape. The mathematical model of this motion is expressed using Eq. (6).

$$X(t + 1) = {X}_{rabbit}(t) - E\left|\Delta X\right.\left.(t)\right|$$
(6)

If \(|\rm {E}| \ge 0.5\rm { but r }< 0.5\), the soft besiege strategy with progressive rapid dives is used. In that case, the rabbit has enough energy to escape, and there is still a soft besiege. This procedure is relatively more innovative than the previous procedure.

$$Y = {X}_{rabbit}(t) - E \left| {JX}_{rabbit}(t) -\right.\left.X(t)\right|$$
(7)

This strategy uses a Lévy flight to improve performance. Also, the two states of Eq. (12) are compared with the current solution. The Lévy flight has not been used as a result of \(Y\) but has been used in \(Z\), given in Eq. (8).

$$Z = Y + S \times LF(D)$$
(8)

In Eq. (8), S is a random number in the dimensions of the problem in the interval [0,1], and \(LF(D)\) is the flight of Lévy in the dimensions of the problem, expressed in Eq. (9).

$$ LF(x) = 0.01 \times \frac{{u \times \sigma }}{{|v|^{{\frac{1}{\beta }}} }},\sigma = \left( {\begin{array}{*{20}l} {\Gamma (1 + \beta ) \times \sin \left( {\frac{{\pi \beta }}{2}} \right)} \hfill \\ {\Gamma \left( {\frac{{1 + \beta }}{2}} \right) \times \beta \times 2^{{\left( {\frac{{\beta - 1}}{2}} \right)}} } \hfill \\ \end{array} } \right)^{{\frac{1}{\beta }}} $$
(9)

In Eq. (9), \(u\) and \(v\) are two random numbers between 0 and 1, and \(\beta \) is a fixed and default number, i.e., 1.5.

$$X(t + 1) = \left\{\begin{array}{c}Y ifF(Y ) < F(X(t)) \\ Z ifF(Z) < F(X(t))\end{array}\right.$$
(10)

According to Eq. (10), the result of Eq. (7) is better than the current solution and, consequently, replaces it; otherwise, the solution obtained from Eq. (8) is compared with the current solution. Suppose \(|E|<0.5 and r<0.5\), the hard besiege strategy with progressive rapid dives is used for optimization operations. In this case, the rabbit does not have enough energy to escape and is besieged hard before the surprise pounce to catch the rabbit. Equations (12) and (13) apply based on Eq. (11).

$$X(t + 1) = \left\{\begin{array}{c}Y ifF(Y ) < F(X(t)) \\ Z ifF(Z) < F(X(t))\end{array}\right.$$
(11)

In Eq. (11), \(Y\) and \(Z\) are obtained using Eqs. (12) and (13).

$$Y = {X}_{rabbit}(t) - E\left|{JX}_{rabbit}(t) \right.\left.- {X}_{m}(t)\right|$$
(12)
$$Z = Y + S \times LF(D)$$
(13)

In this strategy, the solution obtained from Eq. (12) replaces the current solution if it is more efficient than others; otherwise; The solution obtained from Eq. (13) will replace it if it is more efficient than the current solution. Algorithm 1 presents the pseudo-code of the HHO algorithm.

figure c

3.4 Random-key encoding scheme

A random-key encoding scheme [64] is an approach to transforming a position and turn it into a combinatorial position in a continuous space. It utilizes a real-number vector by assigning each of the numbers to a certain weight. The weights are then employed to create a combination in the form of a solution. The uniformly drawn random real numbers from the range [0, 1) constitute a vector illustrated in Fig. 1. A combinatorial vector comprises integers ordered according to actual numbers' weights in the first vector, as shown in Fig. 1.

Fig. 1
figure 1

Random-key encoding scheme

Full size image

3.4.1 Mutation mechanism

In the exploration phase, the DE/best/2 mutation operator [65], used in many studies, has been used as the primary strategy to increase global search operations performance in the HHO algorithm. The details of this mutation operator are shown in Eq. (14).

$$Xnew={X}_{rabbit}\left(t\right)+F\left({X}_{r1}\left(t\right)-{X}_{r2}\left(t\right)\right)+\left({X}_{r3}\left(t\right)-{X}_{r4}\left(t\right)\right)$$
(14)

In Eq. (14), F is the scaling factor, and \(r1\), \(r2\), \(r3\), and \(r4\) are different integers selected from the range [1, N]. N represents the size of the total population. Equation (14) is used in the exploration phase. Mutation operators are used in many models and algorithms to improve optimization performance and global search capability [66,67,68] that motivated us to use this operator in the proposed algorithm.

3.5 Neighborhood operators

The proposed algorithm uses ten neighborhood search operators [17, 69,70,71,72,73,74,75] to improve HHO performance. They are used to achieve optimal solutions. These operators are divided into two groups: point-to-point (pointwise) and sequence operators. In point operators, only one city is selected for change, while in sequence operators, a sequence of cities is selected for change. Point-to-point operators include random swap and random insertion. These ten operators are integrated with the proposed algorithm as 10 LLHs (Fig.2), consisting of four primary operations: reverse, insert, swap, and shuffle. RRS specifically performs a reversing of subsequence operation. RI and RIS perform an insert operation. RS and RSS do a swap operation, and SS does a shuffle operation. Of the ten LLHs, three LLHs, RRSS, RIDC, and RSDC, are made up of a combination of two operators.

  • Random swap (RS): The operator selects two cities at random on a tour and permutation. It then exchanges the location of the two selected cities. Among the advantages of using this operator are keeping more cities adjacent to each other and creating disturbances and minor changes.

  • Random insertion (RI): This operator selects two cities at random. It then inserts city \(i\) in position \(j\). In other words, the insert operator selects a city on tour at random. It then removes that city from the tour, and this action is repeated in the position of another point.

  • Random Reversing of Subsequence (RRS): The second integrated operator in the HHO algorithm is reversing the subsequence operator. The operator selects a sequence of cities on a random tour. It then reverses the order of cities \(i\) to \(j\). In other words, the operator selects two points in the city at random. It then reverses the order of the cities located between the two selected cities.

  • Random Swap of Sub-Sequences (RSS): The operator selects two sequences with the same number of cities in a tour and permutation. It then exchanges the position and location of two sequences of selected cities with each other.

  • Random Insertion of Sub-Sequence (RIS): This operator inserts a sequence of randomly selected cities into the position of a randomly selected city.

  • Random Reversing Swap of Sub-Sequences (RRSS): This operator selects two cities' sequences with the same number at random. It then reverses the cities' order in both sequences and finally replaces the two sequences' positions.

  • Random Double Cycle (RDC): The operator selects a sequence of cities in pairs (at least 4) in the tour at random. It then replaces the position of the cities in pairs.

  • Random Nested Cycles (RNC): The operator selects a sequence of cities in pairs (at least 4) in the tour at random. It then replaces the position of the city \({c}_{1}\) with the city \({c}_{n}\), the last city in the selected sequence. It then enters the sequence once and replaces the second city and the last second city in the selected sequence. This process continues until two inland cities are selected in sequence.

  • Random Swap Double Cycle (RSDC): The operator selects two cities' sequences with the same number in pairs (at least 4) in the tour at random. It then replaces the position of the cities in both sequences in pairs, and finally, replaces the position of the two sequences with each other.

  • Random Insertion Double Cycle (RIDC): The operator selects a sequence of cities in pairs (at least 4) in the tour at random. It then replaces the position of the cities in pairs, and finally, inserts the position of a sequence of cities into the position of a randomly selected city.

Fig. 2
figure 2

Function of Neighbourhood operators

Full size image

3.6 Modified choice function

Modified choice function heuristic selection variates the choice function, emphasizing intensification over-diversification within the heuristic search process. In [22], a choice-based hyper-heuristic with a score-based approach is presented. The scoring model of each LLH is measured based on the previous performance of that LLH. The score of each LLH consists of three different criteria: \({f}_{1}\), \({f}_{2}\), and \({f}_{3}\). In this model, the first measurement criterion, \({f}_{1}\), calculates the recent performance of each LLH (Eq. (15)):

$${f}_{1 }\left({h}_{j}\right)={\sum }_{n}{\alpha }^{n-1}\frac{{I}_{n}\left({h}_{j}\right)}{{T}_{n}\left({h}_{j}\right)}$$
(15)

Where, \({h}_{j}\) is the same as \({\rm {LLH}}^{j}\), \({I}_{n}({h}_{j})\) is the difference between the current solution and the new solution with \({\rm {n}}^{\rm {th}}\) function of \({h}_{j}\), \({T}_{n}({h}_{j})\) is the time spent by nth function of \({h}_{j}\) to suggest a new solution, \(\rm {\alpha }\) is a Parameter between 0 and 1, prioritizing recent performance. The second criterion, \({f}_{2}\) Indicates the dependence between a consecutive pair of LLHs (Eq. (16)):

$${f}_{2 }\left({h}_{k},{h}_{j}\right)={\sum }_{n}{\beta }^{n-1}\frac{{I}_{n}\left({h}_{k}{,h}_{j}\right)}{{T}_{n}\left({h}_{k},{h}_{j}\right)}$$
(16)

where \({I}_{n}\left({h}_{k}{,h}_{j}\right)\) is the value of the difference between the current solution and the new solution using nth consecutive functions of \({h}_{k}\) and \({h}_{j}\) (i.e., \({h}_{j}\) runs right after \({h}_{k}\)). \({T}_{n}\left({h}_{k}{,h}_{j}\right)\) is the time spent by nth consecutive functions of functions of \({h}_{k}\) and \({h}_{j}\) to suggest a new solution, and \(\upbeta \) is a parameter between 0 and 1, prioritizing recent performance. Criteria \({f}_{1}\) and \({f}_{2}\) are among the intensification components of the selection function, which increase the chances of selecting high-performance LLHs. The third criterion, \({f}_{3}\), records the time elapsed since the last execution of a particular LLH (Eq. (17)):

$${f}_{3 }\left({h}_{j}\right)=\tau \left({h}_{j}\right)$$
(17)

where \(\tau \left({h}_{j}\right)\) is the elapsed time since the last execution of \({h}_{j}\) (in seconds). Note that \({f}_{3}\), as a diversification component, plays a role in the selection function, prioritizing those LLHs that have not been used for a long time. The score for each LLH is calculated using the sum of the weights of all three criteria, \({f}_{1}\), \({f}_{2}\), and \({f}_{3}\), as shown in Eq. (18).

$$F\left({h}_{j}\right)={\alpha f}_{1 }\left({h}_{j}\right)+{\beta f}_{2 }\left({h}_{k},{h}_{j}\right)+{\delta f}_{3 }\left({h}_{j}\right)$$
(18)

Where α, β, and δ are parameters that indicate the weights of the criteria \({f}_{1}\), \({f}_{2}\), and \({f}_{3}\) constant values in the initial model. In [76], to increase the improved hyper-heuristic version's efficiency and performance presented in [22], where the parameters can be controlled dynamically during execution. If an LLH improves the solution, the α and β parameters' values increase relative to the degree to which the new solution improves compared to the previous solution. At the same time, there is no improvement in the solution if the LLH is selected. The α and β parameters' values decrease due to the difference in costs between the new solution and the previous solution. Despite the improvements, this version also had some limitations, reviewed in [23]. These restrictions were then lifted. One of these limitations was the reward and penalty mechanism applied by the previous solution, and the new solution commensurate with the resulting improvement. Given the high potential for significant improvement by an insufficient heuristic due to low resolution in the early stages of optimization, it may be advantageous. Also, progress in improving solutions is reduced in the later stages of optimization due to convergence to optimal solutions. It leads to a significant reduction in rewards earned. However, the improvements made in the later stages of optimization are much more critical than those obtained in the early stages. Therefore, this mechanism of reward and penalty is not the correct mechanism. In addition to the above limitations, if no improvement is achieved in the solutions after some iterations, the LLH selection mechanism is done randomly because the α and β parameters decrease due to the reward and penalty mechanism used. Criterion \({f}_{3 }\) is a diversification component, which can dominate other criteria. The limitations expressed in [76], an improved version of the selection function, these limitations have been removed in [23], the modified selection function, and this version of the selection function has been provided to manage the parameters better. In this paper, the α and β parameters' selection function is combined into a single parameter, called μ. Finally, the score of each LLH is calculated using Eq. (19).

$${F}_{t}\left({h}_{j}\right)={{\mu }_{t}[f}_{1 }\left({h}_{j}\right)+{f}_{2 }\left({h}_{k},{h}_{j}\right)]+{\delta f}_{3 }\left({h}_{j}\right)$$
(19)

If an LLH improves the solution, the intensification component is prioritized, and the parameter μ is set to a maximum static value close to 1. At the same time, the parameter δ decreases to a minimum static value close to 0. Conversely, if the LLH does not improve The solution, the parameter μ is fined linearly and bounded below 0.01. This mechanism causes the parameter δ to grow at a uniform and low rate to prevent the rapid loss of intensification components. The parameters μ and δ are calculated using Eqs. (20) and (21). Equation (20) states the difference between the previous solution's cost and its cost.

$${\mu }_{t}\left({h}_{j}\right)=\left\{\begin{array}{ll} 0.99, & d>0\\ \rm {max}\left[0.01,{\mu }_{t-1}\left({h}_{j}\right)-0.01\right],& d\le 0\end{array}\right.$$
(20)
$${\delta }_{t}\left({h}_{j}\right)=1-{\mu }_{t}\left({h}_{j}\right)$$
(21)

The proposed algorithm uses a modified choice function to automatically select the best LLHs during optimization to increase the proposed algorithm's performance using this mechanism.

3.7 Local-search-based strategies (lin–kernighan local search)

Local search has been used to solve many hybrid optimization problems because it increases the ability to solve such problems. Researchers have proposed different types of local searches, such as opt-2 [77], 3opt [78], and local search [79]. Local search can find local optimum solutions; Therefore, the local search ability is limited to intensification. Using the search is restarted from a specific area of the search space after exploitation for increasing the probability of finding the global optimum. This local search utilizes the retrieval mechanism called multi-start local search (MSLS) [80]. MSLS only allows us to search for different initial solutions and finally obtains a set of local optimum solutions. A global optimum solution or a solution close to the global optimum can be found in the set of local optimum solutions. MSLS has been used to solve many different combinatorial problems, including dynamic TSP [81], generalized quadratic multiple KP [82], and periodic VRP [83].

Also, diversification can be used in local search to increase local search performance. In this case, the solutions are improved by repeated perturbation of the solutions and local search. One method that takes advantage of this mechanism is iterated local search (ILS) [84], in which a recurring initial solution is diversified. At this stage, different solutions are created by perturbation of the solutions. The diversification phase is followed by the intensification phase, in which local search begins based on the solutions generated in the diversification phase.

In [85, 86], Chained Lin-Kernighan (CLK) heuristic used the ILS mechanism to solve TSP. In CLK, a double-bridge motion is followed to exchange the four arcs in the solution with the other four arcs. This operation is performed repeatedly on the solution. ILS-based strategies have been used to solve many different problems, including bin-packing problems [87], scheduling problems [88,89,90], variants of VRP [91, 92].

Many metaheuristic algorithms have shown good global search performance. The integration of a metaheuristic and local search algorithm strikes a balance between diversification and intensification. Due to the importance of this issue and the increasing performance of the combination of metaheuristic and local search algorithms, shown in many studies [17, 44, 52, 93], the proposed algorithm (MCF-HHO) is integrated with local LK search. Local search is performed after each time changes are made to the solutions using continuous mechanisms or neighborhood operators before the acceptance condition is applied. Because the proposed algorithm uses local search, it is very similar to the ILS and MSLS models. In the initialization phase of the proposed algorithm, a population of solutions is created, creating a different starting point for the local search process. During the proposed algorithm implementation, a series of repeated changes are applied to each section's solutions using an LLH, and the solution is disrupted. LK Local Search follows this. In other words, each solution is subject to the ILS procedure. In light of the above, the proposed algorithm is very similar to the ILS and MSLS models.

3.7.1 Metropolis acceptance strategy

In solving discrete problems such as TSP, the greedy acceptance strategy quickly causes early convergence. To solve this problem, the DHHO model uses the metropolis acceptance criterion to determine whether a new solution will be accepted if it is worse than the current solution. Suppose A is the current tour at cost \(f(A)\) and B is the newly produced tour at cost \(f\left(B\right)\). If \(f\left(B\right)\)<\(f(A)\), i.e., the newly generated tour is better than the current tour, the generated tour will replace the current tour as a new solution. Conversely, if \(f\left(B\right)\)>\(f(A)\), the newly generated network, is worse than the current network, the metropolis acceptance criterion uses a probability mechanism to determine whether the newly generated solution is accepted. The probability of accepting the solution is calculated using Eq. (21).

$$p=\left\{\begin{array}{c}1, if f\left(B\right)\le f(A) \\ {e}^{-(f\left(B\right)-f\left(A\right))/t} otherwise\end{array}\right., t=\beta \times t$$
(22)

In Eq. (21), \(t>0\) is a temperature parameter. A parameter control strategy must be used to set the initial value of t and adjust the value of this parameter during the search to use the metropolis acceptance criterion in the HHO algorithm. The HHO algorithm is simplified using Eq (15) at the end of each iteration. β is a parameter between 0 and 1, indicating the downward trend of the parameter t. An increase in and approaching this number to 1 reduces the downtrend, and vice versa; if this number approaches 0, the downtrend will increase.

4 Proposed algorithm

This section describes in detail how to integrate the mechanisms described in the previous sections. Equation (22) replaces Eq. (1). In Eq. (22), the mutation mechanism is DE/best/2, used as a powerful operator with high capability in the exploration phase. If \(\left|\rm {E}\right|\ge 1\), the proposed algorithm enters the exploration phase and uses Eq. (22). After each Eq. (22) generates the solution, the Lin-Kernighan local search mechanism is executed on the newly generated solution. Finally, the final solution produced replaces the current solution using the metropolis acceptance criterion.

$$Xnew=\left\{\begin{array}{c} {X}_{rand}(t) - {r}_{1} |{X}_{rand}(t) - 2{r}_{2}X(t)| q \ge 0.5\\ {X}_{rabbit}\left(t\right)+F\left({X}_{r1}\left(t\right)-{X}_{r2}\left(t\right)\right)+\left({X}_{r3}\left(t\right)-{X}_{r4}\left(t\right)\right) q < 0.5\end{array}\right.$$
(23)

Conversely, if \(|\rm {E}|<1\), the proposed algorithm enters the exploitation phase. In the exploitation phase, two different approaches are used: the first approach relates to the main mechanisms of the HHO algorithm and the second approach to improving the tour using neighborhood search operators. At the beginning of the exploitation phase, \(\rm {rand}()\) generates a random number between 0 and 1. If X≥q (0 <q <1)), the first approach is activated; Otherwise, the second approach is used. If the HHO algorithm uses the first approach and \(\rm {r }\ge 0.5\rm { and }|\rm {E}| \ge 0.5\), a soft besiege strategy is used to improve the solution.

Conversely, if \(\rm {r }\ge 0.5\rm { and }|\rm {E}| <0.5\), a hard besiege strategy is used to improve the tour. Following the soft besiege and hard besiege strategies, the Lin-Kernighan local search mechanism is applied to improve the new tour. Eventually, it will be replaced as the current solution using the metropolis acceptance criterion. However, at the beginning of the exploitation phase, if \(\rm {rand}()\) < q, the HHO algorithm uses the second approach to improve the tour. In this step, a neighborhood search operator is selected using the modified choice function to improve the tour. Then, the Lin-Kernighan local search mechanism is applied to and improves the newly generated tour. Finally, the newly produced tour is selected as the current solution using the metropolis acceptance criterion. Algorithm 2 shows the pseudo-code of the proposed algorithm. Figure 3 shows the flowchart of the proposed algorithm.

figure d
Fig. 3
figure 3

Flowchart of proposed algorithm

Full size image

According to Algorithm 2, the computational complexity of the HHO algorithm is \(\rm {O}(\rm {N}\times (\rm {T }+\rm { TD }+ 1))\), where N is the number of search factors, T represents the maximum number of iterations, and D represents the dimensions of the problem. In the proposed algorithm, like the HHO algorithm, only one update operation of the mechanisms in the exploration and operation phases is performed on the search agents. Moreover, local Search and MAC operations are performed on each search agent after each update operation. On the other hand, the proposed algorithm uses MCF and LLH mechanisms only in the operation phase if it is rand ≥ q. Therefore, the proposed algorithm performs three update processes and local Search and MAC only once in each iteration on each search factor, which complicates the computation.

4.1 Experimental settings

The proposed algorithm has been tested using a computer with the following specifications: Intel Core i7-7700k 4.50 GHz processor and 16 GB of RAM. It is then implemented using the Matlab programming language. A total of 75 instances of the existing datasets in TSPLIB [41]with dimensions of 100-85900 cities have been used. The number in the name of each instance indicates the number of cities in that instance; for example, the number of Kroa100 instance cities is equal to 100. Each TSP instance has been examined a total of 30 times using the proposed algorithm. The best net obtained at each run is placed in the set \(\rm {X }= \left\{\rm {c}1,\rm { c}2, \dots ,\rm { c}30\right\}\). The computational time to get the best tour is also placed in another set, i.e., \(\rm {T }= \{\rm {t}1,\rm { t}2, \dots ,\rm { t}30\}\). Here, \(\rm {X}\) is a set of best tours, and \(\rm {T}\) is a set of computational time to get the best tours. Eventually, these two sets are averaged. For this purpose, \({\upmu }_{\rm {T}}\) Moreover, \(Average\) are used to display the averages of the T and X sets, respectively. Finally, \(\rm {PDav}(\rm {\%})\) represents the mean percentage of deviation using Eq. (24).

$$\rm {PDav}(\rm {\%})=\frac{Average-BKS}{BKS}\times 100$$
(24)

Here, \(BKS\) indicates the known optimal tour length. Two criteria, namely the percentage of deviation from the known optimum and the computation time, have been used to obtain the best tour (measured in seconds) to evaluate the proposed algorithm's performance. Table 3 shows the parameter setting of the HHO algorithm.

Table 3 HHO algorithm parameter settings
Full size table

4.2 Experimental results

To evaluate the effect of LLHs performance, if LLHs are integrated with MCF in this section, the three modes of the proposed algorithm, namely, a random selection of LLHs and integration of four main LLHs, i.e., RIS, SS, RSS, and RRS with MCF, and integration of all LLHs with MCF are compared. This comparison has also been performed to evaluate MCF's performance if integrated with the Harris Hawk Optimization Algorithm. A stop condition of 1000 iterations is provided for all three modes HHO (MCF), HHO(5-LLH), and HHO (Random). To evaluate the performance of these three algorithms, the mean tour length, average percentage of deviation (\(\rm {PDav}(\rm {\%})\)), and mean computation time was obtained to achieve the best solution (\({\upmu }_{T}\)) (Table 4).

Table 4 Performance evaluation of HHO (MCF), HHO(5-LLH), and HHO (Random) based on 75 TSP standard instances
Full size table

According to the results in Table 3, HHO-MCF has shown the best performance in finding the best tour. HHO-MCF obtained an average of 0.092 (\(\rm {PDav}(\rm {\%})\)) based on 80 standard TSP instances. The HHO (5-LLH) and HHO (Random) models averaged 0.323 and 0.278, respectively, indicating their more unsatisfactory performance than the HHO-MCF model. On the other hand, with 30 execution times, the HHO-MCF model has solved 34 out of a total of 80 instances of the known optimum. Moreover, the HHO-MCF model has been shown to perform better in most instances; however, the HHO (5-LLH) and HHO (Random) models performed better in some instances.

The Wilcoxon signed-rank test [94] with a 95% confidence interval was used to make a statistical comparison between three models, namely HHO (MCF), HHO (5-LLH), and HHO (Random) in terms of performance. In the Wilcoxon signed-rank test, the difference in \(\rm {PDav}(\rm {\%})\) values in the two algorithms are used to compare and rank. Instances with equal values are not used in the two algorithms. After discarding equal instances, \(N\) indicates the number of use instances and \({R}^{+}\) indicates the set of instance scores. On the other hand, \({R}^{-}\) represents the total score of instances in which the proposed algorithm has shown worse performance than the compared algorithm. In the Wilcoxon signed-rank test, the value of W is compared to a critical value, \({W}_{Cri,N}\). \(\rm {W}\le {W}_{Cri,N}\) indicates a significant difference between the two algorithms in terms of performance. In contrast, \(\rm {W}>{W}_{Cri,N}\) means that there is no significant difference between the two algorithms in terms of performance. Table 5 presents the Wilcoxon signed-rank test results to compare three models, HHO (MCF), HHO(5-LLH), and HHO (Random), indicating the remarkable performance of the HHO (MCF) model.

Table 5 Wilcoxon signed-rank test to compare three models: HHO (MCF) and HHO(5-LLH) and HHO (Random)
Full size table

4.3 Competitiveness HHO-MCF

To further evaluate the performance of the proposed algorithm with other optimization algorithms, which are proposed to solve the TSP problem, which are DFFA [63], DSCA [52], HDABC [95], and MCF-ABC [17] has been tested and compared. These algorithms selected and implemented in this comparison are selected based on similar methods for optimization operations and based on these algorithms' new and powerful. This comparison is based on Average, PDav, and \({{\varvec{\mu}}}_{{\varvec{T}}}({\varvec{s}})\) criteria are done. On the other hand, for better evaluation, the Wilcoxon statistical test [96] with a 5% degree of significance has been performed to detect significant differences according to the results obtained from the proposed algorithm compared to other optimization methods. All experiments were performed using ten populations with a maximum of 1000 replications. All results were stored based on an average of 30 independent executions and compared based on these results. Comparison of algorithm settings DFFA [63], DSCA [52], HDABC [95], and MCF-ABC [17] are provided in the main work that has been performed. Also, the parameter settings of the comparing optimization algorithms are given in Table 6.

Table 6 Parameter settings of optimization algorithms for comparison and evaluation of the proposed algorithm
Full size table

Tables 7, 8, 9 show the results obtained from testing and evaluating the proposed algorithm and other comparative optimization algorithms using samples of small, medium and large dimensions.

Table 7 Comparison of the proposed algorithm with other models in small dimensions instance
Full size table

According to Table 7, the results obtained from the proposed algorithm's performance and other comparable algorithms are shown using small-sized samples. The results show that the proposed algorithm and MCF-ABC have achieved the known optimal value in all samples and have good performance in solving small-scale problems. DFFA algorithms have also shown that it has achieved the known optimal value in many samples in the face of small-scale problems. However, the HDABC and DSCA algorithms have achieved the known optimal value in almost half of the problems. According to the \({\upmu }_{{\varvec{T}}}({\varvec{s}})\) criterion, Maybe the proposed algorithm has the best performance and achieved quality solutions in less time than other optimization algorithms. Table 8 shows the results of testing the proposed algorithm and other comparable optimization algorithms using medium-sized samples.

Table 8 Comparison of the proposed algorithm with other models in medium dimensions' instance
Full size table

Table 8 shows the results obtained from testing the proposed algorithm and other comparable optimization algorithms using medium-sized samples. The results show that the proposed algorithm has a much better performance than other optimization algorithms and can obtain quality solutions compared to other optimization algorithms. Also, the proposed algorithm has been able to achieve the known optimal value in most samples. On the other hand, the MCF-ABC algorithm is ranked second in performance and has achieved the known optimal value in some samples. According to the \({\upmu }_{{\varvec{T}}}\left({\varvec{s}}\right)\) criterion, the proposed algorithm in solving medium-sized problems has been able to achieve quality solutions in less time and perform much better than other comparable algorithms in most samples Has shown itself. Table 9 shows the results of experiments performed using large samples.

Table 9 Comparison of the proposed algorithm with other models in high dimensions' instance
Full size table

According to the results of Table 9, which are the results obtained from the proposed algorithm and other comparable algorithms using large-sized samples, it is clear that the proposed algorithm has performed significantly better in the face of large-scale problems and has been able to In almost all samples to obtain quality and better solutions than the comparable algorithms. On the other hand, the MCF-ABC algorithm has the second-best performance and can obtain acceptable solutions. The third-best performance in experiments performed on large-scale samples is related to DFFA, which can obtain acceptable results in some samples. According to the \({{\varvec{\mu}}}_{{\varvec{T}}}\left({\varvec{s}}\right)\) criterion, the proposed algorithm can still obtain quality solutions in less time than other comparable optimization algorithms, and in almost all samples, it takes less time to find solutions that have spent quality. In this paper, to further investigate the performance of the \(PDav\) criteria proposed algorithm, we compared the proposed algorithm with D-CLPSO [46], SOM [97], and DPIO [48] algorithms in large-scale comparative samples. The results are shown in Table 10.

Table 10 Comparison of the proposed algorithm with DPIO, SOM, and D-CLPSO based on \(PDav\) criteria
Full size table

According to the results shown in Table 10, the proposed algorithm has a good and significant performance compared to the compared algorithms and has achieved much better results than the compared algorithms. The proposed algorithm has excellent and acceptable performance in the face of complex and significant issues. To further evaluate the proposed algorithm, it is compared with CLK [78], with the results shown in Table 11. The CLK source code [85], available in the Concorde TSP solver software, has been used to compare the proposed algorithm with the CLK. Large-scale instances are used for comparison. It is a single-solution-based model in which the population is equal to 1. This model is allowed to perform a maximum of 10,000 iterations. The default settings in Concorde are maintained to run as follows: initialization method (i.e., Quick-Boruvka), choice of the kick (i.e., 50-step random-walk kick) and the level of backtracking (i.e. (4, 3, 3, 2)-breadth).

Table 11 Comparison of the proposed algorithm with the CLK model
Full size table

Table 11 compares the proposed algorithm with the CLK model. Both models use a similar LK local search strategy. Examining this comparison results shows that the proposed algorithm performs better in small-scale instances, and the CLK model performs better in large-scale instances. The Wilcoxon signed-rank test with a confidence interval of 95% was utilized for comparing the proposed algorithm with other algorithms in terms of performance.

Table 12 compares the proposed algorithm with other competing performance optimization algorithms using the Wilcoxon signed-rank test with a confidence interval of 95%. The results indicate significantly better performance of the proposed algorithm compared to the other six models. In all comparisons \({\rm {R}}^{+} \rm {greater than }{\rm {R}}^{-}\rm { and W smaller than }{\rm {W}}_{\rm {Cri},\rm { N}}\) except for the CLK, that is \(\rm {W greater than }{\rm {W}}_{\rm {Cri},\rm { N}}\).

Table 12 Wilcoxon signed-rank test to compare the proposed algorithm with other models
Full size table

5 Discussion of the results

In this subsection, the proposed algorithm's performance is discussed based on the tests and evaluations performed. Table 4 shows the evaluation of MCF performance and the impact of neighborhood search operators on its improvement. According to these evaluations, the proposed algorithm using MCF and all ten neighborhood search operators has obtained higher quality tours than other compared models. This evaluation also shows that MCF has a significant impact on obtaining quality solutions. Because the intelligent choice of neighborhood search operators during optimization operations can be significant, on the other hand, it turns out that the use of MCF also leads to quality tours in a shorter period.

Table 7 shows the results obtained from the proposed algorithm's performance with DSCA, HDABC, DFFA and MCF-ABC algorithms in small samples. The proposed algorithm in all small dimensions has been able to achieve the known optimal value. However, the compared algorithms also performed well in small samples. Nevertheless, the proposed algorithm in terms of time has achieved quality tours in less time. However, the results of evaluations of medium-sized samples are shown in Table 8. The proposed algorithm has a much better performance than the compared algorithms compared to the medium-sized models, and in most of the samples, it has been able to obtain higher quality tours than the compared algorithms in a shorter period. Finally, Table 9 shows the results obtained from the proposed algorithm and the comparable algorithms in solving large-sized samples. According to the evaluations made with large samples, it has been determined that the proposed algorithm has much better performance and efficiency than the compared algorithms because it has been able to make quality tours for a shorter time than the compared algorithms.

On the other hand, in the comparison made in Table 10, the proposed algorithm has shown that it has a significantly good performance compared to DPIO, SOM and D-CLPSO algorithms and has much more capability and efficiency results obtained. It has been significantly better than the proposed algorithm. Compared to CLK, the proposed algorithm has shown complete superiority in small and medium-sized samples, but in partially large CLK samples, it has achieved slightly better results.

In general, the good results obtained from the proposed algorithm indicate the selection of excellent and complementary mechanisms. Because each of these mechanisms has increased the ability and balance of intensification and diversification components, as well as Multi-start Local Search (MSLS) [80] and Iterated Local Search (ILS) [84] systems have been created.

6 Conclusion and future works

The HHO algorithm is a new metaheuristic algorithm used to solve specific problems. This paper utilizes random-key encoding of the continuous optimization problem space to solve the TSP, a discrete permutation problem. The primary purpose of using random-key encoding is to maintain robust HHO strategies. Furthermore, a mutation operator, DE/best/2, was employed in the exploration phase to increase the proposed algorithm's performance in the exploitation phase. Ten neighborhood search operators have been utilized in the exploitation phase, four of which were presented to solve the TSP. A hyper-heuristic mechanism based on an MCF was used to select each neighborhood search operator. The MCF allows intelligent and automatic selection of neighborhood search operators during optimization.

On the other hand, a local search strategy called Lin-Kernighan (LK) was employed to improve the proposed algorithm's performance. Finally, the Metropolis acceptance strategy was utilized to escape the local optima trap. This paper presents and evaluates three models, namely HHO (MCF), HHO (5-LLH), and HHO (Random). The proposed algorithm was tested with 80 instances using two criteria: the computation time to obtain the best tour and the average deviation, compared with the seven previously presented models. The results indicated an acceptable performance of the proposed algorithm. The algorithm presented in this paper can be used to solve other problems. It is a good solution for use in other issues. In the future, the proposed algorithm can be used to solve combinatorial optimization problems such as vehicle routing and scheduling and mixed-integer programming problems. Different types of TSP instances can also be evaluated, including asymmetric, spherical, and generalized TSP.