Spelling suggestions: "subject:"travelingsalesman problem"" "subject:"travelsalesman problem""
21 |
Metaheuristics and combinatorial optimization problems /Skidmore, Gerald. January 2006 (has links)
Thesis (M.S.)--Rochester Institute of Technology, 2006. / Typescript. Includes bibliographical references (leaves [70]-72).
|
22 |
Period traveling salesman with customer stratificationLim, Huay Huay, January 2006 (has links)
Thesis (Ph. D.)--University of Missouri-Columbia, 2006. / The entire dissertation/thesis text is included in the research.pdf file; the official abstract appears in the short.pdf file (which also appears in the research.pdf); a non-technical general description, or public abstract, appears in the public.pdf file. Title from title screen of research.pdf file (viewed on August 10, 2007) Vita. Includes bibliographical references.
|
23 |
TSP - Infrastructure for the Traveling Salesperson ProblemHahsler, Michael, Hornik, Kurt 12 1900 (has links) (PDF)
The traveling salesperson (or, salesman) problem (TSP) is a well known and important
combinatorial optimization problem. The goal is to find the shortest tour that visits each
city in a given list exactly once and then returns to the starting city. Despite this simple
problem statement, solving the TSP is difficult since it belongs to the class of NP-complete
problems. The importance of the TSP arises besides from its theoretical appeal from the
variety of its applications. Typical applications in operations research include vehicle
routing, computer wiring, cutting wallpaper and job sequencing. The main application
in statistics is combinatorial data analysis, e.g., reordering rows and columns of data
matrices or identifying clusters. In this paper, we introduce the R package TSP which
provides a basic infrastructure for handling and solving the traveling salesperson problem.
The package features S3 classes for specifying a TSP and its (possibly optimal) solution
as well as several heuristics to find good solutions. In addition, it provides an interface to
Concorde, one of the best exact TSP solvers currently available. (authors' abstract)
|
24 |
The column subtraction method for the traveling salesman problem.Wolff, Friedel 13 June 2008 (has links)
Smith, T.H.C., Prof.
|
25 |
Markov chain monte carlo and the traveling salesman problem.January 1996 (has links)
by Liang Fa Ming. / Publication date from spine. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1995. / Includes bibliographical references (leaves 49-53). / ABSTRACT --- p.1 / Chapter CHAPTER 1 : --- Introduction --- p.2 / Chapter 1.1 : --- The TSP Problem --- p.2 / Chapter 1.2: --- Application --- p.3 / Chapter CHAPTER 2 : --- Review of Exact and Approximate Algorithms for TSP --- p.4 / Chapter 2.1 : --- Exact Algorithm --- p.4 / Chapter 2.2 : --- Heuristic Algorithms --- p.8 / Chapter CHAPTER 3 : --- Markov Chain Monte Carlo Methods --- p.16 / Chapter 3.1: --- Markov Chain Monte Carlo --- p.16 / Chapter 3.2 : --- Conditioning and Gibbs Sampler --- p.17 / Chapter 3.3: --- The Metropolis-Hasting Algorithm --- p.18 / Chapter 3.4: --- Auxiliary Variable Methods --- p.21 / Chapter CHAPTER 4: --- Weighted Markov Chain Monte Carlo Method --- p.24 / Chapter CHAPTER 5 : --- Traveling Salesman Problem --- p.31 / Chapter 5.1: --- Buildup Order --- p.33 / Chapter 5.2: --- Path Construction through a Group of Points --- p.34 / Chapter 5.3: --- Solving TSP Using the Weighted Markov Chain Method --- p.38 / Chapter 5.4: --- Temperature Scheme --- p.40 / Chapter 5.5 : --- How to Adjust the Constant Prior-Ratio --- p.41 / Chapter 5.6: --- Validation of Our Algorithm by a Simple Example --- p.41 / Chapter 5.7 : --- Adding/Deleting Blockwise --- p.42 / Chapter 5.8: --- The sequential Optimal Method and Post Optimization --- p.43 / Chapter 5. 9 : --- Composite Algorithm --- p.44 / Chapter 5.10: --- Numerical Comparisons and Tests --- p.45 / Chapter CHAPTER 6 : --- Conclusion --- p.48 / REFERENCES --- p.49 / APPENDIX A --- p.54 / APPENDIX B --- p.58 / APPENDIX C --- p.61
|
26 |
BRAIN CONNECTOME NETWORK PROPERTIES VISUALIZATIONChenfeng Zhang (5931164) 17 January 2019 (has links)
<p>Brain
connectome network visualization could help the neurologists inspect the brain
structure easily and quickly. In the thesis, the model of the brain connectome network is visualized in both three
dimensions (3D) environment and two dimensions (2D) environment. One is named “Brain
Explorer for Connectomic Analysis” (BECA) developed by the previous research
already. It could present the 3D model of brain structure with region of
interests (ROIs) in different colors [5]. The other is mainly for the
information visualization of brain connectome in 2D. It adopts the force-directed
layout to visualize the network. However, the brain network visualization could
not bring the user intuitively ideas about brain structure. Sometimes, with the
increasing scales of ROIs (nodes), the visualization would bring more visual
clutter for readers [3]. So, brain connectome network properties visualization
becomes a useful complement to brain network visualization. For a better
understanding of the effect of Alzheimer’s disease on the brain nerves, the
thesis introduces several methods about the brain graph properties
visualization. There are the five selected graph properties discussed in the
thesis. The degree and closeness are node properties. The shortest path,
maximum flow, and clique are edge
properties. Except for clique, the other properties are visualized in both 3D
and 2D. The clique is visualized only in 2D. For the clique, a new hypergraph
visualization method is proposed with three different algorithms. Instead of
using an extra node to present a clique, the thesis uses a “belt” to connect
all nodes within the same clique. The
methods of node connections are based on the traveling salesman problem (TSP)
and Law of cosines. In addition, the thesis also applies the result of the clique to adjust the force-directed layout of
brain graph in 2D to dramatically eliminate the visual clutter. Therefore, with the support of the graph properties
visualization, the brain connectome network visualization tools become more
flexible.</p>
|
27 |
Algorithms for a scheduling application of the Asymmetric Traveling Salesman Problem.Kanellakis, Paris C January 1978 (has links)
Thesis. 1978. M.S.--Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING / Includes bibliographical references. / M.S.
|
28 |
A hierarchical approach for solving the large-scale traveling salesman problemFigueras, Anthony L. 06 April 1994 (has links)
An algorithm for solving the large-scale Traveling Salesman Problem is presented. Research into past work in the area of Hopfield neural network use in solving the Traveling Salesman Problem has yielded design ideas that have been incorporated into this work. The algorithm consists of an unsupervised learning algorithm and a recursive Hopfield neural network. The unsupervised learning algorithm was used to decompose the problem into clusters. The recursive Hopfield neural network was applied to the centroids of the clusters, then to the cities in each cluster, in order to find an optimal path. An improvement in both computation speed and solution accuracy is shown by the proposed algorithm over the straight use of the Hopfield neural network.
|
29 |
An Effective Hybrid Genetic Algorithm with Priority Selection for the Traveling Salesman ProblemHu, Je-wei 07 September 2007 (has links)
Traveling salesman problem (TSP) is a well-known NP-hard problem which can not be solved within a polynomial bounded computation time. However, genetic algorithm (GA) is a familiar heuristic algorithm to obtain near-optimal solutions within reasonable time for TSPs. In TSPs, the geometric properties are problem specific knowledge can be used to enhance GAs. Some tour segments (edges) of TSPs are fine while some maybe too long to appear in a short tour. Therefore, this information can help GAs to pay more attention to fine tour segments and without considering long tour segments as often. Consequently, we propose a new algorithm, called intelligent-OPT hybrid genetic algorithm (IOHGA), to exploit local optimal tour segments and enhance the searching process in order to reduce the execution time and improve the quality of the offspring. The local optimal tour segments are assigned higher priorities for the selection of tour segments to be appeared in a short tour. By this way, tour segments of a TSP are divided into two separate sets. One is a candidate set which contains the candidate fine tour segments and the other is a non-candidate set which contains non-candidate fine tour segments. According to the priorities of tour segments, we devise two genetic operators, the skewed production (SP) and the fine subtour crossover (FSC). Besides, we combine the traditional GA with 2-OPT local search algorithm but with some modifications. The modified 2-OPT is named the intelligent OPT (IOPT). Simulation study was conducted to evaluate the performance of the IOHGA. The experimental results indicate that generally the IOHGA could obtain near-optimal solutions with less time and higher accuracy than the hybrid genetic algorithm with simulated annealing algorithm and the genetic algorithm using the gene expression algorithm. Thus, the IOHGA is an effective algorithm for solving TSPs. If the case is not focused on the optimal solution, the IOHGA can provide good near-optimal solutions rapidly. Therefore, the IOHGA could be incorporated with some clustering algorithm and applied to mobile agent planning problems (MAP) in a real-time environment.
|
30 |
Dynamic Programming: Salesman to SurgeonQian, David January 2013 (has links)
Dynamic Programming is an optimization technique used in computer science and mathematics. Introduced in the 1950s, it has been applied to many classic combinatorial optimization problems, such as the Shortest Path Problem, the Knapsack Problem, and the Traveling Salesman Problem, with varying degrees of practical success.
In this thesis, we present two applications of dynamic programming to optimization problems. The first application is as a method to compute the Branch-Cut-and-Price (BCP) family of lower bounds for the Traveling Salesman Problem (TSP), and several vehicle routing problems that generalize it. We then prove that the BCP family provides a set of lower bounds that is at least as strong as the Approximate Linear Program (ALP) family of lower bounds for the TSP. The second application is a novel dynamic programming model used to determine the placement of cuts for a particular form of skull surgery called Cranial Vault Remodeling.
|
Page generated in 0.1013 seconds