Fakulta elektrotechnická. Agentní model přepravní kontroly ve

ˇ ´ vysoke ´ uc ˇen´ı technicke ´ v Praze Cesk e ´ Fakulta elektrotechnicka

´ PRACE ´ DIPLOMOVA Agentn´ı model pˇ repravn´ı kontroly ve veˇ rejn´ e dopravˇ e

Praha, 2012

Autor: Bc. Jan S´ alus

Podˇ ekov´ an´ı Na tomto m´ıstˇe bych chtˇel podˇekovat vˇsem, kteˇr´ı mi umoˇznili dokonˇcen´ı této práce. Zvláˇstˇe vedouc´ımu práce Ing. Michalu Jakobovi Ph.D. za podnˇetné rady a v´ ybornou spolupráci.

i

ii

Abstrakt Tato diplomová práce je zamˇeˇrena na pouˇzit´ı netradiˇcn´ı simulaˇcn´ı techniky, kterou je agentn´ı modelován´ı. Navazuje na v´ yvoj softwarov´ ych prostˇredk˚ u pro simulaci dopravn´ıch systém˚ u AgentPolis a dále rozˇsiˇruje modul FareEvasion, kter´ y simuluje systém veˇrejné dopravy. Je zde vyhodnocena sada ilustraˇcn´ıch simulac´ı provádˇen´ ych na veˇrejné dopravn´ı s´ıti Los Angeles. Testy jsou nejprve zamˇeˇreny na jednu linku a následnˇe sleduj´ı dynamiku v celé s´ıti, ovˇeˇruj´ı adaptaci pasaˇzéra na prob´ıhaj´ıc´ı kontroly. V práci je navrˇzen plánovac´ı algoritmus vyuˇz´ıvaj´ıc´ı cenovou funkci a zkuˇsenosti cestuj´ıc´ıho k hledán´ı v´ yhodné cesty prostˇredky veˇrejné dopravy, vˇcetnˇe zohlednˇen´ı faktor˚ u ovlivˇ nuj´ıc´ıch jejich rozhodnut´ı. Implementuje model cestuj´ıc´ıho jako adaptivn´ıho agenta interaguj´ıc´ıho s prostˇred´ım, coˇz je vyuˇzitelné pro eliminován´ı u ńiku zisk˚ u dopravn´ıch spoleˇcnost´ı.

iii

Abstract This diploma thesis is focused on using innovative simulation technique known as agent-based modeling. It follows the development of a platform and tools for agent-based transport systems simulation AgentPolis and extends FareEvasion module that simulates public transportation networks. There is a set of illustrative simulations evaluated out to the public transport network in the City of Los Angeles. Tests are first focused on one transportation line and then follow the dynamics across the entire network verify the passenger’s adaptation to the ongoing control. The work proposed planning algorithm using a cost function and the passenger experience convenient way to search for public transport, including consideration of factors influencing their decision. Implements the model as a passenger adaptive agent interacting with the environment, which is useful for eliminating the leakage of profits of transportation companies.

iv

v

vi

Obsah Seznam obr´ azk˚ u

xi

Seznam tabulek

xiii

´ 1 Uvod

1

2 Agentn´ı modelov´ an´ı

3

2.1

Co je agentn´ı modelován´ı . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

2.2

Srovnán´ı pˇr´ıstup˚ u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2.3

V´ yhody agentn´ıho modelován´ı . . . . . . . . . . . . . . . . . . . . . . . .

4

2.4

Pouˇzit´ı pˇr´ıstupu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.5

Shrnut´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

3 Souvisej´ıc´ı pr´ ace

7

3.1

Anal´ yza prostˇred´ı cestuj´ıc´ıch . . . . . . . . . . . . . . . . . . . . . . . . .

7

3.2

Modelován´ı rozhodován´ı cestuj´ıc´ıch . . . . . . . . . . . . . . . . . . . . .

8

3.3

Shrnut´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

4 Specifikace a formalizace probl´ emu 4.1

Reprezentace prostˇred´ı pasaˇzéra . . . . . . . . . . . . . . . . . . . . . . .

9 9

4.1.1

Stavy v prostˇred´ı pasaˇzéra . . . . . . . . . . . . . . . . . . . . . .

11

4.1.2

Akce v prostˇred´ı pasaˇzéra . . . . . . . . . . . . . . . . . . . . . .

11

4.1.3

Mnoˇzina akc´ı j´ızdy metrem . . . . . . . . . . . . . . . . . . . . . .

12

4.1.4

Mnoˇzina akc´ı pˇrechodu mezi stanicemi . . . . . . . . . . . . . . .

12

4.1.5

Mnoˇzina akc´ı vstup do stanice . . . . . . . . . . . . . . . . . . . .

13

4.1.6

Mnoˇzina akc´ı v´ ystup ze stanice . . . . . . . . . . . . . . . . . . .

13

4.2

Vlastnosti pasaˇzéra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

4.3

Plán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

vii

4.4

4.5

Model ocenˇen´ı cestovn´ıho plánu . . . . . . . . . . . . . . . . . . . . . . . ˇ 4.4.1 Casov´ a sloˇzka ceny . . . . . . . . . . . . . . . . . . . . . . . . . .

15

4.4.2

Ekonomická sloˇzka ceny . . . . . . . . . . . . . . . . . . . . . . .

16

4.4.3

Psychologická sloˇzka ceny . . . . . . . . . . . . . . . . . . . . . .

18

Shrnut´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

5 Uvaˇ zov´ an´ı pasaˇ z´ era 5.1

15

19

Plánován´ı trasy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

5.1.1

Metoda vˇetv´ı a mez´ı . . . . . . . . . . . . . . . . . . . . . . . . .

20

5.1.2

Popis plánován´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

5.1.3

Korektnost algoritmu . . . . . . . . . . . . . . . . . . . . . . . . . ´ Uplnost algoritmu . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

5.2

Uˇcen´ı se o pˇrepravn´ı kontrole . . . . . . . . . . . . . . . . . . . . . . . .

23

5.3

Shrnut´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

5.1.4

6 Implementace 6.1

6.2

25

Tˇr´ıdy pro model pasaˇzéra . . . . . . . . . . . . . . . . . . . . . . . . . .

25

6.1.1

Vytvoˇren´ı pasaˇzéra . . . . . . . . . . . . . . . . . . . . . . . . . .

25

6.1.2

Vlastnosti pasaˇzéra . . . . . . . . . . . . . . . . . . . . . . . . . .

26

6.1.3

27

6.1.4

Plán pasaˇzéra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ˇ Zivotn´ ı cyklus pasaˇzéra . . . . . . . . . . . . . . . . . . . . . . . .

6.1.5

Plánovaˇc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

6.1.6

Stav . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

6.1.7

Ukládán´ı informac´ı . . . . . . . . . . . . . . . . . . . . . . . . . .

29

Tˇr´ıdy pro model inspektora . . . . . . . . . . . . . . . . . . . . . . . . .

29

6.2.1

Vytvoˇren´ı inspektora . . . . . . . . . . . . . . . . . . . . . . . . . ˇ Zivotn´ ı cyklus inspektora . . . . . . . . . . . . . . . . . . . . . . .

29

Shrnut´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

6.2.2 6.3

7 Experimenty 7.1

7.2

23

27

29

33

Nastaven´ı pro experimenty . . . . . . . . . . . . . . . . . . . . . . . . . .

33

7.1.1

Konfigurace prostˇred´ı . . . . . . . . . . . . . . . . . . . . . . . . .

33

7.1.2

Nastaven´ı scénáˇre . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

7.1.3

Metriky k vyhodnocen´ı . . . . . . . . . . . . . . . . . . . . . . . .

37

7.1.4

Nastaven´ı simulace . . . . . . . . . . . . . . . . . . . . . . . . . .

38

Experimenty s jednotlivci

. . . . . . . . . . . . . . . . . . . . . . . . . . viii

39

7.2.1

Chybné poˇca´teˇcn´ı nastaven´ı v prostˇred´ı bez inspektora . . . . . .

39

7.2.2

Chybné poˇca´teˇcn´ı nastaven´ı v prostˇred´ı s inspektorem . . . . . . .

41

Experimenty s populac´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

7.3.1

Experimenty na jedné lince . . . . . . . . . . . . . . . . . . . . .

43 46

7.4

Experimenty na celé s´ıti . . . . . . . . . . . . . . . . . . . . . . . V´ ypoˇcetn´ı a pamˇet’ové nároky . . . . . . . . . . . . . . . . . . . . . . . .

7.5

Shrnut´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

7.3

7.3.2

49

8 Z´ avˇ er

51

Literatura

54

A N´ azev pˇ r´ılohy

I

B Obsah pˇ riloˇ zen´ eho CD

VII

ix

x

Seznam obr´ azk˚ u 4.1

Logaritmická závislost na ekonomickém stavu pasaˇzéra . . . . . . . . . .

17

6.1

Závislosti mezi platformami . . . . . . . . . . . . . . . . . . . . . . . . .

26

6.2

Stavov´ y diagram ˇzivotn´ıho cyklu pasaˇzéra . . . . . . . . . . . . . . . . .

27

6.3

Stavov´ y diagram provádˇen´ı plánu . . . . . . . . . . . . . . . . . . . . . .

28

6.4

Diagram deterministického ˇzivotn´ıho cyklu inspektora . . . . . . . . . . .

30

6.5

Diagram nedeterministického ˇzivotn´ıho cyklu inspektora . . . . . . . . .

31

6.6

Zobrazen´ı grafického prostˇred´ı simulaˇcn´ı platformy

. . . . . . . . . . . .

32

7.1

Schéma dopravn´ı s´ıtˇe . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

7.2

V´ ysledek experimentu pro ekonomicky zaloˇzeného pasaˇzéra . . . . . . . .

40

7.3

V´ ysledek experimentu pro ˇcasovˇe zaloˇzeného pasaˇzéra . . . . . . . . . . .

40

7.4

V´ ysledek experimentu pro psychologicky zaloˇzeného pasaˇzéra . . . . . . .

41

7.5

V´ ysledek v prostˇred´ı s inspektorem na vstupn´ı stanici . . . . . . . . . . .

42

7.6

V´ yvoj poˇctu zakoupen´ ych l´ıstk˚ u v prostˇred´ı jedné linky . . . . . . . . . .

44

7.7

Ustálené stavy r˚ uzn´ ych nastaven´ıch situac´ı (jedna linka) . . . . . . . . .

45

7.8

Histogramy poˇctu pasaˇzér˚ u a jejich zmˇen plán˚ u (jedna linka) . . . . . . .

45

Znázornˇen´ı situace na pˇrestupn´ı stanici . . . . . . . . . . . . . . . . . . . 7.10 Ustálené stavy r˚ uzn´ ych nastaven´ıch situac´ı (celá s´ıt’) . . . . . . . . . . . . 7.11 Histogramy poˇctu pasaˇzér˚ u a jejich zmˇen plán˚ u (celá s´ıt’) . . . . . . . . .

47

A.1 V´ yvoj poˇctu zakoupen´ ych l´ıstk˚ u v prostˇred´ı celé s´ıtˇe . . . . . . . . . . . .

IV

7.9

xi

48 48

xii

Seznam tabulek 7.1

Tabulka fixn´ıch parametr˚ u prostˇred´ı . . . . . . . . . . . . . . . . . . . . .

34

7.2

Tabulka fixn´ıch parametr˚ u normalizaˇcn´ıch konstant pasaˇzér˚ u . . . . . . .

37

7.3

Tabulka nastaven´ı experiment˚ u v prostˇred´ı s jednotlivci . . . . . . . . . .

39

7.4

Tabulka nastaven´ı experiment˚ u jedné linky . . . . . . . . . . . . . . . . .

43

7.5

Tabulka nastaven´ı experiment˚ u celé s´ıtˇe . . . . . . . . . . . . . . . . . . .

46

7.6

Poˇcet proj´ıˇzdˇej´ıc´ıch pasaˇzér˚ u stanicemi pˇred um´ıstˇen´ım inspektora . . . .

47

7.7

Poˇcet proj´ıˇzdˇej´ıc´ıch pasaˇzér˚ u stanicemi po um´ıstˇen´ım inspektora . . . . .

47

7.8

V´ ypoˇcetn´ı nároky simulace . . . . . . . . . . . . . . . . . . . . . . . . . .

49

A.1 Pˇr´ıjmy pr˚ umˇerné tˇr´ıˇclenné domácnosti v LA . . . . . . . . . . . . . . . .

I

A.2 Zmˇeny plán˚ u v pˇredv´ıdatelném prostˇred´ı, 0%, jedna linka . . . . . . . . .

II

A.3 Zmˇeny plán˚ u v nepˇredv´ıdatelném prostˇred´ı, 0%, jedna linka . . . . . . .

II

A.4 Zmˇeny plán˚ u v pˇredv´ıdatelném prostˇred´ı, 1.1%, jedna linka . . . . . . . .

II

A.5 Zmˇeny plán˚ u v nepˇredv´ıdatelném prostˇred´ı, 1.1%, jedna linka . . . . . A.6 Zmˇeny plán˚ u v pˇredv´ıdatelném prostˇred´ı, 0%, celá s´ıt’ . . . . . . . . . . A.7 Zmˇeny plán˚ u v nepˇredv´ıdatelném prostˇred´ı, 0%, celá s´ıt’ . . . . . . . . . A.8 Zmˇeny plán˚ u v pˇredv´ıdatelném prostˇred´ı, 0.7%, celá s´ıt’ . . . . . . . . .

.

III

.

IV

.

V

.

V

A.9 Zmˇeny plán˚ u v nepˇredv´ıdatelném prostˇred´ı, 0.7%, celá s´ıt’ . . . . . . . . .

V

xiii

xiv

Kapitola 1 ´ Uvod Tato diplomová práce navazuje na v´ yzkum skupiny p˚ usob´ıc´ı na katedˇre poˇc´ıtaˇc˚ u elekˇ eho vysokého uˇcen´ı technického v Praze pod veden´ım Ing. Mitrotechnické fakulty Cesk´ chala Jakoba, Ph.D.. V´ yzkum této skupiny je zamˇeˇren na v´ yvoj softwarov´ ych prostˇredk˚ u pro simulaci dopravn´ıch systém˚ u nesouc´ı název AgentPolis1 (Jakob, M., Moler, Z., Komenda, A., Yin, Z., Jiang, A., X., Johnson, M., P., Pechoucek, M. a Tambe, M., 2012). Tato práce rozˇsiˇruje modul simuluj´ıc´ı systém veˇrejné dopravy FareEvasion, kter´ y je nadstavbou projektu AgentPolis. Systém dopravn´ı pˇrepravy je pro jejich spoleˇcnosti velmi nákladn´ y. Nav´ıc jako kaˇzd´ y podobn´ y systém trp´ı i tento neˇza´douc´ım jevem, kter´ ym je u ńik zisk˚ u. Tento jev nelze u ´plnˇe odstranit nicménˇe dopravn´ı spoleˇcnosti se ho snaˇz´ı eliminovat. Zp˚ usob eliminace u ńiku zisk˚ u vˇzdy závis´ı na typu prostˇred´ı, ale vˇzdy je potˇreba m´ıt o nˇem dostatek informac´ı, ze kter´ ych vypl´ yvá jeho chován´ı. S reáln´ ym problémem pˇrepravn´ı kontroly je velmi sloˇzité pracovat, vyhodnocovat a vylepˇsovat. Zjednoduˇsen´ı pˇrináˇs´ı simulaˇcn´ı technika - modelován´ı, které nav´ıc pomáhá zlepˇsit pochopen´ı chován´ı systému. Pomoc´ı techniky modelován´ı je moˇzné vytvoˇrit model systému, na kterém lze provádˇet simulace a názornˇe ukázat i skryté chován´ı systému, jeho reakce na vloˇzená data (napˇr. kontroluj´ıc´ı inspektoˇri) nebo m˚ uˇze poskytovat informace, které pˇrispˇej´ı k eliminován´ı u ńiku zisku dopravn´ı spoleˇcnosti napˇr. slabá m´ısta kontroly → rozmist’ován´ı inspektor˚ u .... Pouˇzit´ı tradiˇcn´ıch pˇr´ıstup˚ u (dynamické systémy, diskrétn´ı události) na problém pˇrepravn´ı kontroly je velmi obt´ıˇzné. S v´ yvojem technologie a nár˚ ustem v´ ypoˇcetn´ıho v´ ykonu lze vyuˇz´ıt netradiˇcn´ı simulaˇcn´ı techniku - agentn´ı modelován´ı. Pˇr´ıstup agentn´ıho 1

http://agents.fel.cvut.cz/projects/agentpolis/

1

´ KAPITOLA 1. UVOD

2

modelován´ı je odliˇsn´ y, nepopisuje jiˇz systém jako celek, ale pouze jeho základn´ı jednotku tj. agenta, coˇz b´ yvá ˇcasto jednoduché. Principem techniky je mnoho agent˚ u, kteˇr´ı vzájemnou interakc´ı vyv´ıjej´ı chován´ı odpov´ıdaj´ıc´ı modelovanému systému. V systému pˇrepravn´ı kontroly vystupuje mnoho jednotek, kter´ ymi jsou cestuj´ıc´ı a inspektoˇri. Jednotliv´ı cestuj´ıc´ı interaguj´ı s prostˇred´ım i s inspektory, coˇz pˇr´ımo souvis´ı s pˇr´ıstupem agentn´ıho modelován´ı a bylo tedy v´ yhodné vyuˇzit´ı právˇe této techniky. Pomoc´ı simulaˇcn´ı techniky agentn´ıho modelován´ı byl vytvoˇren model systému pˇrepravn´ı kontroly. Kde popisovan´ y pasaˇzér, jako autonomn´ı agent, samovolnˇe uvaˇzuje tedy vol´ı zp˚ usob cestován´ı v˚ uˇci aktuáln´ımu prostˇred´ı, na které je schopen se pr˚ ubˇeˇznˇe adaptovat tj. uˇcit se ho. C´ılem bylo pochopit chován´ı a adaptaci pasaˇzér˚ u pˇri mˇen´ıc´ıch se podm´ınkách v prostˇred´ı. Pouˇzitá simulaˇcn´ı technika agentn´ıho modelován´ı je popisovaná v druhé kapitole této práce, spoleˇcnˇe s jej´ımi v´ yhodami, pouˇzit´ım a porovnán´ım s ostatn´ımi technikami modelován´ı. Pouˇzit´ı této metody je velmi v´ yhodné aplikovat na systémy, ve kter´ ych jedná v´ıce nezávisl´ ych jednotek jako napˇr. lidé v dopravn´ım systému. Tˇret´ı kapitola práce struˇcnˇe popisuje souvisej´ıc´ı ˇclánky, které byly pouˇzity pro z´ıskán´ı základn´ıho pohledu do veˇrejn´ ych dopravn´ıch systém˚ u. Dalˇs´ı kapitola práce ”Specializace a formalizace problému” popisuje prostˇred´ı dopravn´ıho systému, které pasaˇzér vn´ımá, a dále popisuje model pasaˇzéra. Model obsahuje vlastnosti pasaˇzéra, prostˇred´ı a cenovou funkci, kterou urˇcuje kolik ho daná cesta bude stát. Vlastnosti agenta a jeho chován´ı je definované pomoc´ı sady provediteln´ ych akc´ı a následnˇe jsou plánem popsána vˇsechna jeho rozhodnut´ı. Kapitola ”Uvaˇzován´ı pasaˇzéra”se jiˇz zab´ yvá, jak´ ym zp˚ usobem se pasaˇzér rozhoduje pro nejv´ yhodnˇejˇs´ı plán a dále pokraˇcuje popisem zp˚ usobu jeho adaptace na prostˇred´ı. Pro v´ ybˇer nejv´ yhodnˇejˇs´ıho plánu se vyuˇz´ıvá metody ”Vˇetv´ı a mez´ı”. Praktická ˇcást práce zaˇc´ıná popisem implementace vytvoˇreného modelu, rozhodován´ım a adaptac´ı z pˇredchoz´ıch dvou kapitol. Bylo ovˇeˇreno, ˇze zvolen´ y algoritmus je korektn´ı, a protoˇze se jedná o koneˇcné prostˇred´ı a algoritmus nekonˇc´ı s prvn´ım nalezen´ ym ˇreˇsen´ım, ale hledá dalˇs´ı moˇznosti, je také u ´pln´ y. V posledn´ı kapitole ”Exterimenty” se ovˇeˇruje implementace a jsou vyhodnoceny zaj´ımavé metriky, které ukazuj´ı chován´ı modelovaného systému v r˚ uzn´ ych stavech prostˇred´ı. Experimenty ovˇeˇruj´ı, ˇze implementace systému dopravn´ı spoleˇcnosti se chová intuitivn´ım zp˚ usobem. Dynamika celého systému vˇzdy konverguje do vyváˇzeného stavu.

