Petr Fuks
Institut geoinformatiky
VŠB -Technická univerzita Ostrava
tř. 17. Listopadu
708 33 Ostrava - Poruba
E – mail: petr.fuks.hgf@vsb.cz
This thesis describes a process of creating of application for goods distribution planning. Problems of pathfinding between more that two places are in graph theory known as a travelling salesman problem and its solutions are used in this project. This application is based on several open source projects:
Application uses free dataset issued by silnicni databanka Ostrava.
Tato diplomová práce popisuje tvorbu aplikace pro plánování rozvozných tras zboží. Problematika hledání (plánování) nejkratší cesty, mezi více jak dvěma místy, je popsána v teorii grafů jako problém obchodního cestujího jehož známá řešení byla v tomto projektu použita. Vytvořená aplikace využívá několika open source projektů:
Aplikace používá volně dostupná data vydané silniční databankou Ostrava.
Úkolem této diplomové práce je vytvoření aplikace pro plánování rozvozných tras. Vývoj aplikace byl zahájen na základě požadavku firmy Atoma. Firma zadala požadavek vytvoření IS, který měl usnadnit práci operátora při informování zákazníků o produktech firmy a zkvalitnit tak její informační servis, a také požadavek na vytvoření aplikace, která by komplexně řešila plánování dodávky výrobků ze skladu až ke koncovým zákazníkům. Řešení mělo zahrnovat plánování tras pro rozvoz zboží s omezujícími podmínkami nosnosti automobilu a časového omezení trvání jízdy. Firma požadovala co nejmenší náklady na tento systém s tím, že pro obě úlohy (vyhledávání nejbližší pobočky a plánování trasy) postačuje rozlišení na úrovni spojení mezi jednotlivými obcemi a nebude potřeba vyhledávání uvnitř obcí. Toto zjednodušení nejenže sníží náklady na vstupní data, ale také zjednoduší výpočetní algoritmy. Dalším navrhovaným krokem ke zlevnění vyvíjeného systému je použití otevřených technologií a volně dostupného programového vybavení.
Hledání nejkratší cesty je dobře známým problémem. Pod tímto pojmem si jistě každý představí cestu spojující dvě místa v prostoru tak, že cesta vede co možná nejpřímočařeji od startu k cíli. Prostor, ve kterém je cesta hledána, je ve většině případů síť. Příkladem takovéto sítě může být síť silniční, železniční, vodovodního potrubí nebo distribuční síť elektrické energie. Všude tam, kde je potřeba nalezení optimálního spojení, je využita úloha nalezení nejkratší cesty. V těchto optimalizačních úlohách nemusí pojem „nejkratší“ nutně znamenat prostorově nejkratší. V závislosti na použité ohodnocovací funkci je vyhledána cesta také například nejrychlejší, nejbezpečnější apod.
K popsání a řešení úlohy nalezení nejkratší cesty je ve většině případů využita teorie grafů. Teorie grafů je vědeckou disciplínou, jíž tvoří soubor poznatků a metod, které vznikly především při zkoumání praktických úloh a byly později doplněny a zobecněny. Hledání nejkratší cesty je jednou z těchto praktických úloh. Dnes existuje několik typů úloh hledání nejkratší cesty. Od klasické, kdy je požadováno nalezení nejkratší cesty z jednoho místa do druhého, až po složité úlohy, jako je například problém obchodního cestujícího.
Problémem hledání cesty (pathfinding) se rozumí úloha nalezení nejvhodnější (podle daných kritérií) cesty z místa A do místa B v definovaném prostoru (obvykle grafu) Hledání cest má, kromě již zmiňovaných dopravních systémů, také mnoho aplikací v umělé inteligenci, počítačových hrách, virtuální realitě, vojenství a robotice, kde je třeba vhodně procházet prostředím a vyhýbat se překážkám. Příkladem může být robot na vzdálené planetě, který musí být schopen pohybu nezávisle, protože k němu signály buď neproniknou, nebo je díky veliké latenci signálu nemožné ho dálkově ovládat člověkem. Pathfinding je užitečný v automatickém řízení vozidel a jiných dopravních prostředků. V počítačových hrách má pathfinding velké uplatnění zejména ve strategiích nebo v hrách s počítačem řízenými protihráči. Zde je simulováno chování člověka při hledání cesty nebo se požaduje hledání nejkratších cest. Pathfinding je široce uplatňován také při zjišťování nejlepšího propojení směrovačů pro přenos zpráv v sítích. Pro nalezení nejkratší cesty se využívají tyto algoritmy:
Speciálním případem úlohy nalezení nejkratší cesty je tzv. úloha obchodního cestujícího. Zadání této úlohy je formulováno takto: Je dáno m měst. Některá města jsou propojena silnicemi, délka silnic je známa. Úkolem obchodního cestujícího je navštívit všechna města (právě jednou nebo aspoň jednou). Nalezněte takovou trasu (permutaci měst), aby délka projeté cesty byla co nejmenší.
Úloha obchodního cestujícího patří do skupiny NP- úplných problémů (non-polynomial complete), tedy její řešení je časově velice náročné neboť složitost toho problémů je ex. Řešit tento problém klasickými algoritmy („hrubou silou“) je proto možné jen pro velmi malý počet měst. Pro nalezení řešení při obecně m městech musí být použit jiný sofistikovanější způsob řešení., který nám sice se stoprocentní jistotou neumí říci, zda zvolená trasa je skutečně nejkratší, ale nalezne řešení které se nejkratšímu řešení velice blíží. Toto tzv. suboptimální řešení je často dostačující. Problém obchodního cestujícího se obecně řeší pomocí:
Po nastudování teoretické části byl navržen postup hledání rozvozné trasy s využitím grafu a grafových algoritmů. Prvním z kroků je konverze silniční sítě do podoby grafu. Jako vstupní data byla zvolena vektorová silniční síť silniční databanky Ostrava. Tato síť je složena z uzlů a úseků, jež tvoří jejich spojnice. Vytvoření grafu spočívá v konverzi uzlů sítě na vrcholy grafu a úseků sítě na hrany grafu (Obr. 1). Ohodnocení hran určují atributy dat úseků. Ohodnocení je vypočteno ze součinu prostorové délky a koeficientu třídy silnice. Ohodnocení tedy neodpovídá čistě délce úseku, ale jakési míře náročnosti potřebné k projetí úseku. Touto náročností byla snaha zohlednit kromě délky také kvalitu úseku. Ve výsledku bude proto nalezena cesta jež je označována jako nejrychlejší.
Obrázek 1 vytvoření ohodnoceného, orientovaného grafu
Samotné nalezení nejkratší cesty lze rozdělit do čtyř významných kroků:
Obrázek 2 vzorek silniční sítě s definovanými zastávkami
Obrázek 3 graf nejkratších vzdáleností mezi zastávkami
Obrázek 4 Hamiltonova kružnice grafu nejkratších vzdáleností
Obrázek 5 nejkratší cesta mezi zastávkami v silniční síti
V průběhu tvorby aplikace bylo vytvořeno několik funkčních verzí. Zde je uveden jejich přehled s popisem funkčnosti.
První verze programu byla navržena podle požadavků firmy Atoma. Tato verze měla být schopna spolupráce s aplikací pro správu zakázek firmy, postavenou na databázi MySQL. Z tohoto důvodu bylo využito databáze i jako úložiště dat potřebných pro vyhledání. Výhody tohoto řešení jsou jednoduchá správa dat pro více klientů a rychlé získání potřebných dat pomocí dotazovacího jazyka SQL. Nevýhodou byla pro běžného uživatele komplikovaná instalace této aplikace z důvodu nutnosti instalace MySQL serveru a jeho konfigurace. Implementované postupy pro výpočet nejkratší cesty byly schopny nalézt cestu mezi dvěma až deseti definovanými zastávkami, a to v relativně krátkém čase. Výsledné zobrazení cesty této verze bylo omezeno pouze na textovou podobu.
Obrázek 6 grafické rozhraní první verze aplikace
Druhá verze vznikla po ukončení spolupráce s Firmou Atoma. Ukončením spolupráce s touto firmou také zanikl požadavek na propojení aplikace s databází zakázek firmy. Tato verze byla proto navržena již bez využití databáze MysSQL, neboť nutnost instalace a nastavení databázového serveru by komplikovala využití pro běžné uživatele. Pro reprezentaci grafu byla zvolena vlastní podoba vhodná pro vyhledávání. Graf byl popsán pomocí matice sousednosti a uložen do souborů na pevný disk. Pro převedení dat z formátu dbf do objektů jazyka Java bylo využito nástrojů GeoTools lite. Třídy pro převod dat a výpočetní algoritmy se dále oproti předchozí verzi zoptimalizovaly. Bohužel import dat (vytvoření grafu) zůstal i nadále operací časově velice náročnou. Velké změny doznalo grafické uživatelské rozhraní. K tvorbě grafického rozhraní byly vyzkoušeny hned dva open source projekty zaměřené na zobrazením a práci s geodaty. Výsledná aplikace dokázala nalézt nejkratší cestu mezi 10 definovanými městy a zobrazit výsledek jak graficky nad silniční sítí, tak i pomocí podrobného textového výpisu. Výpis obsahoval čísla silnic, ujeté vzdálenosti po jednotlivých silnicích a trvání jízdy v čase. Dále aplikace kontrolovala, zda není překročena nosnost automobilu nebo zda trvání trasy není delší, než pracovní doba řidiče. Nevýhodou této verze bylo, i přes podstatné zlepšení, stále nedostatečně vyspělé grafické rozhraní a nutnost konverze původních dat.
Obrázek 7 mapové okno druhé verze aplikace spolu s formuláři pro definici zastávek
Po konzultaci s vedoucím práce bylo na základě nevyhovující podoby grafického rozhraní aplikace rozhodnuto o jejím přepsání do podoby pluginu aplikace JUMP. Využití aplikace JUMP k vizualizaci vyvíjeného pluginu PathFinder[CZ] (dále PathFinder[CZ]) má mnohé výhody. První významnou výhodou je využití již vytvořeného a velice uživatelsky příjemného grafického rozhraní. Další výhodou je její koncepce, která dovoluje velice snadno rozšiřovat funkčnost celé aplikace. Koncepce definuje rozšířitelný rámec, do něhož jsou připojeny jednotlivé pluginy. Kromě změny grafického rozhraní byl změněn i způsob vytvoření a práce s grafem. K vytvoření grafu byl využit open source projekt JGraphT. Hlavní výhodou implementace grafu z tohoto projektu je jeho velice rychlé vytvoření, předdefinované typy grafů a také implementace Dijkstrova algoritmu pro nalezení nejkratší cesty. Díky projektu JGraphT byla odstraněna nutnost vytvářet pomocné soubory a také bylo díky obecnému popisu Dijkstrova algoritmu možné vyhledávat cestu i v orientovaném grafu.
Obrázek 8 vizualizace výsledku pluginu v aplikaci JUMP
K vývoji aplikace byly využita silniční síť Silniční databanky Ostrava.
V prvním kroku byl proveden průzkum v oblasti teorie grafů a algoritmů pro vyhledání nejkratší cesty. Na základě tohoto průzkumu byly vybrány vhodné algoritmy a navržen postup řešení zadaného problému. Návrh realizace se nejprve odvíjel od reálných potřeb původního zadavatele. Po ukončení spolupráce s firmou Atoma a následné poradě s Ing. Růžičkou, Ph.D. se práce zaměřila na vývoj aplikace do podoby pluginu pro JUMP Workbench. Vytvořený plugin byl začleněn do projektu JUMP Plugins from GISAK.VSB.CZ[24]. Tento projekt zastřešuje vytvořené GIS nástroje pro JUMP Workbench z domény gisak.vsb.cz, respektive gis.vsb.cz. Vytvořený plugin bude dostupný na domovské stránce tohoto projektu. Kromě již zmíněného projektu JUMP Plugins from GISAK.VSB.CZ byly znalosti v oblasti vyhledávání nejkratší cesty také využity v rámci řešení výzkumného úkolu „Logika a umělá inteligence pro multiagentní systémy“ č. T101940420, financovaného v rámci Národního programu orientovaného výzkumu, podprogram Informační společnost. Výsledky práce měly pomoci při vytváření inteligentní infrastruktury silniční sítě, která je schopna plánování nejkratších cest.
Na základě potřeb původního zadavatele aplikace a složitosti problému, došlo na začátku řešení diplomové práce k zjednodušení obecné úlohy obchodního cestujícího, jež popisuje problém nejkratší cesty mezi obecně n městy, na úlohu nalezení nejkratší cesty mezi maximálně deseti městy. Maximální počet měst vychází z omezené schopnosti využitého vyhledávacího algoritmu. Tato omezující vlastnost by mohla být odstraněna změnou algoritmu. V závěru práce byly vyzkoušeny třídy open source projektu JGAP (Java Genetics Algorithms Package)[25], které by mohly rozšířit možnosti vyhledání na obecně n zastávek hledané cesty. Jednoduchá ukázková třída prokázala vysokou rychlost vyhledání nejkratší cesty i pro větší počty zastávek, ale nalezené řešení (pro 20 zastávek) bylo více jak trojnásobně delší než řešení nejkratší. Tento výsledek byl dosažen pouze pomocí ukázkové třídy uvedené na webových stránkách projektu JGAP. Po podrobnějším nastudování projektu bude jistě dosaženo lepších výsledků. Zapojení projektu JGAP nebo některého jiného řešení obecné úlohy obchodního cestujícího, nebude pravděpodobně realizováno v termínu vyhrazeném na tuto práci, ale je s ním počítáno do budoucnosti.