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.

A MATSim elindítása

A MATSim elindításához látogassunk el a MATsim weboldalára, és töltsük le a legutóbbi verziót. A letöltött tömörített fájl kicsomagolása után csak annyi dolgunk van, hogy duplán kattintsunk a matsim .jar fájljára, és az alkalmazás már el is indult.

A szoftver automatikusan felismeri a gépünkön futó Java verzióját és könyvtárát. Amennyiben ez nem történt meg, tallózzuk be a könyvtárat, ahol a JRE könyvtárunkat. A MATSim futtatásához legalább 7-es verziójú Java szükséges.

A MATSim futtatásához be kell tallózzunk egy konfigurációs filet, minden beállítható paraméterünket ez fogja tartalmazni. A letöltött csomag több példakonfigurációt is tartalmaz, ezeket megtaláljuk az example mappában. Amennyiben a programunk elindítás után hibát dob, abban az esetben nyissuk meg a konfigurációs fájlt és az abban megadott network és plans modulok elérhetőségi útját módosítanunk kell, a megadott elérési út elé illesszük be, hogy "../../". Tehát például ha a megadott elérési út "examples/equil/network.xml", akkor ezt módosítsuk "../../examples/equil/network.xml"-re. Ennek az az oka, hogy a szotfver valamiért a Java könyvtárunkhoz képest próbálja megtalálni a konfigurációs file-ban hivatkozott egyéb fileokat, nem pedig a konfigurációs filehoz képest.

A program paramétereit a konfigurációs fájlokban állíthatjuk be.

A konfigurációs fájlok létrehozása

A konfigurációs fájlok XML fájlok. A fő konfigurációs fájlon kívül egyéb XML fájlokat is meg kell adjunk, például olyanokat amik az úthálózatot vagy olyat ami a napi terveket definiálják.

A hálózat megadása

A hálózat megadása XML formátumban történik, ahol az úthálózat pontjait (vagyis a kereszteződéseket) node tag-ek között kell megadni, ezeket pedig nodes tagek közé rendezni. Az úthálózat éleit (vagyis magukat az utakat) hasonlóképpen lehet megadni, csak link illetve links tagekkel.

Az úthálózat egy node-jának van egy egyedi azonosítója, ezen kívül pedig egy x és egy y koordinátája. A MATSim a távolságszámítást egyszerűen Pithagorasz tétellel végzi, így nyomatékosan kérik a felhasználókat, hogy ne WGS84-es, vagy hasonló gömbi koordinátákat használjanak a MATSim default beállításaival. Derékszögű koordinátarendszert javasolnak, ahol egy koordinátányi távolság egy méternek felel meg.

Az úthálózat linkjeinek már sokkal több paramétere lehet:

• id: az él egyedi azonosítója
• from: az él forrásául szolgáló csúcs azonosítója
• to: az él céljául szolgáló csúcs azonosítója
• length: az él hossza. A javasolt mértékegység a méter, de más is használható, amennyiben ezek az összes konfigurációs fájlban összhangban vannak
• capacity: az él kapacitása, vagyis ahány jármű áthaladhat rajta egy időegység (javasolt: óra) alatt
• freespeed: az a sebesség, amivel a járművek haladnak az élen, amennyiben azon nincs torlódást okozó forgalom (méter per másodperc a javasolt mértékegység)
• permlanes: az él által reprezentált úton rendelkezésünkre álló sávok száma
• modes: a járműtípusok, akik használhatják a sávot. Több is megadható vesszővel elválasztva, például car, bike, taxi.

Megjegyzendő, hogy minden él rendelkezik irányítással, és így egyirányú utaknak felelnek meg. Amennyiben kétirányú utat szeretnénk szmulálni, úgy a linket kétszer kell felvenni a listánkba, alternáló from és to attribútumokkal.

Nézzünk egy példahálózatot:

<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE network SYSTEM "http://www.matsim.org/files/dtd/network_v1.dtd">