Kapitola 2 Agentn´ı modelov´ an´ı Pˇrepravn´ı kontrola se ˇrad´ı mezi známé systémy reálného svˇeta. Obecnˇe je s tˇemito systémy velmi obt´ıˇzné nˇekdy dokonce nemoˇzné dále pracovat, vyhodnocovat je nebo s nimi experimentovat. Pro snaˇzˇs´ı práci s problémy reálného svˇeta se vyuˇz´ıvá simulaˇcn´ı technika zvaná modelován´ı. Modelován´ı zahrnuje proces pˇrevádˇen´ı systému z reálného svˇeta do svˇeta simulac´ı v podobˇe modelu, proces rozboru a optimalizace, pˇrevádˇen´ı ˇreˇsen´ı zpˇet do reálného systému. Existuj´ı tˇri hlavn´ı pˇr´ıstupy v simulaˇcn´ım modelován´ı - dynamické systémy, diskrétn´ı události a agentn´ı modelován´ı1 . Narozd´ıl od prvn´ıch dvou tradiˇcn´ıch pˇr´ıstup˚ u je agentn´ı modelován´ı relativnˇe nová technika nalézaj´ıc´ı ˇsiroké uplatnˇen´ı.

2.1

Co je agentn´ı modelov´ an´ı

Agentn´ı modelován´ı uvaˇzuje systém sloˇzen´ y z mnoha základn´ıch jednotek a zab´ yvá se, oproti jin´ ym pˇr´ıstup˚ um, pouze popsán´ım této jednotky, která se naz´ yvá agent. V prostˇred´ı y modelu se zároveˇ n pohybuje vˇetˇs´ı mnoˇzstv´ı agent˚ u, kteˇr´ı mezi sebou interaguj´ı2 . Kaˇzd´ agent um´ı samostatnˇe posoudit svoji situaci vzhledem k prostˇred´ı, ve kterém se pohybuje, a na základˇe mnoˇziny základn´ıch pravidel sestav´ı odpov´ıdaj´ıc´ı rozhodnut´ı. Jednotka, nesouc´ı název agent, by mˇela b´ yt autonomn´ı (jedná v prostˇred´ı bez pˇr´ımého vlivu ostatn´ıch, ˇr´ıd´ı své akce a vnitˇrn´ı stav), proaktivn´ı (schopnost agenta uj´ımat se iniciativy, ovlivˇ novat prostˇred´ı k dosaˇzen´ı vlastn´ıch c´ıl˚ u), reaktivn´ı (reaguje na zmˇeny v prostˇred´ı), vn´ımaj´ıc´ı 1 2

Dynamic Systems, Discrete Events, Agen-based modeling Jednoduˇse ˇreˇceno, je agentn´ı modelovac´ı systém tvoˇren´ y agenty a vztahy mezi nimi.

3

´ Í KAPITOLA 2. AGENTNÍ MODELOVAN

4

okoln´ı prostˇred´ı, schopnost uˇcen´ı, sociáln´ı vlastnosti (interaguje s ostatn´ımi agenty, kooperac´ı, komunikac´ı, koordinac´ı ˇci konkurenc´ı) atd. (Borshchev, A. a Filippov, A., 2004).

2.2

Srovn´ an´ı pˇ r´ıstup˚ u

Podstatn´ y rozd´ıl mezi pˇr´ıstupy je tvoˇren popisem globáln´ıho chován´ı neboli dynamiky systému. V modelech pˇr´ıstupu ”dynamick´ ych systém˚ u” a ”diskrétn´ıch událost´ı” existuje objekt, ve kterém je toto chován´ı definováno. V ”agentn´ım” pˇr´ıstupu nen´ı ˇza´dn´ y takov´ y objekt, kter´ y by ho sám definoval, a definuje se pouze lokáln´ı chován´ı tj. chován´ı jednotlivce. Globáln´ı chován´ı vyplyne z jednán´ı mnoha (des´ıtek, stovek, tis´ıc˚ u, milión˚ u) jednotlivc˚ u ˇzij´ıc´ıch ve stejném prostˇred´ı, komunikuj´ıc´ıch mezi sebou a interaguj´ıc´ıch s prostˇred´ım3 (Borshchev, A. a Filippov, A., 2004).

2.3

V´ yhody agentn´ıho modelov´ an´ı

V´ yhody, které agentn´ı modelován´ı poskytuje, lze shrnout v následuj´ıc´ım seznamu (Bonabeau, E., 2002): • Agentn´ı modelován´ı pokr´ yvá ˇsirokou ˇskálu problém˚ u - je flexibiln´ı. • Dokonce i jednoduch´ y agentn´ı model m˚ uˇze projevovat sloˇzité (komplexn´ı) vzory chován´ı4 , a poskytovat hodnotnou informaci o dynamice reálného svˇeta, kterou systém napodobuje. • Pouˇzitá technika 5 je jednoduˇse pouˇzitelná a teoreticky pochopitelná a proto z´ıskala znaˇcnou popularitu. • I prostá pravidla jednotlivce mohou vést k ucelenému chován´ı skupiny. • S agentn´ım modelován´ım lze vytvoˇrit model, kter´ y se bude jevit jako realistiˇctˇejˇs´ı. 3

Proto se agentn´ı modelov´ an´ı také naz´ yv´ a botton-up modelován´ı. Emergence phenomena 5 Technika modelov´ an´ı nejmenˇs´ı ˇc´ asti systému, která je ˇcasto jednoduchá. 4

ˇ Í PR ˇ ÍSTUPU 2.4. POUZIT

2.4

5

Pouˇ zit´ı pˇ r´ıstupu

Moˇznost aplikace agentn´ıho modelován´ı je ˇsiroká. Obecnˇe se dá pouˇz´ıt v problémech, kde vystupuje v´ıce samostatn´ ych jednotek, na kter´ ych lze ukázat kolektivn´ı chován´ı tj. na sociáln´ıch, politick´ ych a ekonomick´ ych oborech. Pouˇzit´ı (Bonabeau, E., 2002) napˇr. u tok˚ u (evakuace, doprava, . . . ), trhu (burza, strategické simulace, . . . ), organizace (provozn´ı rizika, organizaˇcn´ı design) a . . . .

2.5

Shrnut´ı

Z v´ yˇse zm´ınˇeného lze soudit, ˇze agentn´ı pˇr´ıstup se skuteˇcnˇe hod´ı na problémy, v nichˇz jsou modelované jednotky lidé. Systém pˇrepravn´ı kontroly je pˇr´ımo tento druh problému. Autonomn´ı agenti jsou tvoˇreni podle pasaˇzér˚ u/inspektor˚ u, kteˇr´ı dennˇe provádˇej´ı urˇcitou cestu/kontrolu. Pasaˇzér popisovan´ y v kapitole 4 a jeho rozhodován´ı v kapitole 5 má povˇedom´ı o prostˇred´ı, reaguje na zmˇeny v nˇem prob´ıhaj´ıc´ı a konkurenˇcnˇe interaguje s inspektorem v podobˇe pˇrepravn´ıch kontrol.

6

´ Í KAPITOLA 2. AGENTNÍ MODELOVAN

Kapitola 3 Souvisej´ıc´ı pr´ ace Pˇrepravn´ı kontrolou se zab´ yvaj´ı jistˇe vˇsechny dopravn´ı spoleˇcnosti, které maj´ı za c´ıl omezit u ńik zisk˚ u v systému. Pro vytvoˇren´ı odpov´ıdaj´ıc´ı simulace prostˇred´ı pˇrepravn´ı kontroly bylo potˇreba z´ıskat informace o problému, ˇcehoˇz bylo dosaˇzeno prostudován´ım nˇekolika prac´ı zab´ yvaj´ıc´ıch se danou problematikou. Tato ˇcást obsahuje struˇcné reˇserˇse souvisej´ıc´ıch v´ yzkum˚ u. Souvisej´ıc´ı práce, které se zab´ yvaj´ı celou oblast´ı u ńik˚ u zisk˚ u v pˇrepravn´ım systému, se mohou rozdˇelit do nˇekolika skupin. Prvn´ı skupinu tvoˇr´ı práce, které se zab´ yvaj´ı anal´ yzou problému a na základˇe poznatk˚ u uˇcin´ı opatˇren´ı, druhou jsou ˇclánky zab´ yvaj´ıc´ı se jednoduch´ ym návrhem rozhodován´ı pasaˇzéra.

3.1

Anal´ yza prostˇ red´ı cestuj´ıc´ıch

V práci (Leung, L., F., 2003), která spadá do prvn´ı skupiny, se autor zab´ yvá pˇr´ıˇcinami a váˇznost´ı u ńiku zisku v Hong Kongském dopravn´ım systému. Autor popisuje problémy odbavovac´ıch mechanism˚ u a to jak v uzavˇreném, tak otevˇrené systému, dále pomoc´ı sestaven´ ych dotazn´ık˚ u z´ıská anal´ yzu prostˇred´ı (kdo a proˇc poruˇsuje) a shrnuje r˚ uzné typy metod u ńik˚ u zisku (jak´ ym zp˚ usobem). ˇ anek (Killias, M., Scheidegger, D. a Nordenson, P., 2009) analyzuje Cl´ prostˇred´ı skuteˇcn´ ym experimentem v pˇr´ımˇestské oblasti a to pˇridán´ım k náhodn´ ym kontrolám i kontrolu vˇsech cestuj´ıc´ıch v kritické dobˇe. V´ ysledky experimentu ukazuj´ı, ˇze jistota trestu funguje jako odstraˇsuj´ıc´ı prostˇredek. 7

´ KAPITOLA 3. SOUVISEJÍCÍ PRACE

8

3.2

Modelov´ an´ı rozhodov´ an´ı cestuj´ıc´ıch

Tato skupina sdruˇzuje ˇclánky, které se zab´ yvaj´ı vytvoˇren´ım základn´ıho rozhodován´ı ˇ anky (Boyd, C., Martini, Ch., Rickard, J. a Russell, A., 1989), cestuj´ıc´ıch. Cl´ (Kooreman, P., 1993) a (Piliavin, I., Thornton, C., Gartner, R. a Matsueda, R., L., 1986) popisuj´ı vytvoˇren´ı rozhodnut´ı mezi j´ızdou bez j´ızdenky a s n´ı. Ke kaˇzdé moˇznosti pˇridˇeluj´ı ohodnocen´ı ve formˇe uˇzitku. To znamená, ˇze urˇcuj´ı jak´ y uˇzitek jim pˇrinese jej´ı vykonán´ı. Shodnˇe ˇreˇs´ı volbu nezakoupen´ı j´ızdenky, kterou popisuj´ı jako ˇ anek (Piliavin, I., Thornmoˇznost obdrˇzen´ı pokuty (s urˇcitou pravdˇepodobnost´ı). Cl´ ton, C., Gartner, R. a Matsueda, R., L., 1986) poukazuje na racionáln´ı volbu, ˇze se vˇzdy zvol´ı v´ yhodnˇejˇs´ı varianta. V ˇclánku (Kooreman, P., 1993) vytváˇrej´ı sloˇzitˇejˇs´ı model. Do uˇzitku v podobˇe nelineárn´ı funkce pˇridali poˇcáteˇcn´ı kapitál a jeho hodnotu poˇc´ıtali jako rozd´ıl uˇzitku pˇred a po proveden´ı dané volby. V ˇclánku (Boyd, C., Martini, Ch., Rickard, J. a Russell, A., 1989) se po sestaven´ı modelu pasaˇzéra, pokouˇseli zjistit, pro jakou velikost rizika - tedy poˇctu revizor˚ u v dopravn´ım systému se zaruˇc´ı nejvyˇsˇs´ı zisk spoleˇcnosti. Udrˇzován´ım urˇcité velikosti rizika pˇri pˇrepravˇe m˚ uˇze zaruˇcit vˇetˇs´ı pˇr´ıjem (z pokut) spoleˇcnosti, neˇz kdyby bylo pˇr´ıliˇs inspektor˚ u nebo naopak málo.

3.3

Shrnut´ı

´ Unik zisk˚ u je nevyhnutelnˇe spojen se systémem veˇrejné dopravn´ı pˇrepravy a nem˚ uˇze b´ yt plnˇe eliminován. Existuje moˇznost jeho omezen´ı napˇr. náhodn´ ymi kontrolami a vysok´ ymi pokutami, coˇz má psychologick´ y zastraˇsovac´ı efekt. Uvedené ˇclánky stav´ı svoje modely na znalosti pravdˇepodobnosti kontroly. Maj´ı urˇcenou tuto pravdˇepodobnost z pohledu dopravn´ı spoleˇcnosti, která je dána poˇctem inspektor˚ u. Nezab´ yvaj´ı se t´ım, jak tuto pravdˇepodobnost vid´ı pasaˇzéˇri. ˇ ank˚ Cl´ u zab´ yvaj´ıc´ıch se u ńikem ze zisk˚ u v pˇrepravn´ı kontrole nen´ı mnoho. Informace z nich z´ıskané jsou ovˇsem dostaˇcuj´ıc´ı k vytvoˇren´ı sloˇzitˇejˇs´ıho1 modelu, jehoˇz návrhem tzn. popisem prostˇred´ı a rozhodován´ı pasaˇzér˚ u se tato práce zab´ yvá v následuj´ıc´ıch dvou kapitolách, které popisuj´ı nejenom moˇznost volby j´ızdenky, ale i obcházen´ı nebezpeˇcn´ ych stanic/´ usek˚ u a dokonce volby ˇcasu v´ yjezdu. 1

Obsahuje v´ıce moˇznost´ı voleb (j´ızdenka, trasa nebo ˇcas v´ yjezdu), které racionáln´ı pasaˇzér má.

Kapitola 4 Specifikace a formalizace probl´ emu Pouˇz´ıvané agentn´ı modelován´ı vyˇzaduje popsán´ı chován´ı agenta a prostˇred´ı, ve kterém se pohybuje. V této kapitole se popisuje prostˇred´ı, vlastnosti agenta a jeho chován´ı definované pomoc´ı sady provediteln´ ych akc´ı. Následnˇe jsou plánem popsaná vˇsechna jeho rozhodnut´ı a nakonec pasaˇzérova funkce ceny, která ohodnocuje zvolen´ y plán tj. sekvence jeho rozhodnut´ı.

4.1

Reprezentace prostˇ red´ı pasaˇ z´ era

Pasaˇzér se pohybuje v prostˇred´ı veˇrejné dopravn´ı s´ıtˇe s jedn´ım typem dopravn´ıho prostˇredku, kter´ ym je metro. Jedna linka metra se skládá ze stanic a odliˇsnˇe dlouh´ ych cest (spoj˚ u) mezi nimi. Dopravn´ı s´ıt’ se vˇetˇsinou skládá z v´ıce linek uzp˚ usoben´ ych tak, aby se v nˇejaké stanici prot´ınaly. Takov´ ym stanic´ım, kde se prot´ınaj´ı dvˇe a v´ıce linek, se ˇr´ıká pˇrestupn´ı stanice. Reprezentace prostˇred´ı neboli sestaven´ı jeho modelu se inspirovalo sekvenˇcn´ımi rozhodovac´ımi problémy (Vidal, J., M., 2010), kde stejnˇe jako zde celková cena cesty1 pasaˇzéra závis´ı na jeho sekvenˇcn´ıch rozhodnut´ıch (napˇr. volba trasy, j´ızdenky a kdy pojede). V pasaˇzérovˇe prostˇred´ı v definici 4.1 je stanovené deterministické provádˇen´ı akc´ı a nedeterministické z´ıskáván´ı odmˇen.

1

Pasaˇzéra jeho cesta nˇeco stoj´ı. U sekvenˇcn´ıch rozhodovac´ıch problém˚ u se tato funkce naz´ yvá uˇzitek.

9

´ KAPITOLA 4. SPECIFIKACE A FORMALIZACE PROBLEMU

10

Definice 4.1 (Prostˇ red´ı pasaˇ z´ era): Prostˇred´ı pasaˇzéra

ε

je

definováno

n-tic´ı

⟨S, A, T, pk , t, cj , cp ⟩: • S . . . mnoˇzina vˇsech stanic metra, • A . . . mnoˇzina vˇsech moˇznost´ı dopravy mezi stanicemi, • T (s, a, s′ ) . . . pˇrechodová funkce, kde s ∈ S a ∈ A a s′ ∈ S, • pk (a, t) . . . pravdˇepodobnost kontrolován´ı pˇri akci a ∈ A v ˇcase t, • t . . . ˇcas, • cj . . . cena j´ızdenky a • cp . . . velikost pokuty.

I

