Teljesítményoptimalizált útvonalkereső szolgáltatás fejlesztése

OData támogatás
Konzulens:
Dr. Heszberger Zalán Tamás
Távközlési és Médiainformatikai Tanszék

Az útvonalkeresés régóta kutatott tudományterület az algoritmuselméleten belül. Számos tömegkiszolgálásra alkalmas szolgáltatás létezik, mely a közúti útvonalkeresés korábban komplexnek vélt feladatát nagyon rövid időn belül és hatékony eredményt adva oldja meg. A külső szemlélő számára mára már hétköznapivá váló szolgáltatások létrehozása azonban korántsem egyszerűsödött le triviális tervezői- és fejlesztői feladattá. Ennek okán, többnyire csak azon cégek képesek önállóan hatékony szolgáltatást létrehozni, ahol adott az algoritmusismereti tudásbázis, illetve egy jelentős hardveres háttér. A jelentős hardveres háttérre elsősorban azért van szükség, mert a jelenleg elterjedt algoritmusok futásideje drasztikus számítási- és tárkapacitást igényel. Hogy ne csak világméretű vállalatok legyenek képesek az útvonalkereséshez szükséges környezetet megteremteni, hatékonyabb, gyorsabb futásidejű algoritmusok irányába kell kutatásokat végeznünk. Az útvonalkereső-szolgáltatók versenyképessége továbbá igen nagy mértékben a felhasználói élménytől függ, aminek egyik legalapvetőbb elvárása, hogy a keresés válaszideje legyen rövid. Manapság egy lassú válaszidejű kereső szolgáltatással nehéz fennmaradni a piacon.

Az útvonalkereső szolgáltatások fejlesztésekor gyakran probléma forrást jelent az algoritmusok elméleti eredményei és a valós implementációs körülmények közötti kontraszt. Egy kereső papíron bizonyítottan teljesítheti az adott futási idő- és kapacitás maximumokat, a valóságban azonban számos hardver-és szoftverkomponens okozhat szűk keresztmetszetet, amely kapásból felülírja az elméleti eredményeket. Ezzel megint csak ott lyukadunk ki, hogy annak van esélye az elméletet gyakorlatba ültetnie, akinek jelentős hardver-kapacitás áll rendelkezésére. Szerényebb anyagi adottságok esetén tehát az algoritmusaink tervezésekor az implementációs korlátait és adottságait jobban előtérbe kell helyeznünk az elméleti, matematikai alapú feltételezésekkel szemben.

A hagyományos algoritmusok a keresést általában egy tetszőleges gráfon értelmezett minimális súlyú útkeresés problémaként fogják fel. A keresési gráf és a metrika (azaz a „mit értünk legrövidebb út alatt” kérdésre adott válasz) ugyanakkor alkalmazásonként más-más, az adott alkalmazásra tipikus jellemzőkkel rendelkezik. Ezek a jellemzők a tetszőleges gráfra értelmezett probléma-teret egy jóval szűkebb térre minimalizálják, ami a hatékonyság növelésével jár. A közúthálózati útvonalkeresők esetére ez a probléma-minimalizálási hatás különösen igaz, ezért érdemes a natív gráf-algoritmusok helyett – vagy azokat módosítva – kimondottan közúti útvonalkeresésre specializált algoritmusokat kutatni.

Az előzőekben vázoltak alapján jelen diplomaterv célja egy közúti útvonalkereső szolgáltatás fejlesztése, az elméleti sík elemzésétől kezdve, a tervezési folyamaton át egészen egy használható implementációig. A szakterület tanulmányozásakor kiemelt cél olyan, frissen publikált algoritmusok vizsgálata, amelyek a legkevesebb hardverigénnyel a legrövidebb futásidejű keresésekre képesek. Az ezt követő tervezői folyamat célja, hogy az implementációs lépésekkel körforgásban olyan helyes döntéseket tudjon hozni, amelyek hosszú távon megalapoznak egy univerzális célokra használható útvonalkereső-szolgáltatás magját. Az implementáció közvetlen célja az elvárásokban megfogalmazott válaszidő- és terhelési paraméterek teljesítése, a terheléselosztás és skálázhatóság.

Letölthető fájlok

A témához tartozó fájlokat csak bejelentkezett felhasználók tölthetik le.