|
|
Routing Problems and Their Solutions
Pospíšil, Václav ; Dvořák, Jiří (referee) ; Šeda, Miloš (advisor)
The first part of the thesis is devoted to an Introduction and a comprehensive description of all important concepts of graph theory, which is followed by descriptions and modifications of two selected types of routing problems: the travelling salesman problem and the vehicle routing problem. The next part of the thesis deals with subsequent possibilities of solving problems through deterministic and stochastic algorithms. It also includes a practical part, which at the end of the thesis deals with the shortest path optimization of the two created models using Nearest neighbour algorithm, Genetic algorithm and solver in GAMS.
|
|
|
Methods for solving selected vehicle routing problems and their implementation.
Drobný, Michal ; Grygarová, Libuše (advisor) ; Zimmermann, Karel (referee)
Various types of transportation issues are a common practice. The issue may be approached mainly as the distribution of products from suppliers to consumers while minimising distribution costs. The difference of real transportation issues predominantly relates to the considered restrictions, such as capacities of vehicles and orders, time windows and other special distribution restrictions. Transportation issues were already defined by F.L. Hitchcock in 1941 and since then, a wide range of stochastic and non- determinist methods providing solutions to transportation issues have been developed. Nevertheless, introducing distribution restrictions in resolving real-life problems makes it difficult for such methods to be applied. This thesis provides a compilation of the well-known determinist methods that may be used to resolve transportation issues. The methods that are appropriate for resolving real issues are discussed in more detail. The solution procedure of the selected method is demonstrated using simple examples and the results are compared with the results of other methods. An analysis of the above methods is used to design and implement new methods to resolve real transportation issues, their results being compared with the methods provided by the commercial software product.
|
|
|
Evolutionary Optimization of Freight Transportation
Beránek, Michal ; Drahošová, Michaela (referee) ; Bidlo, Michal (advisor)
The following thesis deals with optimization of freight transport planning. The goal is to minimize expenses connected to transportation, which emerge from travelled distance. The expenses can be heavily reduced, if the routes are correctly planned, especially when there is a large number of customers to be served. This thesis focuses on solving the problem by using the evolutional algorithms, that are optimization methods based on principles of evolution. Thesis concentrates on Heterogeneous Fixed Fleet Vehicle Routing Problem. Thesis introduces multiple evolutional algorithms and their results are compared. The best algorithm, evolutional strategy with local neighbourhood search, achieves similar, for certain tasks even better results, than other existing evolutional algorithms, created to solve given problem.
|
|
|
Optimizations Methods for Freight Transportation
Gabonay, Michal ; Vašíček, Zdeněk (referee) ; Bidlo, Michal (advisor)
The following work concerns the study of the evolutionary algorithm, which optimizes freight transport planning. The demand for freight transport is constantly increasing nowadays and with creating, implementing and using proper route planning we are able to significantly reduce transportation costs. However, it is preferably to implement it in companies with large numbers of served customers and with a sufficiently large fleet of vehicles. The study starts by defining what fright transport planning problem is and by characterizing its existing specifications and variants. My work proceeds to give a background of the possible solutions to the multifaceted aspects of the problem. The specific subproblem I choose to focus on is the Vehicle routing problem with Pickup and Delivery for which I apply the optimization solution. In the main body of my thesis, I will elaborate on the chosen optimization solution which encompasses the genetic algorithm and evolutionary strategy. The aim of the study is to measure the suitability of the algorithms and techniques used, for which reason the final part of my work will deal with the analysis and evaluation of the experiments.
|
|
| |
|
|
Inventory routing problem
Špolc, Miroslav ; Fábry, Jan (advisor) ; Borovička, Adam (referee)
Inventory routing problem is a mathematical method of operations research, consisting of two basic models (vehicle routing problem and inventory allocation). The goal of this master thesis is to introduce the reader to what exactly inventory routing is, why and how it was created and how it evolved over the course of years. Also, some examples of actual real-life applications of the problem will be shown together with the results of their implementation. Researches and papers of the last almost 40 years, written by experts on the subject are used as the source for this master thesis. From these works, the summarizing thesis was written, putting together the most important knowledge on how to solve the problem. Its contribution is not just the explanation of the theory and its development, but also introduction of some real applications of Inventory routing. Applicability of the model and its positive results in the form of cost savings is shown on real examples.
|
|
|
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.
|
|
|
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
|
|
|
Optimalization of mixed goods pickup and delivery
Šorf, Michal ; Skočdopolová, Veronika (advisor) ; Dvořák, Marek (referee)
This thesis is focused on the use of linear models in the real world. Its main aim is to devise a mathematical model for a specific problem which is repeatedly encountered by the company Pospíchal s.r.o. and also to find an optimal solution with the help of this model. The thesis is based on basic distribution problems, such as the travelling salesman problem or the vehicle routing problem, which I subsequently modify into the required form. The thesis is divided into three main parts. The first one focuses on the description of basic models that will be modified in the last part. The following part deals with a brief description of the company already mentioned above that provided data without which this task could not be demonstrated in practice. The final part includes a detailed analysis of the given task, formulation and description of the mathematical model, which was created on the basis of specific requirements of the company. There is also a comparison of actual results from practice with optimal results.
|
|
|
Application of Vehicle Routing Problem in Geocaching
Frolík, Tomáš ; Skočdopolová, Veronika (advisor) ; Sekničková, Jana (referee)
Geocaching is a worldwide game that uses Global Positioning System (GPS). Most play-ers try to create a route to search for caches to make it as short as possible. The aim of the bachelor thesis is to design a model to be able to create the shortest route between individual caches under certain restrictive conditions within five independent circuits. The first part of the thesis presents the basic theoretical knowledge necessary for un-derstanding practical part. The second part is devoted to the basic terms of geocaching. Furthermore in the second chapter, the basic model, its individual variables, equations and evaluation are presented within the Vehicle Routing Problem. As a result, the mod-el is not entirely correct and needs to be expanded by a third index, which sets the conditions for each created circuit separately.
|
guest ::
