Thesis (M.S.)--Rochester Institute of Technology, 2006. / Typescript. Includes bibliographical references (leaves [70]-72).

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.

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)

Smith, T.H.C., Prof.

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

<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>

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.

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.

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.

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.