非对称距离的旅行商问题的构造算法

章分析了非对称距离的旅行商问题,讨论了节约算法与最小生成树算法两种启发式方法,并用实例进行了说明,最后对算法的有效性进行了说明。     

用列队竞争算法解旅行商问题

给出了列队竞争算法解组合优化问题的框架和确定变异邻域的两条原则。用列队竞争算法解旅行商问题获得了满意的结果,显示出列队竞争算法良好的全局搜索性能。     

旅行推销员问题的算法综述

本文综述了旅行推销员问题 (TSP)近几十年来的算法研究进展 ,给出了一些主要算法的求解思想及其时间复杂度     

基于最小调整法求解旅行商问题

介绍了一种求解旅行商问题的新算法"最小调整法",给出了该算法求解旅行商问题的具体步骤以及有效性证明,对算法的复杂性及近似程度进行了分析.最后通过典型算例进行了检验说明.与经典算法相比,新算法体现了简单易行的特点,对求解旅行商问题具有一定的启发意义.     

带有配额的在线Nomadic旅行商问题

由于自然灾害的频繁发生,灾后的应急物资车辆调度受到了社会的广泛重视,而应急车辆尽快地将应急物资送到受灾点显得尤为重要。针对应急车辆装载物资能力有限和应急车辆不必返回出发点的情形,提出了带有配额的在线Nomadic旅行商问题。分析了该问题在正半轴和一般网络上的下界,针对受灾点仅在正半轴上的情形设计了WTAIB算法,针对受灾点在一般网络上设计了WSB算法,并进一步分析了两个算法的竞争性能。     

求解旅行商问题的搜寻者遗传算法

针对简单遗传算法易陷入局部最优及收敛速度慢的不足,提出一种改进遗传算法-基于启发式策略的搜寻者遗传算法.首先将搜寻者优化算法中的模糊思想和近邻策略相结合改进变异算子,增强种群多样性,避免陷入局部最优;然后针对路径优化问题基于启发式策略设计反转算子,使得路径中不存在交叉边,加快收敛速度;最后将改进遗传算法用于求解旅行商问题.结果表明,改进遗传算法的求解精度和求解效率明显优于基本遗传算法.     

旅行商问题的交叉粒子群优化算法

本文将粒子群优化算法(PSO)应用于求解旅行商问题(TSP),结合遗传算法的交叉算子,建立了求解此问题的交叉粒子群优化算法,数值模拟结果表明了该算法的有效性.     

求解旅行商问题的一种改进粒子群算法

本文研究了求解旅行商问题的粒子群算法。针对标准粒子群算法在求解旅行商问题过程中容易出现早熟和停滞现象的缺点,提出了一种改进的粒子群算法。首先,在初始种群的选取过程中,利用改进的贪婪策略直接获得具有较高性能的初始种群以提高算法的搜索效率。其次,通过引入次优吸引子,使粒子在搜索过程中可以更加充分地利用群体的信息来提高自身的性能,有效抑制收敛过程中的停滞现象,提高算法的搜索能力。最后为了验证所提出的方法的有效性和可行性,对TSPLIB标准库中的多个实例进行了测试,并给出了数值结果。     

求解旅行商问题的基于类Kruskal的混合粒子群算法

本文针对求解旅行商问题的标准粒子群算法所存在的早熟和低效的问题,提出一种基于Greedy Heuristic的初始解与粒子群相结合的混合粒子群算法(SKHPSO)。该算法通过本文给出的类Kruskal算法作为Greedy Heuristic的具体实现手段,产生一个较优的初始可行解,作为粒子群中的一员,然后再用改进的混合粒子群算法进行启发式搜索。SKHPSO的局部搜索借鉴了Lin-Kernighan邻域搜索,而全局搜索结合了遗传算法中的交叉及置换操作。应用该算法对TSPLIB中的典型算例进行了算法测试分析,结果表明:SKHPSO可明显提高求解的质量和效率。     

改进遗传算法求解旅行商问题