Pˇrechodová funkce s oznaˇcen´ım T (s, a, s′ )2 v tomto prostˇred´ı udává pouˇzitelnost akc´ı, která z d˚ uvodu deterministick´ ych akc´ı nab´ yvá pouze dvou hodnot. Stoprocentn´ı pravdˇepodobnosti, pokud je akce a dostupná ve stavu s, a nulové, pokud nen´ı dostupná, tzn. vˇzdy kdyˇz lze akci provést, tak u ´spˇeˇsnˇe provede napˇr. pasaˇzér se pˇresune do jiné stanice. Tedy obor hodnot nab´ yvá pouze {0, 1} a definiˇcn´ı obor pˇrechodové funkce je tvoˇren mnoˇzinou vˇsech stav˚ u a akc´ı. Pravdˇepodobnost chycen´ı pk (a, t) zastává v modelu funkci nedeterministického z´ıskáván´ı odmˇeny za dosaˇzen´ı stavu, neboli po u ´spˇeˇsném dokonˇcen´ı akce. Pasaˇzér m˚ uˇze b´ yt na své cestˇe s urˇcitou pravdˇepodobnost´ı kontrolován inspektorem na vstupn´ı, v´ ystupn´ı a pˇrestupn´ı stanici nebo v soupravˇe mezi nimi. Protoˇze pasaˇzér m˚ uˇze z´ıskat jen zápornou odmˇenu pˇri pokutován´ı ˇci koupi j´ızdenky, pojem odmˇena jiˇz nen´ı na m´ıstˇe a byl nahrazen pojmem penalizace. Aby nebylo nutné rozliˇsovat kontrolu ve stanici a v soupravˇe, jsou vˇsechny moˇznosti sjednoceny pouze do akc´ı, kter´ ymi jsou vstup a v´ ystup ze stanice, pˇrejezdy mezi nimi a pˇrechody pˇeˇsky viz. dále Akce v prostˇred´ı pasaˇzéra sekce 4.1.2. Pasaˇzér potom dostává penalizaci po u ´spˇeˇsném dokonˇcen´ı kaˇzdé akce. Velikost penalizace závis´ı na pasaˇzérovˇe volbˇe. Pokutován´ı se totiˇz net´ yká pasaˇzéra, kter´ y má platnou j´ızdenku, ten obdrˇz´ı nˇejakou malou penalizaci (dle ceny j´ızdenky). Pokud pasaˇzér nemá platnou j´ızdenku, obdrˇz´ı s urˇcitou pravdˇepodobnost´ı, která odpov´ıdá 2

U sekvenˇcn´ıch rozhodovac´ıch problém˚ u oznaˇcuje pravdˇepodobnost dosaˇzen´ı stavu s′ , pokud se agent

nacház´ı ve stavu s a provede akci a neboli pravdˇepodobnost u ´spˇeˇsného dokonˇcen´ı akce (Vidal, J., M., 2010).

ˇ Í PASAZ ˇERA ´ 4.1. REPREZENTACE PROSTRED

11

pokutován´ı, vyˇsˇs´ı penalizaci (velikost pokuty) nebo nez´ıská ˇza´dnou penalizaci, pokud nebyl kontrolován. Z pk (a, t) je vidˇet, ˇze penalizace jsou v pasaˇzérovˇe prostˇred´ı dynamické tj. promˇenlivé v ˇcase. Tedy je zˇrejm´ y pravdˇepodobnostn´ı charakter penalizaˇcn´ı funkce, pravdˇepodobnost, s jakou bude pasaˇzér kontrolován v ˇcase t ve stavu s nebo pˇri provádˇen´ı akce a. Dále je definována mnoˇzina stav˚ u (stanic), do kter´ ych se m˚ uˇze dostat pomoc´ı jednotliv´ ych akc´ı (pˇrechod˚ u/pˇrejezd˚ u).

4.1.1

Stavy v prostˇ red´ı pasaˇ z´ era

Stavy v pasaˇzérovˇe prostˇred´ı reprezentuj´ı skuteˇcné stanice veˇrejné dopravn´ı s´ıtˇe a stavy pˇred vstupy do jednotliv´ ych stanic. Aby jednotlivé linky a stanice byly dobˇre identifikovatelné a pozdˇeji také pro lepˇs´ı identifikaci akc´ı pˇrechod˚ u mezi r˚ uzn´ ymi stanicemi/linkami, je zavedeno znaˇcen´ı stav˚ u INix ve stanici a OU Tix pˇred stanic´ı, kde i je poˇradové ˇc´ıslo stanice na lince x. Mnoˇzina vˇsech stav˚ u je vyjádˇrena rovnic´ı 4.1. S ≡ {INix , OU Tix | x ∈ L ∧ n ∈ {1 . . . len(x)}},

(4.1)

kde L je mnoˇzina vˇsech linek metra (napˇr. L ≡ {a, b, c, . . . }) a funkce len(x) je délka linky metra x.

4.1.2

Akce v prostˇ red´ı pasaˇ z´ era

Z pasaˇzérova pohledu existuj´ı ˇctyˇri akce, které m˚ uˇze vykonávat na cestˇe do c´ılového stavu. Prvn´ı MOVE - pˇrejezd metrem z jedné stanice do následuj´ıc´ı stanice, druhá WALK pˇrechod pˇeˇsky mezi r˚ uzn´ ymi stanicemi, tˇret´ı ENTRY - vstup do stanice a posledn´ı EXIT - v´ ystup ze stanice. V´ ysledná mnoˇzina vˇsech akc´ı, která je znázornˇena v rovnici 4.2, je sjednocen´ım tˇechto ˇctyˇr mnoˇzin akc´ı. A ≡ AMOVE ∪ AWALK ∪ AENTRY ∪ AEXIT ,

(4.2)

kde AMOVE je mnoˇzina akc´ı urˇcuj´ıc´ı j´ızdy metrem, AWALK je mnoˇzina akc´ı urˇcuj´ıc´ı pˇrechody mezi stanicemi, AENTRY je mnoˇzina akc´ı definuj´ıc´ı vstup do stanice a AEXIT je mnoˇzina akc´ı definuj´ıc´ı v´ ystupy ze stanic. Kaˇzdá akce je pevnˇe svázána s konkrétn´ım stavem. Pokud agent bude cht´ıt pouˇz´ıt akci, která je spojena s jin´ ym stavem neˇz, ve kterém se pasaˇzér nacház´ı, pak se akce


12

neprovede viz. pˇrechodov´ y model v´ yˇse.

4.1.3

Mnoˇ zina akc´ı j´ızdy metrem

Mnoˇzina akc´ı je definována v rovnici 4.3 a urˇcuje pro vˇsechny linky metra pˇrejezdy mezi vˇsemi stanicemi na dané lince. Jednotlivá akce MOVE je urˇcena zápisem x x MOVE{INix → INi+1 } a definuje pˇrejezd metrem ze stavu INix do stavu INi+1 na

lince x.

x AMOVE ≡ {MOVE{INix → INi+1 }, x MOVE{INi+1 → INix } | x ∈ L ∧ i ∈ {1 . . . len(x)}}, (4.3)

kde L je mnoˇzina vˇsech linek metra a funkce len(x) je délka linky metra x.

4.1.4

Mnoˇ zina akc´ı pˇ rechodu mezi stanicemi

Pˇrechody mezi stanicemi tvoˇr´ı mnoˇzinu akc´ı viz. rovnice 4.4, které jsou definovány WALK{INix → INjy } s vyuˇzit´ım pˇrestupu a WALK{OU Tix → OU Tjy } pro venkovn´ı pˇrechod. Obˇe akce znamenaj´ı pˇrechod mezi stavem INix /OU Tix a stavem INjy /OU Tjy . Linky x a y pro venkovn´ı pˇrestup mohou b´ yt identické, ovˇsem potom mus´ı b´ yt r˚ uzné stanice i a j (i ̸= j). Moˇznost, kdy x = y a i = j je pro agenta neracionáln´ı volba, která by znamenala z˚ ustat ve stejném stavu. Akce vnitˇrn´ıho pˇrestupu je poté umoˇznˇena pouze na pˇrestupn´ı stanici.

AWALK ≡ {WALK{INix → INjy } | P (INix , INjy ) ̸= ∅} ∪ ∪ {WALK{OU Tix → OU Tjy } | x ∈ L ∧ y ∈ L∧ ∧ i ∈ {1 . . . len(x)} ∧ j ∈ {1 . . . len(y)}}, (4.4) kde L je mnoˇzina vˇsech linek metra, funkce len(x) je délka linky metra x, funkce P (INix , INjy ) vrac´ı pˇrestupy mezi stanicemi INix a INjy , pro x ∈ L ∧ y ∈ L ∧ i ∈ {1 . . . len(x)} ∧ j ∈ {1 . . . len(y)}.

ˇERA ´ 4.2. VLASTNOSTI PASAZ

4.1.5

13

Mnoˇ zina akc´ı vstup do stanice

Vˇsechny vstupy do stanic (akce ENTRY{OU Tix }) tvoˇr´ı dalˇs´ı mnoˇzinu akc´ı viz. rovnice 4.5, které pasaˇzér m˚ uˇze pouˇz´ıt. AENTRY ≡ {ENTRY{OU Tix } | x ∈ L ∧ i ∈ {1 . . . len(x)}},

(4.5)


4.1.6

Mnoˇ zina akc´ı v´ ystup ze stanice

Pasaˇzér také mus´ı m´ıt moˇznost nˇejak´ ym zp˚ usobem vystoupit z kaˇzdé stanice metra. Tuto moˇznost pokr´ yvá mnoˇzina akc´ı (akce EXIT{INix }) definuj´ıc´ı v´ ystup ze stanice v rovnici 4.6. AEXIT ≡ {EXIT{INix } | x ∈ L ∧ i ∈ {1 . . . len(x)}},

(4.6)


4.2

Vlastnosti pasaˇ z´ era

Vlastnosti pasaˇzéra, zapsané v definici 4.2, jsou tvoˇreny poˇcáteˇcn´ı stanic´ı, tedy m´ıstem odkud bude plánovat svoji cestu, c´ılovou stanic´ı, moˇzn´ ym ˇcasem odjezdu, nutn´ ym ˇcasem dojezdu a jeho ekonomick´ ym stavem3 . Ekonomick´ y stav je pasaˇzér˚ uv d˚ uleˇzit´ y parametr pro rozhodnut´ı, zda si koup´ı ˇci nekoup´ı j´ızdenku na svoji trasu. Definice 4.2 (Vlastnosti pasaˇ z´ era): Vlastnosti pasaˇzéra α jsou definovány pˇetic´ı ⟨s0 , g, k, t0 , td ⟩ • s0 . . . poˇcáteˇcn´ı stanice, • g . . . c´ılová stanice, • k . . . ekonomick´ y stav pasaˇzéra (kapitál), • t0 . . . moˇzn´ y ˇcas v´ yjezdu, 3

Inspirov´ ano ˇcl´ ankem (Kooreman, P., 1993).


14

• td . . . ˇcas, kdy mus´ı pasaˇzér bezpodm´ıneˇcnˇe dorazit do c´ılové stanice.

4.3

I

Pl´ an

Plán pasaˇzéra pˇredstavuje jiˇz konkrétn´ı ”cestovn´ı plán”, kter´ y si pasaˇzér zvol´ı. Obsahuje zvolenou trasu, kterou pojede, volbu ˇcasu v´ yjezdu a typ j´ızdenky. Typem j´ızdenky se mysl´ı, zda pasaˇzér zvol´ı jednu z moˇznost´ı - koupit ˇci nekoupit j´ızdenku. Volba ˇcasu v´ yjezdu je pro pasaˇzéra také d˚ uleˇzitá, m˚ uˇze se tak vyhnout nˇejak´ ym kontrolám, které jsou ˇcasovˇe promˇenné (napˇr. nˇekteˇr´ı inspektoˇri se pohybuj´ı souˇcasnˇe se soupravou), a tedy pˇr´ıpadnému pokutován´ı. Jak jiˇz bylo zm´ınˇeno, prostˇred´ı je ˇcasovˇe promˇenné, v ˇcase se mˇen´ı pravdˇepodobnosti kontrol, protoˇze inspektoˇri nejsou stále na stejném m´ıstˇe. Definice 4.3 (Reprezentace trasy): Reprezentace trasy tr je uspoˇrádaná n-tice (a0 , a1 , . . . , an ), kde ∀i ∈ {0, . . . , n} : ai ∈ {MOVE, WALK, ENTRY, EXIT}

Definice 4.4 (Cestovn´ı pl´ an): Cestovn´ı plán π je definován trojic´ı ⟨tr, ts , j⟩, kde • tr . . . zvolená trasa (definice 4.3), • ts . . . zvolen´ y ˇcas v´ yjezdu a • j . . . volba j´ızdenky ANO/NE.

I

V pˇr´ıkladu reprezentace trasy 4.7 akce WALK{INa6 → INc4 } znamená pˇrechod pˇeˇsky na pˇrestupn´ı stanici. Obcházen´ı nebo pˇrecházen´ı mezi stanicemi se v reprezentaci projev´ı v´ ystupem ze stanice pˇred ch˚ uz´ı a potom vstup zpˇet do stanice: {. . . EXIT{INa6 }, WALK{OU Ta6 → OU Tc4 }, ENTRY{OU Ta6 }, . . . }.

{ENTRY{OU Ta3 }, MOVE{INa3 → INa4 }, . . . . . . , WALK{INa6 → INc4 }, MOVE{INc4 → INc5 }, . . . , EXIT{INc8 }} (4.7)

ˇ Í CESTOVNÍHO PLANU ´ 4.4. MODEL OCENEN

4.4

15

Model ocenˇ en´ı cestovn´ıho pl´ anu

Model pasaˇzéra lze jednoduˇse pochopit jako ”agenta” vykonávaj´ıc´ıho cestu v transportn´ım systému veˇrejné dopravy. Jeho u ´kolem je zvolit trasu, kterou pojede, ˇcas a jak´ ym zp˚ usobem pojede ⇒ plán. Zaveden´ı cenové hodnoty plánu neboli pasaˇzérov´ ych rozhodnut´ı v daném prostˇred´ı a vlastnostech vyjadˇruje rovnice 4.8. Pasaˇzér podle cenové hodnoty m˚ uˇze rozliˇsovat kvalitu r˚ uzn´ ych plán˚ u a zvolit ten nejv´ yhodnˇejˇs´ı. U (π | α, ε) ≡ U (⟨tr, ts , j⟩ | ⟨s0 , g, k, t0 , td ⟩, ⟨S, A, T, pk , t, cj , cp ⟩)

(4.8)

Pokud pasaˇzér má plán trasy v prostˇred´ı, pak m˚ uˇze spoˇc´ıtat pravdˇepodobnost kontroly pˇri vykonáván´ı tohoto plánu. Pravdˇepodobnost pokutován´ı je doplˇ nkem k pravdˇepodobnosti situace, kdy pasaˇzér na celé cestˇe nebude kontrolován. Tato pravdˇepodobnost se poˇc´ıtá jako souˇcin pravdˇepodobnost´ı4 nekonrolován´ı pˇri vykonáván´ı jednotlivé akce. Jelikoˇz v prostˇred´ı je jen pravdˇepodobnost kontroly pˇri provádˇen´ı akce, jedná se zase o doplnˇek k této pravdˇepodobnosti v ˇcase t. Cel´ y vztah je znázornˇen´ı v rovnici 4.9 p(kontroly | π, ε) = 1 −

n ∏

(1 − pk (ai , t)),

(4.9)

i=1

kde n je délka trasy v plánu a pk (a, t) ∈ ε je pravdˇepodobnost kontroly pˇri akci a v ˇcase t viz. definice prostˇred´ı 4.1 a ai ∈ π. V´ yˇse zm´ınˇená cenová funkce definována v rovnici 4.10, pro rozliˇsován´ı kvality plán˚ u, je rozdˇelena do jednotliv´ ych sloˇzek urˇcuj´ıc´ı ˇcasovou, ekonomickou a psychologickou sloˇzku plánu.

U (π) = Ut (π) + Ue (π) + Up (π),

(4.10)

kde Ut tvoˇr´ı ˇcasovou sloˇzku ceny, Ue ekonomickou sloˇzku a Up psychologickou sloˇzku.

4.4.1

ˇ Casov´ a sloˇ zka ceny

Cestován´ı mezi stanicemi (provádˇen´ı akce) zabere pasaˇzérovi urˇcit´ y ˇcas. S moˇznost´ı obcházen´ı nebezpeˇcn´ ych stanic mus´ıme zaˇclenit i ˇcasovou penalizaci, doby strávené na cestˇe pˇri pˇresunu. Kdyby v modelu nebyla zaˇclenˇena ˇcasová penalizace, bylo by pro 4

Jedn´ a se o nezávislé jevy, proto souˇcin.


16

