| Popis: |
Įvairūs grafo srautų minimizavimo arba maksimizavimo uždaviniai yra taikomi modeliuoti procesams logistikoje, kompiuteriniuose tinkluose, akcijų biržose, automobilių eisme ir t.t. Tokio uždavinio sprendimas esant dideliems grafams yra labai sudėtingas, todėl modelyje būna mažai kintančių parametrų arba modeliuojama tik dalis proceso. Tokio uždavinio pavyzdys (kuris ir bus nagrinėjamas) yra eismo modeliavimas keliuose. Kiekvienas vairuotojas bando pasiekti savo tikslą per minimalų galimą tuo metu esančiomis sąlygomis laiką. Tokiu būdu yra užimama „geriausia vieta“ kelyje, o kitiems vairuotojams užimtas kelias gali tapti neberacionalus ir bus pasirenkamas alternatyvus. Šioje vietoje atsispindi esminė tokio tipo uždavinio savybė: kiekvienas proceso dalyvis siekia maksimalios naudos sau, tokiu būdu tą naudą atimdamas iš kitų dalyvių. Šiu atveju „nauda“ yra vieta eisme. Darbe yra aprašytas eismo imitavimo sistemos modelis ir realizuotas tokia architektūra, kuri tinkama lygiagretiems skaičiavimams. Pateikta statistiniai gauto modelio analizavimo pavyzdžiai. Taip pat pasiūlyti keli algoritmai specifiniams uždaviniams spręsti, kaip dalinis modelio perskaičiavimas. 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... [to full text] |
