多目标旅行商问题的模拟植物生长算法求解

针对多目标旅行商问题,提出了一种基于模拟植物生长的优化算法。该算法将Deb等人提出的非支配排序及构造偏序集等方法用于模拟植物生长的过程中,克服了模拟植物生长算法搜索空间过大及收敛性不够理想的缺点。基于该算法的核心思想,用MATLAB编程实现,对参考文献的算例进行仿真测试。与其他算法比较,获得了满意的结果。     

A self-organised travelling salesman

Using the principles of self-organisation and Darwin's theory of evolution, an algorithm has been developed to solve the geometric travelling salesman problem (TSP). In this approach, we have virtual and real nodes (cities) which can have equal or different masses (weights). The virtual nodes and their neighours are attracted toward the fixed cities by a Newtonian force. The birth and death of the virtual nodes creates a world in which only the fittest survive. This approach has been successfully tested on many problems of different sizes, with a constant error of about 4.6% across the whole range. The computing time follows a power series (square law) versus the number of cities. Comparison of our results with those obtained by a simulated annealing method showed the solutions that obtained by this self-organisation method are of a better quality, especially for large size problems.     

The intermittent travelling salesman problem

In this paper, we introduce a new variant of the travelling salesman problem, namely the intermittent travelling salesman problem (ITSP), which is inspired by real‐world drilling/texturing applications. In this problem, each vertex can be visited more than once and there is a temperature constraint enforcing a time lapse between two consecutive visits. A branch‐and‐bound approach is proposed to solve small instances to optimality. We furthermore develop four variable neighbourhood search metaheuristics which produce high‐quality solutions for large instances. An instance library is built and made publicly available.     

求解TSP的混合遗传算法

介绍一种求解TSP的混合遗传算法,该算法结合了基于邻域的LK算法和采用Inver-Over算子的遗传算法,并在算法中增加一些控制策略,加快算法的收敛速度,又保证群体的多样性。实验表明该算法是有效的。     

The Euclidean travelling salesman problem is NP-complete

The Travelling Salesman Problem is shown to be NP-Complete even if its instances are restricted to be realizable by sets of points on the Euclidean plane.     

Nonlinear resolving functions for the travelling salesman problem

We propose two approaches to finding lower bounds in the traveling salesman problem (TSP). The first approach, based on a linear specification of the resolving function φ(t, y), uses a two-index TSP model in its solution. This model has many applications. The second approach, based on a nonlinear specification of the resolving function φ(t, y), uses a single-index TSP model. This model is original and lets us significantly reduce the branching procedure in the branch-and-bound method for exact TSP solution. One cannot use the two-index TSP model here due to the nonlinear specification of the resolving function φ(t, y).     

改进的求解旅行商问题的自组织特征映射网络

对自组织特征映射（SOM）网络进行改进,要求神经元在训练过程中不仅数目保持不变而且在每次迭代中保持其权的均值与样本数据均值相同。当训练结束时,每一个城市都会对应于一个神经元的标号。此时,可能会出现两个及两个以上的城市对应于一个神经元的情况。为避免这个问题,采用小数标号代替整数标号。此时,每一个城市就对应于一个不同的实数索引标号,从而按照这个索引标号排列城市就得到了一条合理的路径。用此方法对旅行商问题(TSP)实验数据库（TSPLIB）中算例进行计算,实验结果表明所提算法是有效、可行的。     

Discrete symbiotic organisms search algorithm for travelling salesman problem

A Discrete Symbiotic Organisms Search (DSOS) algorithm for finding a near optimal solution for the Travelling Salesman Problem (TSP) is proposed. The SOS is a metaheuristic search optimization algorithm, inspired by the symbiotic interaction strategies often adopted by organisms in the ecosystem for survival and propagation. This new optimization algorithm has been proven to be very effective and robust in solving numerical optimization and engineering design problems. In this paper, the SOS is improved and extended by using three mutation-based local search operators to reconstruct its population, improve its exploration and exploitation capability, and accelerate the convergence speed. To prove that the proposed solution approach of the DSOS is a promising technique for solving combinatorial problems like the TSPs, a set of benchmarks of symmetric TSP instances selected from the TSPLIB library are used to evaluate its performance against other heuristic algorithms. Numerical results obtained show that the proposed optimization method can achieve results close to the theoretical best known solutions within a reasonable time frame.     

Distributed and incremental travelling salesman algorithm on time-evolving graphs

