Dunaújvárosi Főiskola
http://inf.duf.hu/index.php/ikt2010/
Informatikai Intézet
[email protected]
IKT 2010 Internet technikák
tel.: (25) 551-627 2400 Dunaújváros, Táncsics M. u. 1/A
Google Maps alapú programcsomag útvonalhálózat elemzésének és optimalizációjának támogatására Király András, Abonyi János Pannon Egyetem, Folyamatmérnöki Intézeti Tanszék, 8200 Veszprém, Pf.158.,
[email protected]
Kivonat: A logisztikai ellátó rendszerek optimalizációja rendkívül eszközigényes feladat. A sikeres alkalmazások feltétele nemcsak a hatékony optimalizációs algoritmus - melyeket a mai napig folyamatosan fejlesztenek -, hanem a megfelelő térinformatikai háttér is. A Pannon Egyetem Folyamatmérnöki Intézeti Tanszékén az elmúlt évben olyan kutatásokat folytattunk, melyek mind az algoritmusok fejlesztését, mind pedig a megfelelő térinformatikai háttér biztosítását támogatják. Az alapgondolat az volt, hogy széles körben elérhető eszköz- és megoldáscsomagot hozzunk létre. Ennek érdekében Google Maps API alapú keretrendszert dolgoztunk ki. Ennek moduljai alkalmasak Google Maps térképekből távolságmátrixok automatikus számítására, összetett útvonalhálózatok megjelenítésére, elemzésére, költség- és időigények automatikus számítására. A programcsomag jelenleg 5 modulból áll: Map a kezdeti térkép definiálásához; Coordinates Retrieval komponens a koordináták térképből történő automatikus kinyerésére; Distance Table a távolságmátrix készítésére; Route Planning modul, mely a problémát módosított többes utazóügyök feladatként azonosítva egy genetikus algoritmusra épülő közelítő megoldást szolgáltat; Visualiser komponens az eredmények megjelenítésre. A cikk e modulokat, azok fejlesztésével kapcsolatos részleteket, illetve azok alkalmazási lehetőségeit mutatja be. Kulcsszavak: logisztika, optimalizáció, többes utazóügynök probléma , Google Maps.
1.Bevezetés A logisztika alapvető feladata, hogy a megfelelő termékeket a megfelelő időben a megfelelő helyre juttassa el, valamilyen előre definiált teljesítménymutatók optimalizálása mellett (pl. a teljes működési költség minimalizálása), adott megszorítások figyelembe vételével (pl. idővagy kapacitáskorlátok). A legtöbb elosztó hálózatban, ahol több termelő egységtől kell szállítanunk árukat több felhasználó felé, meg kell határoznunk az egyes szállítmányok összetételét és útvonalát, valamint ezeket a szállítmányokat szállító járművekhez kell rendelnünk. A feladatunk meghatározni a valamilyen célfüggvény szerinti optimális hozzárendelést. Ebben a numerikus optimalizálási feladatban a hozzárendelések lehetséges száma igen magas, az optimum megkeresése általában NP-nehéz feladat. A legjobban ismert, és legtöbbet tárgyalt probléma az ún. járatszervezési probléma (Vehicle Routing Problem - VRP) [1], mely esetében adott az azonos kapacitással rendelkező járművek halmaza, egy központi depó, és számos felhasználói igény; a feladat megtalálni a járművek összesített útvonalköltsége szempontjából minimális járathálózatot, amellyel minden felhasználói elvárás kielégíthető. A VRP probléma kezelésére több kereskedelmi szoftver is található, mint az ILOG1 az IBM-től, vagy az ESRI által forgalmazott ArcLogistics2, melyek 1
http://www.ilog.com/
bevezetése azonban komoly terhet jelenthet egy kisebb vállalat számára. A VRP probléma relaxációja a többes utazóügynök probléma (multiple Traveling Salesman Problem – mTSP) [2], mely esetében a járművek kapacitása végtelen. A VRP-re alkalmazható formalizmusok és eljárások mTSP esetén is érvényesek, megfelelően nagy kapacitások alkalmazásával. Az ellátási hálózatok általában nagyszámú csomópontot tartalmaznak, melyek egy komplex, összekapcsolt struktúrát alkotnak. Ahhoz, hogy az optimalizáció elfogadható időben végrehajtható legyen, célszerű az egyes városok közötti távolságokat előre meghatározni, azaz elkészíteni a hálózat távolságmátrixát, mely bármely két pont közti útvonal hosszát tartalmazza. Továbbá egy sok várost tartalmazó ellátási lánc minden elemét lefedő útvonalhálózat ugyancsak igen bonyolult lehet, melynek megértését nagyban megkönnyítheti az eredmények felhasználóbarát szemléltetése. Sem a VRP, sem az mTSP problémára nem létezik jelenleg teljeskörű megoldást kínáló, ingyenes szolgáltatásokat használó ingyenes, vagy igen olcsó megközelítés. A cikkben egy módosított mTSP probléma optimalizálására képes teljeskörű és könnyen értelmezhető, látványos programcsomagot ajánlunk, ingyenes technológiák alkalmazásával. A célkitűzés egy olyan moduláris rendszer kifejlesztése, mely képes a felhasználó által definiált Google Maps térképből kiindulva az utazóügynökök optimális útvonalainak automatikus kiszámítására, valamint könnyen értelmezhető megjelenítésére.
2.Tervezés A tervezett rendszer komponensdiagramja látható az 1. ábrán. Az első komponens (Maps) a kezdeti térkép definiálását reprezentálja. A Coordinates Retrieval elem az előzőekben definiált térképből automatikusan kinyeri az egyes városok adatait, melyet aztán a Distance Table komponens használ fel a távolságmátrix generálásához. A Route Planning Algorithm egy újszerű reprezentáción alapuló genetikus algoritmus, mely az optimális útvonalhálózatot szolgáltatja, figyelembe véve az előző fejezetben tárgyalt plusz megszorításokat. A Visualiser elem az eredményeket könnyen értelmezhető formában jeleníti meg ugyancsak Google Maps felületen.
1. ábra: Az elkészült rendszer komponensdiagramja 2
http://www.esri.com/software/arclogistics/
A tervezett rendszer minden komponense implementálásra került, ezek együttműködve egy komplett rendszert alkotnak, mely képes félig-automatikusan generálni az optimális útvonalhálózatot. A rendszer részleteit, az egyes komponensek tulajdonságait a következő fejezet ismerteti.
3.Az elkészült rendszer Az előző fejezetben ismertetett komponenseket különböző technológiák alkalmazásával implementáltuk. Ezek részleteit az alábbiakban ismertetjük. A teljes programcsomag, és az egyes komponensek külön-külön is, néhány további tesztelést követően hamarosan elérhetővé válnak a http://www.folyamatmernok.hu/ oldalon. A rendszer első komponense (Map) csupán reprezentatív jellegű, a térkép felhasználó általi definiálását szimbolizálja. Valójában ez a Google által szolgáltatott felületen, böngészőben történik, a felhasználó saját fiókjába való belépés után. A térkép meghatározása után a usernek ki kell lépnie a fiókjából. Ekkor a böngésző címsorában megjelenik a térkép egyedi URL-je, mely a Google szerverén egyértelműen azonosítja azt. Ez az azonosító szolgál bemenetül a következő komponensnek. Mivel a Google Maps térképek formája jól meghatározott, lehetőség nyílik az adatok automatikus kinyerésére. Ehhez csupán a fent ismertetett egyedi azonosítóra van szükség. A komponens (Coordinates Retrieval) felületét a 2. ábra ábrázolja.
2. ábra: A koordináták kinyerésére szolgáló program felülete
Itt megadhatjuk az URL-t, valamint a fájl nevét, amelybe az adatokat mentjük. Ezután a program automatikusan elkészíti a városok adatait tartalmazó állományt, Microsoft Excel táblázat formájában, melyet a 3. Ábra szemléltet. A koordinátákat a szoftver a definiált térkép forrásából vonja ki, melyben jól definiálható kulcsszavak azonosítják az egyes adatok határait, mint pl. az adat kezdetét a "latlng:{lat:" karaktersorozat jelzi, ezután következik a szélességi koordináta, majd a hosszúsági, végül pedig az adott pont leírása. Így ezen azonosítókra történő kereséssel a forrásszövegből kinyerhetőek a szükséges szélességi és hosszúsági koordináták.
3. ábra: A Coordinates Retrieval komponens kimenete
Az optimalizációhoz elengedhetetlenül szükséges két város közötti optimális útvonal ismerete, vagyis egy távolságmátrix megléte. Ehhez bármely két város közötti útvonal hosszát meg kell határoznunk. Jelen eseteben szárazföldön (pl. teherautóval) megtehető útvonalakra gondolunk. Nyilvánvalóan nem elegendő csak egy irányban kiszámolni a két pont közötti távolságot, mivel pl. egyirányú utcák miatt különbözhet a két irányban megteendő útvonal. Jelenleg nem található olyan szoftver a piacon, amelyik egy Excel táblázatban adott városlistából automatikusan, és helyesen kiszámolná a távolságmátrixot, valamelyik ingyenes szolgáltatás használatával (pl. Google Maps, Yahoo Maps, Bing Maps). A piacon létező megoldások közül még a kereskedelmi szoftverek sem működnek megbízhatóan, sok esetben képtelen azonosítani a megadott városokat, így a távolságmátrix kiszámítására saját megoldást hoztunk létre. Ehhez a széles körben használt Google Maps API szolgáltatását használtuk. PHP és Javascript nyelvek használatával az elkészült szoftver (Distance Table komponens) képes az előző komponens által nyújtott (3. ábra) Excel táblázatból kiszámítani, majd ugyancsak egy Excel táblázatba elmenteni a távolságmátrixot. Ennek eredményét szemlélteti a 4. ábra.
4. ábra: A távolságmátrix
Mivel a Google Maps API szabályzata csak a Javascript hívásokat támogatja, a távolságmátrix-számító program is ezt az elvet követi. Ebből mutat egy rövid részletet a következő programrészlet: 1 function initialize() { 2 geocoder = new GClientGeocoder(); 3 gDir = new GDirections(); 4 GEvent.addListener(gDir, "load", function() { 5 distancesMI.push((gDir.getDistance().meters/1609).toFixed(2)); 6 distancesKM.push((gDir.getDistance().meters / 1000).toFixed(2)); 7 durations.push(gDir.getDuration().seconds / 60); 8 if (++i < data.length) 9 setTimeout("doIt()",200); 10 }); 11 }
12 function showLocation(address1,address2) { 13 geocoder.getLocations(address1, function(response) { 14 location1 = {lat:response.Placemark[0].Point.coordinates[1], lon:response.Placemark[0].Point.coordinates[0], address:response.Placemark[0].address}; 15 geocoder.getLocations(address2,function(response){ 16 location2={lat:response.Placemark[0].Point.coordinates[1], lon:response.Placemark[0].Point.coordinates[0], address:response.Placemark[0].address}; 17 gDir.load("from: "+address1+" to: "+address2); 18 }); 19 }); 20 }
Az initialize() függvényben létrehozunk egy-egy új GclientGeocoder és Gdirections objektumot, melyek szükségesek a Google szolgáltatását használó távolságszámításhoz. Az 5,6,7-es sorok a távolságok számítását végzik kilométerben, mérföldben, illetve percben. Az API aszinkron módú működést enged meg, ami a hívásokat nem blokkolja, így helytelen adatokat kaphatunk vissza, ezért a 8-10 sorokban a hívások szinkronizálást oldjuk meg. A számítás során a showLocation() függvényt hívjuk iteratívan, ami geokódolja a koordinátákat (13-16 sorok), majd meghívja a Gdirections objektum eseménykezelőjét (17. sor), ami a már vázolt módon kiszámítja a távolságokat. Az utazóügynökök optimális útvonalainak kiszámítására egy olyan új típusú reprezentáción alapuló genetikus algoritmust fejlesztettünk ki, mely az előzőleg kiszámított távolságmátrix használatával képes az eddigi megoldásoknál kevesebb iterációs lépésben megadni az optimális megoldást, figyelembe véve előre definiált plusz megszorításokat, mint pl. az utazóügynökök maximális száma, vagy az egy utazóügynök által megtehető maximális útvonalhossz. Ennek részletesebb ismertetése megtalálható [3] munkában. A MATLAB-ban implementált algoritmus egy tömbben adja vissza az útvonalakt, amit az alábbi formára alakítunk: 1|5|2|1;1|7|4|6|3|1
Az utolsó komponens képes az algoritmus által szolgáltatott eredményeket egy könnyen értelmezhető, Google Maps térkép formájában vizualizálni, mely segítségével egyszerűen leolvashatók az egyes utazóügynökök által megteendő útvonalak, melyek színekkel jól láthatóan elkülönülnek egymástól. Ezt ábrázolja az 5. Ábra. A megjelenítéshez ugyancsak PHP és Javascript nyelvek használatával, a Google Maps API szolgáltatását használtuk, melynek egy rövid részletét az alábbi programrészlet mutatja be: 1 point = new GLatLng(parseFloat(datas[optPath[optIndex][index-1]-1][0]), parseFloat(datas[optPath[optIndex][index-1]-1][1])); 2 point2 = new GLatLng(parseFloat(datas[optPath[optIndex][index]-1][0]), parseFloat(datas[optPath[optIndex][index]-1][1])); 3 setIcons(); 4 marker = new GMarker(point2, {icon:icon}); 5 map.addOverlay(marker); 6 dirn.loadFromWaypoints([point2, point], {getPolyline:true});
Az 1. És 2. Sorok a geokódolás folyamatát végzi, mely során a komponens a koordináták alapján azonosítja a térképen a városok helyzetét. Ezután beállítja a használandó ikonokat
(3.sor), majd ezzel létrehoz egy új jelölőt (4. Sor). Ezután, amint az 5. sorban látható, elhelyezi a markert a térképen, végül pedig az aktuális és az előző pont között kirajzolja a térképre a pontokat összekötő vonalat (6. sor).
5. ábra: Az optimalizáció végeredményét ábrázoló Google Maps térkép
4.Alkalmazási lehetőségek A fejezet a rendszer által szolgáltatott eredmények további alkalmazhatóságára világít rá egy a távolságmátrix korszerű módszerrel történő vizsgálatán keresztül. Az 5. ábrán a távolságmátrix dendrogramja látható, melyen jól látszik, hogy a mátrix jól elkülöníthető csoportokra bontható. A VAT metódust (Visual Assessment of Cluster Tendency) 2002-ben vezette be Bezdek és Hathaway [4]. A VAT elemzés eredményét mutatja a 6. ábra, melyen az egyes klaszterek könnyen kivehetők. Az egyes csoportok felderítése további optimalizálási lehetőségeket, valamint heurisztikák bevezetését teheti lehetővé, mellyel a módszer hatékonysága, gyorsasága tovább javítható.
5. ábra: a távolságmátrix Dendrogramja
6. ábra: A távolságmátrixon végrehajtott VAT metódus eredménye
5.Összefoglalás A cikk ismertet egy olyan programcsomagot, mellyel lehetőség nyílik a többes utazóügynök feladat optimalizálására, egy egyszerű Google Maps térképből kiindulva. A modulárisan felépülő rendszer automatikusan képes elvégezni a minimalizáció egyes lépéseit, egy a szerzők által korábban bevezetett genetikus algoritmus segítségével pedig képes kezelni további, a logisztikában igen fontos korlátokat is, mint pl. az egy teherautó által megtehető maximális útvonalhossz. A keretrendszer széleskörű alkalmazhatósága megkérdőjelezhetetlen, melyet az mTSP probléma gyakorlati életben való alkalmazásának elterjedtsége garantál.
Irodalomjegyzék [1] Laporte, G.: The vehicle routing problem: An overview of exact and approximate algorithms, European Journal of Operational Research, 59(13), 345-358, Citeseer, 1992 [2] Bektas, T.: The multiple traveling salesman problem: an overview of formulations and solution procedures, Omega, 34, 209–219, 2006 [3] András Király, János Abonyi: Optimization of Multiple Traveling Salesmen Problem by a Novel Representation based Genetic Algorithm, 10th International Symposium of Hungarian Researchers on Computational Intelligence and Informatics, november 12-14, 2009, Budapest, Hungary [4] Bezdek, J.C. and Hathaway, R.J.: VAT: A tool for visual assessment of (cluster) tendency, Proceedings of IJCNN, 2225-2230, 2002
