MATSim

A MATSim (Multi-Agent Transport Simulation) egy aktivitás-alapú, multi-agent közlekedési szimulációs keretrendszer, melynek elsődleges célja a forgalom és a torlódások szimulálása, de egyéb alkalmazási is léteznek. Java-ban fejlesztették és nyílt forráskódú. Könnyen kiterjeszthető, és moduláris jellege miatt a részegységei könnyen lecserélhetőek más implementációkra.

Bevezetés

A MATSim célja egyetlen nap közlekedésének szimulálása. A közlekedésnek rengeteg, akár 10^7 résztvevője lehet.

A program a co-evolúciós elvet használja, melynek lényege az hogy a résztvevők újra és újra optimalizálják a napi aktivitásukat miközben egymással versengenek a közlekedési infrastruktúrában. Minden résztvevő memóriájában eltárolunk egy rögzített mennyiségű napi tervet: egy napi terv egy aktivitási láncból és a hozzá tartozó hasznossági pontból áll. Az aktivitási láncokat empirikus adatok alapján készítjük, a hozzájuk tartozó pontokra pedig úgy érdemes gondolni, mint a tevékenységlánc egyfajta gazdasági hasznosságára.

Egy MATSim futás konfigurálható számú iterációból áll. Minden iterációban, mielőtt a résztvevők megkezdenék a mobilitási szimulációt (mobsim), kiválasztanak egy napi tervet a memóriájukból, majd végrehajtják a mobilitási szimulációt, végül pedig megváltoztatják a napi terveikhez tartozó hasznossági pontokat. A napi terv kiválasztása függ a tervek hasznossági pontjától. A résztvevők egy bizonyos százaléka (például 10%) számára megengedett, hogy a kiválasztott tervet klónozzák és módosítsák: ezt a folyamatot hívják újratervezésnek.

Az újratervezést az újratervező modulok hajtják végre. Általában egy tervnek négy elemeét veszik figyelembe: indulási időpont, útvonal, mód és célállomás (és ezáltal implicit módon az aktivitás hosszát is). További szempontok is figyelembe vehetők, mint például aktivitások hozzáadása vagy elvetése, parkolás, stb., de ezek egyelőre csak kísérleti stádiumban részei a MATSimnek. Az újratervező funkciók különböző stratégiákat alkalmazhatnak: lehet, hogy a fenti szempontok közül az egyiket véletlen mutációval változtatja, míg egy másikat a úgy, hogy a számára lehető léegjobbat választja ki (Best response). Ha az újratervezés eredményeként egy résztvevőnek túl sok terve lesz (a tervek száma konfigurálható), akkor a legkisebb pontszámú tervet elveti.

Azok a résztvevők, akik nem terveznek újra, választanak egy tervet a memóriájukból valamilyen választási stratégia alapján. Ezután az összes résztvevő számára végrehajtódik a mobsim, vagyis a mobilitási szimuláció, ami egy napnak felel meg. A nap végén a résztvevők pontozzák az aznap végrehajtott tervüket. A napok iterációját addig ismételjük, amíg az átlagos pontszám stabilizálódik.

A közelekedési folyam modellje

A szimulációnak a magja magának a közlekedésnek a szimulálása. Ez a MATSim közlekedési szimulálójával (röviden mobsim) történik. A közelekedés szimulációja szempontjából a következő eseteket különböztethetjük meg:

• fizikai szimulációk, melyek tartalmazzák a járművek részletes követési modelljeit
• cellular automata, ahol az utak helyett cellákat használunk
• sor-alapú szimulációk, ahol a közelekedés dinamikáját várakozási sorokkal modellezzük
• makroszkopikus modellek, ahol nem különálló egységeket (autókat) tekintünk, hanem a folyamot egy egészként

A MATSim modellje

