|
|
Vehicle Routing Problem with Private and Common Carriers
Zikmund, Adam ; Pelikán, Jan (advisor) ; Fábry, Jan (referee)
This diploma thesis deals with a problem from the field of combinatorial optimization called Vehicle Routing Problem with Private and Common Carriers (VRPPC). A complete undirected symmetric graph is given. The task is to satisfy demands in all nodes with minimal total costs. There are two possibilities of doing so. Either private fleet or common carrier can be used for the transport of the demanded goods. The private costs depend on the covered distance whereas the common costs are conditional only on the weight of demand. Several heuristic methods for solving this problem are proposed and tested on three experimental instances of different sizes (in terms of number of nodes). Emphasis is primarily put on comparison between the presented heuristic and the classical optimization approach, which can often lead to inferior results (especially in case of larger instances) because of the computational complexity of the given problem.
|
|
|
Implementation of Heuristics for Vehicle Routing Problem with Time Windows
Trunda, Otakar ; Pelikán, Jan (advisor) ; Holý, Vladimír (referee)
Vehicle Routing Problem with Time Windows is a hard optimization problem. Even though it has numerous practical applications, the question of solving it efficiently has not been satisfyingly solved yet. This thesis studies the Vehicle Routing Problem with Time Windows and presents several new algorithms for solving it. There are two heuristics presented here, as well as several more complex algorithms which use those heuristics as their components. The efficiency of presented techniques is evaluated experimentally using a set of test samples. As a part of this thesis, I have also developed a desktop application which implements presented algorithms and provides a few additional features useful for solving routing prob-lems in practice. Among others, there is a generator of pseudo-random problem instances and several visualization methods.
|
|
|
Jobs scheduling in a volunteer organization
Žofák, Norbert ; Trunda, Otakar (advisor) ; Barták, Roman (referee)
The aim of the work is analysis and implementation of a tool, which will support a job scheduling for workers on the annual voluntary service which lasts for a week. The scheduling is done semiautomatically based on various criteria. Users of the tool are able to track a current state of the algorithm execution and influence it. The analysis of the chosen scheduling algorithms and their comparison on real data is also a part of the work. The tool can also be used as a register of worker, job, area and car properties. The emphasis is on the simplicity and intuitivity of the tool controlling and the data input.
|
|
|
Component Interconnection Inference
Olšarová, Nela ; Rychlý, Marek (referee) ; Křivka, Zbyněk (advisor)
The Master Thesis deals with the design of hardware component interconnection inference algorithm that is supposed to be used in the FPGA schema editor that was integrated into educational integrated development environment VLAM IDE. The aim of the algorithm is to support user by finding an optimal interconnection of two given components. The editor and the development environment are implemented as an Eclipse plugin using GMF framework. A brief description of this technologies and the embedded systems design are followed by the design of the inference algorithm. This problem is a topic of combinatorial optimization, related to the bipartite matching and assignment problem. After this, the implementation of the algorithm is described, followed by tests and a summary of achieved results.
|
|
|
Experiments with the Swarm Intelligence
Hula, Tomáš ; Zbořil, František (referee) ; Grulich, Lukáš (advisor)
This work deals with the issue of swarm intelligence as a subdiscipline of artificial intelligence. It describes biological background of the dilemma briefly and presents the principles of searching paths in ant colonies as well. There is also adduced combinatorial optimization and two selected tasks are defined in detail: Travelling Salesman Problem and Quadratic Assignment Problem. The main part of this work consists of description of swarm intelligence methods for solving mentioned problems and evaluation of experiments that were made on these methods. There were tested Ant System, Ant Colony System, Hybrid Ant System and Max-Min Ant System algorithm. Within the work there were also designed and tested my own method Genetic Ant System which enriches the basic Ant System i.a. with development of unit parameters based on genetical principles. The results of described methods were compared together with the ones of classical artificial intelligence within the frame of both solved problems.
|
|
|
Probabilistic Neural Networks for Special Tasks in Electromagnetics
Koudelka, Vlastimil ; Tučková,, Jana (referee) ; Hartnagel, Hans Ludwig (referee) ; Raida, Zbyněk (advisor)
Tato práce pojednává o technikách behaviorálního modelování pro speciální úlohy v elektromagnetismu, které je možno formulovat jako problém aproximace, klasifikace, odhadu hustoty pravděpodobnosti nebo kombinatorické optimalizace. Zkoumané methody se dotýkají dvou základních problémů ze strojového učení a combinatorické optimalizace: ”bias vs. variance dilema” a NP výpočetní komplexity. Boltzmanův stroj je v práci navržen ke zjednodušování komplexních impedančních sítí. Bayesovský přístup ke strojovému učení je upraven pro regularizaci Parzenova okna se snahou o vytvoření obecného kritéria pro regularizaci pravděpodobnostní a regresní neuronové sítě.
|
|
| |
|
|
Solving the combinatorial optimization problems with the Ant Colony Optimization metaheuristic method
Chu, Andrej ; Jablonský, Josef (advisor) ; Janáček, Jaroslav (referee) ; Linda, Bohdan (referee)
The Ant Colony Optimization belongs into the metaheuristic methods category and it has been developing quite recently. So far it has shown its capabalities to over-perform other metaheuristic methods in quality of the solutions. This work brings analysis of the possible applications of the method on the classical optimization combinatorial problems -- traveling salesman problem, vehicle routing problem, knapsack problem, generalized assignment problem and maximal clique problem. It also deals with the practical experiments with application on several optimization problems and analysis of the time and memory complexity of such algorithms. The last part of the work is dedicated to the possibility of parallelization of the algorithm, which was result of the application of the ACO method on the traveling salesman problem. It brings analysis of the crucial operations and data synchronization issues, as well as practical example and demonstration of the parallelized version of the algorithm.
|
|
|
The quadratic assignment problem and its solution
Nováčková, Monika ; Jablonský, Josef (advisor) ; Fábry, Jan (referee)
The QAP (quadratic assignment problem) is one of the most involved combinatorial optimization problems. This formidable decision problem is included in the complexity class called NP-complete. The QAP has been first time introduced by Koopmans and Beckman in year 1957. Since then the various methods for solving this problem have been investigated. The studied methods include both: exact algorithms and heuristic methods. Some of them will be shortly described in this paper. One of them, the branch and bound algorithm based on Gilmore Lawler bounds will be analyzed in detail. View applications of this problem will be also discussed. Described applications include the problem of localization of the departments or clinics in a hospital in order to minimize the total traveling distance among clinics by patients. Another described example of application of this problem is the task how to place the components on a computer motherboard optimally.
|
|
| |
guest ::
