|
|
Heuristic and metaheuristic methods for travelling salesman problem
Burdová, Jana ; Kalčevová, Jana (advisor) ; Zouhar, Jan (referee)
Minimal length of a travelling salesman's problem had been studied in this diploma these. Travelling salesman must come trough each place just once and then go back to the starting place. This problem can be illustrated as a problem of graph theory, such that places are the vertices, roads are the edges, distances of roads are the lengths of edges. The optimal travelling salesman's problem tour is the shortest Hamiltionian cycle in the graph. It is a classical NP-complete problem. There is no algorithm that solves this problem in polynomial time. This problem can be solved by using various approximation algorithms, they offer less time consumption and lowest quality than optimization. This diploma these had been dedicated to approximation algorithms, for example: nearest neighbor method, minimal spanning tree method, Christofide's method, 2-opt., genetic algorithm, etc.
|
|
|
Watering garden problem
Janovský, Martin ; Kalčevová, Jana (advisor) ; Mynařík, Petr (referee)
Watering garden problem is focused on using a special methods of linear programming on real garden. Especially using of travelling salesman problem and vehicle routing problem. Practices of these methods are demonstrated on real garden. The problem comes when it's necessary to find an optimal path between source of water and plants needing some water. Both problems (travelling salesman problem and vehicle routing problem) are solved through optimization software and heuristic methods (method of the nearest neighbour, savings method and method of the cheapest input). Main goal is to find the best solution which is usable.
|
|
|
An Application of Travelling Salesman Problem for a Delivery Transportation
Havlová, Irena ; Skočdopolová, Veronika (advisor) ; Kuncová, Martina (referee)
Optimal route or the most suitable configuration finding occurs in different areas of human activities as science, engineering or business. In mathematics these problems are usually assigned to Travelling Salesman Problem (TSP) and its modifications. This thesis is devoted to finding a solution of TSP using a linear model and some simpler heuristics such as Method of the Closest Neighbour. The practical part of the thesis shows usage of TSP for delivery transportation of warranty orders in a part of a wholesale network, including a solution of route divided into more than one cycle. Upon obtained results some financial comparison of the present and potential situation is given.
|
|
|
Application of the Vehicle Routing Problem in Geodesy Jobs
Richtr, Vít ; Skočdopolová, Veronika (advisor) ; Šindelářová, Irena (referee)
The Vehicle Routing Problem -- part of distribution problems in linear programming -- has a lot of real forms and applications. This work dealing with optimization real data afforded by geodetic company. The target is complete effective workweek design of the orders so as to working hours will be efficient and long ways between destinations will be minimized. In the first part of application the work is solve without any limitations. In the second part the condition is add that declare utmost day of orders serve. The setting is solving by two heuristic methods -- the nearest neighbour search and the Clark-Wright algorithm -- and with the aid of optimization systems LINGO and Gurobi. The results of several methods are analyzed and confronted with each other.
|
|
| |
|
| |
|
|
Travelling salesman problem solved by Clark-Wright's method
Brož, Vojtěch ; Fábry, Jan (advisor) ; Ráčková, Adéla (referee)
Essay solves two real-life travelling salesman problems with 18 and 30 nodes. Applicating Clark-Wright's solving method chosen by author as most suitable, mainly because it takes into account real constraints. In the beginning the essay consists of travelling salesman's problem needful theoretical basics, it's resolvability and practical use. Followed by detailed description of Clark-Wright's method computational process. Solving of real-life problems includes also the description of how were data used in essay obtained and adapted. The results are compared with optimal solution and results gained without including the constraints. Possibility of using this method in practice is discussed in conclusion.
|
|
|
Ant Colony Optimization
Zahálka, Jaroslav ; Fábry, Jan (advisor) ; Zouhar, Jan (referee)
This diploma thesis deals with Ant Colony algorithms and their usage for solving Travelling Salesman Problems and Vehicle Routing Problems. These algorithms are metaheuristics offering new approach to solving NP-hard problems. Work begins with a description of the forementioned tasks including ways to tackle them. Next chapter analyses Ant Colony metaheuristic and its possible usage and variations. The most important part of the thesis is practical and is represented by application Ant Colony Optimization Framework. It is easily extensible application written in Java that is able to solve introduced problems. In conclusion this work presents analysis of solutions on test data.
|
|
| |
|
| |
guest ::
