Közlekedési hálózatok modellezése és optimalizálása

Absztrakt (kivonat)

Dolgozatomban napjaink egy meghatározó problémájával foglalkozom, nevezeten a közlekedés optimalizálásával. A köznapi életben, számos hálózat struktúrájú jelenséggel találkozunk – közlekedés, telekommunikációs hálózat, internet, kapcsolati hálók, áramszolgáltatás – melyek vizsgálata fontos mind gazdasági, mind társadalmi szempontból. Az ok, amiért a közlekedés témakörét választottam az, hogy ennek kapcsán tapasztalunk legtöbbször, és legközvetlenebbül torlódást és késedelmet. Tárgyalásom során kitérek először azon problémára, hogy miképpen tudjuk matematikailag kezelni, modellezni az úthálózatokat. A valóságban mi kereszteződéseket és utakat látunk, és ezáltal egy természetes megközelítés, hogy gráfokkal reprezentáljuk a közlekedési hálózatokat. Ez alkalmas arra, hogy szemléletesen is leírjuk milyen a valóság, azonban matematikai elemzések során általában arra kényszerülünk, hogy valamilyen formában számítógépen tároljuk el a gráfot. Ezen probléma kapcsán felvázolom, hogy milyen lehetőségeink adódnak e feladat megoldására, és különböző természetű vizsgálódások esetén melyek a hatékony, preferálandó módszerek. A közlekedési hálózat struktúrájának összetettsége és nagy mérete megkívánja, hogy valamilyen pótlólagos információt tudjunk elmondani általánosan egy úthálózat gráfjáról. E kívánalmat úgy elégítettem ki, hogy a vizsgálandó gráfokat síkbarajzolhatónak tekintettem, ezáltal különböző tételek alapján választ kaptam arra, hogy mennyire sűrű általában a vizsgálandó gráf. Ezáltal további útmutatást kaphatunk arra vonatkozólag, hogy tároljuk a gráfunkat. Ha megfelelő sűrűségű egy gráf összekötöttsége, akkor ritkán alakul ki olyan helyzet, hogy egy váratlan esemény bekövetkezése jelentősen korlátozná a csúcspontok elérhetőségét az egész hálózatot tekintve. Kifejtésemben felvázolok egy lehetséges módszert arra, hogyan vizsgálható egy gráf stabilitása ebből a szempontból, ezáltal egy úthálózat tervezése során kapunk egy modellezési eszközt arra vonatkozóan, hogyan építsük ki az infrastruktúrát. Mint a legtöbb rendszerben, a közlekedésben is meg szeretnénk vizsgálni, hogy létezik-e egyensúly, és ha igen, hogyan érhető el. Egyensúly alatt egy olyan állapotot értek, amelyben senkinek sem érdeke eltérni a kiválasztott útvonalától. Ez a közlekedésbeli megfelelője a Nash egyensúlynak. Ennek vizsgálatához felvázolok egy optimalizálási modellt, amely alkalmas arra, hogy egyszerűbb alakú költségfüggvények esetén meghatározzuk az egyensúlyt. A probléma akkor adódik, ha általánosabb függési viszonyt szeretnénk számításba venni az élköltségekre vonatkozóan. Dolgozatomban bemutatom a variációs egyenlőtlenségek által nyújtott modellezési lehetőséget, mely alkalmas általánosabban kezelni az egyensúly fogalmást, ezáltal nagyobb szabadságot ad valóságbeli problémák formalizálása esetén. Ehhez kapcsolódóan ismertetek egy általános iteratív sémát, melyet alkalmazva ki is tudjuk számolni konkrétan az egyensúlyi állapotot. A globális optimum vizsgálatát követően rátérek az egyéni szereplők problémájára, vagyis a legrövidebb útvonalak megtalálására. Ismertetek néhány olyan algoritmust, mely statikus élköltségek mellett megtalálja a legrövidebb utat egy adott kiindulópontból egy végcélba. Ezt követően bemutatom, hogyan alakíthatók ezen algoritmusok olyanná, hogy időben változó súlyok esetén is megtalálják a kívánt útvonalat. Kifejtésem végén bemutatom az általam írt alkalmazást, mely figyelembe veszi, hogy különböző terheltségek mellett, eltérő áthaladási időket tapasztalunk az egyes éleken. Emellett számításba veszi azon járművek viselkedését, melyeknek ő ajánlott útvonalat, ezáltal képes rövid időhorizonton viszonylag jól megbecsülni a forgalmi állapotot. Megvizsgálom, hogy ezen elvek figyelembevételével, milyen mértékű javítás érhető el a realizált áthaladási időkben, a statikus esethez képest. Dolgozatomban tehát a közlekedési hálózatok számos jellemzőjét vizsgálom meg, valamint bemutatom milyen módszerek és elvek szerint lehetséges optimálisan cselekedni a közlekedésben.