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í vozy 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: Ačkoli byla pro tento model vytvořena jedna mapa, model sám umožňuje výběr z více map k importování do modelu v případě tvorby map dalších. Poslední položka značí náhodné generování mapy. Metoda pro generování mapy však zatím není v modelu implementována a představuje tak možné rozšíření do budoucna.

• 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

Veškeré popsané funkce v modelu fungují bez problémů tak, jak mají. Jediným zádrhelem je samotný A* algoritmus pro hledání optimální cesty taxíků k cíli. Samotný nástroj není v rámci NetLoga příliš často využíván, ale pokud je využíván pro potřeby jediného agenta, funguje dobře. Mapa vytvořená pro tento model je poměrně veliká a se složitostí mapy roste i výpočetní složitost simulace. Při vyšším množství taxíků potom hledání cesty k cíli trvá určitou dobu. Nejobtížnější je úvodní spuštění modelu, kdy se hledají cesty pro většinu dostupných taxíků najednou. V takovém případě model potřebuje pár minut na to, aby se pořádně rozběhl. K chybám při běhu však nedochází, simulaci brzdí pouze vázanost NetLoga na jediné jádro procesoru.

Shrnutí a výsledky

Model simulace v současném stavu považuji za solidní, v ohledu výpočetní náročnosti je však na hranici možností nástroje NetLogo a/nebo mého osobního počítače. Model by bylo možné zjednodušit výrazně menší mapou, která by mohla snížit výpočetní náročnost. Příliš jednoduchá mapa by ale nemusela mít dostatečnou členitost a různorodost k tomu, aby různé strategie přinášely různé výsledky. Naštěstí lze dostat zajímavé výsledky i s nižším množstvím taxíků, se kterým nemá model takové potíže. Podařilo se tak získat i některé zajímavé poznatky co se týče podobností a rozdílů jednotlivých strategií.

• Závislost na ceně paliva: Poměr ceny paliva k výši tržeb tvoří zásadní prvek, který umožňuje jednotlivým strategiím se mezi sebou diferenciovat. Pokud je cena za ježdění bez naloženého zákazníka nízká, výsledky jednotlivých strategií jsou si zpravidla velice podobné. Naopak pokud jsou podmínky ve vstupních parametrech tvrdší (dražší palivo a menší cena za jízdu taxíkem), v modelu začne být výrazně úspěšnější strategie číslo 4 (parkování na předem vybraných místech).

• Závislost na celkovém množství vozů: Množství vozů v modelu ovlivňuje výsledky simulace velmi podobně jako závislost na ceně paliva. Pokud se v modelu nachází větší množství vozů, dojde v modelu k více rovnoměrnému rozprostření vozů taxislužby v mapě, čímž se do jisté míry redukují rozdíly mezi strategiemi. Výjimku v případě vyššího množství vozů tvoří rozdíl mezi čistým ziskem vozů se strategiemi 1 a 2 - pokud je rozložení vozů v mapě víceméně náhodné, vozy které zůstanou stát na místě budou úspornější nežli vozy "bezcílně bloudící".

Naopak pokud je množství vozů nižší, mohou se ukázat některé strategie výhodnější. V tomto případě opět vystupuje na povrch strategie číslo 4 - vozy zaparkované v místech, kde je vyšší šance na objevení se zákazníka jsou v případě menšího množství vozů v modelu úspěšnější, zejména v poměru čistého zisku a poměru času stráveného za jízdy s prázdným a obsazeným vozem.

• Závislost na poměru vozů jednotlivých strategií: V rámci této závislosti platí patrně stejná pravidla jako v předchozím bodě, simulace však odhaluje jeden efekt navíc. S narůstajícím počtem vozů (nebo případně s klesajícím množstvím zákazníků) v modelu klesá příjem i čistý zisk taxíků uplatňujících strategii číslo 3. Tyto taxíky se všechny zdržují okolo středu mapy města a v centru mapy je potom pro tuto skupinu příliš vysoká "konkurence".

• Vzájemné ovlivňování dvojic strategií: Ze simulací vyplývá, že některé modely se mohou navzájem doplňovat a snížit tak čas, po který musí průměrný zákazník čekat, než se dočká svého vozu taxi. Jiné naopak mohou plnit v zásadě stejnou roli a jejich vzájemný efekt pak může být pouze v rámci zvýšení množství a hustoty vozů bez přímého vlivu, který by bylo možné pomocí modelu identifikovat.

Strategie číslo 4 se ve většině provedených simulací jevila jako optimální. Vozy s touto strategií pak mohou doplnit vozy se strategiemi 1 a 2, které se budou obvykle nacházet na náhodně vybraných místech a mohou tak pokrýt "slepá" místa, která se nenachází poblíž míst, kde čekají taxíky se strategií číslo 4. Zda bude v takovém případě lepší strategie stání na místě nebo kroužení kolem pak bude záviset na výši nákladů na palivo.

Předem vybraná místa pro strategii číslo 4 by bylo také možné upravit z dosavadního stavu, ve kterém jsou vybrána optimální místa. Pokud by došlo k redukci optimálních míst a zůstala by pouze optimální místa poblíž okrajů mapy, mohla by se tato strategie velmi dobře doplňovat se strategií číslo 3. Taxíky s touto strategií se zdržují poblíž těžiště všech míst, odkud v předchozí době volali zákazníci. To zpravidla odpovídá středu mapy města - množství vozů by tak bylo relativně pravidelně rozložené následkem cílené strategie a nikoliv náhody.

Obrázky modelu

Obrázek 1 - Celý interface modelu

• 

  Obrázek 2 - Obvyklá situace, při které viditelně vítězí strategie 4

• 

  Obrázek 3 - Pokud se počet zákazníků sníží, ze zisku se rychle stávají ztráty

Kód

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

Mapa pro simulaci: File:Zikl00 mapa netlogo.zip -> rozbalte ZIP a soubor "mapa.asc" vložte do stejného adresáře, jako soubor "zikl00.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]