This article presented a parallel cooperative hybrid algorithm for solving traveling salesman problem. Although heuristic approaches and hybrid methods obtain good results in solving the TSP, they cannot successfully ...
详细信息
This article presented a parallel cooperative hybrid algorithm for solving traveling salesman problem. Although heuristic approaches and hybrid methods obtain good results in solving the TSP, they cannot successfully avoid getting stuck to local optima. Furthermore, their processing duration unluckily takes a long time. To overcome these deficiencies, we propose the parallel cooperative hybrid algorithm (PACO-3opt) based on ant colony optimization. This method uses the 3-opt algorithm to avoid local minima. PACO-3opt has multiple colonies and a master-slave paradigm. Each colony runs ACO to generate the solutions. After a predefined number of iterations, each colony primarily runs 3-opt to improve the solutions and then shares the best tour with other colonies. This process continues until the termination criterion meets. Thus, it can reach the global optimum. PACO-3opt was compared with previous algorithms in the literature. The experimental results show that PACO-3opt is more efficient and reliable than the other algorithms.
The (1,2)-TSP is a special case of the TSP where each edge has cost either 1 or 2. In this paper we give a lower bound of 3/2 for the approximation ratio of the 2-optalgorithm for the (1,2)-TSP. Moreover, we show tha...
详细信息
The (1,2)-TSP is a special case of the TSP where each edge has cost either 1 or 2. In this paper we give a lower bound of 3/2 for the approximation ratio of the 2-optalgorithm for the (1,2)-TSP. Moreover, we show that the 3-opt algorithm has an exact approximation ratio of 11/8 for the (1,2)-TSP. Furthermore, we introduce the 3-opt++-algorithm, an improved version of the 3-opt algorithm for the (1-2)-TSP with an exact approximation ratio of 4/3. (C) 2021 Elsevier B.V. All rights reserved.
In this paper we propose a new Hybrid Bat algorithm to solve the traveling salesman problem (TSP) that has attracted many researchers applying exact and metaheuristic methods trying to solve it. The new proposed metho...
详细信息
ISBN:
(纸本)9781467387095
In this paper we propose a new Hybrid Bat algorithm to solve the traveling salesman problem (TSP) that has attracted many researchers applying exact and metaheuristic methods trying to solve it. The new proposed method is based on the basics of Bat algorithm (BA) recently proposed as a new bio-inspired meta-heuristic algorithm. Accordingly, we use the concepts of Swap Operator (SO) and Swap Sequence (SS) to redefine respectively BA position and velocity operators for TSP. Additionally, based on ordered crossover and 3-opt algorithm, we propose to redefine the Bat's local search method. We compare our algorithm to other state of the art methods from the literature by using benchmark datasets of symmetric TSP from TSPLIB library in order to test its effectiveness. Based on the recorded experiments our method outperforms most of the compared methods.
The Traveling Salesman Problem (TSP) is one of the standard test problems used in performance analysis of discrete optimization algorithms. The Ant Colony optimization (ACO) algorithm appears among heuristic algorithm...
详细信息
The Traveling Salesman Problem (TSP) is one of the standard test problems used in performance analysis of discrete optimization algorithms. The Ant Colony optimization (ACO) algorithm appears among heuristic algorithms used for solving discrete optimization problems. In this study, a new hybrid method is proposed to optimize parameters that affect performance of the ACO algorithm using Particle Swarm optimization (PSO). In addition, 3-opt heuristic method is added to proposed method in order to improve local solutions. The PSO algorithm is used for detecting optimum values of parameters alpha and beta which are used for city selection operations in the ACO algorithm and determines significance of inter-city pheromone and distances. The 3-opt algorithm is used for the purpose of improving city selection operations, which could not be improved due to falling in local minimums by the ACO algorithm. The performance of proposed hybrid method is investigated on ten different benchmark problems taken from literature and it is compared to the performance of some well-known algorithms. Experimental results show that the performance of proposed method by using fewer ants than the number of cities for the TSPs is better than the performance of compared methods in most cases in terms of solution quality and robustness. (C) 2015 Elsevier B.V. All rights reserved.
In this paper we propose a new Hybrid Bat algorithm to solve the traveling salesman problem (TSP) that has attracted many researchers applying exact and metaheuristic methods trying to solve it. The new proposed metho...
详细信息
In this paper we propose a new Hybrid Bat algorithm to solve the traveling salesman problem (TSP) that has attracted many researchers applying exact and metaheuristic methods trying to solve it. The new proposed method is based on the basics of Bat algorithm (BA) recently proposed as a new bio-inspired meta-heuristic algorithm. Accordingly, we use the concepts of Swap Operator (SO) and Swap Sequence (SS) to redefine respectively BA position and velocity operators for TSP. Additionally, based on ordered crossover and 3-opt algorithm, we propose to redefine the Bat's local search method. We compare our algorithm to other state of the art methods from the literature by using benchmark datasets of symmetric TSP from TSPLIB library in order to test its effectiveness. Based on the recorded experiments our method outperforms most of the compared methods.
As one of the most popular combinatorial optimization problems, Traveling Salesman Problem (TSP) has attracted lots of attention from academia since it was proposed. Numerous meta heuristics and heuristics have been p...
详细信息
As one of the most popular combinatorial optimization problems, Traveling Salesman Problem (TSP) has attracted lots of attention from academia since it was proposed. Numerous meta heuristics and heuristics have been proposed and used to solve the TSP. Although Ant Colony optimization (ACO) is a natural TSP solving algorithm, in the process of solving it, there are also some shortcomings such as slow convergence speed and prone to fall into local optimum. Therefore, this paper proposes an improved ant colony optimization based on graph convolutional network: Graph Convolutional Network Improved Ant Colony optimization (GCNIACO). The graph convolutional network is introduced to generate a better solution, and the better solution is converted into the pheromone on the initial path of the ACO. Thereby, the guiding effect of the pheromone concentration for the ants at the beginning of the algorithm is enhanced. In the meantime, through adaptive dynamic adjustment of the pheromone volatility factor and the introduction of the 3-opt algorithm, the algorithm???s ability to jump out of the local optimum is enhanced. Finally, GCNIACO is simulated on TSP datasets and engineering application example. Comparing the optimization results with other classical algorithms, it is verified that the graph convolutional network improved ant colony optimization has better performance in obtaining the optimal solution.
This paper presents a software application allowing to solve and compare the key metaheuristic approaches for solving the Traveling Salesman Problem (TSP). The focus is based on Ant Colony optimization (ACO) and its m...
详细信息
ISBN:
(纸本)9783319529417;9783319529400
This paper presents a software application allowing to solve and compare the key metaheuristic approaches for solving the Traveling Salesman Problem (TSP). The focus is based on Ant Colony optimization (ACO) and its major hybridization schema. In this work, the hybridization ACO algorithm with local search approach and the impact of parameters while solving TSP are investigated. The paper presents results of an empirical study of the solution quality over computation time for Ant System (AS), Elitist Ant System (EAS), Best-Worst Ant System (BWAS), MAX-MIN Ant System (MMAS) and Ant Colony System (ACS), five well-known ACO algorithms. In addition, this paper describes ACO approach combined with local search approach as 2-opt and 3-opt algorithms to obtain the best solution compared to ACO without local search with fixed parameters setting. The simulation experiments results show that ACO hybridized with the local search algorithm is effective for solving TSP and for avoiding the premature stagnation phenomenon of standard ACO.
The nested partitions method (NPM) is a global optimization method, which can be applied to solve many large-scale discrete optimization problems. The basic procedure of this method for solving the traveling salesman ...
详细信息
ISBN:
(数字)9783642549243
ISBN:
(纸本)9783642549243;9783642549236
The nested partitions method (NPM) is a global optimization method, which can be applied to solve many large-scale discrete optimization problems. The basic procedure of this method for solving the traveling salesman problem (TSP) was introduced. Based on the analysis and determination of the strategy of the four arithmetic operators of NPM, an improved NPM was proposed. The initial most promising region was improved by weighted sampling method;The historical optimal solution of every region was recorded in a global array;the 3-opt algorithm was combined in the local search for improving the quality of solution for every subregion;the improved Lin-Kernighan algorithm was used in the search for improving the quality of solution for surrounding region. Some experimental results of TSPLIB (TSP Library) show that the proposed improved NPM can find solutions of high quality efficiently when applied to the TSP.
暂无评论