A perturbation based modified BAT algorithm for priority based covering salesman problem

In this study, Bat algorithm (BA) is modified along with K-opt operation and one newly proposed perturbation approach to solve the well known covering salesman problem (CSP). Here, along with the restriction of the radial distances of the unvisited cities from the visited cities another restriction is imposed where a priority is given to some cities for the inclusion in the tour, i.e., some clusters to be created where the prioritised cities must be the visiting cities and the corresponding CSP is named as Prioritised CSP (PCSP). In the algorithm, 3-opt and 4-opt operations are used for two different purposes. The 4-opt operation is applied for generating an initial solution set of CSP for the BA and the 3-opt operation generates some perturbed solutions of a solution. A new perturbation approach is proposed for generating neighbour solutions of a potential solution where the exchange of some cities in the tour is made and is named as K-bit exchange operation. The proposed solution approach for the CSP and PCSP is named as the modified BA embedded with K-bit exchange and K-opt operation (MBAKEKO). It is a two-stage algorithm where in the first stage of the algorithm the clustering of the cities is done with respect to a fixed visiting city of each cluster in such a manner that the distances of the other cities of the cluster must lie with in the fixed covering distance of the problem and in the second stage the BA is applied to find the minimum cost Hamiltonian circuit by passing through the visiting cities of the clusters. MBAKEKO is tested with a set of benchmark test problems with significantly large sizes from the TSPLIB. To measure the performance of MBAKEKO, its results are compared with the results of different well-known approaches for CSPs available in the literature. It is observed from the comparison studies that MBAKEKO searches the minimum cost tour for any of the considered instances compared to all other well-known algorithms in the literature. It can be concluded from the numerical studies that the performance of MBAKEKO is better with respect to the state-of-the-art algorithms available in the literature.

A Two-Way Parallel Slime Mold Algorithm by Flow and Distance for the Travelling Salesman Problem

In order to solve the problem of poor local optimization of the Slime Mold Algorithm (SMA) in the Travelling Salesman Problem (TSP), a Two-way Parallel Slime Mold Algorithm by Flow and Distance (TPSMA) is proposed in this paper. Firstly, the flow between each path point is calculated by the “critical pipeline and critical culture” model of SMA; then, according to the two indexes of flow and distance, the set of path points to be selected is obtained; finally, the optimization principle with a flow index is improved with two indexes of flow and distance and added random strategy. Hence, a two-way parallel optimization method is realized and the local optimal problem is solved effectively. Through the simulation of Traveling Salesman Problem Library (TSPLIB) on ulysses16, city31, eil51, gr96, and bier127, the results of TPSMA were improved by 24.56, 36.10, 41.88, 49.83, and 52.93%, respectively, compared to SMA. Furthermore, the number of path points is more and the optimization ability of TPSMA is better. At the same time, TPSMA is closer to the current optimal result than other algorithms by multiple sets of tests, and its time complexity is obviously better than others. Therefore, the superiority of TPSMA is adequately proven.

A Hybrid Particle Swarm Optimization Algorithm Enhanced with Nonlinear Inertial Weight and Gaussian Mutation for Job Shop Scheduling Problems

Job shop scheduling problem (JSSP) has high theoretical and practical significance in academia and manufacturing respectively. Therefore, scholars in many different fields have been attracted to study this problem, and many meta-heuristic algorithms have been proposed to solve this problem. As a meta-heuristic algorithm, particle swarm optimization (PSO) has been used to optimize many practical problems in industrial manufacturing. This paper proposes a hybrid PSO enhanced with nonlinear inertia weight and and Gaussian mutation (NGPSO) to solve JSSP. Nonlinear inertia weight improves local search capabilities of PSO, while Gaussian mutation strategy improves the global search ability of NGPSO, which is beneficial to the population to maintain diversity and reduce probability of the algorithm falling into the local optimal solution. The proposed NGPSO algorithm is implemented to solve 62 benchmark instances of JSSP, and the experimental results are compared with other algorithms. The results obtained by analyzing the experimental data show that the algorithm is better than other comparison algorithms in solving JSSP.

Hybrid Algorithm Based on Ant Colony Optimization and Simulated Annealing Applied to the Dynamic Traveling Salesman Problem

The dynamic traveling salesman problem (DTSP) falls under the category of combinatorial dynamic optimization problems. The DTSP is composed of a primary TSP sub-problem and a series of TSP iterations; each iteration is created by changing the previous iteration. In this article, a novel hybrid metaheuristic algorithm is proposed for the DTSP. This algorithm combines two metaheuristic principles, specifically ant colony optimization (ACO) and simulated annealing (SA). Moreover, the algorithm exploits knowledge about the dynamic changes by transferring the information gathered in previous iterations in the form of a pheromone matrix. The significance of the hybridization, as well as the use of knowledge about the dynamic environment, is examined and validated on benchmark instances including small, medium, and large DTSP problems. The results are compared to the four other state-of-the-art metaheuristic approaches with the conclusion that they are significantly outperformed by the proposed algorithm. Furthermore, the behavior of the algorithm is analyzed from various points of view (including, for example, convergence speed to local optimum, progress of population diversity during optimization, and time dependence and computational complexity).