Search for dissertations about: "traveling salesman problem"

Showing result 1 - 5 of 11 swedish dissertations containing the words traveling salesman problem.

2. 1. Optimizing and Approximating Algorithms for the Single and Multiple Agent Precedence Constrained Generalized Traveling Salesman Problem

   Author : Raad Salman; Göteborgs universitet; []
   Keywords : TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY; NATURVETENSKAP; NATURAL SCIENCES; NATURVETENSKAP; NATURAL SCIENCES; PCGmTSP; GTSP; SOP; mTSP; branch and bound; asymmetric generalized multiple traveling salesman problem; VRP; PCGTSP; dynamic programming; sequential ordering problem; vehicle routing problem; ant colony optimization; metaheuristic local search heuristic; precedence constraints; edge exchange; ant colony optimization;

   Abstract : In the planning phases of automated manufacturing, generating efficient programs for robot stations is a crucial problem which needs to be solved. One aspect of the programming is the optimization of task sequences, such as series of welds or measuring points, so that the cycle time is minimized. READ MORE

4. 2. Decomposition schemes for the traveling salesman subtour problem

   Author : Andreas Westerlund; Athanasios Migdalas; Linköpings universitet; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES;

   Abstract : Given an undirected graph with edge costs and both revenues and weights on the vertices, the Traveling Salesman Subtour Problem is to find a subtour that passes a depot vertex, satisfies a knapsack constraint on the vertex weights, and that minimizes edge costs minus vertex revenues along the subtour. This problem generalizes the Traveling Salesman Problem and is therefore -hard. READ MORE

5. 3. The Euclidean traveling salesman problem with neighborhoods and a connecting fence

   Author : Håkan Jonsson; Luleå tekniska universitet; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES; Dependable Communication and Computation Systems; Kommunikations- och beräkningssystem;

   Abstract : An important class of problems in robotics deals with the planning of paths. In this thesis, we study this class of problems from an algorithmic point of view by considering cases where we have complete knowledge of the environment and each solution must ensure that a point-sized robot capable of moving continuously and turning arbitrarily accomplishes the following: (1) visits a given set of objects attached to an impenetrable simple polygon in the plane, and (2) travels along a path of minimum length over all the possible paths that visit the objects without crossing the polygon. READ MORE

6. 4. From Art Galleries to Terrain Modelling --- A Meandering Path through Computational Geometry

   Author : Mikael Hammar; Data Vetenskap; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES; system; numerisk analys; Datalogi; systems; control; numerical analysis; Approximation Algorithms; Computational Geometry; Online Algorithms; Art Gallery Problem; Linear Search; Traveling Salesman Problem; R-Tree; Delaunay Triangulation; Polygon Exploration; Computer science; Shortest Watchman Routes; kontroll; Mathematics; Matematik;

   Abstract : We give approximation and online algorithms as well as data structures for some well studied problems in computational geometry. The thesis is divided into three parts. In part one, we study problems related to guarding, exploring and searching geometric environments. READ MORE

7. 5. Guidance and Control for Multiple Spacecraft Formation

   Author : Sumeet Gajanan Satpute; George Nikolakopoulos; Per Bodin; Kazuya Yoshida; Luleå tekniska universitet; []
   Keywords : TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY; Spacecraft Formation; Concurrent maneuver planning; Co-location; Geostationary satellite; Asteroid visual coverage; Trajectory planning; Traveling salesman problem; Onboard space systems; Rymdtekniska system;

   Abstract : Multiple spacecraft formation forms a distributed space system where multiple spacecraft cooperatively exhibit the functionality of a single monolithic spacecraft or work in a cooperative way towards the completion of a common goal. This possibility of distributing the workload between different spacecraft provides the ability to work in parallel, enable economic and simple solutions in terms of spacecraft design, while is redundant towards partial or complete failure of a spacecraft. READ MORE