首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 176 毫秒
1.
利用确定性退火技术的旅行商问题求解算法*   总被引:2,自引:0,他引:2  
将确定性退火技术及聚类方法应用于旅行商问题,给出了求解旅行商问题的一种启发式算法.该方法将旅行商问题的离散模型转化为连续模型去求解,通过求解一系列随温度变化的物理系统的自由能函数的局部极小来获得旅行商问题的解,并给出了一个简单的显式迭代公式.算例表明,该算法性能良好.  相似文献   

2.
旅行商问题作为组合优化研究中最具挑战的问题之一, 自被提出以来就引起了学术界的广泛关注并提出了大量的方法来解决它. 蚁群算法是求解复杂组合优化问题的一种启发式仿生进化算法, 是求解旅行商问题的有效手段. 本文分别介绍蚁群算法中几个有代表性的算法, 综述了蚁群算法的改进、融合和应用的文献研究进展, 以评价近年来不同版本的蚁群算法为解决旅行商问题的发展和研究成果, 并针对改进蚁群算法结构框架、算法参数的设置及优化、信息素优化和混合算法等方面, 对现被提出的改进算法进行了分类综述. 对蚁群算法在未来对旅行商问题及其他不同领域的研究内容和研究热点的进一步发展提供了展望和依据.  相似文献   

3.
旅行商问题是一个典型的组合优化问题,也是多种复杂问题的一种简化形式.因此,寻求一种有效的算法来求解此问题成为研究热点.随机松弛法是一种基于Metropolis迭代法求解的启发式随机搜索算法.针对该算法在求解旅行商问题时,存在易陷入局部最优的缺点,本文提出了三种不同的改进方法.即就是说,在解变换产生新解的过程中,首先,随机选择三个城市.然后,分别给出了三种不同的随机处理方法.最后,在仿真研究中,与已有方法相比,结果表明所给的三种方法的路径更短,结果更优.  相似文献   

4.
将确定性退火技术及聚类方法应用于旅行商问题,给出了求解旅行商问题的一种启发式算法.该方法将旅行商问题的离散模型转化为连续模型去求解,通过求解一系列随温度变化的物理系统的自由能函数的局部极小来获得旅行商问题的解,并给出了一个简单的显式迭代公式.算例表明,该算法性能良好.  相似文献   

5.
蚁群算法是一种元启发式算法,其经典应用是解决旅行商问题。该算法有着先天的并行特性。介绍了该算法的两种并行实现策略,给出了蚁群算法的并行实现模型,分析了该算法并行实现需要解决的问题。  相似文献   

6.
本文在旅行商问题(TSP)启发式算法的基础上进行修改,给出了瓶颈旅行商问题(BTSP)的一种启发式算法,并在微机上作了试算,效果较好,许多情况下都能得到最优解。  相似文献   

