| Abstract [eng] |
In this work we will try to apply various path search algorithm optimizations for solving traffic simulation problem. These optimizations are made on the basis of processes and patterns specific to car traffic. Other areas like logistics, money traffic and stocks should have their own specific optimizations. Primary selection criteria will be calculation time. Errors are also introduced by these optimizations, but benefits of solving more complex problems in much shorter time will outweigh those errors. Most of described algorithms are just modifications of traditional Dijkstra's algorithm. This allows to show step by step every optimization introduced, which we can split into 3 categories: Algorithms for finding shortest path in untouched graph, Algorithms for finding shorted path which need modified graph, Algorithms specific for traffic simulation. Algorithms up to graph transformations have been analyzed in previous works. These optimizations proved to be very perspective in point-to-point path search. Thou applying them to traffic modeling and introducing modeling specific optimizations is a relatively new research area. Also an algorithm imitating traffic laws has to be implemented. One of suggested optimizations could be called “fast partial recalculation”. This would allow a faster recalculation of main path loads. Assuming that traffic is the same and graph is slightly modified. A modified idea could be adapted for a recalculation with modified traffic loads. Vastly improved calculations times would allow larger graphs or more combinations to be analyzed. This allows to create more precise models or more evolution paths to be analyzed in the same time. |
