Spelling suggestions: "subject:"traveling salesman problem""
21 |
Ammunition Transfer System Optimization ProblemGunsel, H. Sinem 01 March 2012 (has links) (PDF)
Ammunition Transfer System (ATS) is the electro-mechanical system of the Ammunition Resupply Vehicle (ARV) which will be used to meet T-155 mm Firtina howitzers&rsquo / ammunition demand for tactical requirements of higher firing rate by off-road mobility and survivability. The transfer of ammunitions from ARV to Firtina is to be optimized for an effective improvement of firing rate.
In this thesis the transferring order of carried ammunitions is being optimized to minimize the total ammunition transferring time. This transfer problem is modeled as a modification of Travelling Salesman Problem (TSP). The given locations of the ammunitions are treated as cities to be visited and the gripper of ATS is treated as the traveling salesman. By GAMS / the small-size problems are solved optimally but large-size ones get only local optimum. A heuristic algorithm that contains nearest neighbor heuristics as construction method and 2-opt exchange heuristic as improvement method is developed to obtain same or better solutions obtained by GAMS with less computational time.
|
22 |
Applications of Circulations and Removable Pairings to TSP and 2ECSSFu, Yao 08 May 2014 (has links)
In this thesis we focus on two NP-hard and intensively studied problems: The travelling salesman problem (TSP), which aims to find a minimum cost tour that visits every node exactly once in a complete weighted graph, and the 2-edge-connected spanning subgraph problem (2ECSS), which aims to find a minimum size 2-edge-connected spanning subgraph in a given graph.
TSP and 2ECSS have many real world applications. However, both problems are NP-hard which means it is unlikely that polynomial time algorithms exist to solve them, so methods that return close to optimal solutions are sought. In this thesis we mainly focus on k-approximation algorithms for the two problems, which efficiently return a solution within k times of the optimal solution.
For a special case of TSP called graph TSP, using ideas from Momke and Svensson, we present a 25/18-approximation algorithm for a special class of graphs using circulations and T-joins, which improves the previous known best bound of 7/5 for such graphs. Moreover, if the graph does not contain special nodes, our algorithm ensures the ratio of 4/3.
For 2ECSS, given any k-edge-connected graph G=(V,E), |V|=n, |E|=m, we present an approximation algorithm that gives a 2-edge-connected spanning subgraph with the number of edges at most n+(m-n)/(k-1)-(k-2)/(k-1) with a novel use of circulations, which improves both the approximation ratio and the simplicity of the proof compared to a result by Huh in 2004.
|
23 |
Application of Combinatorial Optimization Techniques in Genomic Median ProblemsHaghighi, Maryam 13 December 2011 (has links)
Constructing the genomic median of several given genomes is crucial in developing evolutionary trees, since the genomic median provides an estimate for the ordering of the genes in a common ancestor of the given genomes.
This is due to the fact that the content of DNA molecules is often similar, but the difference is mainly in the order in which the genes appear in various genomes. The mutations that affect this ordering are called genome rearrangements, and many structural differences between genomes can be studied using genome rearrangements.
In this thesis our main focus is on applying combinatorial optimization techniques to genomic median problems, with particular emphasis on the breakpoint distance as a measure of the difference between two genomes. We will study different variations of the breakpoint median problem from signed to unsigned, unichromosomal to multichromosomal, and linear to circular to mixed.
We show how these median problems can be formulated in terms of problems in combinatorial optimization, and take advantage of well-known combinatorial optimization techniques and apply these powerful methods to study various median problems.
Some of these median problems are polynomial and many are NP-hard. We find efficient algorithms and approximation methods for median problems based on well-known combinatorial optimization structures. The focus is on algorithmic and combinatorial aspects of genomic medians, and how they can be utilized to obtain optimal median solutions.
|
24 |
Application of mixed-integer programming in chemical engineeringPogiatzis, Thomas January 2013 (has links)
Mixed-Integer Programming has been a vital tool for the chemical engineer in the recent decades and is employed extensively in process design and control. This dissertation presents some new Mixed-Integer Programming formulations developed for two well-studied problems, one with a central role in the area of Optimisation, the other of great interest to the chemical industry. These are the Travelling Salesman Problem and the problem of scheduling cleaning actions for heat exchanger networks subject to fouling. The Travelling Salesman Problem finds a plethora of applications in many scientific disciplines, Chemical Engineering included. None of the mathematical programming formulations proposed for solving the problem considers fewer than O(n^2) binary degrees of freedom. The first part of this dissertation introduces a novel mathematical description of the Travelling Salesman Problem that succeeds in reducing the binary degrees of freedom to O(nlog2(n)). Three Mixed-Integer Linear Programming formulations are developed and the computational performance of these is tested through computational studies. Sophisticated methods are now available for scheduling the cleaning actions for networks of heat exchangers subject to fouling. In the majority of these, only one form of cleaning is used, which restores the performance of the exchanger back to its clean level. A recent study revised the scheduling problem for the case where there are several cleaning methods available. The second part of this dissertation extends their approach, developed for individual units, to heat exchanger networks and explores the concept of selection of cleaning techniques further. Mixed-Integer Programming formulations are proposed for the scheduling task, for two fouling scenarios: (i) chemical reaction fouling and (ii) biological fouling. A series of results are presented for the implementation of the scheduling formulations to networks of different sizes.
|
25 |
Application of Combinatorial Optimization Techniques in Genomic Median ProblemsHaghighi, Maryam January 2012 (has links)
Constructing the genomic median of several given genomes is crucial in developing evolutionary trees, since the genomic median provides an estimate for the ordering of the genes in a common ancestor of the given genomes.
This is due to the fact that the content of DNA molecules is often similar, but the difference is mainly in the order in which the genes appear in various genomes. The mutations that affect this ordering are called genome rearrangements, and many structural differences between genomes can be studied using genome rearrangements.
In this thesis our main focus is on applying combinatorial optimization techniques to genomic median problems, with particular emphasis on the breakpoint distance as a measure of the difference between two genomes. We will study different variations of the breakpoint median problem from signed to unsigned, unichromosomal to multichromosomal, and linear to circular to mixed.
We show how these median problems can be formulated in terms of problems in combinatorial optimization, and take advantage of well-known combinatorial optimization techniques and apply these powerful methods to study various median problems.
Some of these median problems are polynomial and many are NP-hard. We find efficient algorithms and approximation methods for median problems based on well-known combinatorial optimization structures. The focus is on algorithmic and combinatorial aspects of genomic medians, and how they can be utilized to obtain optimal median solutions.
|
26 |
On Applying Methods for Graph-TSP to Metric TSPDesjardins, Nicholas January 2016 (has links)
The Metric Travelling Salesman Problem, henceforth metric TSP, is a fundamental problem in combinatorial optimization which consists of finding a minimum cost Hamiltonian cycle (also called a TSP tour) in a weighted complete graph in which the costs are metric. Metric TSP is known to belong to a class of problems called NP-hard even in the special case of graph-TSP, where the metric costs are based on a given graph. Thus, it is highly unlikely that efficient methods exist for solving large instances of these problems exactly.
In this thesis, we develop a new heuristic for metric TSP based on extending ideas successfully used by Mömke and Svensson for the special case of graph-TSP to the more general case of metric TSP. We demonstrate the efficiency and usefulness of our heuristic through empirical testing.
Additionally, we turn our attention to graph-TSP. For this special case of metric TSP, there has been much recent progress with regards to improvements on the cost of the solutions. We find the exact value of the ratio between the cost of the optimal TSP tour and the cost of the optimal subtour linear programming relaxation for small instances of graph-TSP, which was previously unknown. We also provide a simplified algorithm for special graph-TSP instances based on the subtour linear programming relaxation.
|
27 |
Applications of Circulations and Removable Pairings to TSP and 2ECSSFu, Yao January 2014 (has links)
In this thesis we focus on two NP-hard and intensively studied problems: The travelling salesman problem (TSP), which aims to find a minimum cost tour that visits every node exactly once in a complete weighted graph, and the 2-edge-connected spanning subgraph problem (2ECSS), which aims to find a minimum size 2-edge-connected spanning subgraph in a given graph.
TSP and 2ECSS have many real world applications. However, both problems are NP-hard which means it is unlikely that polynomial time algorithms exist to solve them, so methods that return close to optimal solutions are sought. In this thesis we mainly focus on k-approximation algorithms for the two problems, which efficiently return a solution within k times of the optimal solution.
For a special case of TSP called graph TSP, using ideas from Momke and Svensson, we present a 25/18-approximation algorithm for a special class of graphs using circulations and T-joins, which improves the previous known best bound of 7/5 for such graphs. Moreover, if the graph does not contain special nodes, our algorithm ensures the ratio of 4/3.
For 2ECSS, given any k-edge-connected graph G=(V,E), |V|=n, |E|=m, we present an approximation algorithm that gives a 2-edge-connected spanning subgraph with the number of edges at most n+(m-n)/(k-1)-(k-2)/(k-1) with a novel use of circulations, which improves both the approximation ratio and the simplicity of the proof compared to a result by Huh in 2004.
|
28 |
Využití matematických metod při plánování sítě obchodních zástupců / Application of mathematical methods for planning and managing network of sales representativesMitas, Lukáš January 2016 (has links)
Companies from multiple branches use as one way to offer their products and services network of sales representatives. This thesis study mainly designing process of such network and process of planning day to day routes of sales representatives with focus on minimizing cost caused by their work. For designing such network set covering problem model and matching problem model were used. For planning sales representatives routes travelling salesman problem, multiple salesperson travelling salesman problem, vehicle routing problem, nearest neighbor heuristic and authors own solution were used. Usage of multicriterial decision making is briefly mentioned as tool for managing such network on examples of equipment selection. As demonstration on real case, data from Tata Global Beverages (Jemča) company were used.
|
29 |
Analýza a optimalizace efektivnosti zemědělsko-dřevozpracujícího podniku (reálná situace) / Analyses and optimization of efficiency in agriculture and wood-working companyJágerová, Tereza January 2008 (has links)
This thesis aspires to optimize the processes in agriculture and wood-working company and to propose some changes if needed. At first, it is wood-working branch which is analyzed. The intent is to find an optimal route to distribute pallets and afterwards freight the vehicle by sawn wood and return back with. This is some modification of travelling salesman problem with more than one salesman and more centers including the condition that the travelling is dynamic in time and that only selected clients are visited. The agriculture problem is more complicated and complex because the model aims to find an optimal portfolio of diverse animal and vegetal production influenced by many factors and some of them are mentioned below. The agriculture model includes for example the stochastic character of weather and the condition that the herd of cattle should be stable.
|
30 |
Výpočetní úlohy pro řešení paralelního zpracování dat / Computational tasks for solving parallel data processingRexa, Denis January 2019 (has links)
The goal of this diploma thesis was to create four laboratory exercises for the subject "Parallel Data Processing", where students will try on the options and capabilities of Apache Spark as a parallel computing platform. The work also includes basic setup and use of Apache Kafka technology and NoSQL Apache Cassandra database. The other two lab assignments focus on working with a Travelling Salesman Problem. The first lab was designed to demonstrate the difficulty of a task where the student will face an exponential increase in complexity. The second task consists of an optimization algorithm to solve the problem in cluster. This algorithm is subjected to performance measurements in clusters. The conclusion of the thesis contains recommendations for optimization as well as comparison of running with different number of computing devices.
|
Page generated in 0.0983 seconds