期刊文献+
共找到49篇文章
< 1 2 3 >
每页显示 20 50 100
On the “Onion Husk” Algorithm for Approximate Solution of the Traveling Salesman Problem
1
作者 Mikhail E. Abramyan Nikolai I. Krainiukov Boris F. Melnikov 《Journal of Applied Mathematics and Physics》 2024年第4期1557-1570,共14页
The paper describes some implementation aspects of an algorithm for approximate solution of the traveling salesman problem based on the construction of convex closed contours on the initial set of points (“cities”) ... The paper describes some implementation aspects of an algorithm for approximate solution of the traveling salesman problem based on the construction of convex closed contours on the initial set of points (“cities”) and their subsequent combination into a closed path (the so-called contour algorithm or “onion husk” algorithm). A number of heuristics related to the different stages of the algorithm are considered, and various variants of the algorithm based on these heuristics are analyzed. Sets of randomly generated points of different sizes (from 4 to 90 and from 500 to 10,000) were used to test the algorithms. The numerical results obtained are compared with the results of two well-known combinatorial optimization algorithms, namely the algorithm based on the branch and bound method and the simulated annealing algorithm. . 展开更多
关键词 Branch and Bound Method Contour Algorithm “Onion Husk” Algorithm Simulated Annealing Method traveling salesman problem
下载PDF
Solving the Generalized Traveling Salesman Problem Using Sequential Constructive Crossover Operator in Genetic Algorithm
2
作者 Zakir Hussain Ahmed Maha Ata Al-Furhood +1 位作者 Abdul Khader Jilani Saudagar Shakir Khan 《Computer Systems Science & Engineering》 2024年第5期1113-1131,共19页
The generalized travelling salesman problem(GTSP),a generalization of the well-known travelling salesman problem(TSP),is considered for our study.Since the GTSP is NP-hard and very complex,finding exact solutions is h... The generalized travelling salesman problem(GTSP),a generalization of the well-known travelling salesman problem(TSP),is considered for our study.Since the GTSP is NP-hard and very complex,finding exact solutions is highly expensive,we will develop genetic algorithms(GAs)to obtain heuristic solutions to the problem.In GAs,as the crossover is a very important process,the crossovermethods proposed for the traditional TSP could be adapted for the GTSP.The sequential constructive crossover(SCX)and three other operators are adapted to use in GAs to solve the GTSP.The effectiveness of GA using SCX is verified on some GTSP Library(GTSPLIB)instances first and then compared against GAs using the other crossover methods.The computational results show the success of the GA using SCX for this problem.Our proposed GA using SCX,and swap mutation could find average solutions whose average percentage of excesses fromthe best-known solutions is between 0.00 and 14.07 for our investigated instances. 展开更多
关键词 Generalized travelling salesman problem NP-HARD genetic algorithms sequential constructive crossover swap mutation
下载PDF
K-DSA for the multiple traveling salesman problem 被引量:1
3
作者 TONG Sheng QU Hong XUE Junjie 《Journal of Systems Engineering and Electronics》 SCIE EI CSCD 2023年第6期1614-1625,共12页
Aimed at a multiple traveling salesman problem(MTSP)with multiple depots and closed paths,this paper proposes a k-means clustering donkey and a smuggler algorithm(KDSA).The algorithm first uses the k-means clustering ... Aimed at a multiple traveling salesman problem(MTSP)with multiple depots and closed paths,this paper proposes a k-means clustering donkey and a smuggler algorithm(KDSA).The algorithm first uses the k-means clustering method to divide all cities into several categories based on the center of various samples;the large-scale MTSP is divided into multiple separate traveling salesman problems(TSPs),and the TSP is solved through the DSA.The proposed algorithm adopts a solution strategy of clustering first and then carrying out,which can not only greatly reduce the search space of the algorithm but also make the search space more fully explored so that the optimal solution of the problem can be more quickly obtained.The experimental results from solving several test cases in the TSPLIB database show that compared with other related intelligent algorithms,the K-DSA has good solving performance and computational efficiency in MTSPs of different scales,especially with large-scale MTSP and when the convergence speed is faster;thus,the advantages of this algorithm are more obvious compared to other algorithms. 展开更多
关键词 k-means clustering donkey and smuggler algorithm(DSA) multiple traveling salesman problem(MTSP) multiple depots and closed paths.
下载PDF
A Scheme Library-Based Ant Colony Optimization with 2-Opt Local Search for Dynamic Traveling Salesman Problem
4
作者 Chuan Wang Ruoyu Zhu +4 位作者 Yi Jiang Weili Liu Sang-Woon Jeon Lin Sun Hua Wang 《Computer Modeling in Engineering & Sciences》 SCIE EI 2023年第5期1209-1228,共20页
The dynamic traveling salesman problem(DTSP)is significant in logistics distribution in real-world applications in smart cities,but it is uncertain and difficult to solve.This paper proposes a scheme library-based ant... The dynamic traveling salesman problem(DTSP)is significant in logistics distribution in real-world applications in smart cities,but it is uncertain and difficult to solve.This paper proposes a scheme library-based ant colony optimization(ACO)with a two-optimization(2-opt)strategy to solve the DTSP efficiently.The work is novel and contributes to three aspects:problemmodel,optimization framework,and algorithmdesign.Firstly,in the problem model,traditional DTSP models often consider the change of travel distance between two nodes over time,while this paper focuses on a special DTSP model in that the node locations change dynamically over time.Secondly,in the optimization framework,the ACO algorithm is carried out in an offline optimization and online application framework to efficiently reuse the historical information to help fast respond to the dynamic environment.The framework of offline optimization and online application is proposed due to the fact that the environmental change inDTSPis caused by the change of node location,and therefore the newenvironment is somehowsimilar to certain previous environments.This way,in the offline optimization,the solutions for possible environmental changes are optimized in advance,and are stored in a mode scheme library.In the online application,when an environmental change is detected,the candidate solutions stored in the mode scheme library are reused via ACO to improve search efficiency and reduce computational complexity.Thirdly,in the algorithm design,the ACO cooperates with the 2-opt strategy to enhance search efficiency.To evaluate the performance of ACO with 2-opt,we design two challenging DTSP cases with up to 200 and 1379 nodes and compare them with other ACO and genetic algorithms.The experimental results show that ACO with 2-opt can solve the DTSPs effectively. 展开更多
关键词 Dynamic traveling salesman problem(DTSP) offline optimization and online application ant colony optimization(ACO) two-optimization(2-opt)strategy
下载PDF
Improved ant colony optimization algorithm for the traveling salesman problems 被引量:22
5
作者 Rongwei Gan Qingshun Guo +1 位作者 Huiyou Chang Yang Yi 《Journal of Systems Engineering and Electronics》 SCIE EI CSCD 2010年第2期329-333,共5页
Ant colony optimization (ACO) is a new heuristic algo- rithm which has been proven a successful technique and applied to a number of combinatorial optimization problems. The traveling salesman problem (TSP) is amo... Ant colony optimization (ACO) is a new heuristic algo- rithm which has been proven a successful technique and applied to a number of combinatorial optimization problems. The traveling salesman problem (TSP) is among the most important combinato- rial problems. An ACO algorithm based on scout characteristic is proposed for solving the stagnation behavior and premature con- vergence problem of the basic ACO algorithm on TSP. The main idea is to partition artificial ants into two groups: scout ants and common ants. The common ants work according to the search manner of basic ant colony algorithm, but scout ants have some differences from common ants, they calculate each route's muta- tion probability of the current optimal solution using path evaluation model and search around the optimal solution according to the mutation probability. Simulation on TSP shows that the improved algorithm has high efficiency and robustness. 展开更多
关键词 ant colony optimization heuristic algorithm scout ants path evaluation model traveling salesman problem.
下载PDF
A Hybrid Genetic Algorithm for the Traveling Salesman Problem with Pickup and Delivery 被引量:10
6
作者 Fang-Geng Zhao Jiang-Sheng Sun +1 位作者 Su-Jian Li Wei-Min Liu 《International Journal of Automation and computing》 EI 2009年第1期97-102,共6页
In this paper, a hybrid genetic algorithm (GA) is proposed for the traveling salesman problem (TSP) with pickup and delivery (TSPPD). In our algorithm, a novel pheromone-based crossover operator is advanced that... In this paper, a hybrid genetic algorithm (GA) is proposed for the traveling salesman problem (TSP) with pickup and delivery (TSPPD). In our algorithm, a novel pheromone-based crossover operator is advanced that utilizes both local and global information to construct offspring. In addition, a local search procedure is integrated into the GA to accelerate convergence. The proposed GA has been tested on benchmark instances, and the computational results show that it gives better convergence than existing heuristics. 展开更多
关键词 Genetic algorithm (GA) pheromone-based crossover local search pickup and delivery traveling salesman problem(TSP).
下载PDF
Collision-free Scheduling of Multi-bridge Machining Systems: A Colored Traveling Salesman Problem-based Approach 被引量:2
7
作者 Jun Li Xianghu Meng Xing Dai 《IEEE/CAA Journal of Automatica Sinica》 SCIE EI CSCD 2018年第1期139-147,共9页
Multi-bridge machining systems(MBMS) have gained wide applications in industry due to their high production capacity and efficiency. They contain multiple bridge machines working in parallel within their partially ove... Multi-bridge machining systems(MBMS) have gained wide applications in industry due to their high production capacity and efficiency. They contain multiple bridge machines working in parallel within their partially overlapping workspaces.Their scheduling problems can be abstracted into a serial-colored travelling salesman problem in which each salesman has some exclusive cities and some cities shared with its neighbor(s). To solve it, we develop a greedy algorithm that selects a neighboring city satisfying proximity. The algorithm allows a salesman to select randomly its shared cities and runs accordingly many times. It can thus be used to solve job scheduling problems for MBMS. Subsequently, a collision-free scheduling method is proposed to address both job scheduling and collision resolution issues of MBMS. It is an extension of the greedy algorithm by introducing time window constraints and a collision resolution mechanism. Thus, the augmented greedy algorithm can try its best to select stepwise a job for an individual machine such that no time overlaps exist between it and the job sequence of the neighboring machine dealt in the corresponding overlapping workspace; and remove such a time overlap only when it is inevitable. Finally, we conduct a case study of a large triplebridge waterjet cutting system by applying the proposed method. 展开更多
关键词 Collision resolution greedy algorithm modeling multiple traveling salesman problem SCHEDULING
下载PDF
The Quantum Approximate Algorithm for Solving Traveling Salesman Problem 被引量:3
8
作者 Yue Ruan Samuel Marsh +2 位作者 Xilin Xue Zhihao Liu Jingbo Wang 《Computers, Materials & Continua》 SCIE EI 2020年第6期1237-1247,共11页
The Quantum Approximate Optimization Algorithm(QAOA)is an algorithmic framework for finding approximate solutions to combinatorial optimization problems.It consists of interleaved unitary transformations induced by tw... The Quantum Approximate Optimization Algorithm(QAOA)is an algorithmic framework for finding approximate solutions to combinatorial optimization problems.It consists of interleaved unitary transformations induced by two operators labelled the mixing and problem Hamiltonians.To fit this framework,one needs to transform the original problem into a suitable form and embed it into these two Hamiltonians.In this paper,for the well-known NP-hard Traveling Salesman Problem(TSP),we encode its constraints into the mixing Hamiltonian rather than the conventional approach of adding penalty terms to the problem Hamiltonian.Moreover,we map edges(routes)connecting each pair of cities to qubits,which decreases the search space significantly in comparison to other approaches.As a result,our method can achieve a higher probability for the shortest round-trip route with only half the number of qubits consumed compared to IBM Q’s approach.We argue the formalization approach presented in this paper would lead to a generalized framework for finding,in the context of QAOA,high-quality approximate solutions to NP optimization problems. 展开更多
关键词 Quantum approximate optimization algorithm traveling salesman problem NP optimization problems
下载PDF
Parallel discrete lion swarm optimization algorithm for solving traveling salesman problem 被引量:2
9
作者 ZHANG Daoqing JIANG Mingyan 《Journal of Systems Engineering and Electronics》 SCIE EI CSCD 2020年第4期751-760,共10页
As a typical representative of the NP-complete problem, the traveling salesman problem(TSP) is widely utilized in computer networks, logistics distribution, and other fields. In this paper, a discrete lion swarm optim... As a typical representative of the NP-complete problem, the traveling salesman problem(TSP) is widely utilized in computer networks, logistics distribution, and other fields. In this paper, a discrete lion swarm optimization(DLSO) algorithm is proposed to solve the TSP. Firstly, we introduce discrete coding and order crossover operators in DLSO. Secondly, we use the complete 2-opt(C2-opt) algorithm to enhance the local search ability.Then in order to enhance the efficiency of the algorithm, a parallel discrete lion swarm optimization(PDLSO) algorithm is proposed.The PDLSO has multiple populations, and each sub-population independently runs the DLSO algorithm in parallel. We use the ring topology to transfer information between sub-populations. Experiments on some benchmarks TSP problems show that the DLSO algorithm has a better accuracy than other algorithms, and the PDLSO algorithm can effectively shorten the running time. 展开更多
关键词 discrete lion swarm optimization(DLSO)algorithm complete 2-opt(C2-opt)algorithm parallel discrete lion swarm optimization(PDLSO)algorithm traveling salesman problem(TSP)
下载PDF
Applying the Method for Solving Traveling Salesman Problem Based on Backtracking Algorithm to Order Picking 被引量:1
10
作者 Jie Zhu Ying Huang Lijuan Xu 《Open Journal of Optimization》 2016年第2期84-89,共6页
In the distribution center, the way of order picking personnel to pick goods has two kinds: single picking and batch picking. Based on the way of the single picking and assumed warehouse model, in order to reduce the ... In the distribution center, the way of order picking personnel to pick goods has two kinds: single picking and batch picking. Based on the way of the single picking and assumed warehouse model, in order to reduce the walking path of order picking, the order picking problem is transformed into the traveling salesman problem in this paper. Based on backtracking algorithm, the order picking path gets optimized. Finally verifing the optimization method under the environment of VC++6.0, order picking path in the warehouse model get optimized, and compared with the traditional order picking walking paths. The results show that in small and medium-sized warehouse, the optimization method proposed in this paper can reduce order picking walking path and improve the work efficiency as well as reduce the time cost. 展开更多
关键词 Single Picking Path Optimization traveling salesman problem Backtracking Algorithm
下载PDF
A Multi-Agent Approach for Solving Traveling Salesman Problem
11
作者 ZHOU Tiejun TAN Yihong XING Lining 《Wuhan University Journal of Natural Sciences》 CAS 2006年第5期1104-1108,共5页
The traveling salesman problem (TSP) is a classical optimization problem and it is one of a class of NP- Problem. This paper presents a new method named multiagent approach based genetic algorithm and ant colony sys... The traveling salesman problem (TSP) is a classical optimization problem and it is one of a class of NP- Problem. This paper presents a new method named multiagent approach based genetic algorithm and ant colony system to solve the TSP. Three kinds of agents with different function were designed in the multi-agent architecture proposed by this paper. The first kind of agent is ant colony optimization agent and its function is generating the new solution continuously. The second kind of agent is selection agent, crossover agent and mutation agent, their function is optimizing the current solutions group. The third kind of agent is fast local searching agent and its function is optimizing the best solution from the beginning of the trial. At the end of this paper, the experimental results have shown that the proposed hybrid ap proach has good performance with respect to the quality of solution and the speed of computation. 展开更多
关键词 traveling salesman problem multi-agent approach genetic algorithm ant colony system
下载PDF
Ant-cycle based on Metropolis rules for the traveling salesman problem
12
作者 龚劬 《Journal of Chongqing University》 CAS 2005年第4期229-232,共4页
In this paper, recent developments of some heuristic algorithms were discussed. The focus was laid on the improvements of ant-cycle (AC) algorithm based on the analysis of the performances of simulated annealing (SA) ... In this paper, recent developments of some heuristic algorithms were discussed. The focus was laid on the improvements of ant-cycle (AC) algorithm based on the analysis of the performances of simulated annealing (SA) and AC for the traveling salesman problem (TSP). The Metropolis rules in SA were applied to AC and turned out an improved AC. The computational results obtained from the case study indicated that the improved AC algorithm has advantages over the sheer SA or unmixed AC. 展开更多
关键词 heuristics algorithm simulate annealing algorithm metropolis rules ant colony algorithm ant-cycle algorithm traveling salesman problem (TSP)
下载PDF
Novel Local Search Method for the Traveling Salesman Problem
13
作者 黄文奇 王磊 《Journal of Southwest Jiaotong University(English Edition)》 2005年第1期1-4,共4页
A new local search method for the traveling salesman problem based on an original greedy representation of solution space and neighborhood structure is proposed. First, a partial closed route that only consists of thr... A new local search method for the traveling salesman problem based on an original greedy representation of solution space and neighborhood structure is proposed. First, a partial closed route that only consists of three cities is given; then other cities are added to this route by a greedy procedure successively. Implemented on a personal computer, this algorithm finds optimal solutions for 24 out of 27 standard benchmarks, and outperforms the Full Subpath Ejection Algorithm (F-SEC) proposed by Rego in 1998. 展开更多
关键词 traveling salesman problem HEURISTICS Local search
下载PDF
A Parallel Search System for Dynamic Multi-Objective Traveling Salesman Problem
14
作者 Weiqi Li 《Journal of Mathematics and System Science》 2014年第5期295-314,共20页
This paper introduces a parallel search system for dynamic multi-objective traveling salesman problem. We design a multi-objective TSP in a stochastic dynamic environment. This dynamic setting of the problem is very u... This paper introduces a parallel search system for dynamic multi-objective traveling salesman problem. We design a multi-objective TSP in a stochastic dynamic environment. This dynamic setting of the problem is very useful for routing in ad-hoc networks. The proposed search system first uses parallel processors to identify the extreme solutions of the search space for each ofk objectives individually at the same time. These solutions are merged into the so-called hit-frequency matrix E. The solutions in E are then searched by parallel processors and evaluated for dominance relationship. The search system is implemented in two different ways master-worker architecture and pipeline architecture. 展开更多
关键词 dynamic multi-objective optimization traveling salesman problem parallel search algorithm solution attractor.
下载PDF
Algorithm for Solving Traveling Salesman Problem Based on Self-Organizing Mapping Network
15
作者 朱江辉 叶航航 +1 位作者 姚莉秀 蔡云泽 《Journal of Shanghai Jiaotong university(Science)》 EI 2024年第3期463-470,共8页
Traveling salesman problem(TSP)is a classic non-deterministic polynomial-hard optimization prob-lem.Based on the characteristics of self-organizing mapping(SOM)network,this paper proposes an improved SOM network from ... Traveling salesman problem(TSP)is a classic non-deterministic polynomial-hard optimization prob-lem.Based on the characteristics of self-organizing mapping(SOM)network,this paper proposes an improved SOM network from the perspectives of network update strategy,initialization method,and parameter selection.This paper compares the performance of the proposed algorithms with the performance of existing SOM network algorithms on the TSP and compares them with several heuristic algorithms.Simulations show that compared with existing SOM networks,the improved SOM network proposed in this paper improves the convergence rate and algorithm accuracy.Compared with iterated local search and heuristic algorithms,the improved SOM net-work algorithms proposed in this paper have the advantage of fast calculation speed on medium-scale TSP. 展开更多
关键词 traveling salesman problem(TSP) self-organizing mapping(SOM) combinatorial optimization neu-ral network
原文传递
Appropriate Combination of Crossover Operator and Mutation Operator in Genetic Algorithms for the Travelling Salesman Problem
16
作者 Zakir Hussain Ahmed Habibollah Haron Abdullah Al-Tameem 《Computers, Materials & Continua》 SCIE EI 2024年第5期2399-2425,共27页
Genetic algorithms(GAs)are very good metaheuristic algorithms that are suitable for solving NP-hard combinatorial optimization problems.AsimpleGAbeginswith a set of solutions represented by a population of chromosomes... Genetic algorithms(GAs)are very good metaheuristic algorithms that are suitable for solving NP-hard combinatorial optimization problems.AsimpleGAbeginswith a set of solutions represented by a population of chromosomes and then uses the idea of survival of the fittest in the selection process to select some fitter chromosomes.It uses a crossover operator to create better offspring chromosomes and thus,converges the population.Also,it uses a mutation operator to explore the unexplored areas by the crossover operator,and thus,diversifies the GA search space.A combination of crossover and mutation operators makes the GA search strong enough to reach the optimal solution.However,appropriate selection and combination of crossover operator and mutation operator can lead to a very good GA for solving an optimization problem.In this present paper,we aim to study the benchmark traveling salesman problem(TSP).We developed several genetic algorithms using seven crossover operators and six mutation operators for the TSP and then compared them to some benchmark TSPLIB instances.The experimental studies show the effectiveness of the combination of a comprehensive sequential constructive crossover operator and insertion mutation operator for the problem.The GA using the comprehensive sequential constructive crossover with insertion mutation could find average solutions whose average percentage of excesses from the best-known solutions are between 0.22 and 14.94 for our experimented problem instances. 展开更多
关键词 Travelling salesman problem genetic algorithms crossover operator mutation operator comprehensive sequential constructive crossover insertion mutation
下载PDF
A Novel Insertion Solution for the Travelling Salesman Problem
17
作者 Emmanuel Oluwatobi Asani Aderemi Elisha Okeyinka +5 位作者 Sunday Adeola Ajagbe Ayodele Ariyo Adebiyi Roseline Oluwaseun Ogundokun Temitope Samson Adekunle Pragasen Mudali Matthew Olusegun Adigun 《Computers, Materials & Continua》 SCIE EI 2024年第4期1581-1597,共17页
The studypresents theHalfMax InsertionHeuristic (HMIH) as a novel approach to solving theTravelling SalesmanProblem (TSP). The goal is to outperform existing techniques such as the Farthest Insertion Heuristic (FIH) a... The studypresents theHalfMax InsertionHeuristic (HMIH) as a novel approach to solving theTravelling SalesmanProblem (TSP). The goal is to outperform existing techniques such as the Farthest Insertion Heuristic (FIH) andNearest Neighbour Heuristic (NNH). The paper discusses the limitations of current construction tour heuristics,focusing particularly on the significant margin of error in FIH. It then proposes HMIH as an alternative thatminimizes the increase in tour distance and includes more nodes. HMIH improves tour quality by starting withan initial tour consisting of a ‘minimum’ polygon and iteratively adding nodes using our novel Half Max routine.The paper thoroughly examines and compares HMIH with FIH and NNH via rigorous testing on standard TSPbenchmarks. The results indicate that HMIH consistently delivers superior performance, particularly with respectto tour cost and computational efficiency. HMIH’s tours were sometimes 16% shorter than those generated by FIHand NNH, showcasing its potential and value as a novel benchmark for TSP solutions. The study used statisticalmethods, including Friedman’s Non-parametric Test, to validate the performance of HMIH over FIH and NNH.This guarantees that the identified advantages are statistically significant and consistent in various situations. Thiscomprehensive analysis emphasizes the reliability and efficiency of the heuristic, making a compelling case for itsuse in solving TSP issues. The research shows that, in general, HMIH fared better than FIH in all cases studied,except for a few instances (pr439, eil51, and eil101) where FIH either performed equally or slightly better thanHMIH. HMIH’s efficiency is shown by its improvements in error percentage (δ) and goodness values (g) comparedto FIH and NNH. In the att48 instance, HMIH had an error rate of 6.3%, whereas FIH had 14.6% and NNH had20.9%, indicating that HMIH was closer to the optimal solution. HMIH consistently showed superior performanceacross many benchmarks, with lower percentage error and higher goodness values, suggesting a closer match tothe optimal tour costs. This study substantially contributes to combinatorial optimization by enhancing currentinsertion algorithms and presenting a more efficient solution for the Travelling Salesman Problem. It also createsnew possibilities for progress in heuristic design and optimization methodologies. 展开更多
关键词 Nearest neighbour heuristic farthest insertion heuristic half max insertion heuristic tour construction travelling salesman problem
下载PDF
Two-Level Genetic Algorithm for Clustered Traveling Salesman Problem with Application in Large-Scale TSPs 被引量:9
18
作者 丁超 成晔 何苗 《Tsinghua Science and Technology》 SCIE EI CAS 2007年第4期459-465,共7页
Let G = (V, E) be a complete undirected graph with vertex set V, edge set E, and edge weights I(e) satisfying the triangle inequality. The vertex set V is partitioned into clusters V1, V2 ,…, Vk. The clustered tr... Let G = (V, E) be a complete undirected graph with vertex set V, edge set E, and edge weights I(e) satisfying the triangle inequality. The vertex set V is partitioned into clusters V1, V2 ,…, Vk. The clustered traveling salesman problem (CTSP) seeks to compute the shortest Hamiltonian tour that visits all the vertices, in which the vertices of each cluster are visited consecutively. A two-level genetic algorithm (TLGA) was developed for the problem, which favors neither intra-cluster paths nor inter-cluster paths, thus realized integrated evolutionary optimization for both levels of the CTSP. Results show that the algorithm is more effective than known algorithms. A large-scale traveling salesman problem (TSP) can be converted into a CTSP by clustering so that it can then be solved by the algorithm. Test results demonstrate that the clustering TLGA for large TSPs is more effective and efficient than the classical genetic algorithm. 展开更多
关键词 clustered traveling salesman problem (CTSP) traveling salesman problem (TSP) Hamiltonian cycle genetic algorithm integrated evolutionary optimization
原文传递
An improved fruit fly optimization algorithm for solving traveling salesman problem 被引量:4
19
作者 Lan HUANG Gui-chao WANG +1 位作者 Tian BAI Zhe WANG 《Frontiers of Information Technology & Electronic Engineering》 SCIE EI CSCD 2017年第10期1525-1533,共9页
The traveling salesman problem(TSP), a typical non-deterministic polynomial(NP) hard problem, has been used in many engineering applications. As a new swarm-intelligence optimization algorithm, the fruit fly optimizat... The traveling salesman problem(TSP), a typical non-deterministic polynomial(NP) hard problem, has been used in many engineering applications. As a new swarm-intelligence optimization algorithm, the fruit fly optimization algorithm(FOA) is used to solve TSP, since it has the advantages of being easy to understand and having a simple implementation. However, it has problems, including a slow convergence rate for the algorithm, easily falling into the local optimum, and an insufficient optimization precision. To address TSP effectively, three improvements are proposed in this paper to improve FOA. First, the vision search process is reinforced in the foraging behavior of fruit flies to improve the convergence rate of FOA. Second, an elimination mechanism is added to FOA to increase the diversity. Third, a reverse operator and a multiplication operator are proposed. They are performed on the solution sequence in the fruit fly's smell search and vision search processes, respectively. In the experiment, 10 benchmarks selected from TSPLIB are tested. The results show that the improved FOA outperforms other alternatives in terms of the convergence rate and precision. 展开更多
关键词 traveling salesman problem Fruit fly optimization algorithm Elimination mechanism Vision search OPERATOR
原文传递
A Puzzle-Based Genetic Algorithm with Block Mining and Recombination Heuristic for the Traveling Salesman Problem 被引量:1
20
作者 张百栈 黄伟修 张真真 《Journal of Computer Science & Technology》 SCIE EI CSCD 2012年第5期937-949,共13页
In this research, we introduce a new heuristic approach using the concept of ant colony optimization (ACO) to extract patterns from the chromosomes generated by previous generations for solving the generalized trave... In this research, we introduce a new heuristic approach using the concept of ant colony optimization (ACO) to extract patterns from the chromosomes generated by previous generations for solving the generalized traveling salesman problem. The proposed heuristic is composed of two phases. In the first phase the ACO technique is adopted to establish an archive consisting of a set of non-overlapping blocks and of a set of remaining cities (nodes) to be visited. The second phase is a block recombination phase where the set of blocks and the rest of cities are combined to form an artificial chromosome. The generated artificial chromosomes (ACs) will then be injected into a standard genetic algorithm (SGA) to speed up the convergence. The proposed method is called "Puzzle-Based Genetic Algorithm" or "p-ACGA". We demonstrate that p-ACGA performs very well on all TSPLIB problems, which have been solved to optimality by other researchers. The proposed approach can prevent the early convergence of the genetic algorithm (GA) and lead the algorithm to explore and exploit the search space by taking advantage of the artificial chromosomes. 展开更多
关键词 artificial chromosome blocks mining block recombination traveling salesman problem
原文传递
上一页 1 2 3 下一页 到第
使用帮助 返回顶部