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

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

Compact formulations of the Steiner Traveling Salesman Problem and related problems

The Steiner Traveling Salesman Problem (STSP) is a variant of the TSP that is particularly suitable when routing on real-life road networks. The standard integer programming formulations of both the TSP and STSP have an exponential number of constraints. On the other hand, several compact formulations of the TSP, i.e., formulations of polynomial size, are known. In this paper, we adapt some of them to the STSP, and compare them both theoretically and computationally. It turns out that, just by putting the best of the formulations into the CPLEX branch-and-bound solver, one can solve instances with over 200 nodes. We also briefly discuss the adaptation of our formulations to some related problems.     

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

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

一个关于非对称距离的旅行商问题的迭代算法

本对非对称距离的旅行商问题，给出了一个迭代算法，并分析了此迭代算法的复杂度为M^nO(N^4)，其中，N是问题中旅行商所要经过的城镇数，M是两城镇间的最大距离。最后用实例对此算法进行了验算和说明。     

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

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

Expanding Neighborhood GRASP for the Traveling Salesman Problem

In this paper, we present the application of a modified version of the well known Greedy Randomized Adaptive Search Procedure (GRASP) to the TSP. The proposed GRASP algorithm has two phases: In the first phase the algorithm finds an initial solution of the problem and in the second phase a local search procedure is utilized for the improvement of the initial solution. The local search procedure employs two different local search strategies based on 2-opt and 3-opt methods. The algorithm was tested on numerous benchmark problems from TSPLIB. The results were very satisfactory and for the majority of the instances the results were equal to the best known solution. The algorithm is also compared to the algorithms presented and tested in the DIMACS Implementation Challenge that was organized by David Johnson.     

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

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

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.     

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.     

最小Hamilton回路是最优旅行商路线的条件

本文给出并证明了一个非完全图 G的最小 Hamilton回路必为最优旅行商路线的条件是除了应满足广义三角不等式外 ,还必须满足正则收缩性     

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

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

New neighborhood structures for the Double Traveling Salesman Problem with Multiple Stacks

The changing requirements in transportation and logistics have recently induced the appearance of new vehicle routing problems that include complex constraints as precedence or loading constraints. One of these problems that have appeared during the last few years is the Double Traveling Salesman Problem with Multiple Stacks (DTSPMS), a vehicle routing problem in which some pickups and deliveries must be performed in two independent networks, verifying some precedence and loading constraints imposed on the vehicle. In this paper, four new neighborhood structures for the DTSPMS based on reinsertion and permutation of orders to modify both the routes and the loading planning of the solutions are introduced and described in detail. They can be used in combination with any metaheuristic using local search as a subprocedure, guiding the search to unexplored zones of the solution space. Some computational results obtained using all proposed neighborhood structures are presented, providing good quality solutions for real sized instances.      

Transgenetic algorithm for the Traveling Purchaser Problem

In this paper an evolutionary algorithm is presented for the Traveling Purchaser Problem, an important variation of the Traveling Salesman Problem. The evolutionary approach proposed in this paper is called transgenetic algorithm. It is inspired on two significant evolutionary driving forces: horizontal gene transfer and endosymbiosis. The performance of the algorithm proposed for the investigated problem is compared with other recent works presented in the literature. Computational experiments show that the proposed approach is very effective for the investigated problem with 17 and 9 new best solutions reported for capacitated and uncapacitated instances, respectively.     

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.     

Multi-objective Meta-heuristics for the Traveling Salesman Problem with Profits

We introduce and test a new approach for the bi-objective routing problem known as the traveling salesman problem with profits. This problem deals with the optimization of two conflicting objectives: the minimization of the tour length and the maximization of the collected profits. This problem has been studied in the form of a single objective problem, where either the two objectives have been combined or one of the objectives has been treated as a constraint. The purpose of our study is to find solutions to this problem using the notion of Pareto optimality, i.e. by searching for efficient solutions and constructing an efficient frontier. We have developed an ejection chain local search and combined it with a multi-objective evolutionary algorithm which is used to generate diversified starting solutions in the objective space. We apply our hybrid meta-heuristic to synthetic data sets and demonstrate its effectiveness by comparing our results with a procedure that employs one of the best single-objective approaches.      

Online scheduling of ordered flow shops

We consider online as well as offline scheduling of ordered flow shops with the makespan as objective. In an online flow shop scheduling problem, jobs are revealed to a decisionmaker one by one going down a list. When a job is revealed to the decision maker, its operations have to be scheduled irrevocably without having any information regarding jobs that will be revealed afterwards. We consider for the online setting the so-called Greedy Algorithm which generates permutation schedules in which the jobs on the machines are at all times processed without any unnecessary delays. We focus on ordered flow shops, in particular proportionate flow shops with different speeds and proportionate flow shops with different setup times. We analyze the competitive ratio of the Greedy Algorithm for such flow shops in the online setting. For several cases, we derive lower bounds on the competitive ratios.     

Analysis of Random Restart and Iterated Improvement for Global Optimization with Application to the Traveling Salesman Problem

The optimization method employing iterated improvement with random restart (I2R2) is studied. Associated with each instance of an I2R2 search is a fundamental polynomial, in which the coefficient p_k is the probability of starting a search k improvement steps from a local minimum. The positive root of f can be used to calculate the convergence and speedup properties of that instance.Since the coefficients of f are naturally related to the search, it is possible to estimate them online if an a priori estimate of the size of the goal basin is available, for example by analysis or prior experience. In this case, the runtime statistical estimate of converges many times faster than the estimates of the coefficients themselves.The foregoing is illustrated with an application to the traveling salesman problem (TSP) using the k-change as the improvement discipline. Among other things, it is shown that a k-change improvement can be affected by k 2-changes, that =1 for convex city sets, and that good estimates of can be made from a reduced TSP related to the given one.This research was partially supported by the National Sciences and Engineering Research Council of Canada (NSERC) in the form of a discovery grant. The authors thank the referees for helpful suggestions and timeliness.     

Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems

We consider an -hard variant (Δ-Max-ATSP) and an -hard relaxation (Max-3-DCC) of the classical traveling salesman problem. We present a -approximation algorithm for Δ-Max-ATSP and a -approximation algorithm for Max-3-DCC with polynomial running time. The results are obtained via a new way of applying techniques for computing undirected cycle covers to directed problems.     

On the integrality ratio of the subtour LP for Euclidean TSP

A long standing conjecture says that the integrality ratio of the subtour LP for metric TSP is 4/3$4/3$. A well known family of graphic TSP instances achieves this lower bound asymptotically. For Euclidean TSP the best known lower bound on the integrality ratio was 8/7$8/7$. We improve this value by presenting a family of Euclidean TSP instances for which the integrality ratio of the subtour LP converges to 4/3.