|
|
Comparison of Methods for Travelling Salesman Problem
Šušová, Lucia ; Janoušek, Vladimír (referee) ; Rozman, Jaroslav (advisor)
This work is about comparison of methods for solving the traveling salesman problem. There are many algorithms for finding solution of this NP complete problem but it is not easy to choose the right one. Main goal of this thesis is experimental methods comparison between each other. Reader is going to learn what result she can expect if she chooses certain algorithm for finding the path. First part is focused on theoretical basics where is described all needed information for understanding the problem. Second part describes single heuristics and methods for solving these problems. The methods are divided into groups by principle of working. Next part contains experimental comparison of methods. This comparison was done based on own implementation of single heuristics. The following part of this work contains information about this implementation and also describes comparison application. Next possible steps of this project are described in conclusion.
|
|
|
Agent Based Gameplaying System
Trutman, Michal ; Zbořil, František (referee) ; Král, Jiří (advisor)
This thesis deals with general game playing agent systems. On the contrary with common agents, which are designed only for a specified task or a game, general game playing agents have to be able to play basically any arbitrary game described in a formal declarative language. The biggest challenge is that the game rules are not known beforehand, which makes it impossible to use some optimizations or to make a good heuristic function. The thesis consists of a theoretical and a practical part. The first part introduces the field of general game playing agents, defines the Game Description Language and covers construction of heuristic evaluation functions and their integration within the Monte Carlo tree search algorithm. In the practical part, a general method of creating a new heuristic function is presented, which is later integrated into a proper agent, which is compared then with other systems.
|
|
|
Job Scheduling in Logistic Warehouses
Povoda, Lukáš ; Uher, Václav (referee) ; Karásek, Jan (advisor)
The main aim of this thesis is flow shop and job shop scheduling problem in logistics warehouses. Managing and scheduling works is currently often problem. There is no simple solution due to complexity of this problem. This problem must be resolved because of a lack efficiency of work with a higher load such as during the christmas holidays. This paper describes the methods used to solve this problem focusing mainly on the use of search algorithms, evolutionary algorithms, specifically grammar guided genetic programming. This paper describes the problem of job shop scheduling on a simple theoretical example. The implemented algorithm for solving this problem was subjected to tests inspired on data from real warehouse, as well as synthetically created tests with more jobs and a greater number of workers. Synthetic tests were generated randomly. All tests were therefore run several times and the results were averaged. In conclusion of this work are presented the results of the algorithm and the optimum parameter settings for different sizes of problems and requirements for the solution. Genetic algorithm has been extended to calculate fitness of individuals with regard to number of collisions, extended to use priority rules during run of evolution, and some parts of algorithm was parallelized.
|
|
|
Mathematical models for transportation problems
Votavová, Helena ; Novotný, Jan (referee) ; Popela, Pavel (advisor)
The thesis deals with modelling and solution techniques for the selected transportation problems. Firstly, historical remarks and application-related comments are introduced. Then the selected transportation problems are defined and mathematical programming and graph theory concepts are utilised to model them. The travelling salesman problem and suitable algorithms are under focus. The original implementation in GAMS and Python is discussed. Algorithms have been tested for the instance based on the set of 73 towns in the Czech Republic. Finally, the test results are evaluated and compared.
|
|
|
Heuristics for capacitated messenger problem
Přibylová, Lenka ; Fábry, Jan (advisor) ; Pelikán, Jan (referee)
This diploma thesis deals with static and dynamic capacitated messenger problem and its solving with heuristic algorithms. Different variations of the capacitated messenger problem were considered, with a single messenger or multiple messengers, with one depot or multiple depots in case of multiple messengers. Limited time for route realization was another modification that was considered. Modified nearest neighbour method, modified insertion method and modified exchange method were used to solve the problem. The main contribution of the thesis is deriving heuristics for described types of messenger problem and programming the algorithms in VBA (Visual Basic for Applications) in MS Excel. The results of computational experiments indicate that modified nearest neighbour method leads to better outcomes in static multiple messenger problems with a single depot, while modified insertion method is associated with lower values of objective function in static multiple messenger problem with multiple depots. Modified exchange method improves original solutions. Modified insertion method was approved for solving dynamic multiple messenger problems.
|
|
|
Optimization of medicaments distribution from Movianto s.r.o. Warehouse
Šimáně, Čestmír ; Kuncová, Martina (advisor) ; Fábry, Jan (referee)
Nowadays, when great emphasis is put on cost savings, transport optimization is necessary part of every company life in which transportation costs produce significant part. There are optimization methods and possibilities presented in this thesis. In the first chapter there are explained methods such as the travelling salesman problem, the vehicle routing problem, the multiple vehicle routing problem and the split delivery vehicle routing problem and then the reader gets to know the heuristics methods in the chapter two where description of the nearest neighbour method, Clarke-Wright method and split delivery heuristic is mentioned. In the last but one chapter author applies previous methods on concrete distribution arranged by Movianto Česká republika s.r.o. on 5th September, 2013. Based on gained outputs, analysis and comparison of results (including the original distribution) are provided in the fourth chapter. Obtained results of analysis lead to recommendation on how the company should plan its future distribution.
|
|
|
Psychological principles in techniques of social engineering
Pohorelec, Pavel ; Sigmund, Tomáš (advisor) ; Kašparová, Eva (referee)
Social engineering is type of attack, usable against an organization or individual. It focuses on weaknesses of human factor. In recent times, characterized by anonymity, fast pace and focus on technologies presents this way of attack a dangerous threat. Human factor tends to be underestimated in defense, into which organizations invest large amounts of money. Even though social engineering has been written about many times, most of work has been focused more on technical part, and explaining techniques of social engineering has been left out. The goal of this paper is explaining these techniques from psychological point of view, and using that as a basis for defense for organizations, threaten by social engineering attack. In first part, this work describes two main themes -- social engineering and social psychology. Afterwards, it describes principles, which are used in social engineering attack, and ways in which social engineering uses them. In second part are these information used to analyze several practical examples of social engineering attack. Then, they are used to formulate practical advices to defend against social engineering attack.
|
|
|
Application of heuristic methods in real vehicle routing problem
Slavíková, Monika ; Fábry, Jan (advisor) ; Kobzareva, Maria (referee)
This thesis is continuation of the bachelor thesis "Model of delivery routes and placement logistics centers with opportunities of their optimization". It is about distribution problems and specifically a vehicle routing problem. The aim of this thesis is finding a solution of the vehicle routing problem which will be used repeatedly in the firm. The main task is achieving the lowest costs (total kilometers) with maximum utilization of vehicle capacity; in such conditions that all requirements of logistics centers will be satisfied and maximal capacity of vehicle will be tolerated. For calculation was used a solver Gurobi 6.0.3 in system MPL for Windows 4.2, which won't, however, provide the optimal solution and problem solving takes too long time. Next for calculation was used heuristics insert method and is written by VBA (Visual Basic for Applications) in MS Excel. Finally, there is a comparison of these methods with the original solution of the vehicle routing plan and solution of the bachelor thesis. Then the computational experiment was done, which tested effect to result, if other distribution center (starting point) will be bulit. The computational experiment was consist from heuristic insert method, solver Gurobi and heuristic saving algorithm from bachelor thesis.
|
|
|
Rationality versus Irrationality in Managerial Decision Making
Daňková, Tereza ; Hiršová, Miloslava (advisor) ; Čejka, Pavel (referee)
The thesis focuses on rationality in decisions by managers. The terms rationality, irrationality and bounded rationality are defined in the first part. The current state of knowledge on the concept of bounded rationality in decision making is then followed by a specific consideration of managerial decision making. The chosen bounded rationality effects, including heuristics, are also described. The purpose of the second part of this study is to examine experimentally the differential uses of heuristics among the students of the Faculty of Management relative to completion of the Managerial Decision Making course. The effect of time to use of heuristics is examined as well.
|
|
|
Economics of Biased Estimation
Drvoštěp, Tomáš ; Špecián, Petr (advisor) ; Tříska, Dušan (referee)
This thesis investigates optimality of heuristic forecasting. According to Goldstein a Gigerenzer (2009), heuristics can be viewed as predictive models, whose simplicity is exploiting the bias-variance trade-off. Economic agents learning in the context of rational expectations (Marcet a Sargent 1989) employ, on the contrary, complex models of the whole economy. Both of these approaches can be perceived as an optimal response complexity of the prediction task and availability of observations. This work introduces a straightforward extension to the standard model of decision making under uncertainty, where agents utility depends on accuracy of their predictions and where model complexity is moderated by regularization parameter. Results of Monte Carlo simulations reveal that in complicated environments, where few observations are at disposal, it is beneficial to construct simple models resembling heuristics. Unbiased models are preferred in more convenient conditions.
|
guest ::