7.
TSP问题的脂肪计算复杂性与启发式算法设计   总被引:2,自引:0,他引:2  
江贺  胡燕  李强  于红 《软件学报》2009,20(9):2344-2351
旅行商问题(traveling salesman problem,简称TSP)是经典的NP-难解组合优化问题之一,求解它的高效启发式算法一直是计算机科学研究的热点.脂肪作为描述TSP结构特征的新工具,对启发式算法设计具有重要意义.目前,TSP问题的脂肪研究还处于初始阶段,缺乏理论分析结果及相关的启发式算法.首先分析了TSP问题的脂肪计算复杂性,通过构造偏移实例的技巧,证明了获取TSP的脂肪是NP-难解的,即在P(NP的假设下,不存在算法可以在多项式时间内获得完整脂肪.在此基础上,通过分析TSP问题局部最优解与脂肪的关系,给出了求解TSP问题的元启发式算法--动态候选集搜索(dynamic candidate set search,简称DCSS)算法.利用该算法,改进了目前求解TSP问题最好算法之一的LKH.TSPLIB典型实例的实验结果表明,改进后的算法在解的质量上有较为明显的提高.新的基于脂肪的启发式算法对于求解其他NP-难解问题具有一定的参考价值.  相似文献   

8.
鉴于旅行商问题是一个NP难问题,而猴群算法是一种新的群体智能优化算法,因此,利用猴群算法给出旅行商问题的求解。在分析了旅行商问题的特点后,采用整数编码的方式来表示猴群的位置,这样就解决了猴群算法在求解含有离散变量的组合优化问题时,算法中的爬过程失效的问题,有效地利用猴群算法求解旅行商问题。为了提高猴群算法的性能,在猴群算法的爬过程中,引入好动策略,给出改进算法,并将其应用到求解旅行商问题。在仿真实验中,与其他算法进行比较,结果表明利用改进猴群算法能够有效地求解旅行商问题。  相似文献   

9.
启发式算法是求解组合优化问题求解的重要手段,其主要特征是能够以可接受的计算代价找到足够好的可行解.然而,设计良好的用于求解组合优化问题的启发式算法需要大量的专业领域知识以及大量的试错工作,且人工设计的启发式算法不能够保证在不同问题集上均具有一致性表现.另一方面,深度学习方法能够通过学习自动设计启发式规则,然而深度学习方法通常缺少在解空间内搜索的能力.为克服以上问题,提出了一种基于蚁群优化和深度强化学习的混合启发式算法框架.在该框架中,蚁群算法能够利用深度强化学习提取的启发式信息,而深度强化学习方法的解空间搜索性能也由于蚁群算法的加入而获得提高.采用经典的TSPLIB中的算例对该算法求解旅行商问题的效能进行了计算验证,结果表明采用深度学习方法能够极大地提升蚁群算法的计算表现,并降低其计算代价.  相似文献   

10.
基于混合杂交的遗传算法求解旅行商问题   总被引:4,自引:0,他引:4  
郑立平  郝忠孝 《计算机工程》2005,31(20):168-169,172
通过混合使用多种杂交算子,提出了一种求解旅行商问题的新型遗传算法,并给出了实验验证。通过实验用该算法求解了城市数为50到100不等的旅行商问题,获得了比其它算法更精确或更接近最优的解,表明了算法的有效性。  相似文献   

11.
This paper proposes a new formulation and a column generation approach for the black and white traveling salesman problem. This problem is an extension of the traveling salesman problem in which the vertex set is divided into black vertices and white vertices. The number of white vertices visited and the length of the path between two consecutive black vertices are constrained. The objective of this problem is to find the shortest Hamiltonian cycle that covers all vertices satisfying the cardinality and the length constraints. We present a new formulation for the undirected version of this problem, which is amenable to the Dantzig–Wolfe decomposition. The decomposed problem which is defined on a multigraph becomes the traveling salesman problem with an extra constraint set in which the variable set is the feasible paths between pairs of black vertices. In this paper, a column generation algorithm is designed to solve the linear programming relaxation of this problem. The resulting pricing subproblem is an elementary shortest path problem with resource constraints, and we employ acceleration strategies to solve this subproblem effectively. The linear programming relaxation bound is strengthened by a cutting plane procedure, and then column generation is embedded within a branch-and-bound algorithm to compute optimal integer solutions. The proposed algorithm is used to solve randomly generated instances with up to 80 vertices.  相似文献   

12.
Many real world problems, e.g. personnel scheduling and transportation planning, can be modeled naturally as Constrained Shortest Path Problems (CSPPs), i.e., as Shortest Path Problems with additional constraints. A well studied problem in this class is the Resource Constrained Shortest Path Problem. Reduction techniques are vital ingredients of solvers for the CSPP, that is frequently NP-hard, depending on the nature of the additional constraints. Viewed as heuristics, these techniques have not been studied theoretically with respect to their efficiency, i.e., with respect to the relation of filtering power and running time. Using the concepts of Constraint Programming, we provide a theoretical study of cost-based filtering for shorter path constraints on acyclic, on undirected, and on directed graphs that do not contain negative cycles. We then show empirically how reasoning about path-substructures in combination with CP-based Lagrangian relaxation can help to improve significantly over previously developed problem-tailored filtering algorithms for the resource constrained shortest path problem and investigate the impact of required-edge detection, undirected versus directed filtering, and the choice of the algorithm optimizing the Lagrangian dual.  相似文献   

13.
Recently, several general optimization algorithms based on the demon algorithm from statistical physics have been developed and tested on a few traveling salesman problems with encouraging results. In this paper, we conduct an extensive computational study of 11 annealing-based heuristics for the traveling salesman problem. We code versions of simulated annealing, threshold accepting, record-to-record travel and eight heuristics based on the demon algorithm. We apply each heuristic to 29 traveling salesman problems taken from a well-known online library, compare the results with respect to accuracy and running time and provide insights and suggestions for future work  相似文献   

14.
Capacitated arc routing problems (CARP) arise in distribution or collecting problems where activities are performed by vehicles, with limited capacity, and are continuously distributed along some pre-defined links of a network. The CARP is defined either as an undirected problem or as a directed problem depending on whether the required links are undirected or directed. The mixed capacitated arc routing problem (MCARP) models a more realistic scenario since it considers directed as well as undirected required links in the associated network. We present a compact flow based model for the MCARP. Due to its large number of variables and constraints, we have created an aggregated version of the original model. Although this model is no longer valid, we show that it provides the same linear programming bound than the original model. Different sets of valid inequalities are also derived. The quality of the models is tested on benchmark instances with quite promising results.  相似文献   

15.
The objective of the multi-dimensional knapsack problem (MKP) is to find a subset of items with maximum value that satisfies a number of knapsack constraints. Solution methods for MKP, both heuristic and exact, have been researched for several decades. This paper introduces several fast and effective heuristics for MKP that are based on solving the LP relaxation of the problem. Improving procedures are proposed to strengthen the results of these heuristics. Additionally, the heuristics are run with appropriate deterministic or randomly generated constraints imposed on the linear relaxation that allow generating a number of good solutions. All algorithms are tested experimentally on a widely used set of benchmark problem instances to show that they compare favourably with the best-performing heuristics available in the literature.  相似文献   

16.
The Eulerian Editing problem asks, given a graph G and an integer k, whether G can be modified into an Eulerian graph using at most k edge additions and edge deletions. We show that this problem is polynomial-time solvable for both undirected and directed graphs. We generalize these results for problems with degree parity constraints and degree balance constraints, respectively. We also consider the variants where vertex deletions are permitted. Combined with known results, this leads to full complexity classifications for both undirected and directed graphs and for every subset of the three graph operations.  相似文献   

17.
We address the one-to-one multi-commodity pickup and delivery traveling salesman problem (m-PDTSP) which is a generalization of the TSP and arises in several transportation and logistics applications. The objective is to find a minimum-cost directed Hamiltonian path which starts and ends at given depot nodes and such that the demand of each given commodity is transported from the associated source to its destination and the vehicle capacity is never exceeded. In contrast, the many-to-many one-commodity pickup and delivery traveling salesman problem (1-PDTSP) just considers a single commodity and each node can be a source or target for units of this commodity. We show that the m-PDTSP is equivalent to the 1-PDTSP with additional precedence constraints defined by the source–destination pairs for each commodity and explore several models based on this equivalence. In particular, we consider layered graph models for the capacity constraints and introduce new valid inequalities for the precedence relations. Especially for tightly capacitated instances with a large number of commodities our branch-and-cut algorithms outperform the existing approaches. For the uncapacitated m-PDTSP (which is known as the sequential ordering problem) we are able to solve to optimality several open instances from the TSPLIB and SOPLIB.  相似文献   

18.
The aim of railway rolling stock planning problem is to find an optimal allocation of train-sets for a given set of trips in the train timetable in order to minimize the total cost. We propose a column generation and Lagrangian relaxation heuristics for short-term rolling stock planning problems with regular inspection constraints. The problem is formulated as a subtour traveling salesman problem to find a set of elementary shortest cycles that cover all trips in the timetable. In the proposed method, a tight lower bound is obtained from the continuous relaxation of Dantzig–Wolfe reformulation by column generation. The pricing problem can be formulated as an elementary shortest cycle problem with resource constraints. A labeling algorithm is applied to solve the pricing problem. In order to reduce the computational effort, we apply a general state space augmenting algorithm to solve the pricing problems. Computational results show that the proposed column generation and Lagrangian relaxation heuristics can find good lower and upper bounds for 300 trips within reasonable computing time.  相似文献   

19.
This paper introduces the family traveling salesperson problem (FTSP), a variant of the generalized traveling salesman problem. In the FTSP, a subset of nodes must be visited for each node cluster in the graph. The objective is to minimize the distance traveled. We describe an integer programming formulation for the FTSP and show that the commercial grade integer programming solver CPLEX 11 can only solve small instances of the problem in reasonable running time. We propose two randomized heuristics for finding optimal and near‐optimal solutions of this problem. These heuristics are a biased random‐key genetic algorithm and a GRASP with evolutionary path‐relinking. Computational results comparing both heuristics are presented in this study.  相似文献   

20.
The generalized traveling salesman problem (GTSP) is an extension of the well-known traveling salesman problem. In GTSP, we are given a partition of cities into groups and we are required to find a minimum length tour that includes exactly one city from each group. The recent studies on this subject consider different variations of a memetic algorithm approach to the GTSP. The aim of this paper is to present a new memetic algorithm for GTSP with a powerful local search procedure. The experiments show that the proposed algorithm clearly outperforms all of the known heuristics with respect to both solution quality and running time. While the other memetic algorithms were designed only for the symmetric GTSP, our algorithm can solve both symmetric and asymmetric instances.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号