A MATSim, mivel nagy méretű modellekre tervezték, a kevésbé számításigényes sor-alapú szimulációt használja, a következő módon: amikor egy résztvevő (jármű) belép a hálózat egy élére (egy útszakaszra), akkor hozzáadódik az útszakasz kilépését modellező várakozási sorhoz. A jármű akkor léphet ki az útszakaszról, ha az alábbi feltételek mindegyike teljesül:

• eltelt annyi idő, amennyi szükséges volna az útszakasz bejárásához, ha az üres lenne (úgynezevett free flow)
• a várakozási sor elején van
• a következő él (útszakasz) megengedi a belépést

Ez a megközelítés számítsi szempontból nagyon hatékony, de leegyszerűsítő: a valóságban a járművek lassaban közlekednek, ha egy másik járművet követve kell lassítaniuk (megállniuk) vagy gyorsítaniuk (elindulniuk). Ezek az úgynevezett járműkövetési hatások, amiket a fenti modell figyelmen kívül hagy.

A MATSim hálózati modellje nagyban függ az élek (útszakaszok) két fontos paraméterétől: tárolási kapacitás (storage capacity) és folyam kapacitás vagy kimeneti kapacitás (flow capacity). Az előbbi azt mondja meg, hogy hány jármű fér rá egy adott útszakaszra, míg az utóbbi azt, hogy egy adott időegység alatt hány jármű tudja elhagyni az útszakaszt.

Beépített mobsimek

A MATSim két beépített mobsimet bocsát rendelkezésünkre: a QSim-et és a JDEQSim-et (Java Discrete Event Queue Simulation). A két beépített mobsimtől eltérő szimulációs modellt is használhatunk, volt már példa a C++-ben írt DEQSim (Discrete Event Queue Simulation) hozzákapcsolására a MATSimhez, de beépített funkciókként csak a fenti kettő szimulációs modellt kapjuk.

A több szálon futó QSim a MATSim default szimulációs modellje. Egy idő alapú (time-step) implementációt használ, vagyis az idő múlását kicsiny lépésekben szimulálja. Ezzel szemben a JDEQSim (számítási okokból) a sor alapú hozzáállást egy eseményvezérelt implementációval kombinálja. Így nincs idő alapú szimuláció és így garantált, hogy a járművekhez csak akkor nyúlunk hozzá, ha arra valóban szükség van (vagyis ha egy műveletet kivált egy esemény). Az eseményeket egy global scheduler menedzseli.

További fontos különbség a beépített mobsimek között, hogy a JDEQSim megengedi, hogy az élekhez egy bemeneti kapacitást is definiáljunk (a fent említett tárolási és kimeneti kapacitás mellé). A QSimben nincsen ilyen lehetőség, így a bemeneti kapactisának nincsen felső értéke. Ez azt jelenti, hogy bár az útszakaszon tartózkodó járművek számának van felső határa (storage capacity), az útra belépésnek nincs.

A MATSim co-evolúciós algoritmusa

A co-evolúciós algoritmusok különböző fajokat (co-)evolválnak, akik rendszeres interakcióban (versenyben) vannak egymással. Az evoluciós algoritmusok - leegyszerűsítve - a rendszer valamilyen optimumát keresik, hiszen az optimalizációt egy globális fitness függvény biztosítja. Ezzel szemben a co-evolúciós algoritmusok nem a rendszer optimumát keresik, hanem egy sztochasztikus, fajra vonatkozó optimumot, hiszen itt nincsen globális (mindenkire ugyanúgy érvényes) fitness függvény.

A MATSim-ben minden résztvevő a co-evolúciós algoritmus egy fajának felel meg, a résztvevő tervei pedig a faj egyedeinek. A co-evolúciós algoritmusban az optimalizáció a résztvevők terveire (vagyis a napi tervekre, tevékenységekre és utazásukra) vonatkozik. Idővel a rendszer el fog érni egy (bizonyos korlátokkal szabályozott) egyensúlyi állapotot, ahol a résztvevők nem fogják tudni tovább javítani a napi terveiket.