|
|
Solving vehicle routing problems and algorithm implementation on GPU
Hájek, Jan ; Fábry, Jan (advisor) ; Černý, Michal (referee)
A very wide-ranging subgroup of vehicle routing problems from the graph theory is a common and frequent problem handled daily by transport companies, airline businesses, hi-tech companies with planning drilling of printed circuits boards or other companies from different industries. During numerous previous researches of these problems a lot of analyses were made and many solutions proposed -- of which an outline is in this paper. Some of them giving better or worse results in longer or shorter computing time. In spite of the fact that the processors and new technologies performance is increasing, with some algorithms we cannon compute the result in a reasonable time. That is why this paper is asking a question, if there can be found a fitting algorithm which could be applied on different and faster processing unit structures so it could be ensured a multiple computing speed increase so far. The analysis was carried out using computer experiments on a new build and implemented branch and bound algorithm with a matrix rate reduction.
|
|
|
Travelling salesman problem and method GENIUS
Škopek, Michal ; Pelikán, Jan (advisor) ; Fábry, Jan (referee)
The target of this thesis is to explain the Travelling Salesman Problem and also create a special program, which will be able to make calculations using the heuristics GENIUS. The Travelling Salesman Problem will be described from two different points of view. The first one is the historical description of the idea of the Travelling Salesman Problem and later will be the problem will be described with some of the very wide number of the calculation methods. For the explanation of the methods, in the thesis there has been chosen some of the algorithms which belong to that methods. The heuristics and also the exact algorithms will be explained. The focus of this thesis is on the heuristics called GENIUS and also in the creation of the program which can calculate it. The program works first with the GENI algorithm and after that it works with US post-optimization algorithm. The program will be described from the point of view of the user and the manual will be written as well. The program will be tested on two different examples and will be compared with the exact algorithm.
|
|
|
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.
|
|
|
Optimization of Business Trips Schedule -Vehicle Routing Problem Application
Dvořáčková, Tereza ; Šindelářová, Irena (advisor) ; Skočdopolová, Veronika (referee)
My bachelor thesis deals with the special linear programming problems, so called distribution problems. Special attention is paid to the travelling salesman problem (TSP) and the vehicle routing problem (VRP). The introductory theoretical chapters explain mathematical models of selected distribution problems, as well the description of some heuristic methods for solving the TSP problem. The modifications of these heuristics are then applied to the real vehicle routing problem. In that real task (included in the last part of this thesis) the daily schedule for a sales representative of one unnamed Czech company is optimized. That sales representative regularly attends customers in his assigned territory and my optimization is focused on saving his time. The results obtained by means of heuristics as well by LINGO software are compared in the thesis conclusion. In chapter 3.5 the real task was modified by means of introducing new limitations, so-called time windows. The results of my thesis will be present to the company.
|
|
|
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.
|
|
|
The Solving of Distribution Problems in MS Excel / LINGO
Bisová, Sára ; Jablonský, Josef (advisor) ; Skočdopolová, Veronika (referee)
The goal of this work is to explain the topic of distribution problems, special kind of linear programming problems, and also to show possibilities for solving them in some programming systems. For solving several types of distribution problems - transportation problem, container transportation problem, assignment problem, allocation problem and travelling salesman problem - I have created an application which connects MS Excel with programming language LINGO. This connection is realized by means of VBA - Visual Basic for Applications. There are described the main procedures and functions of LINGO and VBA including minute description of interconnection of these systems. Created application is illustrated on several small problems in the last part of work.
|
|
|
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 ::
