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.展开更多
The traveling salesman problem( TSP) is a well-known combinatorial optimization problem as well as an NP-complete problem. A dynamic multi-swarm particle swarm optimization and ant colony optimization( DMPSO-ACO) was ...The traveling salesman problem( TSP) is a well-known combinatorial optimization problem as well as an NP-complete problem. A dynamic multi-swarm particle swarm optimization and ant colony optimization( DMPSO-ACO) was presented for TSP.The DMPSO-ACO combined the exploration capabilities of the dynamic multi-swarm particle swarm optimizer( DMPSO) and the stochastic exploitation of the ant colony optimization( ACO) for solving the traveling salesman problem. In the proposed hybrid algorithm,firstly,the dynamic swarms,rapidity of the PSO was used to obtain a series of sub-optimal solutions through certain iterative times for adjusting the initial allocation of pheromone in ACO. Secondly,the positive feedback and high accuracy of the ACO were employed to solving whole problem. Finally,to verify the effectiveness and efficiency of the proposed hybrid algorithm,various scale benchmark problems were tested to demonstrate the potential of the proposed DMPSO-ACO algorithm. The results show that DMPSO-ACO is better in the search precision,convergence property and has strong ability to escape from the local sub-optima when compared with several other peer algorithms.展开更多
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.展开更多
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.展开更多
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.展开更多
文摘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.
基金National Natural Science Foundation of China(No.70971020)the Subject of Ministry of Education of Hunan Province,China(No.13C818)+3 种基金the Project of Industrial Science and Technology Support of Hengyang City,Hunan Province,China(No.2013KG63)the Open Project Program of Artificial Intelligence Key Laboratory of Sichuan Province,Sichuan University of Science and Engineering,China(No.2012RYJ03)the Fund Project of Humanities and Social Sciences,Ministry of Education of China(No.13YJCZH147)the Special Fund for Shanghai Colleges' Outstanding Young Teachers' Scientific Research Projects,China(No.ZZGJD12033)
文摘The traveling salesman problem( TSP) is a well-known combinatorial optimization problem as well as an NP-complete problem. A dynamic multi-swarm particle swarm optimization and ant colony optimization( DMPSO-ACO) was presented for TSP.The DMPSO-ACO combined the exploration capabilities of the dynamic multi-swarm particle swarm optimizer( DMPSO) and the stochastic exploitation of the ant colony optimization( ACO) for solving the traveling salesman problem. In the proposed hybrid algorithm,firstly,the dynamic swarms,rapidity of the PSO was used to obtain a series of sub-optimal solutions through certain iterative times for adjusting the initial allocation of pheromone in ACO. Secondly,the positive feedback and high accuracy of the ACO were employed to solving whole problem. Finally,to verify the effectiveness and efficiency of the proposed hybrid algorithm,various scale benchmark problems were tested to demonstrate the potential of the proposed DMPSO-ACO algorithm. The results show that DMPSO-ACO is better in the search precision,convergence property and has strong ability to escape from the local sub-optima when compared with several other peer algorithms.
基金supported by the National Natural Science Foundation of China(61771293)the Key Project of Shangdong Province(2019JZZY010111)。
文摘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.
文摘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.
基金the National Natural Science Foundation of China (No.61627810)the National Science and Technology Major Program of China (No.2018YFB1305003)the National Defense Science and Technology Outstanding Youth Science Foundation (No.2017-JCJQ-ZQ-031)。
文摘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.
