|
| |
|
|
Heuristics for paths in maps
Kudláčková, Lada ; Mareš, Martin (advisor) ; Kratochvíl, Miroslav (referee)
The content of the thesis is a description of heuristic procedures, which are used to find the shortest paths in the graphs and verify their effec- tiveness on the actual data. It deals with heuristics for Dijkstra's algorithm, especially the A* algorithm, which uses a lower distance-to-target estimate. Heuristics are implemented and tested on the road network of the Czech Re- public. 1
|
|
|
Optimal path planning for electric vehicles
Horák, Filip ; Šoustek, Petr (referee) ; Kůdela, Jakub (advisor)
This master’s thesis is about optimal route planning for electric vehicles. The first, theoretical part of this work introduces the issue and describes several heuristic methods that have been used to address optimization tasks. A practical part of the thesis is based around software implementation of the methods described earlier. Finally, several experiments and comparisons of obtained results are carried out.
|
|
|
Heuristics for paths in maps
Kudláčková, Lada ; Mareš, Martin (advisor) ; Kratochvíl, Miroslav (referee)
The content of the thesis is a description of heuristic procedures, which are used to find the shortest paths in the graphs and verify their effec- tiveness on the actual data. It deals with heuristics for Dijkstra's algorithm, especially the A* algorithm, which uses a lower distance-to-target estimate. Heuristics are implemented and tested on the road network of the Czech Re- public. 1
|
|
|
On the Dijkstra's algorithm in the pedestrian flow problem
Petrášová, Tereza ; Felcman, Jiří (advisor) ; Kučera, Václav (referee)
Title: On the Dijkstra's algorithm in the Pedestrian Flow Problem Author: Tereza Petrášová Department: Department of Numerical Mathematics Supervisor: doc. RNDr. Jiří Felcman, CSc., Department of Numerical Mathe- matics Abstract: The pedestrian flow problem is described by a coupled system of the first order hyperbolic partial differential equations with the source term and by the functional minimization problem for the desired direction of motion. The functional minimization is based on the modified Dijkstra's algorithm used to find the minimal path to the exit. The original modification of the Dijkstra's algorithm is proposed to increase its efficiency in the pedestrian flow problem. This approach is compared with the algorithm of Bornemann and Rasch for determination of the desired direction of motion based on the solution of the so- called Eikonal equation. Both approaches are numerically tested in the framework of two splitting algorithms for solution of the coupled problem. The former splitting algorithm is based on the finite volume method yielding for the given time instant the piecewise constant approximation of the solution. The latter one uses the implicit discretization by a space-time discontinuous Galerkin method based on the discontinuous piecewise polynomial approximation. The numerical examples...
|
|
| |
|
| |
|
|
Application of the Dijkstra's Algorithm in the Pedestrian Flow Problem
Petrášová, Tereza ; Felcman, Jiří (advisor) ; Dolejší, Vít (referee)
The purpose of this work is to study the pedestrian flow equations as the coupled system formed by the eikonal equation and the first order hyperbolic system with the source term. The hyperbolic system consists of the continuity equation and the equations of motion of a compressible inviscid fluid. To specify the outer volume forces in the latter equation it is assumed that the pedestrians try to move in a desired direction with a desired velocity, which are dependent on the density in their surroundings. The desired direction is obtained as the gradient of the solution of the eikonal equation. We show that the solution of the eikonal equation has the meaning of the time needed to pass the fastest path to the exit. We suggest avoiding solving the eikonal equation by using the graph theory, where as the graph we use the underlying triangulation. The norm of each edge in the graph is density-dependent and has the dimension of time. This is together with the use of the modified Dijkstra's algorithm the novelty of the work. Numerical results of the two approaches are presented. Powered by TCPDF (www.tcpdf.org)
|
|
| |
|
| |
guest ::