ˇ pasaˇzéra nejv´ yhodnˇejˇs´ı napˇr. doj´ıt celou cestu nebo obej´ıt podstatnˇe velk´ yu ´sek. Casov´ a penalizace je urˇcena rovnic´ı 4.11. { Ut (π) =

0 + τ (tr) − t0 , td − τ (tr) ≥ 0 ρ + τ (tr) − t0 , td − τ (tr) < 0

,

(4.11)

kde tr ∈ π je trasa, t0 je doba moˇzného startu, τtr je doba doraˇzen´ı do c´ıle v rovnici 4.12, td je nejzazˇs´ı term´ın doraˇzen´ı do c´ıle a pokuta ρ za nedodrˇzen´ı term´ınu.

τ (tr) = t0 +

n ∑

t ai ,

(4.12)

i=1

kde tr je trasa tj. posloupnost akc´ı, n délka plánu a tai je doba provádˇen´ı akce ai ∈ tr.

4.4.2

Ekonomick´ a sloˇ zka ceny

Hypotézou, proˇc jezd´ı lidé bez j´ızdenek, se stal jejich ekonomick´ y stav (neboli ”poˇca´teˇcn´ı”majetek daného jedince), cena j´ızdenky a velikost moˇzné pokuty. Tento fakt je moˇzno zohlednit v modelu zaveden´ım denn´ıho rozpoˇctu pasaˇzéra v hodnotˇe k. Vytvoˇrená funkce ceny je závislá na ekonomickém stavu jedince a znázornˇená v rovnici 4.13. Ue′ (k) =

log(k) , NORM EKO

(4.13)

kde NORM EKO je normalizaˇcn´ı konstanta, která je urˇcena z pr˚ uzkumu ekonomické situace simulovaného prostˇred´ı. Cena ekonomické sloˇzky je závislá na v´ ybˇeru j´ızdenky. Pokud si pasaˇzér koup´ı j´ızdenku, tak se v uˇzitkové hodnotˇe nepoˇc´ıtá s pravdˇepodobnost´ı pokutován´ı. Naopak se s n´ı poˇc´ıtá, kdyˇz si pasaˇzér j´ızdenku nekoup´ı. Moˇznosti ekonomické sloˇzky jsou znázornˇeny v rovnici 4.14. { UE (π | α, ε) =

Ue′ (k) − Ue′ (k − cj ), iff π ≡ ⟨tr, ts , true⟩

∑ a∈A

pk (a, t) · (Ue′ (k) − Ue′ (k − cp )), iff π ≡ ⟨tr, ts , true⟩

,

(4.14)

kde pk (a, t) ∈ ε je pravdˇepodobnost chycen´ı pˇri provádˇen´ı akce a ∈ tr, trasa tr ∈ π, k je ekonomick´ y stav pasaˇzéra, cj je cena j´ızdenky a Ue′ je funkce ekonomické závislosti popsané v´ yˇse.

ˇ Í CESTOVNÍHO PLANU ´ 4.4. MODEL OCENEN

17

ˇ ast cenové funkce UE s cestovn´ım plánem π ≡ ⟨tr, ts , true⟩ (s j´ızdenkou) v rovnici C´ 4.14 vycház´ı z kombinace uˇzitkové funkce U (N E) = −cj 5 (Boyd, C., Martini, Ch., Rickard, J. a Russell, A., 1989) a závislosti pasaˇzéra na jeho ekonomickém stavu. Je vidˇet, ˇze hodnota cenové funkce nákupu l´ıstku je rozd´ıl hodnot ekonomického stavu pˇred nákupem a po nákupu j´ızdenky (Kooreman, P., 1993). Ze znalosti vztahu ekonomického stavu viz. rovnice 4.13 vypl´ yvá jej´ı logaritmická závislost. Tedy pokud je pasaˇzér ekonomicky slabˇs´ı je pro nˇeho tento rozd´ıl vyˇsˇs´ı, neˇz kdyby pasaˇzér mˇel vyˇsˇs´ı poˇcáteˇcn´ı kapitál (viz. obrázek 4.16 ). Pokud tuto myˇslenku pˇrevedeme do skuteˇcnosti, kaˇzdého v´ıce mrz´ı, kdyˇz plat´ı pomˇerovˇe vˇetˇs´ı ˇca´stku z kapitálu a naopak ménˇe tráp´ı, kdyˇz mus´ı zaplatit ˇca´st menˇs´ı.

5 4.5 4

Uzitek [−]

3.5 3 2.5 2 1.5 1 0.5 0

0

20

40

60

80

100

Kapital [$]

Obrázek 4.1: Logaritmická závislost na ekonomickém stavu pasaˇzéra

Druhá ˇca´st cenové funkce UE s cestovn´ım plánem π ≡ ⟨tr, ts , true⟩ (bez j´ızdenky neboli riskován´ı) tvoˇr´ı souˇcet cen provádˇen´ ych akc´ı z trasy cestovn´ıho plánu. Cena provádˇen´ı akce byla odvozena z uˇzitkové funkce U (E) = −pr · cp 7 (Boyd, C., Martini, Ch., 5

Uˇzitkov´ a hodnota j´ızdy s j´ızdenkou z ˇclánku (Boyd, C., Martini, Ch., Rickard, J. a Russell, A.,

1989). 6 Na obrázku je logaritmick´ a závislost na ekonomickém stavu pasaˇzéra a ukazuje, jak stejn´ y pokles kapitálu znamená jinou cenu. 7 Uˇzitkov´ a hodnota riskov´ an´ı v ˇcl´ anku (Boyd, C., Martini, Ch., Rickard, J. a Russell, A., 1989). Kde pr je pravdˇepodobnost kontroly.


18

Rickard, J. a Russell, A., 1989) a v rovnici byla nahrazena velikost pokuty rozd´ılem ekonomického stavu pˇred a po zaplacen´ı pokuty pˇri provádˇen´ı akce.

4.4.3

Psychologick´ a sloˇ zka ceny

D˚ uleˇzitou vlastnost´ı pˇri rozhodován´ı o koupi j´ızdenky je psychika pˇri pˇr´ıpadném pokutován´ı. Zpravidla ˇc´ım vyˇsˇs´ı postaven´ı (tj. ekonomick´ y stav) pasaˇzér má, t´ım je pro nˇeho v´ıce nepˇr´ıjemné, ˇze by mohl b´ yt vidˇen pˇri pokutován´ı. Tento fakt je vyjádˇren´ y v rovnici 4.15 a taktéˇz závis´ı na pasaˇzérovˇe volbˇe l´ıstku. { 0, pokud π ≡ ⟨tr, ts , true⟩ UPSY (π | α, ε) = , 2 k , pokud π ≡ ⟨tr, ts , f alse⟩ NORM PSY

(4.15)

kde k je ekonomick´ y stav a N ORM P SY je normalizaˇcn´ı konstanta urˇcena z pr˚ uzkumu prostˇred´ı.

4.5

Shrnut´ı

V popisu modelu pasaˇzéra se uvaˇzuj´ı pouze jednorázové j´ızdenky. Dlouhodobé j´ızdenky by znamenaly sloˇzitˇejˇs´ı model. Dalˇs´ım zjednoduˇsen´ım modelu je nezávislost jednotliv´ ych cest tzn. ˇze pasaˇzér˚ uv kapitál pro dalˇs´ı cestu nen´ı ovlivnˇen´ y zakoupen´ım j´ızdenky nebo pokutován´ım. Samostatn´ y model popsan´ y v této kapitole nestaˇc´ı pro rozhodován´ı pasaˇzéra. V následuj´ıc´ı kapitole se popisuje model spoleˇcnˇe s uˇcen´ım se prostˇred´ı. Jeho dobrá znalost je d˚ uleˇzitá pro tvorbu nejv´ yhodnˇejˇs´ıho plánu.

Kapitola 5 Uvaˇ zov´ an´ı pasaˇ z´ era V pˇredcházej´ıc´ı kapitole byl popsán model pasaˇzéra a jeho prostˇred´ı. To samostatnˇe nestaˇc´ı pro pasaˇzérovo samovolné jednán´ı a je potˇreba mechanismus k tvorbˇe posloupnosti rozhodnut´ı a dosaˇzen´ı c´ıl˚ u pasaˇzéra. Mechanismem, pˇri v´ ybˇeru sekvenc´ı rozhodnut´ı, je plánovac´ı algoritmus, kter´ y by pasaˇzérovi staˇcil v pˇr´ıpadˇe, ˇze by znal vˇsechny pˇresné pravdˇepodobnosti kontroly. Bez pˇresn´ ych znalost´ı je pro správné chován´ı poˇzadována schopnost adaptace na prostˇred´ı, která se popisuje na konci kapitoly.

5.1

Pl´ anov´ an´ı trasy

Pasaˇzér na urˇcité ekonomické u ´rovni mus´ı kaˇzd´ y den vykonat urˇcité cesty. Na kaˇzdou cestu má vyhrazen´ y ˇcasov´ y interval ⟨t0 , td ⟩. Dobu, kdy nejdˇr´ıve m˚ uˇze zaˇc´ıt svoji cestu t0 a dobu td , kdy mus´ı b´ yt bezpodm´ıneˇcnˇe v c´ılovém m´ıstˇe. Pasaˇzér mus´ı naplánovat trasu z m´ısta A (poˇcáteˇcn´ıho stanice) do m´ısta B (c´ılové stanice) tak, aby cena jeho plánu byla minimáln´ı tj. minimalizuje cenovou funkci. Z kapitoly 4 sekce Cestovn´ı plán jsou známy moˇznosti rozhodován´ı pasaˇzéra: zda si koup´ı/nekoup´ı j´ızdenku, jakou zvol´ı trasu a ˇcas, kdy zaˇcne s realizac´ı plánu. Prostˇred´ı, ve kterém se pasaˇzér pohybuje definované v sekci Reprezentace prostˇred´ı pasaˇzéra kapitoly 4, m˚ uˇze b´ yt také názornˇe popsáno stavov´ ym diagramem. Pasaˇzér má mnoˇzinu dostupn´ ych stav˚ u, kde kaˇzd´ y z nich obsahuje mnoˇzinu akc´ı, které m˚ uˇze v daném stavu aplikovat (vyuˇz´ıt). 19

ˇ AN ´ Í PASAZ ˇERA ´ KAPITOLA 5. UVAZOV

20

Pasaˇzér nehledá jen nˇejak´ y plán, se kter´ ym se dostane z poˇca´teˇcn´ıho stavu do c´ılového. Hledá nejlepˇs´ı moˇzn´ y plán, kter´ y má nejmenˇs´ı hodnotu cenové funkce. Prostˇred´ı je pozorovatelné, pasaˇzér má tedy k dispozici nˇejakou informaci o prostˇred´ı, ve kterém se pohybuje.

5.1.1

Metoda vˇ etv´ı a mez´ı

K plánován´ı v pozorovatelném stavovém diagramu se vyuˇz´ıvaj´ı informované plánovac´ı algoritmy. Nejlépe vyhovuj´ıc´ım plánovac´ım algoritmem pro tento problém je metoda Vˇetv´ı a Mez´ı (Clausen, J., 1999) s prohledáván´ım do hloubky. V´ yhoda metody vˇetv´ı a mez´ı s prohledáván´ım do hloubky je ta, ˇze rychle1 najde nˇejaké ˇreˇsen´ı, podle kterého m˚ uˇze dále proˇrezávat vˇetve prohledávaného stromu, ve kterém se tvoˇr´ı jiˇz jen horˇs´ı plány, neˇz je doposud nalezen´ y. Toto proˇrezáván´ı znaˇcnˇe urychluje v´ ypoˇcet a tedy nalezen´ı nejlepˇs´ı moˇzné trasy resp. plánu. Existuje nˇekolik pˇredpoklad˚ u, které je tˇreba splnit pro nasazen´ı algoritmu na tento plánovac´ı problém. Jedn´ım je pˇredpoklad diskretizovaného ˇcasu a druh´ ym je fakt, ˇze z kaˇzdého stavu lze zrekonstruovat plán. Jeho vykonán´ım se agent dostane do poˇzadovaného stavu, a proto se kaˇzd´ y stav m˚ uˇze prezentovat jako plán. Pseudokód je znázornˇen v algoritmu 18. Aby proˇrezáván´ı algoritmu bylo co moˇzná nejefektivnˇejˇs´ı, jsou u prohledáván´ı preferovány v´ ybˇery akc´ı j´ızdy metrem, ˇc´ımˇz se rychle nalezne (prohledáván´ı do hloubky s backtrakingem) dostateˇcnˇe kvalitn´ı ˇreˇsen´ı. Poté se jiˇz horˇs´ı ˇreˇsen´ı zahazuj´ı neboli proˇrezávaj´ı dˇr´ıve a zbyteˇcnˇe se dále nerozv´ıjej´ı, coˇz urychluje v´ ypoˇcet. Metoda vˇetv´ı a mez´ı byla zvolena i z d˚ uvodu, ˇze nebyla nalezena pˇr´ıpustná heuristika pro optimáln´ı algoritmus A*. Metoda s prohledáván´ım do hloubky a preferován´ım j´ızdy

1

Pˇri správném poˇrad´ı akc´ı.

´ ´ Í TRASY 5.1. PLANOV AN metrem je dostateˇcnˇe efektivn´ı. Algorithm 1: Metoda vˇetv´ı a mez´ı s prohledáván´ım do hloubky Data: Prostˇred´ı ε ≡ ⟨S, A, T, Pkontroly , t, cj , cp ⟩;Vlastnosti α ≡ ⟨s0 , g, k, t0 , d⟩ Result: Plán π ≡ ⟨trasa, ts , j⟩; 1

Doln´ı mez ←− ∞;

2

foreach ts ::=

3

t0 : d do

foreach j ∈ {true, f alse} do

4

Otevˇrená mnoˇzina←− s0 ;

5

Uzavˇrená mnoˇzina←− ∅;

6

while Open ̸= ∅ do

7

P ≡ ⟨trasa, ts , j⟩ ←−Prvn´ı z otevˇrené mnoˇziny();

8

Otevˇrená mnoˇzina←−Otevˇrená mnoˇzina \ P ;

9 10

Uzavˇrená mnoˇzina←−Uzavˇrená mnoˇzina ∪ P ; if (g ∈ trasa) ∧ (Doln´ı mez > Ohodnot’(P )) then

11

π ←− P ;

12

Doln´ı mez←−Ohodnot’(P );

13

else

14

P ′ ←−Rozˇsiˇr plán(P );

15

P ′ ←− P ′ \ Uzavˇrená mnoˇzina;

16

foreach p ∈ P ′ do

17 18

if Doln´ı Mez > Ohodnot’(p) then Pˇridej na zaˇcátek otevˇrené mnoˇziny(p);

21


22

5.1.2

Popis pl´ anov´ an´ı

Pasaˇzéˇri si kaˇzd´ y den pˇred moˇzn´ ym zaˇca´tkem své cesty zaˇc´ınaj´ı plánovat své trasy. Informace o prostˇred´ı a jejich vlastnostech, které maj´ı k dispozici, se stávaj´ı vstupem pro plánovac´ı algoritmus. Vstupy jsou tedy definované v sekci 4.1 a 4.2 kapitoly 4 tj. vlastn´ı znaj´ı kapitál, odkud, kam a kdy jet, z prostˇred´ı znaj´ı cenu l´ıstku, velikost pokuty, dopravn´ı s´ıt’ a pravdˇepodobnost kontroly v n´ı. 1. Plánovat pasaˇzér zaˇc´ıná ze stavu pˇred poˇca´teˇcn´ı stanic´ı v ˇcase startu. 2. Ze známého prostˇred´ı zjist´ı, jaké akce m˚ uˇze z této pozice provést. Tato ˇc´ ast je vˇetv´ıc´ım m´ıstem. Velikost vˇetv´ıc´ıho faktoru a poˇrad´ı vyb´ıraných akc´ı urˇcuje sloˇzitost výpoˇctu, která m˚ uˇze být aˇz O(bd ), kde b je vˇetv´ıc´ı faktor a d hloubka prohled´ avaného stromu. 3. Zvol´ı si (dalˇs´ı) jednu akci, kterou si pˇridá do prozat´ımn´ıho plánu. K ostatn´ım akc´ım se vrát´ı pozdˇeji, protoˇze prohledáv´ a do hloubky. Pokud jiˇz proˇsel vˇsechny akce, odebere z plánu naposled pˇridanou akci a pokraˇcuje bodem 3. Pokud vyzkouˇsel vˇsechny moˇzné akce a prozat´ımn´ı plán neobsahuje ˇzádnou akci → prohledáván´ı konˇc´ı a vrac´ı nejlepˇs´ı nalezen´ y plán. Tento plán m˚ uˇze být prázdný pouze v pˇr´ıpadˇe, ˇze neexistuje. 4. Ohodnot´ı prozat´ımn´ı plán souˇctem vˇsech cen akc´ı v plánu viz. kapitola 4 sekce 4.4. 5. Zkontroluje, zda cena plánu nen´ı horˇs´ı neˇz cena doposud nejlepˇs´ıho nalezeného plánu. Pokud je horˇs´ı, akci z plánu odstran´ı a pokraˇcuje bodem 3. V tomto m´ıstˇe nastáv´ a moˇzné proˇrezán´ı prohled´ avaného stromu. Proˇr´ızne celou vˇetev pod plánem, který jiˇz má horˇs´ı cenu, neˇz doposud nalezený. 6. Pokud má nov´ y plán lepˇs´ı cenu, tak ji pasaˇzér pomyslnˇe provede a posune se do dalˇs´ıho stavu (ve stanici nebo pˇred stanic´ı). 7. Zkontroluje, zda je dosaˇzen´ y stav c´ılov´ y. Pokud ano, uloˇz´ı ho jako doposud nejlepˇs´ı nalezen´ y, odstranˇen´ı posledn´ı akce z plánu a pokraˇcuje bodem 3. Pokud nen´ı c´ılov´ ym m´ıstem, pokraˇcuje dalˇs´ım rozv´ıjen´ım plánu tedy bodem 2. Tento postup pasaˇzér opakuje pro r˚ uzné ˇcasy v´ yjezd˚ u poˇc´ınaj´ıc´ı moˇzn´ ym startem. Pro kaˇzd´ y ˇcas v´ yjezdu zkouˇs´ı nalézt plán s j´ızdenkou i bez j´ızdenky. Postupem v´ yˇse procház´ı cel´ y stavov´ y prostor tam, kde jsou plány s lepˇs´ı cenou neˇz je doposud nejlepˇs´ı nalezen´ y plán.

ˇ Í SE O PREPRAVN ˇ Í KONTROLE 5.2. UCEN

23

V´ ystup tvoˇr´ı sestaven´ y ”cestovn´ı plán” tj. posloupnost akc´ı, ˇcas v´ yjezdu, a volbu j´ızdenky viz. sekce 4.3 kapitoly 4.

5.1.3

Korektnost algoritmu

Algoritmus postupn´ ym rozˇsiˇrován´ım plán˚ u tvoˇr´ı nové plány. Vrát´ı tedy plán vedouc´ı do c´ılové stanice nebo ˇzádn´ y, pokud cesta neexistuje. Zvolen´ y algoritmus je proto korektn´ı.

5.1.4

´ Uplnost algoritmu

Protoˇze se jedná o koneˇcn´ y stavov´ y diagram s koneˇcnou mnoˇzinou stav˚ u a akc´ı, a protoˇze algoritmus nekonˇc´ı s prvn´ım nalezen´ ym ˇreˇsen´ım, ale hledá dalˇs´ı moˇzná ˇreˇsen´ı, je algoritmus také u ´pln´ y. Je u ´pln´ y i vzhledem k jeho proˇrezáván´ı. Algoritmus proˇrezává pouze taková ˇreˇsen´ı, které jiˇz nemohou dosáhnout ˇreˇsen´ı s lepˇs´ı cenou, neˇz je doposud nalezené.

5.2

Uˇ cen´ı se o pˇ repravn´ı kontrole

Plánovac´ı algoritmus hledá ˇreˇsen´ı s nejniˇzˇs´ı cenou v aktuáln´ım prostˇred´ı, které má k dispozici. Model vˇsak m˚ uˇze obsahovat zkreslené informace a v´ ysledky plánován´ı pak mohou b´ yt chybné. Pasaˇzér proto potˇrebuje schopnost uˇcen´ı se správnému modelu a to jak pˇri informac´ıch chybˇej´ıc´ıch, tak zastaral´ ych vlivem dynamiky systému. Pro adaptaci na (ne)deterministicky vyv´ıjej´ıc´ı se prostˇred´ı nen´ı uvaˇzováno plné uˇcen´ı s posilován´ım, protoˇze v mˇen chyb´ı fáze explorace. Pasaˇzér vyuˇz´ıvá exploitaci v podobˇe prostého statistického uˇcen´ı, které slouˇz´ı k poznáván´ı a pˇredv´ıdán´ı jev˚ u v reáln´ ych podm´ınkách. Do uˇcen´ı jsou nav´ıc zaˇclenˇeny apriorn´ı pravdˇepodobnosti metodou fiktivn´ıch dat, která je pˇridána z d˚ uvodu pasaˇzérovy poˇcáteˇcn´ı informace o prostˇred´ı. pk (a, t) =

n1 , n1 + n0

(5.1)

kde n1 je poˇcet kolikrát byl pasaˇzér pˇri provádˇen´ı akce a v ˇcase t kontrolován a n0 poˇcet kdy ne. Vztah 5.1 udává v´ ypoˇcet pravdˇepodobnosti kontroly pˇri provádˇen´ı akce a v ˇcase t. Pˇridán´ı apriorn´ı pravdˇepodobnosti spoˇc´ıvá pouze v poˇcáteˇcn´ım nastaven´ı n1 a n0 podle


24

z´ıskan´ ych fiktivn´ıch dat viz. rovnice 5.2 a 5.3. n1 =

T ∑

ft

(5.2)

(1 − ft ),

(5.3)

Metoda fiktivn´ıch dat je kombinac´ı ”expertn´ı”

informace, u které se apriorn´ı

t=1

n0 =

T ∑ t=1

kde f ∈ {0, 1} je vektor fiktivn´ıch dat. pravdˇepodobnost zadává na základˇe zkuˇsenost´ı experta, a apriorn´ıch dat namˇeˇren´ ych do zaˇca´tku odhadován´ı. Metoda spoˇc´ıvá v sestavován´ı fiktivn´ıch pokus˚ u expertem tak, aby data vycházej´ıc´ı z pokus˚ u odpov´ıdala pˇredstavám experta (Nagy, I., Nedoma, P., Kratky, M., Pavelkova, L. a Ettler, P., 2002). Horizont, kter´ y udává poˇcet fiktivn´ıch dat, udává ve statistice d˚ uvˇeryhodnost experta tj. nakolik pasaˇzér vˇeˇr´ı z´ıskan´ ym dat˚ um. Následná u ´prava pravdˇepodobnosti pk (a, t) se odhaduje jako aritmetick´ y pr˚ umˇer. Pasaˇzér upravuje pravdˇepodobnosti kontroly, na základˇe pozorován´ı, vˇzdy po dokonˇcen´ı celého plánu. Pasaˇzér m˚ uˇze upravovat pouze ty pravdˇepodobnosti, o kter´ ych z´ıskal novou informaci tj. pro vˇsechny akce z plánu a ∈ π v ˇcase t. Krátk´ y horizont odpov´ıdá slabˇs´ı apriorn´ı pravdˇepodobnosti tzn. ˇze se uˇcen´ y model bude rychleji adaptovat na zmˇeny prostˇred´ı neboli rychleji uprav´ı chybné informace o prostˇred´ı. S krátk´ ym horizontem nemaj´ı pˇr´ıliˇs velkou váhu informace od experta. Pˇri nepravdivé expertn´ı informaci, bude zpoˇcátku budouc´ı odhadovaná hodnota pravdˇepodobnˇe chybná, ale pozorován´ı bude postupnˇe korigovat ˇspatnou apriorn´ı znalost.

5.3

Shrnut´ı

V této kapitole bylo k modelu pasaˇzéra pˇridáno i jeho rozhodován´ı v podobˇe hledán´ı plánu s nejniˇzˇs´ı cenou a zp˚ usob pasaˇzérovy adaptace na prostˇred´ı. Lze tedy pˇrej´ıt od teoretické ˇcásti k praktické.

Kapitola 6 Implementace Model pasaˇzéra popsan´ y v kapitole 4, pasaˇzérovo plánován´ı a uˇcen´ı popsané v kapitole 5, bylo implementováno jako rozˇs´ıˇren´ı stávaj´ıc´ıho frameworku FareEvasion. Implementace agentn´ıho modelu pˇrepravn´ı kontroly je tedy nástavbou na existuj´ıci framework FareEvasion, kter´ y tvoˇr´ı nástavbu agentn´ı simulaˇcn´ı platformy AgentPolis slouˇz´ıc´ı pro simulaci, verifikaci a experimentován´ı agentn´ıch model˚ u. FareEvasion, AgentPolis i platforma A-lite, na které je AgentPolis postaven, jsou napsány v programovac´ım jazyku Java. Implementace rozˇs´ıˇren´ı tˇechto simulaˇcn´ıch platforem zachovává tento objektovˇeorientovan´ y jazyk. Ukázka struktury rozˇs´ıˇren´ı a závislost´ı mezi platformami je zobrazena na obrázku 6.1. V této ˇcásti zprávy je bl´ıˇze popsána implementace rozˇs´ıˇren´ı platformy agentn´ım modelem pˇrepravn´ı kontroly. Jsou zde popsané tˇr´ıdy pouˇzité v implementaci.

6.1

Tˇ r´ıdy pro model pasaˇ z´ era

Vytvoˇrené tˇr´ıdy pro chován´ı dˇr´ıve popsaného pasaˇzéra byly inspirovány z tˇr´ıd, které umoˇzn ˇuj´ı pohyb základn´ıho pasaˇzéra v projektu FareEvasion.

6.1.1

Vytvoˇ ren´ı pasaˇ z´ era

Vytvoˇren´ı pasaˇzéra je implementováno ve tˇr´ıdˇe PassengerInit a spoˇc´ıvá v nastaven´ı poˇcáteˇcn´ıch vlastnost´ı pasaˇzéra implementované ve tˇr´ıdˇe PassengerStatus. Dále se zde inicializuje ˇzivotn´ı cyklus pasaˇzéra a vytvoˇr´ı se plánovaˇc trasy. 25

26

KAPITOLA 6. IMPLEMENTACE

Obrázek 6.1: Závislosti mezi platformami

6.1.2

Vlastnosti pasaˇ z´ era

Vlastnosti pasaˇzéra jsou um´ıstˇeny ve tˇr´ıdˇe PassengerStatus a obsahuj´ı informace shrnuté v definici 4.2 v kapitole 4. Dále jsou ve vlastnostech pasaˇzéra uloˇzeny informace o prostˇred´ı z definice prostˇred´ı 4.1. Tyto informace maj´ı sice zpoˇca´tku nastavené vˇsichni pasaˇzéˇri stejnˇe, ale dále si je kaˇzd´ y upravuje vlastn´ım zp˚ usobem podle sv´ ych zkuˇsenost´ı z j´ızd. Z d˚ uvodu ˇcasové spojitosti, existuje nekoneˇcnˇe r˚ uzn´ ych stav˚ u prostˇred´ı. Pro jejich koneˇcnost byla diskretizována ˇcasová osa mˇen´ıc´ıho se prostˇred´ı tj. vˇsechny moˇzné stavy z urˇcitého ˇcasového rozmez´ı se nahrad´ı jedn´ım reprezentantem. T´ım je zaruˇcena koneˇcnost stav˚ u prostˇred´ı. Pasaˇzér napˇr. ˇcasov´ yu ´sek od 12:30 do 12:40 vn´ımá jako jeden stav, tedy prostˇred´ı se v tomto ˇcasovém intervalu pro nˇeho nezmˇen´ı. Jelikoˇz si v této tˇr´ıdˇe pasaˇzér udrˇzuje vlastn´ı pˇredstavu o prostˇred´ı, bylo také nutné implementovat jeho uˇcen´ı. S uˇcen´ım, které bylo definováno v kapitole 5, je spojená konstanta horizontu fiktivn´ıch j´ızd, urˇcuj´ıc´ı vˇerohodnost poˇcáteˇcn´ıch informac´ı. Uˇcen´ı neboli adaptace na aktuáln´ı prostˇred´ı prob´ıhá u kaˇzdého navˇst´ıveného stavu prostˇred´ı1 . Tˇr´ıda implementuje i model pasaˇzéra, kterého se plánovaˇc, volan´ y z ˇzivotn´ıho cyklu 1

Stav prostˇred´ı je ch´ ap´ an jako stanice ˇci u ´sek v daném ˇcasovém rozmez´ı

ˇ ÍDY PRO MODEL PASAZ ˇERA ´ 6.1. TR

27

pasaˇzéra dotazuje, na uˇzitkové hodnoty aktuáln´ıho prohledávaného stavu.

6.1.3

Pl´ an pasaˇ z´ era

V implementaci tˇr´ıdy PassengerPlan je uchováván jiˇz cel´ y plán pasaˇzéra.

6.1.4

ˇ Zivotn´ ı cyklus pasaˇ z´ era

ˇ Zivotn´ ı cyklus pasaˇzéra zaˇc´ıná ”narozen´ım agenta” tedy metodou born, ve které se pasaˇzérovi nastav´ı kaˇzdodenn´ı cesta. Pokraˇcován´ı v denn´ım cyklu pasaˇzéra je plánován´ı této trasy zobrazené na stavovém diagramu v obrázku 6.2.

Obrázek 6.2: Stavov´ y diagram ˇzivotn´ıho cyklu pasaˇzéra

Po plánován´ı pasaˇzér ˇceká na ˇcas, kdy m˚ uˇze zaˇc´ıt plnit sv˚ uj plán, kter´ y pˇri dosaˇzen´ı správného ˇcasu zaˇcne plnit. Na závˇer jednoho cyklu pasaˇzér vyhodnot´ı svou cestu t´ım, ˇze si uprav´ı informace o prostˇred´ı (uˇc´ı se). Implementace provádˇen´ı pasaˇzérova plánu je shodná se stavov´ ym diagramem zobrazeném v obrázku 6.3.

28


Obrázek 6.3: Stavov´ y diagram provádˇen´ı plánu

6.1.5

Pl´ anovaˇ c

Plánovaˇc cesty vyuˇz´ıvá metody Vˇetv´ı a mez´ı popsané v kapitole 5. Pro plánován´ı pouˇz´ıvá oznaˇcen´ı celé linky ROUTE ID.

6.1.6

Stav

Stav, ve kterém se pasaˇzér nacház´ı, je implementován ve tˇr´ıdˇe PlannerNode. Tento stav uchovává informace o vˇsech pˇredchoz´ıch stavech a akc´ıch, které vedly k dosaˇzen´ı tohoto stavu. Na kaˇzd´ y stav se nahl´ıˇz´ı jako na ˇcásteˇcné nebo u ´plné ˇreˇsen´ı, tud´ıˇz je potˇreba znát ohodnocen´ı nebo-li pasaˇzérovu cenu dosaˇzen´ı tohoto stavu. Stavu vyuˇz´ıvá plánovaˇc, kter´ y prostˇrednictv´ım tˇr´ıdy PassengerStatus, tento stav ohodnot´ı uˇzitkovou funkc´ı plánuj´ıc´ıho pasaˇzéra.

ˇ ÍDY PRO MODEL INSPEKTORA 6.2. TR

6.1.7

29

Ukl´ ad´ an´ı informac´ı

Pro vyhodnocen´ı v´ ysledk˚ u kaˇzdé simulace se v jej´ım pr˚ ubˇehu ukládaj´ı informace o pasaˇzérovi (typ pasaˇzéra), jeho plánu (trasa, j´ızdenka) a vyhodnocen´ı plánu po jeho dokonˇcen´ı (kontrola, pokutován´ı). Na konci kaˇzdé simulace se vˇsechny informace uloˇz´ı do souboru s hodnotami oddˇelen´ ymi ˇca´rkou (csv soubor˚ u)2 .

6.2

Tˇ r´ıdy pro model inspektora

Chován´ı inspektora v projektu FareEvasion se v´ yraznˇe neliˇs´ı od tohoto inspektora, proto byly pˇrevzaty z nˇeho. Upraven byl zejména ˇzivotn´ı cyklus inspektora, ve kterém se rozliˇsuje v´ ybˇer strategie kontroly.

6.2.1

Vytvoˇ ren´ı inspektora

Vytvoˇren´ı a nastaven´ı vlastnost´ı inspektora prob´ıhá ve tˇr´ıdˇe inspektorInit. Vlastnost´ı inspektora je poˇcet pasaˇzér˚ u, které inspektor zkontroluje bˇehem jedné minuty a pomˇer udávaj´ıc´ı kolik procent pasaˇzér˚ u m˚ uˇze inspektor maximálnˇe zkontrolovat na jednom u ´seku tj. mezi sousedn´ımi stanicemi. Pˇri vytváˇren´ı inspektora se také spust´ı jeho ˇzivotn´ı cyklus.

6.2.2

ˇ Zivotn´ ı cyklus inspektora

Do modelu pˇrepravn´ı kontroly byly implementovány dva typy ˇzivotn´ıch cykl˚ u inspektora. Tyto ˇzivotn´ı cykly se liˇs´ı pouze ve v´ ybˇeru strategie kontroly pro následuj´ıc´ı den. V jednom ˇzivotn´ım cyklu je v´ ybˇer strategie kontroly na dalˇs´ı den shodn´ y se strategi´ı v pˇredchoz´ım dni, jak je ukázáno ve stavovém diagramu 6.43 . Takové chován´ı inspektor˚ u je pˇredv´ıdatelné, proto prostˇred´ı pouze s t´ımto typem inspektor˚ u je deterministické. Kaˇzd´ y inspektor bude m´ıt kaˇzd´ y den stejnou strategii kontroly tzn. bude kontrolovat na shodn´ ych m´ıstech, ve stejn´ y ˇcas, kaˇzd´ y den. 2 3

CSV: Comma-separated values - hodnoty oddˇelené ˇcárkami. Obrázek byl pˇrekreslen ze zprávy (Moler, Z., n.d.).

30


Obrázek 6.4: Diagram deterministického ˇzivotn´ıho cyklu inspektora

Druh´ ym ˇzivotn´ım cyklem se vyb´ırá nová strategie kontroly kaˇzd´ y den. Stavov´ y diagram 6.54 ukazuje chován´ı inspektora s t´ımto druhem ˇzivotn´ıho cyklu. Prostˇred´ı, v nˇemˇz se vyskytuj´ı tito inspektoˇri, je nedeterministické. V´ ybˇer strategie kontroly prob´ıhá na zaˇca´tku kaˇzdého dne v´ yˇse uveden´ ym zp˚ usobem. Kaˇzd´ y inspektor má k dispozici seznam moˇzn´ ych strategi´ı, kde kaˇzdá strategie kontroly obsahuje pravdˇepodobnost, s kterou se bude vykonávat. Pravdˇepodobnosti vˇsech strategi´ı tvoˇr´ı hustotu pravdˇepodobnosti, ze které se vyb´ıraj´ı jednotlivé strategie pro inspektora. Kaˇzdá strategie inspektora se m˚ uˇze skládat z jedné nebo v´ıce akc´ı, které inspektor mus´ı bˇehem dne provést napˇr. kontrola ve stanici, kontrola na nˇejakém u ´seku a kontrola v jiné stanici.

4

Obrázek byl inspirov´ an zprávou (Moler, Z., n.d.).

6.3. SHRNUTÍ

31

Obrázek 6.5: Diagram nedeterministického ˇzivotn´ıho cyklu inspektora

6.3

Shrnut´ı

K ovˇeˇren´ı implementace byly provedeny a vyhodnoceny experimenty, které jsou rozepsány v následuj´ıc´ı kapitole. K jejich vyhodnocen´ı bylo potˇrebné pr˚ ubˇeˇznˇe ukládat informace uvedené v´ yˇse. K vyhodnocen´ı v´ ysledk˚ u simulace (vykreslen´ı graf˚ u, . . . ), byl pouˇzit v´ ypoˇcetn´ı nástroj MATLAB. Kv˚ uli provádˇen´ı v´ıce experiment˚ u, byl opˇet v programovac´ım jazyku java implementován spouˇstˇec´ı program, kter´ y postupnˇe provádˇel dané experimenty. Z d˚ uvodu rychlého vyhodnocován´ı v´ ysledk˚ u bylo do nˇeho implementováno pˇredzpracován´ı dat pro MATLAB5 . Projekt FareEvasion je implementované grafické rozhran´ı, které je ukázáno na obrázku 6.6(a) pro jednu linku a na 6.6(b) pro celou s´ıt’, zobrazuj´ıc´ı dráhy linek dopravn´ı s´ıtˇe, moˇznosti pˇeˇs´ıho pˇrestupu, pohybuj´ıc´ı se dopravn´ı soupravy, rozm´ıstˇen´ı inspektor˚ u a pohyb dopravn´ı soupravy s pasaˇzéry. 5

Pˇreveden´ı MATLAB kódu na jar soubor, kter´ y lze spustit javou. Tento jar soubor volá MATLAB

knihovny, bez kter´ ych se neobejde.

32


(a) Simulace jedné linky

(b) Simulace celé s´ıtˇe

Obrázek 6.6: Zobrazen´ı grafického prostˇred´ı simulaˇcn´ı platformy

Kapitola 7 Experimenty V pˇredchoz´ıch kapitolách bylo definováno prostˇred´ı, model pasaˇzéra a zp˚ usob pasaˇzérovy adaptace na okoln´ı prostˇred´ı. Adaptac´ı je myˇsleno uˇcen´ı se novému (aktuáln´ıho) prostˇred´ı nebo nauˇcen´ı se na zmˇeny v prostˇred´ı. V této kapitole je provedena a vyhodnocena sada experiment˚ u ovˇeˇruj´ıc´ı pˇredpoklady1 chován´ı vytvoˇreného modelu. Experimenty jsou rozdˇeleny do dvou ˇcást´ı. Prvn´ı ˇcást tvoˇr´ı základn´ı experimenty pro simulaci chován´ı jednotliv´ ych typ˚ u pasaˇzér˚ u a druhou ˇcást tvoˇr´ı experimenty s populac´ı pasaˇzér˚ u a inspektor˚ u. V druhé ˇcásti jsou rozdˇeleny podle velikosti prostˇred´ı (jedna linka, celá s´ıt’).

7.1 7.1.1

Nastaven´ı pro experimenty Konfigurace prostˇ red´ı

Vˇetˇsina parametr˚ u, potˇrebn´ ych ke konfiguraci prostˇred´ı, je popsána v kapitole 4 v sekci ”reprezentace prostˇred´ı pasaˇzéra”. Jsou jimi vˇsechny stanice dopravn´ı s´ıtˇe reprezentované stavy a vˇsechny zp˚ usoby pˇrepravy mezi nimi v podobˇe akc´ı. Jedn´ım z parametr˚ u, které nejsou viditelnˇe zanesené v reprezentaci prostˇred´ı je poˇcet linek. Prostˇred´ı, které je pouˇz´ıvané frameworkem FareEvasion (v kapitole 6) je podobné dopravn´ı s´ıti amerického mˇesta Los Angeles viz. obrázek 7.12 . V prostˇred´ı, které je tvoˇreno geograficky rozm´ıstˇen´ ymi stanicemi a trasami mezi nimi, je umoˇznˇeno cestován´ı pouze jedn´ım dopravn´ım prostˇredkem, kter´ ym je metro. Samozˇrejmˇe je umoˇznˇena i pˇreprava mezi stani1 2

Intuitivn´ı chov´ an´ı. http://www.metro.net/riding metro/maps/images/rail map.pdf

33

34

KAPITOLA 7. EXPERIMENTY

cemi ch˚ uz´ı. Z v´ ypoˇcetn´ı nároˇcnosti v simulaci byly uvaˇzovány jen d˚ uleˇzité pˇeˇs´ı pˇrechody mezi stanicemi, kter´ ymi jsou krátké pˇrechody pˇreváˇznˇe v okol´ı pˇrestupn´ıch stanic a pˇrestupy mezi sousedn´ımi stanicemi3 . Ned˚ uleˇzité pˇrechody, které zpomaluj´ı v´ ypoˇcet, jsou pˇr´ıliˇs dlouhé a pro pasaˇzéry nev´ yhodné. Konfiguraci prostˇred´ı tedy urˇcuj´ı tyto parametry: • Seznam vˇsech stanic, • seznam vˇsech pˇr´ım´ ych cest mezi stanicemi, • zp˚ usoby pˇrepravy, • kapacita dopravn´ıho prostˇredku, • rychlost cestován´ı v dopravn´ım prostˇredku, • rychlost ch˚ uze, • diskretizace ˇcasu, • cena j´ızdenky a • velikost pokuty. Kde pro experimenty jsou zafixovány parametry uvedené v tabulce 7.1. Tabulka 7.1: Tabulka fixn´ıch parametr˚ u prostˇred´ı

Parametry

Hodnota

Parametry kontroly Kontrol za minutu [-]

2

Max. kontrol na u ´seku [%]

0.1

Parametry pˇrepravy Cena j´ızdenky [$]

4

Velikost pokuty [$]

50

Kapacita prostˇredku [os.] Rychlost prostˇredku Rychlost ch˚ uze [ km ] h 3

[ km h

]

50 40 4.3

Pasaˇzér je schopen kombinac´ı tˇechto pˇrechod˚ u uj´ıt v´ıce stanic. Tato varianta m˚ uˇze b´ yt ménˇe v´ yhodná,

neˇz by byla ta skuteˇcn´ a.

7.1. NASTAVENÍ PRO EXPERIMENTY

35

Obrázek 7.1: Schéma dopravn´ı s´ıtˇe

7.1.2

Nastaven´ı sc´ en´ aˇ re

Scénáˇr obsahuje nˇekolik parametr˚ u, které je potˇreba nastavit pro pˇribl´ıˇzen´ı k reáln´ ym v´ ysledk˚ u tˇechto experiment˚ u. Volby hodnot tˇechto parametr˚ u tedy urˇcuj´ı, jak se bu-

36


dou vyv´ıjet mˇeˇrené metriky, tedy poˇzadované (vyhodnocované) v´ ystupy z experimentu. Nˇekteré z parametr˚ u scénáˇre z˚ ustanou, at’ uˇz z v´ ypoˇcetn´ıch nebo jin´ ych d˚ uvod˚ u, nemˇenné. Seznam parametr˚ u scénáˇre lze rozdˇelit do dvou skupin. Jedna skupina je tvoˇrena nastaven´ım inspektor˚ u tedy parametry: • Poˇcet inspektor˚ u, • rozvrh (strategie) inspektor˚ u, • rozdˇelen´ı pravdˇepodobnosti v´ ybˇeru strategie, • poˇcet kontrol inspektorem za minutu a • kolik procent pasaˇzér˚ u maximálnˇe zkontroluje inspektor na jednom u ´seku, Prvn´ı dva parametry se liˇs´ı experiment od experimentu. Sada strategi´ı inspektor˚ u a jejich pravdˇepodobnostn´ı rozdˇelen´ı byla z´ıskána od dopravn´ıho podniku Los Angeles dále v pˇriloˇzeném CD. Pokud nen´ı v experimentech uvedeno jinak, je vyuˇz´ıváno této sady strategi´ı s v´ ybˇerem podle jejich rozdˇelen´ı pravdˇepodobnosti. Druhá ˇca´st tvoˇr´ı vlastnosti druhého typu agenta umoˇzn ˇuj´ıc´ı simulaci, kter´ ym je pasaˇzér. Parametry jsou popsané v kapitole 4 v definici 4.2. • poˇcet cestuj´ıc´ıch pasaˇzér˚ u, • sada cest pasaˇzér˚ u: – Poˇcáteˇcn´ı stanice, – c´ılová stanice, – moˇzn´ y ˇcas v´ yjezdu, – nutn´ y ˇcas dojezdu do c´ılové stanice, • pravdˇepodobnostn´ı rozdˇelen´ı v´ ybˇeru cesty, • parametry uˇzitku pasaˇzéra: – Kapitál pasaˇzéra, – penalizace za pˇrekroˇcen´ı ˇcasu nutného dojezdu, – parametry z prostˇred´ı (cena j´ızdenky a velikost pokuty), • parametry urˇcuj´ıc´ı pasaˇzér˚ uv typ:

7.1. NASTAVENÍ PRO EXPERIMENTY

37

– preferuj´ıc´ı ˇcasov´ y uˇzitek, – preferuj´ıc´ı ekonomick´ y uˇzitek, – preferuj´ıc´ı psychologick´ y uˇzitek, • apriorn´ı znalost prostˇred´ı a • horizont (pro fiktivn´ı data od experta). Cesty pasaˇzér˚ u jsou stejnˇe jako v pˇredchoz´ı sadˇe (jako strategie inspektor˚ u) z´ıskány od dopravn´ı spoleˇcnosti Los Angeles. Denn´ı rozpoˇ cet pasaˇ z´ era Z d˚ uvodu podobnosti dopravn´ı s´ıtˇe s mˇestem Los Angeles byly vygenerovány pasaˇzér˚ um denn´ı rozpoˇcty dle ekonomického rozloˇzen´ı v LA v roce 2009, tabulka A.1. Nastaven´ı parametr˚ u urˇ cuj´ıc´ı typ pasaˇ z´ era Podle pozorován´ı jednotliv´ ych sloˇzek cenové funkce pasaˇzéra, která p˚ usob´ı na chován´ı pasaˇzéra, byly nastaveny ˇrádovˇe vlivy jednotliv´ ych sloˇzek. Pasaˇzéˇri se tedy dˇel´ı do skupin podle toho jaká sloˇzka u nich pˇrevaˇzuje. Fixn´ı nastaven´ı parametr˚ u, která jsou zobrazena v tabulce 7.2, z˚ ustávaj´ı ve vˇsech experimentech shodná. Tabulka 7.2: Tabulka fixn´ıch parametr˚ u normalizaˇcn´ıch konstant pasaˇzér˚ u

Typ pasaˇ z´ era

ˇ Casov´ y uˇ zitek Ekonom. uˇ zitek Psycholog. uˇ zitek

ˇ Casov´ y [-]

5 · 106

100

106

Ekonomick´ y [-]

2 · 107

5 · 10−1

106

Psychologick´ y [-]

2 · 107

100

5 · 102

7.1.3

Metriky k vyhodnocen´ı

Pro vyhodnocen´ı experiment˚ u je potˇreba bˇehem experimentu ukládat r˚ uzné parametry simulace pˇrepravy, ze kter´ ych lze následnˇe tvoˇrit závˇery o chován´ı systému. • U modelu pˇrepravn´ı kontroly je oˇcekávanou a sledovanou statistikou v´ yvoj poˇctu neplat´ıc´ıch pasaˇzér˚ u. Dopravn´ı podnik se ˇcasto snaˇz´ı sledovat, jakou ztrátu jim neplat´ıc´ı pasaˇzéˇri zp˚ usobili nebo pˇr´ıpadnˇe zisk z udˇelen´ ych pokut v pˇr´ıpadˇe nasazen´ı inspektor˚ u do dopravn´ı s´ıtˇe.

38

KAPITOLA 7. EXPERIMENTY • Pozorovat dynamiku systému tj. za jak dlouhou dobu se pasaˇzéˇri nauˇc´ı rozm´ıstˇen´ı inspektor˚ u. • Sledován´ı velikosti u ńiku zisk˚ u (v podobˇe zakoupen´ ych l´ıstk˚ u), poˇctu kontrol a udˇelen´ ych pokut v ustáleném sytému v závislosti na poˇctu inspektor˚ u v nˇem se pohybuj´ıc´ıch. Dopravn´ı spoleˇcnosti toto pozorován´ı umoˇzn ˇuje maximalizovat zisk. • Sledovat, jak se pasaˇzéˇri zachovaj´ı pˇri statické kontrole. Kolik pasaˇzér˚ u proj´ıˇzd´ı pˇrestupn´ı stanic´ı pˇred a po pˇridán´ı inspektora.

7.1.4

Nastaven´ı simulace

Pro vˇetˇsinu experiment˚ u byla z v´ ypoˇcetn´ıch nárok˚ u pouˇzita jen jedna linka. Bylo by zaj´ımavé pozorovat, jak moc se pasaˇzéˇri adaptuj´ı ve velké s´ıti, tedy s moˇznost´ı pˇrestup˚ u. Celá s´ıt’, která je pro experimenty k dispozici nen´ı natolik komplexn´ı, aby se v n´ı ukázaly moˇznosti obj´ıˇzdˇen´ı. Prostˇred´ı agentn´ı kontroly bylo simulováno ve vˇsech experimentech po dobu 200 dn´ı. V simulovaném prostˇred´ı byla z v´ ypoˇcetn´ıch d˚ uvod˚ u zvolena velikost populace pro jednu linku rovna 300 a pro celou s´ıt’ 120. Dále pro jednoduˇsˇs´ı vyhodnocován´ı má kaˇzd´ y pasaˇzér v prostˇred´ı urˇcenou jedinou cestu, kterou bude dennˇe jezdit. Protoˇze stavov´ y prostor, kter´ y pokr´ yvá simulované prostˇred´ı pˇres cel´ y den, je velk´ y, bylo zavedeno zjednoduˇsen´ı v podobˇe simulován´ı cest zaˇc´ınaj´ıc´ıch mezi ˇsestou a osmou hodinou rann´ı. Pro simulaci bylo pouˇzito diskretizován´ı ˇcasu po 10 minutov´ ych intervalech.

7.2. EXPERIMENTY S JEDNOTLIVCI

7.2

39

Experimenty s jednotlivci

Tato ˇcást experiment˚ u se zab´ yvá základn´ım chován´ım jednotliv´ ych typ˚ u pasaˇzér˚ u a jejich adaptac´ı na zmˇeny prostˇred´ı. Je evidentn´ı, ˇze pasaˇzér zvol´ı sv˚ uj nejv´ yhodnˇejˇs´ı plán pˇri nastaven´ı správn´ ych parametr˚ u prostˇred´ı tj. pravdˇepodobnosti chycen´ı z´ıskané od experta. Pasaˇzér by v tomto pˇr´ıpadˇe zvolil jeden plán (nejv´ yhodnˇejˇs´ı), kterého by se drˇzel kaˇzd´ y den (po celou dobu simulace). Stejná situace, kdy pasaˇzér sv˚ uj plán nemˇen´ı, je bez schopnosti pasaˇzéra uˇcen´ı se zmˇenám. Pasaˇzér v této situaci v´ı, jak´ y je jeho nejv´ yhodnˇejˇs´ı plán a jiˇz nezkoumá, jestli jsou jeho informace správné. Protoˇze v modelu nen´ı fáze explorace, pasaˇzér nebude náhodnˇe zkouˇset, zda existuje nˇejaká jiná cesta, která by pro nˇej byla v urˇcité situaci v´ yhodnˇejˇs´ı. Zmˇenu plánu mohou zp˚ usobit pouze expertem ˇspatnˇe nastavené poˇca´teˇcn´ı pravdˇepodobnosti nebo zmˇena v prostˇred´ı. Pasaˇzér si zvol´ı aktuálnˇe nejv´ yhodnˇejˇs´ı plán a vlivem uˇcen´ı muˇze docházet i k postupnému zhorˇsován´ı ceny plánu aˇz do doby, kdy se pro pasaˇzéra stane v´ yhodnˇejˇs´ı jin´ y. V této ˇcásti experiment˚ u jsou nastaveny dalˇs´ı fixn´ı parametry scénáˇre a to pro poˇcet pasaˇzér˚ u roven tˇrem, jedinou moˇznou cestu a to ze stanice oznaˇcené ˇc. 63 do stanice ˇc. 60, horizont expertn´ıch znalost´ı roven 100 a denn´ı kapitál pasaˇzér˚ u pro prvn´ı ze dvou experiment˚ u ˇcin´ı 25$ a druh´ y 75$. Kapitál je takto stanoven z d˚ uvodu pozorován´ı chován´ı ´ pasaˇzéra s menˇs´ım/vˇetˇs´ım kapitálem, neˇz je velikost pokuty. Udaje o experimentech, ve kter´ ych jsou rovnomˇernˇe rozdˇelené typy pasaˇzér˚ u, shrnuje tabulka 7.3. Tabulka 7.3: Tabulka nastaven´ı experiment˚ u v prostˇred´ı s jednotlivci

7.2.1

Experiment

Cesta

Poˇ cet pasaˇ z´ er˚ u Horizont Kapit´ al

ˇc. 1

63 - 60

3

100

25

ˇc. 2

63 - 60

3

100

75

Chybn´ e poˇ c´ ateˇ cn´ı nastaven´ı v prostˇ red´ı bez inspektora

Nastavená situace v tomto experimentu spoˇc´ıvá v zobrazen´ı chován´ı pasaˇzér˚ u na ˇspatné poˇcáteˇcn´ı nastaven´ı pravdˇepodobnost´ı kontroly. V situaci se u ´myslnˇe nastav´ı informace pasaˇzér˚ um (expertn´ı informace), ˇze na u ´seku mezi stanicemi ˇc. 62 a ˇc. 61 s pravdˇepodobnost´ı 10% dojde ke kontrole inspektorem. Avˇsak ve scénáˇri nen´ı nastaven´ y

40


ˇzádn´ y inspektor. C´ıle tohoto experimentu maj´ı zjistit, jak se budou chovat jednotlivé typy pasaˇzér˚ u ve stanoveném scénáˇri.

(a) Pro kapit´ al 25$

(b) Pro kapitál 75$

Obrázek 7.2: V´ ysledek experimentu pro ekonomicky zaloˇzeného pasaˇzéra

V´ ysledky nejsou pˇr´ıliˇs pˇrekvapivé4 ekonomicky slabˇs´ı pasaˇzér si na poˇca´tku zvol´ı jako nejv´ yhodnˇejˇs´ı plán obej´ıt nebezpeˇcn´ yu ´sek. Pasaˇzér se t´ım pádem nikdy nedozv´ı, ˇze na obcházeném u ´seku nehroz´ı kontrola. Pr˚ ubˇeh je vidˇet na obrázku 7.2(a). Pasaˇzér, kter´ y má naopak vyˇsˇs´ı poˇcáteˇcn´ı kapitál, zvol´ı koupi j´ızdenky a pˇr´ımou cestu metrem. Pr˚ ujezdem zjiˇst’uje, ˇze mˇel p˚ uvodnˇe k dispozici chybnou informaci a upravuje si pravdˇepodobnosti kontroly. T´ım se mu vylepˇsuje uˇzitková hodnota j´ızdy bez j´ızdenky viz. obrázek 7.2(b).



Obrázek 7.3: V´ ysledek experimentu pro ˇcasovˇe zaloˇzeného pasaˇzéra 4

Takov´ y byl u ´mysl.

7.2. EXPERIMENTY S JEDNOTLIVCI

41

ˇ Casovˇ e zaloˇzen´ y pasaˇzér vol´ı pˇr´ımou cestu metrem s j´ızdenkou, protoˇze se mu nevyplat´ı u ´sek obcházet. Také se uˇc´ı nové informace o prostˇred´ı a ˇcasem pˇrejde na j´ızdu bez j´ızdenky viz. obrázky 7.3. V porovnán´ı tˇechto dvou pr˚ ubˇeh˚ u s rozd´ıln´ ym denn´ım kapitálem je vidˇet, jak pasaˇzérovi s niˇzˇs´ım kapitálem trvá déle, neˇz zaˇcne jezdit bez j´ızdenky. Jelikoˇz pasaˇzér má niˇzˇs´ı denn´ı rozpoˇcet, neˇz je velikost pokuty, tak by pˇriˇsel o vˇse a nav´ıc by z˚ ustal dluˇzen. Mus´ı si b´ yt jistˇejˇs´ı, ˇze ho na daném u ´seku inspektor nechyt´ı.


Obrázek 7.4: V´ ysledek


experimentu

pro

psychologicky

zaloˇzeného

pasaˇzéra

Psychologicky zaloˇzen´ y pasaˇzér s niˇzˇs´ım kapitálem zareaguje na situaci stejn´ ym zp˚ usobem jako ekonomicky zaloˇzen´ y pasaˇzér se stejn´ ym kapitálem viz. 7.4 (a). Naopak u pasaˇzéra s vyˇsˇs´ım denn´ım rozpoˇctem pˇrevládne psychika pokutován´ı a zvol´ı j´ızdenku. Na obrázku 7.4 (b) je vidˇet, ˇze za simulovanou dobu se mu nezmˇenila v´ yhodnost tohoto plánu.

7.2.2

Chybn´ e poˇ c´ ateˇ cn´ı nastaven´ı v prostˇ red´ı s inspektorem

Nastavená situace je opaˇcná, neˇz v pˇredchoz´ım pˇr´ıpadˇe. Pasaˇzér opˇet dostává mylnou informaci o prostˇred´ı a zpoˇca´tku se domn´ıvá, ˇze z poˇca´teˇcn´ıho do c´ılového m´ısta nedocház´ı k ˇza´dn´ ym kontrolám. Avˇsak je zde um´ıstˇen jeden inspektor na vstupn´ı stanici tedy na stanici oznaˇcené ˇc. 63. Inspektor na stanici stoj´ı od zapoˇcet´ı pasaˇzérovy j´ızdy 20 minut.

42


(a) Dvacet minut kontroly

(b) Patnáct minut kontroly

Obrázek 7.5: V´ ysledek v prostˇred´ı s inspektorem na vstupn´ı stanici

V této ˇcásti se vˇsichni pasaˇzéˇri zachovaj´ı obdobn´ ym zp˚ usobem. Pasaˇzéˇri si zpoˇcátku mysl´ı, ˇze na jeho cestˇe nehroz´ı ˇza´dná pokuta, zvol´ı tedy plán bez j´ızdenky. Vlivem uˇcen´ı se mu tento plán v d˚ usledku kontrol zhorˇs´ı a zkouˇsej´ı tedy nalézt jin´ y plán. Nakonec vˇsichni postupnˇe pˇrejdou na plán s j´ızdenkou viz. obrázek 7.5(a), kter´ y je reprezentantem. Obcházen´ı stanice je pro nˇe nev´ yhodné z d˚ uvodu vˇetˇs´ı vzdálenosti a t´ım pádem tento plán obsahuje penalizaci za poruˇsen´ı nutného ˇcasu dojezdu. Ze stejného d˚ uvodu se jim nevyplat´ı posunut´ı zaˇcátku odjezdu aˇz na dobu, kdy inspektor zmiz´ı. Z d˚ uvodu otestován´ı posunut´ı ˇcasu odjezdu byla sn´ıˇzena doba kontroly inspektora na 15 minut. Jak ukazuje vzorov´ y pr˚ ubˇeh na obrázku 7.5(b) vˇsichni pasaˇzéˇri si postupnˇe posunuli ˇcasy v´ yjezdu aˇz na v´ yhodnˇejˇs´ı ˇcas a tedy mohli jet bez j´ızdenky.

7.3. EXPERIMENTY S POPULACÍ

7.3

43

Experimenty s populac´ı

Tato sada, která je rozdˇelena na experimenty s jednou linkou a s celou s´ıt´ı, jiˇz pracuje s populac´ı pasaˇzér˚ u a inspektor˚ u. V experimentech se kv˚ uli zjiˇstˇen´ı dynamiky systému pouˇz´ıvaj´ı dvˇe r˚ uzná poˇca´teˇcn´ı nastaven´ı pasaˇzérova vn´ımán´ı prostˇred´ı. Jedno s chybnou apriorn´ı informac´ı, která je rovna 0% kontrole a druhá s pˇresnou, ale uniformˇe rozdˇelenou apriorn´ı informac´ı, která ˇcin´ı na jedné lince 1.1% a na celé s´ıti 0.7% pravdˇepodobnost kontroly kdekoliv. Pravdˇepodobnosti kontroly byly vypoˇc´ıtány ze strategi´ı inspektor˚ u. Pasaˇzéˇri s chybnou apriorn´ı informac´ı se zpoˇcátku domn´ıvaj´ı, ˇze nemohou b´ yt v systému kontrolovan´ı. Varianta s pˇresnou ale uniformn´ı pravdˇepodobnost´ı je v´ıce realistická, pasaˇzéˇri totiˇz tuˇs´ı, ˇze existuje nˇejaká pravdˇepodobnost kontroly ale neznaj´ı jej´ı pˇresné rozloˇzen´ı.

7.3.1

Experimenty na jedn´ e lince

Parametry pro tuto sadu experiment˚ u zobrazuje tabulka 7.4. Experimenty byly provádˇeny jak pro prostˇred´ı s deterministick´ ym5 , tak i nedeterministick´ ym6 rozvrhem inspektor˚ u a pro kaˇzdé prostˇred´ı s r˚ uznou apriorn´ı informac´ı (0%, 1.1%). Pro kaˇzdé nastaven´ı prostˇred´ı bylo provedeno ˇsest experiment˚ u (pro r˚ uzné poˇcty inspektor˚ u) s pˇeti opakován´ımi. V´ ysledky jsou tvoˇreny pr˚ umˇerem tˇechto pˇeti bˇeh˚ u. Tabulka 7.4: Tabulka nastaven´ı experiment˚ u jedné linky

Parametry

Hodnoty experiment˚ u

Populace pasaˇzér˚ u

300

Horizont znalost´ı

100

Populace inspektor˚ u 1 5

10

20

35

50

Dynamika systému je vidˇet v grafech na obrázc´ıch 7.6, na kter´ ych lze pozorovat v´ yvoj zakoupen´ ych l´ıstk˚ u v pr˚ ubˇehu celé simulace. Je moˇzné pozorovat, ˇze vˇsechny bˇehy, které jsou urˇceny nastaven´ım situace, konverguj´ı k vyváˇzenému stavu systému. V prostˇred´ı, s deterministick´ ym rozvrhem inspektor˚ u, je moˇzné pozorovat, ˇze málo statick´ ych inspektor˚ u nestaˇc´ı pokr´ yt velk´ y prostor. Pasaˇzéˇri se danému stavu prostˇred´ı pˇrizp˚ usob´ı a je zˇrejmé, ˇze k pokryt´ı prostˇred´ı a zv´ yˇsen´ı pˇr´ıjm˚ u je nutné m´ıt hodnˇe kontrol. 5 6

Inspektor si kaˇzd´ y den prov´ ad´ı stejnou strategii kontroly. Je tedy pˇredv´ıdatelné jeho chován´ı. Inspektor si kaˇzd´ y den vol´ı jinou strategii kontroly.

44


V porovnán´ı s jejich nedeterministick´ ym rozvrhem jiˇz menˇs´ı poˇcet inspektor˚ u staˇc´ı k

300

300

250

250

200

200 Pocet listku [ks]

Pocet listku [ks]

pokryt´ı daného prostˇred´ı.

150 1 inspektor 5 inspektoru 10 inspektoru 20 inspektoru 35 inspektoru 50 inspektoru

100

50

0

0

50

100 Cas [den]

150

150

100

1 inspektor 5 inspektoru 10 inspektoru 20 inspektoru 35 inspektoru 50 inspektoru

50

0

200

0

50

100 Cas [den]

150

200

(b) Chybná (0%) apriorn´ı informace s nedetermi-

tick´ ym rozvrhem inspektor˚ u

nistick´ ym rozvrhem inspektor˚ u

300

300

250

250

200


Pocet listku [ks]

(a) Chybná (0%) apriorn´ı informace s determinis-

150


100

50

0

0

50

100 Cas [den]

150

150


100

50

200

0

0

50

100 Cas [den]

150

200

(c) Pˇresná (1.1%) uniformn´ı apriorn´ı informace s (d) Pˇresná (1.1%) uniformn´ı apriorn´ı informace s deterministick´ ym rozvrhem inspektor˚ u

deterministick´ ym rozvrhem inspektor˚ u

Obrázek 7.6: V´ yvoj poˇctu zakoupen´ ych l´ıstk˚ u v prostˇred´ı jedné linky

Ustálené stavy poˇctu koupen´ ych j´ızdenek, kontrol a udˇelen´ ych pokut jsou znázornˇeny v grafech 7.7. Hodnoty l´ıstk˚ u, pokut a kontrol v grafu jsou v´ ysledkem pr˚ umˇeru za 20 posledn´ıch dn´ı. Zejména na grafu 7.7(b), kde je znázornˇené nepˇredv´ıdatelné prostˇred´ı, je vidˇet saturován´ı. Za bodem zlomu, kter´ ym je urˇcit´ y poˇcet inspektor˚ u, nen´ı dále moˇzné zvyˇsovat zisk spoleˇcnosti z d˚ uvodu poctivého chován´ı pasaˇzér˚ u tj. náhodné kontroly funguj´ı podle oˇcekáván´ı. V grafech jsou zobrazeny pr˚ ubˇehy dvou prostˇred´ı, které mˇely odliˇsnou apriorn´ı informaci.


45

300

350

300 Pocet listku,konrol a pokut [ks]

Pocet listku,konrol a pokut [ks]

250

200

150

100

Pocet koupenych listku (0%) Pocet prepravnich kontrol (0%) Pocet udelenych pokut (0%) Pocet koupenych listku (1.1%) Pocet prepravnich kontrol (1.1%) Pocet udelenych pokut (1.1%)

50

0

0

10

20 30 Pocet inspektoru [ks]

40

250

200

150 Pocet koupenych listku (0%) Pocet prepravnich kontrol (0%) Pocet udelenych pokut (0%) Pocet koupenych listku (1.1%) Pocet prepravnich kontrol (1.1%) Pocet udelenych pokut (1.1%)

100

50

0

50

0

10


40

50

(a) Prostˇred´ı s deterministick´ ym rozvrhem inspek- (b) Prostˇred´ı s nedeterministick´ ym rozvrhem intor˚ u

spektor˚ u

Obrázek 7.7: Ustálené stavy r˚ uzn´ ych nastaven´ıch situac´ı (jedna linka)

Chován´ı pasaˇzér˚ u lze ukázat na poˇctu zmˇen, které jsou donuceni udˇelat vlivem adaptace na prostˇred´ı. Na grafech 7.8, kde jsou zobrazeny pr˚ umˇerné poˇcty7 zmˇen pasaˇzér˚ uv daném prostˇred´ı, je moˇzné pozorovat, ˇze pasaˇzéˇri provedou jednu zmˇenu v deterministickém prostˇred´ı naopak v´ıce zmˇen v nedeterministickém, coˇz je logické. V histogramu 7.8(a) sice pˇrevládá poˇcet pasaˇzér˚ u, kteˇr´ı neudˇelaj´ı ˇzádnou zmˇenu. Toto je zp˚ usobeno pr˚ umˇerem pˇres vˇsechny pr˚ ubˇehy, protoˇze pˇri malém poˇctu inspektor˚ u nemus´ı hodnˇe pasaˇzér˚ u udˇelat ˇza´dnou zmˇenu. Histogram 7.8(c) ukazuje chován´ı v nedeterministickém prostˇred´ı a zde je vidˇet, ˇze v´ıce pasaˇzér˚ u zmˇenilo v´ıcekrát sv˚ uj plán. V histogramech 7.8(b) a (d) pak opˇet pˇrevládá chován´ı beze zmˇeny, coˇz je zp˚ usobeno apriorn´ı znalost´ı a

200

180

180

140 120 100 80 60 40 20 0

160 140 120 100 80 60 40 20

0

1

2

3

4

5

6

7

Pocet zmen [−]

(a)

8

9

10

0

250

Pocet pasazeru [ks]

200

160

Pocet pasazeru [ks]

180

Pocet pasazeru [ks]

Pocet pasazeru [ks]

vˇetˇsina pasaˇzér˚ u se jiˇz rozhodla pro správn´ y plán.

160 140 120 100 80 60 40

200

150

100

50

20 0

1

2

3

4

5

6

7

Pocet zmen [−]

(b)

8

9

10

0

0

1

2

3

4

5

6

7

Pocet zmen [−]

(c)

8

9

10

0

0

1

2

3

4

5

6

7

8

9

10

Pocet zmen [−]

(d)

Obrázek 7.8: Histogramy poˇctu pasaˇzér˚ u a jejich zmˇen plán˚ u (jedna linka) 7

Jedn´ a se o pr˚ umˇer vˇsech nastaven´ı poˇct˚ u inspektor˚ u v daném deterministickém/nedeterministickém

prostˇred´ı. Podrobné informace o zmˇenách pasaˇzér˚ u jsou uvedeny v tabulkách A.2, A.3, A.4 a A.5 v pˇr´ıloze A.

46

KAPITOLA 7. EXPERIMENTY Histogram (a) zobrazuje kolik pasaˇzér˚ u udˇelalo zmˇeny v plánu v prostˇred´ı s determis-

nistick´ ym rozvrhem inspektor˚ u a chybnou apriorn´ı informac´ı (0%), (b) v prostˇred´ı s determisnistick´ ym rozvrhem inspektor˚ u a pˇresnou apriorn´ı informac´ı (1.1%), (c) v prostˇred´ı s nedetermisnistick´ ym rozvrhem inspektor˚ u a chybnou apriorn´ı informac´ı (0%) a (d) v prostˇred´ı s nedetermisnistick´ ym rozvrhem inspektor˚ u a pˇresnou apriorn´ı informac´ı (1.1%).

7.3.2

Experimenty na cel´ e s´ıti

Tato sada experiment˚ u byla také provádˇena jak pro prostˇred´ı s deterministick´ ym, tak i nedeterministick´ ym rozvrhem inspektor˚ u. Kaˇzdé prostˇred´ı bylo spouˇstˇeno pro dvˇe r˚ uzné apriorn´ı informace (0%, 0.7%). Pro kaˇzdé nastaven´ı bylo provedeno ˇsest experiment˚ u pro r˚ uzn´ y poˇcet inspektor˚ u v prostˇred´ı a protoˇze se zvˇetˇsilo simulované prostˇred´ı, byl zv´ yˇsen i jejich poˇcet. Parametry experiment˚ u jsou uvedeny v tabulce 7.5.

Tabulka 7.5: Tabulka nastaven´ı experiment˚ u celé s´ıtˇe

Parametry

Hodnoty experiment˚ u

Populace pasaˇzér˚ u

120

Horizont znalost´ı

100

Populace inspektor˚ u 5

10

25

50

75

100

V celé s´ıti se nab´ız´ı vyzkouˇset, jak se zachovaj´ı pasaˇzéˇri na pˇrestupn´ı stanici v pˇr´ıpadˇe, ˇze se na n´ı pravidelnˇe objevuje inspektor. Bylo sledováno, jak se v ˇcase zmˇen´ı situace na pˇrestupn´ı a okoln´ıch stanic´ıch (poˇcet pasaˇzér˚ u, kteˇr´ı pˇres n´ı proj´ıˇzdˇej´ı) pˇred a po um´ıstˇen´ı inspektora. Situace, která je v okol´ı pˇrestupn´ı stanice, je znázornˇena na obrázku 7.9. Vˇsem pasaˇzér˚ um byla nastavena stejná trasa ze stanice ˇc. 21 do ˇc. 62. Na pˇrestupn´ı stanici ˇc. 12 byl v dobu jejich pr˚ ujezdu (pˇrestupu) um´ıstˇen inspektor na 10 minut (ˇcasové rozmez´ı 8:50 aˇz 9:00). Pr˚ ujezdnost ukázaná v tabulce 7.6 se pˇres pˇrestupn´ı stanici zmˇenila a v´ ysledná pr˚ ujezdnost je znázornˇena v tabulce 7.7. Z tabulek je vidˇet, ˇze vˇetˇsina pasaˇzér˚ u vol´ı pˇrestup mezi stanicemi ˇc. 12 a ˇc. 57 a j´ızdu bez j´ızdenky. Postupnˇe se nauˇc´ı, ˇze v danou dobu na stanici je inspektor a tedy zvol´ı posunut´ı ˇcasu odjezdu, nˇekteˇr´ı obcházej´ı stanici a ostatn´ı si koup´ı j´ızdenku.


47

Obrázek 7.9: Znázornˇen´ı situace na pˇrestupn´ı stanici

Tabulka 7.6: Poˇcet proj´ıˇzdˇej´ıc´ıch pasaˇzér˚ u stanicemi pˇred um´ıstˇen´ım inspektora

V´ ystupy ze stanice

Vstupy do stanice

ˇ Cas

ˇc. 11

ˇc. 12

ˇc. 57

ˇc. 56

8:50 - 9:00

4

116

0

0

9:00 - 9:10

0

0

116

0

9:40 - 9:50

0

0

0

4

Tabulka 7.7: Poˇcet proj´ıˇzdˇej´ıc´ıch pasaˇzér˚ u stanicemi po um´ıstˇen´ım inspektora

V´ ystupy ze stanice

Vstupy do stanice

ˇ Cas

ˇc. 11

ˇc. 12

ˇc. 57

ˇc. 56

8:50 - 9:00

4

23

0

0

9:00 - 9:10

0

39

62

0

9:20 - 9:30

0

0

54

0

9:40 - 9:50

0

0

0

4

Dynamika systému v celé dopravn´ı s´ıt’ je obdobná jako dynamika jedné linky (viz. pˇr´ıloha ...). Na grafech 7.10, ve kter´ ych jsou hodnoty pr˚ umˇerem za 20 posledn´ıch dn´ı, jsou

48


zobrazeny v´ ysledky v ustáleném stavu tj. poˇcet koupen´ ych j´ızdenek, kontrol a udˇelen´ ych pokut v závislosti na poˇctu inspektor˚ u v systému. Na grafu 7.10 vlevo jsou pr˚ ubˇehy s deterministick´ ym rozvrhem inspektor˚ u a vpravo s nedeterministick´ ym. V porovnáván´ı v´ ysledk˚ u z obou prostˇred´ı je moˇzné si vˇsimnout, ˇze v nepˇredv´ıdatelném prostˇred´ı je v´ıce pasaˇzér˚ u donuceno si koupit j´ızdenku, neˇz v prostˇred´ı pˇredv´ıdatelném.

100

100 Pocet listku,konrol a pokut [ks]

120

Pocet listku,konrol a pokut [ks]

120

80


40

20

0

0

20


80

80


40

20

0

100

0

20


80

100

(a) Prostˇred´ı s deterministick´ ym rozvrhem inspek- (b) Prostˇred´ı s nedeterministick´ ym rozvrhem intor˚ u

spektor˚ u

Obrázek 7.10: Ustálené stavy r˚ uzn´ ych nastaven´ıch situac´ı (celá s´ıt’)

Histogramy 7.11 ukazuj´ı zmˇeny pr˚ umˇerného poˇctu pasaˇzér˚ u v pˇredv´ıdatelném obrázek

45

40 35 30 25 20 15 10 5 0

40 35 30 25 20 15 10 5

0

1

2

3

4

5

6

7

Pocet zmen [−]

(a)

8

9

10

0

0

1

2

3

4

5

6

7

Pocet zmen [−]

(b)

8

9

10

70

70

60

60

Pocet pasazeru [ks]

50

45

Pocet pasazeru [ks]

50

Pocet pasazeru [ks]

Pocet pasazeru [ks]

vlevo a nepˇredv´ıdatelném prostˇred´ı. I je podobná situace jako v prostˇred´ı jedné linky.

50 40 30 20 10 0

50 40 30 20 10

0

1

2

3

4

5

6

7

Pocet zmen [−]

(c)

8

9

10

0

0

1

2

3

4

5

6

7

Pocet zmen [−]

8

9

10

(d)

Obrázek 7.11: Histogramy poˇctu pasaˇzér˚ u a jejich zmˇen plán˚ u (celá s´ıt’)

Histogram (a) zobrazuje, kolik pasaˇzér˚ u udˇelalo zmˇeny v plánu v prostˇred´ı s determisnistick´ ym rozvrhem inspektor˚ u a chybnou apriorn´ı informac´ı (0%), (b) v prostˇred´ı s determisnistick´ ym rozvrhem inspektor˚ u a pˇresnou apriorn´ı informac´ı (0.7%), (c) v prostˇred´ı s nedetermisnistick´ ym rozvrhem inspektor˚ u a chybnou apriorn´ı informac´ı (0%) a (d) v prostˇred´ı s nedetermisnistick´ ym rozvrhem inspektor˚ u a pˇresnou apriorn´ı informac´ı (0.7%).

´ ˇ Í A PAME ˇ TOV ˇ ´ NAROKY ´ 7.4. VYPO CETN E

7.4

49

V´ ypoˇ cetn´ı a pamˇ et’ov´ e n´ aroky

Experimenty byly provádˇeny na notebooku vybaven´ y procesorem Intel Core i5 2520M s frekvenc´ı 2,5 GHz (2 jádra / 4 vlákna) a pamˇet´ı 4GB DDR3. Dobu v´ ypoˇctu a pamˇet’ové nároky jsou uvedeny v tabulce 7.8, které ovˇsem závis´ı na nastaven´ı simulace (poˇcet pasaˇzér˚ u a inspektor˚ u). Tabulka 7.8: V´ ypoˇcetn´ı nároky simulace

Prostor

Pr˚ umˇerná v´ ypoˇcetn´ı doba

Pr˚ umˇerné nároky na pamˇet’

Jedna linka Celá s´ıt’

1 minuta

0.5 (max 0.5) GB

24 minut

1.2 (max 1.5) GB

V´ ypoˇcetn´ı i pamˇet’ov´ y nár˚ ust na celé s´ıti, oproti jedné lince, je zp˚ usoben vˇetˇs´ım prostorem k prohledán´ı. V´ ypoˇcetn´ı doba stoupla pˇreváˇznˇe kv˚ uli vˇetˇs´ımu faktoru vˇetven´ı a vˇetˇs´ı hloubce prohledávaného stromu. Pamˇet’ová nároˇcnost se zvˇetˇsila v d˚ usledku vˇetˇs´ı s´ıtˇe s vyˇsˇs´ım poˇctem dopravn´ıch prostˇredk˚ u a pouˇz´ıván´ım v´ıce objekt˚ u v plánován´ı.

7.5

Shrnut´ı

Experimenty ovˇeˇruj´ı, ˇze implementace systému dopravn´ı spoleˇcnosti se chová intuitivn´ım zp˚ usobem tj. pasaˇzéˇri se adaptuj´ı na aktuáln´ı prostˇred´ı. Dynamika celého systému - pˇri pouˇzit´ı celé dopravn´ı s´ıtˇe - je obdobná jako dynamika jedné linky. Systém vˇzdy konverguje do vyváˇzeného stavu. Z ustálen´ ych stav˚ u vypl´ yvá, ˇze v pˇredv´ıdatelném prostˇred´ı je k sn´ıˇzen´ı u ńiku zisk˚ u zapotˇreb´ı v´ıce inspektor˚ u, neˇz v prostˇred´ı nepˇredv´ıdatelném, napˇr. v´ ysledná hladina u ńiku zisk˚ u jedné linky je pro 35 deterministick´ ych inspektor˚ u srovnatelná s 5 - 10 nedeterministik´ ymi inspektory. Náhodn´ ym pohybem inspektoˇri pokr´ yvaj´ı vˇetˇs´ı prostor a udrˇzuj´ı rozloˇzenou m´ıru pravdˇepodobnosti kontroly. Pravdˇepodobnost kontroly nebude pˇri statick´ ych kontrolách normálnˇe rozloˇzená. Statiˇct´ı inspektoˇri na sv´ ych m´ıstech zvyˇsuj´ı pravdˇepodobnost kontroly na u ´kor ostatn´ıch m´ıst, ve kter´ ych se pasaˇzéˇri mohou nauˇcit cestovat, tedy bez j´ızdenky bez vˇetˇs´ıho rizika.

50


Kapitola 8 Z´ avˇ er Touto diplomovou prac´ı jsem z´ıskal pˇrehled o silné simulaˇcn´ı technice agetn´ıho modelován´ı. Experimentálnˇe jsem vyhodnotil fungován´ı modelu s pˇrihlédnut´ım vlivu jednotliv´ ych faktor˚ u, ovlivˇ nuj´ıc´ıch rozhodnut´ı pasaˇzéra - ekonomické, psychologické a ˇcasové faktory. Do navrˇzeného plánovac´ıho algoritmu, kter´ y hledá v´ yhodné cesty prostˇredky veˇrejné dopravy, jsem implementoval model cestuj´ıc´ıho jako adaptivn´ıho agenta, kter´ y byl integrován do simulaˇcn´ı platformy. Pˇrestoˇze je uˇc´ıc´ı model pro pouˇzité dopravn´ı s´ıtˇe, které nejsou pˇr´ıliˇs sloˇzité, dostaˇcuj´ıc´ı, existuje moˇznost vylepˇsen´ı. Pˇridat do uˇcen´ı fázi explorace, tedy celé uˇcen´ı s posilován´ım. Náhodné prozkoumáván´ı jin´ ych cest m˚ uˇze vést k odhalen´ı lepˇs´ıho plánu. Dalˇs´ım vylepˇsen´ım pasaˇzérovy adaptace na prostˇred´ı je pˇridán´ı interakce i mezi pasaˇzéry napˇr. pomoc´ı sociáln´ıch s´ıt´ı nebo vymˇen ˇován´ı informac´ı pˇr´ımo pˇri cestován´ı. Taková interakce by vedla k prozkoumán´ı vˇetˇs´ıho tˇreba i nenavˇst´ıveného prostoru, coˇz by bylo v´ yhodné pˇri cestován´ı do m´ıst, kde pasaˇzér ˇcasto nejezd´ı. Pro reálné pouˇzit´ı a vyhodnocován´ı agentn´ıho modelu pˇrepravn´ı kontroly, je nutné v simulaci nastavit skuteˇcné hodnoty a parametry prostˇred´ı tj. poˇcty pasaˇzér˚ u atd.. Simulace provádˇená v této práci je pouze ilustrativn´ı, ovˇeˇruje správnost a intuitivn´ı chován´ı navrˇzeného modelu. V uvedené simulaci je málo pasaˇzér˚ u, k pˇretˇeˇzován´ı inspektor˚ u nedocház´ı, proto je i vˇetˇs´ı pravdˇepodobnosti kontroly, coˇz implikuje rychlejˇs´ı konvergenci systému a ve v´ ysledku ménˇe udˇelen´ ych pokut. Dopravn´ı spoleˇcnosti by mohly, tuto simulaci vyuˇz´ıvat k maximalizaci zisk˚ u tj. optimalizován´ı poˇctu inspektor˚ u v systému, dále k ovˇeˇren´ı a vytváˇren´ı strategi´ı sv´ ych inspektor˚ u. Ze sledován´ı dynamiky systému by mohly zjiˇst’ovat, po jaké dobˇe je dobré zmˇenit rozloˇzen´ı nebo celé strategie inspektor˚ u, protoˇze se jiˇz pasaˇzéˇri nauˇcili jejich chován´ı. Simulátor poskytuje ovˇeˇren´ı, ˇze pˇri statick´ y kontrolách je potˇrebné pouˇz´ıt vˇetˇs´ı mnoˇzstv´ı 51

´ ER ˇ KAPITOLA 8. ZAV

52

inspektor˚ u, coˇz sniˇzuje zisky dopravn´ı spoleˇcnosti. Ze simulace dopravn´ıho sytému je moˇzné z´ıskat informace o stanic´ıch ˇci u ´sec´ıch, na kter´ ych se nejv´ıce pohybuj´ı neplat´ıc´ı pasaˇzéˇri, tedy m˚ uˇze odhalit slabá m´ısta v kontrole dopravn´ı s´ıtˇe. Problematika pˇrepravn´ı kontroly v s´ıt´ıch veˇrejné dopravy a u ńiky zisk˚ u dopravn´ıch spoleˇcnost´ı, které zp˚ usobuj´ı neplat´ıc´ı cestuj´ıc´ı, je aktuáln´ı téma. U simulovaného modelu jsou zohlednˇeny pouze hlavn´ı faktory ovlivˇ nuj´ıc´ı rozhodován´ı pasaˇzér˚ u, kter´ ych je ve skuteˇcnosti v´ıce. S v´ yvojem nov´ ych technologi´ı jako jsou napˇr. chytré telefony a aplikace v nich, vzniká vˇetˇs´ı a rychlejˇs´ı informovanost o prostˇred´ı veˇrejné dopravy a t´ım i rychlejˇs´ı adaptace cestuj´ıc´ıch. I na takovou situaci se vyvinut´ y model, d´ıky vyuˇzit´ı agentn´ıho modelován´ı, dá snadno pˇrizp˚ usobit.

Literatura Bonabeau, E. (2002), ‘Agent-based modeling: Methods and techniques for simulating human systems’, 99, 7280–7287. Borshchev, A. a Filippov, A. (2004), From system dynamics and discrete event to practical agent based modeling: Reasons, techniques, tools, in ‘The 22nd International Conference of the System Dynamics Society’. Boyd, C., Martini, Ch., Rickard, J. a Russell, A. (1989), ‘Fare evasion and noncompliance’, Journal of transport economics and policy . Clausen, J. (1999), Branch and bound algoritms - principles and examples, Technical report, Deparment of Computer Science, University of Copenhagen. Jakob, M., Moler, Z., Komenda, A., Yin, Z., Jiang, A., X., Johnson, M., P., Pechoucek, M. a Tambe, M. (2012), Agentpolis: Towards a platform for fully agent-based modeling of multi-modal transportation (demonstration), in ‘12th International Conference on Autonomous Agents and Multiagent Systems (to appear)’. Killias, M., Scheidegger, D. a Nordenson, P. (2009), ‘The effects of increasing the certainty of punishment’, Criminology 6. Kooreman, P. (1993), ‘Fare evasion as a result of expected utility maximisation’, Journal of transport economics and policy . Leung, L., F. (2003), A study of fare evasion in railway systems in hong kong, Master’s thesis, The University of Hong Kong. Moler, Z. (n.d.), Fare evasion abm req spec and analysis example, Technical report, ˇ Katedra poˇc´ıtaˇc˚ u, FEL CVUT. Nagy, I., Nedoma, P., Kratky, M., Pavelkova, L. a Ettler, P. (2002), ‘O bayesovském uˇcen´ı’, Automa 7, 56–61. 53

54

LITERATURA

Piliavin, I., Thornton, C., Gartner, R. a Matsueda, R., L. (1986), ‘Crime, deterrence, and rational choice’, American Sociological Review 51, 101–119. Vidal, J., M. (2010), Fundamentals of multiagent system with netlogo examples, in ‘Fundamentals of Multiagent System’.

Pˇ r´ıloha A N´ azev pˇ r´ılohy

Rozmez´ı pˇ r´ıjm˚ u

Poˇ cet dom´ acnost´ı

Ménˇe neˇz $10,000:

169738

$10,000 aˇz $14,999:

96131

$15,000 aˇz $19,999:

91434

$20,000 aˇz $24,999:

90634

$25,000 aˇz $29,999:

83895

$30,000 aˇz $34,999:

79625

$35,000 aˇz $39,999:

68487

$40,000 aˇz $44,999:

62754

$45,000 aˇz $49,999:

54614

$50,000 aˇz $59,999:

91959

$60,000 aˇz $74,999:

106186

$75,000 aˇz $99,999:

107198

$100,000 aˇz $124,999:

61105

$125,000 aˇz $149,999:

33453

$150,000 aˇz $199,999:

32418

$200,000 a v´ıce:

46978

Tabulka A.1: Pˇr´ıjmy pr˚ umˇerné tˇr´ıˇclenné domácnosti v LA

I

ˇ ÍLOHA A. NAZEV ´ ˇ ÍLOHY PR PR

II

Tabulka A.2: Zmˇeny plán˚ u v pˇredv´ıdatelném prostˇred´ı, 0%, jedna linka

Poˇcet pasaˇzér˚ u Poˇ cet inspektor˚ u

0

1

2

3

4

5 6

7

8

9

10 a v´ıce

1 inspektor

288

10

0

2

0

0

0

0

0

0

0

5 inspektor˚ u

243

51

0

4

0

2

0

0

0

0

0

10 inspektor˚ u

200

88

1

8

0

1

0

0

0

0

2

25 inspektor˚ u

129 155

5

7

1

0

1

0

0

0

2

35 inspektor˚ u

65

208

6

9

5

3

1

0

0

0

3

50 inspektor˚ u

50

230

5

4

3

2

1

2

0

0

3

Tabulka A.3: Zmˇeny plán˚ u v nepˇredv´ıdatelném prostˇred´ı, 0%, jedna linka


0

1

2

3

4

5

6

7

8

9

10 a v´ıce

1 inspektor

168

79

15

19

8

4

5

2

0

0

0

5 inspektor˚ u

68

156

10

38

4

12

5

2

1

2

2

10 inspektor˚ u

39

198

8

32

4

7

1

3

0

1

7

25 inspektor˚ u

20

234

10

16

7

3

0

4

1

0

5

35 inspektor˚ u

14

247

9

14

3

3

1

1

0

1

7

50 inspektor˚ u

11

253

11

12

2

4

0

0

1

0

6

Tabulka A.4: Zmˇeny plán˚ u v pˇredv´ıdatelném prostˇred´ı, 1.1%, jedna linka


2

3

4

5 6

7

8

9

10 a v´ıce

193 107

0

0

0

0

0

0

0

0

0

5 inspektor˚ u

195

97

3

4

1

0

0

0

0

0

0

10 inspektor˚ u

197

96

0

5

0

0

0

0

1

0

1

25 inspektor˚ u

197

91

6

3

1

0

1

0

0

0

1

35 inspektor˚ u

203

84

9

2

1

0

0

0

0

0

1

50 inspektor˚ u

196

96

3

2

2

0

0

0

0

0

1

1 inspektor

0

1

III Tabulka A.5: Zmˇeny plán˚ u v nepˇredv´ıdatelném prostˇred´ı, 1.1%, jedna linka


0

1

2

3

4

5

6

7

8

9

10 a v´ıce

1 inspektor

239 22

19

4

9

4

0

1

2

0

0

5 inspektor˚ u

237 27

8

14

3

4

2

0

1

1

3

10 inspektor˚ u

215 50

11

14

2

4

1

2

0

1

0

25 inspektor˚ u

203 79

2

11

0

1

1

1

0

0

2

35 inspektor˚ u

197 81

11

8

0

1

0

0

0

0

2

50 inspektor˚ u

196 93

2

5

1

0

0

0

1

0

2


120

120

100

100

80


Pocet listku [ks]

IV

60

5 inspektoru 10 inspektoru 25 inspektoru 50 inspektoru 75 inspektoru 100 inspektoru

40

20

0

0

50

100 Cas [den]

150

60


40

20

0

200

0

50

100 Cas [den]

150

200

(b) Chybná (0%) apriorn´ı informace s nedetermi-

tick´ ym rozvrhem inspektor˚ u

nistick´ ym rozvrhem inspektor˚ u

120

120

100

100

80


Pocet listku [ks]

(a) Chybná (0%) apriorn´ı informace s determinis-

60


40

20

0

0

50

100 Cas [den]

150

60


40

20

0

200

0

50

100 Cas [den]

150

200

(c) Pˇresná (0.7%) uniformn´ı apriorn´ı informace s (d) Pˇresná (0.7%) uniformn´ı apriorn´ı informace s deterministick´ ym rozvrhem inspektor˚ u

deterministick´ ym rozvrhem inspektor˚ u

Obrázek A.1: V´ yvoj poˇctu zakoupen´ ych l´ıstk˚ u v prostˇred´ı celé s´ıtˇe

Tabulka A.6: Zmˇeny plán˚ u v pˇredv´ıdatelném prostˇred´ı, 0%, celá s´ıt’


0

1

2

3

4

5

6

7

8

9

10 a v´ıce

5 inspektor˚ u

98

15

1

0

0

1

0

0

1

0

4

10 inspektor˚ u

80

30

2

2

0

0

0

0

0

0

6

25 inspektor˚ u

42

53

5

4

2

1

2

1

0

1

9

50 inspektor˚ u

30

62

6

4

2

3

5

0

2

0

6

75 inspektor˚ u

22

65

6

8

5

2

3

1

1

0

7

100 inspektor˚ u

20

70

5

6

5

1

4

1

2

0

6

V Tabulka A.7: Zmˇeny plán˚ u v nepˇredv´ıdatelném prostˇred´ı, 0%, celá s´ıt’


0

1

2

3

4

5

6

7

8

9

10 a v´ıce

5 inspektor˚ u

27 48

4

16

4

4

2

4

0

2

9

10 inspektor˚ u

21 59

2

10

6

4

4

2

1

1

10

25 inspektor˚ u

17 68

3

9

2

1

3

4

1

3

9

50 inspektor˚ u

15 71

5

7

3

4

0

4

2

0

9

75 inspektor˚ u

15 73

6

7

3

2

0

2

3

1

8

100 inspektor˚ u

15 73

7

5

5

0

2

2

3

0

8

Tabulka A.8: Zmˇeny plán˚ u v pˇredv´ıdatelném prostˇred´ı, 0.7%, celá s´ıt’


0

1

2

3

4

5

6

7

8

9

10 a v´ıce

5 inspektor˚ u

97 15

1

2

0

0

0

0

1

0

4

10 inspektor˚ u

80 30

2

2

0

0

0

0

0

0

6

25 inspektor˚ u

40 57

4

2

2

3

0

1

1

0

10

50 inspektor˚ u

30 62

6

4

2

3

5

0

2

0

6

75 inspektor˚ u

22 65

6

8

5

2

3

1

1

0

7

100 inspektor˚ u

21 70

5

6

5

2

2

1

2

0

6

Tabulka A.9: Zmˇeny plán˚ u v nepˇredv´ıdatelném prostˇred´ı, 0.7%, celá s´ıt’

Poˇcet pasaˇzér˚ u 1

2

3

4

5

6

7

8

9

10 a v´ıce

5 inspektor˚ u

28 47

3

13

3

8

5

1

1

0

11

10 inspektor˚ u

21 57

4

12

5

6

0

3

2

2

8

25 inspektor˚ u

17 67

4

11

2

3

0

2

4

1

9

50 inspektor˚ u

16 72

7

5

3

2

1

3

1

1

9

75 inspektor˚ u

15 73

6

7

3

2

0

2

3

1

8

100 inspektor˚ u

15 73

8

5

7

0

2

0

1

1

8

Poˇ cet inspektor˚ u

0

VI


Pˇ r´ıloha B Obsah pˇ riloˇ zen´ eho CD K této práci je pˇriloˇzeno CD, na kterém jsou uloˇzeny zdrojové kódy. ˇ anky: • Cl´ • Experimenty: • Obrázky: – Grafy – Diagramy • Zdrojové kódy: – Pomocné kódy: ∗ Kódy pro pˇredzpracován´ı ∗ Kódy pro generován´ı dat ∗ Spouˇstˇec´ı kód ∗ Vyhodnocovac´ı kód – Pˇrepravn´ı kontrola – Spustiteln´ y soubor

VII

Fakulta elektrotechnická. Agentní model přepravní kontroly ve

Recommend Documents