Távműködtetett Google Maps alapú útvonaltervező alkalmazás


ALKALMAZÁS ELÉRÉSE

Távműködtetett alkalmazásoknak már hosszú idő óta nagy szerep jut mind a kutatások, mind a mindennapi alkalmazások területén. Veszélyes környezetben való munkák elképzelhetetlenek ilyen jellegű laborok, eszközök alkalmazása nélkül, de olyan erőforrás-igényes feladatok elvégzésénél is nagyon hasznos lehet, amikor az egyes felhasználók nem rendelkeznek megfelelő mennyiségű és minőségű eszközzel a feladatok elvégzéséhez.
A Pannon Egyetem Folyamatmérnöki Intézeti Tanszékén egy olyan távolról vezérelhető környezetet hoztunk létre, mely számításigényes feladatok elvégzésére képes. Egész pontosan egy olyan keretrendszert alkottunk meg, mely képes egy kiinduló Google Maps térképből a koordináták kinyerésére, az alapján távolságmátrix generálására, majd ezen adatok alapján egy többes utazóügynök probléma, vagy inkább egy járműütemezési probléma optimalizálására, végül az eredmények szemléletes megjelenítésére, egy Google Maps térképen. A keretrendszer sematikus ábrája az alábbi képen látható.

Keretrendszer sematikus ábrája

Ahogy említettük, a folyamat egy bárki által könnyen létrehozható Google Maps térképből indul ki. Ezen e térképen létre kell hoznunk helyjelölőket, melyek a támaszpontjainkat definiálják koordináták alapján. A második elem adatbányászati módszerek alkalmazásával meghatározza térképen található jelölők szélességi- és hosszúsági koordinátáit. A "Távolságmátrix generálás" komponens a koordinátákból létrehozza a távolságmátrixot, mely bármely két pont között lévő út hosszát tartalmazza mindkét irányban. Az oda-vissza irányok mindegyikére azért van szükség, mivel pl. az egyirányú utak miatt eltérés lehet a két irányban megteendő útvonal hossza között. A negyedik komponens bemeneteként meg kell határoznunk, hogy melyik a raktár támaszpont, ugyanis minden járművünk minden útja során innen indul el, és ide érkezik is vissza útja végén. Maga a probléma, tehát a fuvarszervezési probléma az alábbi módon definiálható: adott a támaszpontok halmaza, és adott hogy maximálisan hány darab járművünk van, adottak továbbá különböző megszorítások, mint hogy egy jármű maximálisan hány kilométert mehet, vagy hogy minden egyes támaszponton mennyit kell várakozniuk az autóknak (pl. az áru pakolása). Feladatunk találni egy olyan útvonaltervet a járműveink részére, mellyel az összes támaszpontra eljutunk, és minimális költséget generálunk, tehát a járművek által megtett utak összegének minimálisnak kell lennie. Mindegyik autó egy központi raktárból indul, és ugyanoda is érkezik vissza. Ez egy tipikusan nehéz (úgynevezett np-nehéz) optimalizálási probléma, melynek megoldása heurisztikus algoritmusok alkalmazását kívánja meg. Az egyik ilyen osztálya az algoritmusoknak a genetikus algoritmusok, mely a Darwin által felállított evolúciós stratégiát képezik le a számítástudomány nyelvére. Ezen algoritmusokban egy egyed a probléma egy teljes megoldását reprezentálja, tehát esetünkben egy egyedbe bele kell kódolnunk minden járművünk útvonalát. Ezt úgy tehetjük meg, hogy a támaszpontjainkat sorszámokkal látjuk el, 0-tól kezdődően, ahol a 0-ás támaszpont mindig a központi raktárt jelenti, és az egyedünkbe csak az útvonal által érintett támaszpontok számát tesszük bele. Egy ilyen, a tanszékünkön kifejlesztett genetikus reprezentációt mutat a következő ábra:

Genetikus reprezentáció

Könnyen látható, hogy az egyed első kromoszómája jelenti az első járművet, amelyik elindulva a raktárból, először elmegy a 2-es támaszpontra, majd sorban az 5-ös, 14-es és 6-os támaszpontokra, majd végül visszatér a depóba. A depót nem jelenítjük meg itt, ezzel is csökkentve a számolások erőforrásigényét. A negyedik komponens egy ilyen egyedekkel dolgozó genetikus algoritmussal minimalizálja a problémát. Az algoritmus első lépésben egy teljesen véletlenszerű egyedekből felépülő populációval indul, majd minden iterációs lépésben keresztezi egymással a legjobb egyedeket, majd a létrejött egyedeken mutációkat hajt végre, így alakítva ki egyre jobb és jobb egyedeket. Végeredményként egyetlen egyedet szolgáltat, tehát egyetlen megoldást, melyben lévő járművek által megtett útvonalösszeg a legkisebb. Az utolsó, "Megjelenítés" komponens ezeket az eredményeket jeleníti meg egy Google Maps térképen, az egyes járművek útvonalát sorszámokkal egyértelműen jelölve, az autókat pedig különböző színekkel szeparálva egymástól.

Mivel az optimalizáció folyamata (és a hozzá tartozó kiegészítő funkcióké) igen erőforrás-igényes feladat, tanszékünkön létrehoztunk egy távolról vezérelhető alkalmazást, mellyel a felhasználók az egyetem szerverét használva otthonról, kényelmes körülmények közt végezhetik el a fent leírt optimalizálási folyamatot.

Az említett program ITT ÉRHETŐ EL.

Ahol az útvonaltervezést egy a háttérben futó MATLAB szoftver végzi el. A teljes rendszer informatikai megvalósítását az alábbi ábra szemlélteti. A rendszerben az útvonaltervező kivételével minden komponens a Google Maps API szolgáltatására épül, mellyel lehetőség van téképek létrehozására, két pont között közúton megteendő útvonal számítására, továbbá az eredmények térképen történő megjelenítésére.

Genetikus reprezentáció




Kezdőlap
Témakörök
Alkalmazások
Publikációk
Alprojektek
Kapcsolat