The Journal of Supercomputing - Travelling salesman problem (TSP) is a graph problem that has been widely used in many applications, especially for transportation and logistics. Because TSP is a NP...     

Discrete cuckoo search algorithm for the travelling salesman problem

In this paper, we present an improved and discrete version of the Cuckoo Search (CS) algorithm to solve the famous traveling salesman problem (TSP), an NP-hard combinatorial optimisation problem. CS is a metaheuristic search algorithm which was recently developed by Xin-She Yang and Suash Deb in 2009, inspired by the breeding behaviour of cuckoos. This new algorithm has proved to be very effective in solving continuous optimisation problems. We now extend and improve CS by reconstructing its population and introducing a new category of cuckoos so that it can solve combinatorial problems as well as continuous problems. The performance of the proposed discrete cuckoo search (DCS) is tested against a set of benchmarks of symmetric TSP from the well-known TSPLIB library. The results of the tests show that DCS is superior to some other metaheuristics.     

基于近邻策略的旅行商问题求解

根据TSP问题的特征信息并借鉴邻域搜索算法的有关思想,提出了一种基于近邻策略的TSP问题求解算法,该算法首先依据TSP问题的特殊性求出相应的近邻模式,再将近邻模式用于初始种群的生成,而后在进化过程中随机引入这类模式。该算法可以大大缩短遗传进程,提高进化效率。通过仿真实验,验证了该算法的有效性,并且随着城市数目的增加其优越性更为明显。     

Beam-ACO for the travelling salesman problem with time windows

The travelling salesman problem with time windows is a difficult optimization problem that arises, for example, in logistics. This paper deals with the minimization of the travel-cost. For solving this problem, this paper proposes a Beam-ACO algorithm, which is a hybrid method combining ant colony optimization with beam search. In general, Beam-ACO algorithms heavily rely on accurate and computationally inexpensive bounding information for differentiating between partial solutions. This work uses stochastic sampling as a useful alternative. An extensive experimental evaluation on seven benchmark sets from the literature shows that the proposed Beam-ACO algorithm is currently a state-of-the-art technique for the travelling salesman problem with time windows when travel-cost optimization is concerned.     

Environmental inspection routes and the constrained travelling system salesman problem

The constrained version of the classical travelling salesman problem (TSP) is seen to be a generic model for a wide variety of problems. Our concern here is limited to those problems which impinge directly on the environmental issues. Some potential applications are in the areas of resource management, energy conservation and transportation.The version of the problem we are faced with can be stated as: Given 1 or more persons (or vehicles) that must visit a set of n sites (plants, bus stops, pickup point, and so on) how can one develop a route which is of minimum mileage and meets certain restrictions (8 hour work day, bus seating capacity, vehicle capacity, length of trip and so on).This paper addresses the following issues in light of this problem:

1. 1. Data problems: in particular, efficient means of gathering and maintaining data.

2. 2. Numerical results: the study of efficient algorithms so that the model can be used efficiently on large problems and also on a day-to-day basis.

3. 3. Areas of potential application: for example, locational problems (office location), regionalization studies (development of efficient regional boundaries, efficient inspection and delivery routes, long range and short term resource management).

4. 4. Decision making applications in terms of analysis of operations, planning and analysis of resources via sensitivity analysis.

     

A hybrid swarm intelligence algorithm for the travelling salesman problem

Abstract: We present a hybrid model named HRKPG that combines the random‐key search method and an individual enhancement scheme to thoroughly exploit the global search ability of particle swarm optimization. With a genetic algorithm, we can expand the area of exploration of individuals in the solution space. With the individual enhancement scheme, we can enhance the particle swarm optimization and the genetic algorithm for the travelling salesman problem. The objective of the travelling salesman problem is to find the shortest route that starts from a city, visits every city once, and finally comes back to the start city. With the random‐key search method, we can search the ability of the particle and chromosome. On the basis of the proposed hybrid scheme of HRKPG, we can improve solution quality quite a lot. Our experimental results show that the HRKPG model outperforms the particle swarm optimization and genetic algorithm in solution quality.     

The symmetric travelling salesman problem II. New low bounds

The branch-and-bound method is adduced for the symmetric salesman problem where two lower bounds are proposed as bounds. The first bound is a solution to the problem of optimal 2-matching; the second one, to the problem of minimum spanning 1-tree. The last bound is enhanced by applying the problem of optimal 2-matching. Both these bounds considerably improve the symmetric traveling salesman problem as compared to the asymmetric problem.