|
Ant colony optimization
Kovács, Peter ; Pangrác, Ondřej (advisor) ; Balko, Martin (referee)
The aim of this work was to compare metaheuristic Ant Colony with other metaheuristics like Simulated Annealing, Tabu Search or Greedy algo- rithms. Metaheuristics were compared on three different NP-hard problems. Specificaly, Traveling Salesman Problem, Graph Coloring Problem and Set Covering Problem. Detailed description of implementation of metaheuristics in particular problems can be found in this work. Metaheuristics were com- pared based on cost function and execution time. However, this work tries to identify instances, in which Ant Colony was the best choice. Ant Colony is reliable metaheuristic on large Traveling Salesman or Set Covering problems.
|
|
Theory and Applications of Monte Carlo Methods
Hruda, Petr ; Šimek, Václav (referee) ; Bidlo, Michal (advisor)
This bachelor thesis deals with applications of Monte Carlo methods on various problems. In particular, Metropolis algorithm and Simulated Annealing were applied on optimization of Traveling Salesman Problem and the problem of graph coloring. Moreover, "traditional" Monte Carlo approach was utilized for statistical analysis of electronic circuits in which the values of components exhibit random variations with a given tolerance. The results are evaluated for different setups of Monte Carlo methods.
|
|
Optimization Using Ant Algorithms
Válek, Matěj ; Drábek, Vladimír (referee) ; Bidlo, Michal (advisor)
This bachelor thesis will deal with various applications of ant colony optimisation. In particular, Ant Colony System will be applied on the optimisation of traveling salesman problem and the design of rules for the development of cellular automata. The obtained results will be statistically analysed. Moreover, a GUI-based application has been developed which allows to interactively observe the progress of Ant Colony System for the educational purposes.
|
|
Applications of Ant Algorithms
Kaščák, Imrich ; Vašíček, Zdeněk (referee) ; Bidlo, Michal (advisor)
The presented thesis focuses on the basic optimization algorithm of Ant Colony Optimization (ACO) - Ant System (AS) and its extension, Ant Colony System (ACS) on Traveling Salesman Problem (TSP). The essence of these algorithms is to find the optimal solution (the shortest path) in a specified instance containing several locations. The thesis demonstrates verification of behaviour of both algorithms, experimental study of impact of adjustable parameters of ant algorithms on result. Furthermore, the thesis is focused on examining the idea of optimizing detection of image edges by introducing a modification into an existing solution. Modified solution experiments are performed and compared to the original.
|
|
Optimalization of distribution of immobile clients
Maříková, Eliška ; Skočdopolová, Veronika (advisor) ; Fábry, Jan (referee)
Distribution problems today belong to one of the most used mathematical models in our everyday life. You can come across them when delivering items or transporting people. In my work I deal with the application of the distribution problems and their modification to transporting of handicapped people, specially for finding a route for the transfer of customers from the starting point to its destination while maintaining the capacities of the vehicles with the subsequent extension of the time windows and a further modification in the form of finding the routes where the customer is transported from the final destination point back to its starting point. To find the optimal solution, the combination of traveling salesman problem and the vehicle routing problem is used in my Bachelor thesis. The model is applied to real-time data from the company Societa o. p. s., which is one of the major companies in providing services to immobile people. The software MPL was used to calculate the optimal solution
|
|
Optimization of a a route for collecting waste with Traveling Salesman Problem
Trnka, Zdeněk ; Borovička, Adam (advisor) ; Pelikán, Jan (referee)
The Bachelor's dissertation deals with optimization of route designed for collecting communal waste of a company FCC Czech Republic, Ltd. Dissertation search for the most suitable method to solve the real-life example. So formed economic model is to be solved via Traveling Salesman Problem method, whose mathematical model, modifications and solutions options are described in detail in theoretical sections of the dissertation. Exact methods, which are suitable for smaller problem, and heuristic methods, which did not have to give optimal solution, can be used for solving the Traveling Salesman Problem. The Traveling Salesman Problem will be solved here with help of modeling software MPL for Windows. There will be also used two heuristic approaches - Nearest Neighbor algorithm and Savings method. Due to increasing efficiency, a modified Traveling Salesman Problem with Time Windows will be used and solved also through MPL for Windows. To close the dissertation, the result will be summarized and compare firstly among each other and secondly against current company route.
|
|
Management of logistics processes municipal waste processing
Anděrová, Veronika ; Černá, Anna (advisor) ; Váchová, Lucie (referee)
The aim of this diploma thesis is to describe the logistic processes in the processing of municipal waste in the company Local Enterprise in Hluboká nad Vltavou. Describe the business and analyze its decision-making issues. Then analyze the current situation and propose changes to apply optimization methods through a special computer program. The conclusion of the thesis is a concrete proposal of route optimization to improve the current situation of the company, which will lead to a positive economic effect on logistics of waste processing.
|
|
Vehicle Routing Problem
Kafka, Ondřej ; Branda, Martin (advisor) ; Hanzák, Tomáš (referee)
The thesis deals with optimization problems which arise at distribution planning. These problems can often be easily formulated as integer programming problems, but rarely can be solved using mixed integer programming techniques. Therefore, it is necessary to study the efficiency of heuristic algorithms. The main focus of the thesis is on the vehicle routing problem with time windows. A tabu search algorithm for this problem was developed and implemented. It uses integer programming to solve the set partitioning problem in order to find optimal distribution of all customers into feasible routes found during the search. The results of the classical integer programming approach, basic insertion heuristic and presented tabu search algorithm are compared in a numerical study.
|
|
Route optimization for the parcels distribution
Ptáčková, Michaela ; Borovička, Adam (advisor) ; Čížek, Ondřej (referee)
This thesis deals with optimization problems of the parcels distribution. This issue can be solved on the ground of traveling salesman problem whose mathematical and economic model, including their modifications, are presented in the theoretical part of the thesis. We can solve these problems by using exact methods, heuristic and metaheuristic algorithms. In the theoretical part are described traveling salesman problem, traveling salesman problem with time windows, traveling salesman problem with multiple time windows and dynamic traveling salesman problem including possible ways of solution. In the practical part we can find application of problems on the real example, when we are finding the shortest possible route for the PPL's employee under different assumptions. The solution is obtained by using solver Gurobi within the modelling system MPL for Windows. In conclusion of the thesis the results are summarized and models are compared with each other.
|
|
Integer Optimization for Transportation Problems
Cabalka, Matouš ; Žák, Libor (referee) ; Popela, Pavel (advisor)
The thesis deals with optimization models in transportation problems with emphasis on traveling salesman problem. Brief introduction to the history is followed by theoretical part describing linear programming, integer programming and formulation of traveling salesman problem. Description of data preprocessing is included. Finally computational results are discussed and evaluated.
|