Nalezení nejlepší strategie řidičů Taxi

Nalezení nejlepší strategie řidičů Taxi

---

Název simulace: Nalezení nejlepší strategie řidičů Taxi

Autor: Zikl00 (talk) 23:34, 4 June 2020 (CET)

Typ modelu: Multiagentní

Modelovací nástroj: NetLogo

Popis modelu: Taxikářská společnost v jednom malém městečku se snaží přizpůsobit strategii svých taxikářů tak, aby zákazníci čekali co nejkratší dobu. Pro přiblížení skutečnosti je město rozděleno na segmenty, kde se zákazníci vyskytují více či méně. Stav dopravní situace v průběhu dne zachycuje běžné rozdělení řidičů na silnici (dopravní špičky ráno a odpoledne, klid v nočních hodinách, atd.). Operátor vypočítá, který taxík bude u zákazníka nejrychleji, a toho k zákazníkovi pošle - do výpočtu se zahrnuje i čas cesty, kterou musí taxík ještě absolvovat se stávajícím pasažérem (vznikne tak jakási jednoduchá fronta). Někteří zákazníci nevydrží čekat, takže si zařídí jiný způsob přepravy. Tímto se zabrání hromadění čekajících zákazníků - simulace nemá primárně zkoumat, kolik zákazníků se podařilo převézt atd., ale jaká je nejvhodnější strategie pro taxikáře ve chvílích, kdy nemají co na práci. Takové strategie jsou celkem čtyři.

Cíl simulace: Účelem této simulace je na základě nastavených parametrů zjistit, která strategie řidičů se nejlépe osvědčí v souvislosti s čekací dobou zákazníků. Díky různým parametrům modelu se ale také mohou objevit další zajímavé spojitosti.

Model

Model je vytvořen v softwaru NetLogo, který je určen především pro modelování multiagentních systémů. Dalším důvodem, proč je použit tento software, je užití mapy, resp. černobílého obrázku, kde bílé spojité úseky definují trasu (silniční komunikaci). Z toho plyne obrovská výhoda modelu - variabilita - kód umí zpracovat jakoukoli mapu ve správném formátu, tedy bílá trasa na černém pozadí. Vzhledem k tomu, že každý bod má své souřadnice, je možné implementovat vyhledávací algoritmus A* pro vozy taxi, resp. jejich orientaci na mapě.

Mapa

V tomto případě byla použita mapa České Lípy z webu www.mapstyle.withgoogle.com, kde se dá nastavit kombinace barevných stylů zobrazení. Nastavením zobrazení mapy se dosáhlo odstranění názvů ulic, autobusových stanic a dalších "rušivých" prvků. Mapa se pak také zobrazila pouze v několika málo variantách černé nebo bílé. Následnými lehčími úpravami v jednom ze základním grafickém softwaru bylo dosaženo ryze černobílé barevné kombinace.

Agenty

Po mapě se pohybují řidiči taxi. Všichni vozí pasažéry z jednoho místa na druhé. Liší se však v chování, které nastane ve volné chvíli po vysazení pasažéra, kdy se na dalšího pasažéra musí nějakým způsobem čekat. To lze podle modelu celkem čtyřmi způsoby. Oproti původnímu zadání zde tedy přibyl čtvrtý typ řidiče taxi. Dále se pak přidal pasažér.

• Taxikář_1: Po dokončení trasy řidič čeká a místě, dokud nezavolá další zákazník. Předpokládá se parkovací místo hned u místa vysazení pasažéra.

• Taxikář_2: Po dokončení trasy řidič náhodně jezdí po mapě.

• Taxikář_3: Po dokončení trasy řidič jede na polohu centroidu, který se průběžně počítá z polohy všech zákazníků, kteří dosud volali operátorovi společnosti.

• Taxikář_4: Po dokončení trasy řidič jede na nejbližší parkoviště, které je umístěné na optimálním místě na základě hustoty silniční komunikace.

• Pasažér: Po objevení si zavolá nejbližší volný taxík a čeká, než přijede. Pokud žádný taxík není volný, čeká, dokud se některý z vozů taxi neuvolní. Jakmile je však doba čekání delší, než ta nastavená parametrem, potenciální pasažér ze systému odchází.

Metody modelu

• setup: Základní metoda pro nastavení celého modelu. Tato metoda načte mapu z externího souboru, vytvoří šedé "chodníčky" okolo silnic určené pro "spawnování" zákazníků a umístí do mapy přednastavený počet taxíků

• go: Druhá základní metoda zaštiťuje základní chod simulace - tedy pohyb taxíků, volání taxíků zákazníky a vytváření nových zákazníků. Také slouží jako počítadlo "ticků" a tím umožňuje sledovat dobu, po kterou zákazníci čekají na svůj taxík.

• run-spawner: Tato metoda zajišťuje vytváření nových zákazníků, to lze ovlvnit pomocí parametrů pro maximální počet zákazníků, který může být v modelu v jednu chvíli a rychlost, s jakou se noví zákazníci objevují.

• find-path: Stěžejní metoda simulace. Využívá A* algoritmu pro hledání otimální cesty k cíli taxíku. Tato metoda vytvoří seznam polí, přes která se taxík dostane k cíli co nejrychleji a pouze po silnicích vyobrazených v mapě.

• spawn-taxis: Metoda určená pro vytvoření taxíků, je odpovědná za vytvoření taxíků s odpovídajícím tvarem, barvou a velikostí a také s jednou ze čtyř strategií na základě vstupních parametrů modelu.

• strategize: Tato metoda po uvolnění taxíku nebo vysazení zákazníka zajistí, aby se taxík opět začal chovat tak, jak mu určuje jemu přidělená strategie.