<network name="equil test network">
   <nodes>
      <node id="1" x="-20000" y="0"/>
      <node id="2" x="-15000" y="0"/>
      <node id="3" x="-865" y="5925"/>
      <node id="4" x="-2498" y="4331"/>
      <node id="5" x="-3829" y="3215"/>
   </nodes>
   <links capperiod="01:00:00">
      <link id="1" from="1" to="2" length="10000.00" capacity="36000" freespeed="27.78" permlanes="1"  />
      <link id="2" from="2" to="3" length="10000.00" capacity="3600" freespeed="27.78" permlanes="1"  />
      <link id="3" from="2" to="4" length="10000.00" capacity="3600" freespeed="27.78" permlanes="1"  />
      <link id="4" from="2" to="5" length="10000.00" capacity="3600" freespeed="27.78" permlanes="1"  />
   </links>
</network>

További példahálózatokat találhatunk a letöltött matsim csomag examples könyvtárában.

A tervek/populáció konfigurálása

A MATSimben a résztvevők napi tervei határozzák meg az utazásaikat. Ezeknek az összességét terveknek (plans) és populációnak (population) is szokás nevezni. A populáció tartalmaz egy emberekből álló (person) listát, minden person tartalmaz egy tervekből álló (plan) listát, és minden plan tartalmaz egy activity-kből és leg-ekből álló listát.

Nézzünk egy példatervet:

<plans>
<person id="1">
	<plan selected="yes" score="93.2987721">
		<act type="home" x="-25000" y="0" link="1" end_time="06:00" />
		<leg mode="car" />
		<act type="work" x="10000" y="0" link="20" dur="00:10" />
		<leg mode="car" />
		<act type="home" x="-25000" y="0" link="1" />
	</plan>
</person>
</plans>

Minden embernek pontosan egy terve lehet selected státuszú, ez ugyan a szimuláció alatt többször is változhat (akár egyetlen napon belül az újratervezési fázisban is). A tervhez tartozhat score érték, de ennek az inputban nem kell szerepelnie, hiszen a MATSim fogja kiszámítani a terv végrehajtása után az értékelő ciklusban.

Az aktivitások egy résztvevő napi teendőit szimbolizálják, és összességükből áll össze a résztvevő napi terve. Az aktivitásoknak a következő tulajdonságaik lehetnek:

• Az aktivitás hossza. Ez megadható az end_time attribútummal vagy a dur (duration) attribútummal, értelemszerűen az előbbi a végzés időpontját jelenti, míg az utóbbi a végzés időtartamát.
  • Az utolsó napi aktivitáshoz nem tartozik se időtartam, se befejezési időpont
• Az aktivitás helyszíne. Ezt megadhatjuk x és y koorinátákkal, illetve a helyszínhez legközelebbi él azonosítójával.
  • A helyszínhez legközelebbi él azt jelenti, hogy az adott aktivitás az adott élről érhető el. Tehát például a munka aktivitáshoz a munkahely utcáját érdemes megadni.
  • Amennyiben nem adunk meg legközelebbi élt, úgy a MATSim automatikusan kiszámolja a koordinátákhoz legközelebb eső élt.
  • Amennyiben megadunk élt, úgy a koordináták elhagyhatóak.
• Az aktivitás típusa a tevékenység jellegét írja le, például otthon, munka, stb.
• A leg mode attribútuma határozza meg, hogy hogyan fog a résztvevő az egyik helyszínről a másikra utazni, például car, pt (public transportation).
  • A legeknek lehet opcionálisan egy trav_time attribútuma, ami az utazás várható idejét adhatja meg.
  • A legeknek tartalmazniuk kell egy útvonalat is. A kezdeti legek persze ezt nem tartalmazzák, ezt a MATSim kiszámolja.

Egy résztvevő egyből elkezdi a következő leget, amint az előző (leg vagy activity) befejeződött. Amennyiben a mobsim olyan mode-ba ütközik, amit nem ismer, úgy a teleportálás utazási módot választja: ebben az esetben a kezdeti pontról eltűnik a résztvevő és a célponton felbukkan a várható utazási idő elteltével.