针对采用自然编码的遗传算法在求解旅行商问题(TSP)过程中初始群体设置过于复杂的问题,采用了Grefenstette编码设置初始群体,有效保证了初始群体的随机性和多样性.同时,在遗传算法实施过程中采用了自然编码,吸取边重组交叉算子和简单交叉算子的优点,提出一种新的交叉算子.这种处理解决了Grefenstette编码在遗传算法的交叉和变异过程中只能部分遗传父代的优良特性的问题.对TSP试算结果表明,采用这种遗传算法策略有利于问题的求解.这种实施的策略可以大量用于加工领域和交通领域以及其他规划领域的路径规划中.     

Dynamics of Local Search Trajectory in Traveling Salesman Problem

This paper investigates dynamics of a local search trajectory generated by running the Or-opt heuristic on the traveling salesman problem. This study evaluates the dynamics of the local search heuristic by estimating the correlation dimension for the search trajectory, and finds that the local heuristic search process exhibits the transition from high-dimensional stochastic to low-dimensional chaotic behavior. The detection of dynamical complexity for a heuristic search process has both practical as well as theoretical relevance. The revealed dynamics may cast new light on design and analysis of heuristics and result in the potential for improved search process.     

用嵌套插队算法解决TSP问题

本提出了一种求解TSP问题的近似算法—嵌套插队算法。这种算法结合了启发式算法和随机化算法以及局部寻优的思想。实验结果表明对于较小规模的。TSP问题，直接用插队算法(QJA)就能以很大的概率获得已知最优解。对于规模较大的问题实例。嵌套插队算法(NQJA)能获得质量高于名的启发式算法的解。另外，用嵌套插队算法找到的China144的最短路径优于目前已知的最短路径。嵌套插队算法是专门针对TSP问题而提出的，但其思想也可以给求解其他NP难解的组合优化问题以启发。     

A New Memetic Algorithm for the Asymmetric Traveling Salesman Problem

This paper introduces a new memetic algorithm specialized for the asymmetric instances of the traveling salesman problem (ATSP). The method incorporates a new local search engine and many other features that contribute to its effectiveness, such as: (i) the topological organization of the population as a complete ternary tree with thirteen nodes; (ii) the hierarchical organization of the population in overlapping clusters leading to the special selection scheme; (iii) efficient data structures. Computational experiments are conducted on all ATSP instances available in the TSPLIB, and on a set of larger asymmetric instances with known optimal solutions. The comparisons show that the results obtained by our method compare favorably with those obtained by several other algorithms recently proposed for the ATSP.     

Random Tours in the Traveling Salesman Problem: Analysis and Application

Random solutions to the traveling salesman problem (TSP) exhibit statistical regularities across problem instances. These patterns can assist heuristic search for good solutions by providing easy estimates of the length of the optimal tour.     

A Branch & Cut Algorithm for the Asymmetric Traveling Salesman Problem with Precedence Constraints

In this article we consider a variant of the classical asymmetric traveling salesman problem (ATSP), namely the ATSP in which precedence constraints require that certain nodes must precede certain other nodes in any feasible directed tour. This problem occurs as a basic model in scheduling and routing and has a wide range of applications varying from helicopter routing (Timlin, Master's Thesis, Department of Combinatorics and Optimization, University of Waterloo, 1989), sequencing in flexible manufacturing (Ascheuer et al., Integer Programming and Combinatorial Optimization, University of Waterloo, Waterloo, 1990, pp. 19–28; Idem., SIAM Journal on Optimization, vol. 3, pp. 25–42, 1993), to stacker crane routing in an automatic storage system (Ascheuer, Ph.D. Thesis, Tech. Univ. Berlin, 1995). We give an integer programming model and summarize known classes of valid inequalities. We describe in detail the implementation of a branch&cut-algorithm and give computational results on real-world instances and benchmark problems from TSPLIB. The results we achieve indicate that our implementation outperforms other implementations found in the literature. Real world instances with more than 200 nodes can be solved to optimality within a few minutes of CPU-time. As a side product we obtain a branch&cut-algorithm for the ATSP. All instances in TSPLIB can be solved to optimality in a reasonable amount of computation time.