• move: Další z páteřních metod modelu, zajišťuje pohyb taxíků v modelu podle jejich určené trasy. Každý taxík se posouvá patch po patchi směrem k cíli, což dovoluje postupně měřit ujetou vzdálenost a čas, který trvala cesta k zákazníkovi. Cestu tvoří v rámci každého agentu (taxíku) seznam patchů, po kterých se bude taxík posouvat k cíli, navštívené patche jsou tak mazány ze seznamu, dokud taxík nedorazí až na konec cesty. Pokud taxík dojede na konec své cesty, tato metoda poté odkáže podle situace na další metodu a dojde tak k naložení/vyložení zákazníka a/nebo k návratu ke strategii taxíku.

• roam: Tato metoda určuje chování taxíků se strategií číslo 2 - tyto taxíky se (pokud nemají svého zákazníka) náhodně "potulují" po mapě.

• go-com: Metoda pro taxíky se strategií číslo 3 - tyto taxíky zjistí "těžiště" ze všech míst, odkud se předtím ozval nějaký zákazník a navede taxík na nejbližší místo k tomuto těžišti ležící na silnici nebo jiném místě, kam se může taxík dostat. Toto těžiště se průběžně posouvá s každým dalším zákazníkem a v průběhu simulace se mění. (Taxík však v průběhu jízdy již svoji destinaci nemění, nové místo platí pouze pro nové hledání cíle)

• park: Tato metoda slouží k určení chování taxíků se čtvrtou strategií - tyto taxíky metoda nasměřuje k nejblížšímu z míst, která byla předem odhadnuta jako optimální místo pro parkování prázdných vozů taxislužby.

• loadup: Tato metoda slouží k "naložení" zákaníka ve chvíli, kdy k němu dorazí jemu určený volný taxík. V ten okamžik se změní cíl taxíku na místo, kam se požaduje dostat zákazník a na toto místo bude nalezena nejkratší cesta. Taxík se změní na obsazený a změní svoji barvu na oranžovou.

• unload: Toto je přesní opak "nakládací" metody - po dosažení destinace, kterou si vyžádal zákazník dojde k vystoupení zákazníka. Daný taxík se změní na volný taxík opět žluté barvy a následně pojede dál nebo zůstane na místě, v závislosti na jeho strategii.

• call-taxi: Jedná se o metodu, která slouží zákazníkům k volaní taxi. Tato metoda vybere z volných taxíků ten nejbližší k zákazníkovi, a pokud takový taxík existuje, dojde přidělení taxíku k zákazníkovi (a naopak) Přidělený vůz taxislužby poté najde nejkratší trasu a vydá na adresu zákazníka.

• create-sidewalks: Pomocná metoda, která po načtení mapy vytvoří po okraji silnic šedé "chodníčky," které slouží k vytváření a nakládání zákazníků. To zajišťuje, aby se zákazníci objevili vždy na okraji, a nikdy ne uprostřed komunikace či na jiném nepříliš optimálním místě.

Parametry modelu

Model obsahuje také několik vstupních parametrů, které lze upravit skrze uživatelské rozhraní a ovlivnit tak chování a výsledky celého modelu.

• Mapa: Tento parametr nabízí výběr z několika map k importování do modelu a také náhodné generování mapy. Tato metoda však zatím není v modelu implementována.

• Počet řidičů taxi dané strategie: Jedná se o čtyři různé parametry, které určují počet taxíků s různými strategiemi, které se v modelu objeví

• Cena paliva: Určuje cenu paliva (a dalších možných započtených nákladů) v korunách na ujetý kilometr. Jeden patch (buňka, pixel) v prostředí simulace odpovídá přibližně šesti metrům délky ve skutečnosti a sledování ujeté vzdálenosti a vynaložených nákladů pomocí nástrojů v modelu je tomu přizpůsobeno.

• Cena za taxi: Parametr "taxi-cost" určuje cenu, kterou zákazník zaplatí za kilometr jízdy v taxíku. Měřítko mapy zůstává stejné a tomu odpovídají také měřené hodnoty v průběhu samotné simulace.

• Počet pasažérů: Určuje počet čekajících zákazníků, kteří se v jeden okamžik mohou objevit v modelu. Tento parametr lze upravit podle sledovaných výsledků a počtu dostupných taxíků pro co nejhladší průběh simulace. Tento parametr lze také volně upravit i během spuštěné simulace.

• Generování pasažérů: Parametr úzce spjatý s předchozím parametrem, dovoluje určovat rychlost, s jakou se objevují noví pasažéři. Konkrétně tento parametr určuje šanci, že se právě v následujícím kroku simulace objeví nový zákazník. Tektéž i tento parametr lze upravovat za chodu simulace.

• Doba čekání na taxi: Určuje maximální možnou dobu, kterou jsou zákazníci ochotni čekat na příjezd taxíku. Pokud je lhůta překročena, zákazník zmizí. Pokud v tu chvíli již k zákazníkovi přijížděl taxík, daný taxík bude uvolněn a navrátí se zpět ke své strategii.

Průběh simulace

Ano, simulace proběhla.

Shrnutí a výsledky

Tak tady to hezky shrnu a ukážu výsledky.

Obrázky modelu

File:Jmeno 1

popisek

Kód

Zdrojový kód simulace: File:Zikl00.nlogo

Mapa pro simulaci: File:Zikl00 mapa netlogo.zip -> mapu vložte do stejného adresáře, jako soubor .nlogo, jinak nebude simulace fungovat.

Zdroje

• Příklad jednoduchého vyhledávání v NetLogu [1]

• A* vyhledávací algoritmus [2]

• NetLogo 6.1.0 User Manual [3]

• Kontrastní mapy bez popisků [4]