Lektion 10: Trafiksimulering

Simuleringar

Ett stort användningsområde för datorer är simuleringar d.v.s. att man skapar en datormodell av någon process (i vid bemärkelse) som man vill studera. Det kan röra sig om en modell för vädret eller klimatet, för hur snödrivor bildas kring olika byggnader, för trafikflödet i ett gatunät eller för en värld med sköldpaddor som föds, äter, lever och dör.

Meningen med modellen är att man skall kunna göra förutsägelser om vad som händer om man ändrar olika parametrar (släpper ut mer koldioxid, ändrar byggnadens form, gör en rondell eller ger sköldpaddorna mer mat ...).

Det är i regel väsentligt billigare att experimentera med en datormodell än att göra det i verkligheten (bygga en eller flera olika rondeller) eller att göra det med fysiska modeller (bygga modellhus och blåsa potatismjöl på dem i en vindtunnel).

När man bygger modeller så måste man i regel förenkla och bortse från många detaljer som man inte tror har någon eller åtminstone bara liten effekt.

Ett sätt att göra simuleringar är att dela upp tiden i ett antal diskreta tidssteg. Man utgår från ett starttillstånd och stegar sig sedan fram i tiden och noterar vad som händer i varje tidssteg:

Ibland kan man veta exakt vad som sker i varje steg men oftast har man bara approximationer. Dessutom kan det finnas ett visst mått av slump som man får approximera med någon sannolikhet. Man vet till exempel sällan exakt vid vilka tidpunkter ett fordon anländer till en rondell men man kan ha mätt upp en intensitet så att man har en sannolikhet för att ett fordon skall anlända ett visst tidssteg.

Problembeskrivning

Programmet ska simulera trafikflödet i olika typer av trafiksystem. Ett trafiksystem består, i vårt fall, av körfält (oftast kallat filer), trafiksignaler och köer. Vägar byggs upp av filer men vi kommer inte ha några vägobjekt.

Exempel 1

Exempel 2

Exempel 3

Korsningen kontrolleras alltså av de fyra ljussignaler s1, s2, s3 och s4.

Ett problem i denna typ av korsningar är att fordon som kommer från E och vill svänga vänster mot S i korsningen blir blockerade av fordon som kommer från W vilket i sin tur blockerar fordon som vill köra rakt fram.

Exempel 4

För att lösa problemet kan man att bygga svängfiler för fordon som kommer från E respektive W och som skall vänster i korsningen d.v.s. man vill ha en korsning av detta utseende:

Denna korsning har alltså svängfiler kontrollerade av signalerna vid s2 och s5.

En typisk fråga är då hur långa svängfilerna ska göras för att undvika att köerna på dessa växer in i de andra filerna.

Datormodell

Ett trafiksystem ska byggas upp av två generella komponenter: trafikljus (klassen Light) och körfält (klassen Lane). Det innehåller också ett varierande antal fordonsobjekt (klassen Vehicle). Vi kommer också behöva köer men sådana representeras enkel med listor. Vidare används klassen Destinations för att simulera ankomster av fordon till systemet. Denna sista klass får du färdig i övningen.

Klassen Vehicle

Klassen Vehicle är mycket simpel. Dess uppgift är bara att hålla reda på när fordonet skapades och vart det ska. För detta räcker det med två instansvariabler, t.ex. benämnda destination och borntime.

Ett fordon behöver alltså inte veta var det är, inte titta på signaler och inte kunna se andra fordon. Fordonen kan betraktas som pjäser som flyttas av "någon annan".

Det behövs således bara en konstruktor som tar emot destination och födelsetid. Om man vill kan man lägga till en __str__()-metod.

Klassen Destinations

Denna klass används för att simulerar ankomster av nya fordon till trafiksystemet. Varje anrop till dess step-metod returnerar antingen None, som anger att inget fordon kom detta steg, eller en destination ('W' eller 'S').

Klassen skulle kunna baseras på uppmätta eller uppskattade intensiteter vid olika tidpunkter på dygnet men i vårt fall returnerar den en förutbestämd sekvens. Detta gör det enklare att förutsäga resultatet och därmed också kontrollera att programmet är korrekt.

Klassen är helt given och behöver inte ändras. Den kan hämtas här.

Klassen Light

Klassen Lane

Anmärkning: I fortsättningen använder vi ordet fil eller fil-objekt för att beteckna ett körfält och datafil eller Python-fil för att beteckna filer i datorns filsystem.

Klassen TrafficSystem

Denna klass definierar ett specifikt trafiksystem. Den håller reda på vilka filer och vilka signaler som ingår och hur fordonen ska flyttas genom systemet.

För att t.ex. representera systemet i exempel 1 behövs två filer och en signal:

Se beskrivningen av klassen !

Uppgift: Det första systemet

d.v.s. ett system med två filer och en trafiksignal.

Lämplig arbetsgång

1. Kopiera Pythonfilen trafficComponents.py. Den innehåller skal till klasserna Vehicle, Lane och Light. Dessutom innehåller den funktioner som demonstrerar dessa klasser (samma exempelkod som finns i beskrivningarna av klasserna).
2. Implementera klasserna Vehicle, Lane och Light. Kör demonstrationsmetoderna och kontrollera att du får rätt utskrifter!
3. Kopiera Pythonfilen destinations.py (om du inte redan gjort det). Den innehåller bara klassen Destinations. Du behöver inte göra några ändringar i denna klass.
4. Kopiera Pythonfilen trafficSystem0.py. Denna fil innehåller ett skal till klassen TrafficSystem samt en färdigskriven main-funktion.
5. Skriv klart klassen TrafficSystem:
   1. Skriv konstruktorn som skapar två filer, en signal och och ett Destinations-objekt.
   2. Skriv snapshot()-metoden. Basera den på __str()__-metoderna i de olika komponenterna.
   3. Skriv step-metoden så här:
      1. Ta ut första fordonet från den första (vänstra) filen i figuren.
      2. Stega den första filen med dess step-metod.
      3. Om signalen är grön så flytta första fordonet på den andra (högra) filen till den första.
      4. Stega signalen med dess step-metod.
      5. Stega den andra filen.
      6. Anropa step-metoden i Destinations-objektet. Om denna returnerar en destination (d.v.s. något annat än None) så skapa ett fordon och lägg det sist på den andra filen.
6. Testkör! Nu bör du se hur fordonen glider genom systemet och hur signalen skiftar färg.

7. Det finns ett problem: Om det redan ligger ett fordon på sista platsen på den andra filen kommer detta att tappas bort när vi lägger ett nytt där. För att undvika det ska du organisera en kö för fordon som väntar på att komma in i filen. Lägg till ytterligare en instansvariabel av listtyp för detta. Kön ska också skrivas ut av snapshot-metoden.

   Tips: Koden blir enklast om man alltid placerar tillkommande fordon i kön och sedan hämtar det första från kön.

   Se till att du inte lagrar None på kön!

Det andra systemet

Trafiksystemet ska således bestå av tre filer (lane, lane_west och lane_south) och ljussignalerna light_west och light_south (tidigare kallade s1 och s2):

Det kan vara snyggt att ha korta körfiler efter (till vänster om) signalerna så att man ser hur fordonen passerar.

Vid punkten E finns det en kö (ej utritad).

Vid ett tidssteg kan en eller flera av följande saker hända i denna ordning:

• Ett fordon från vardera lane_west och lane_south passerar sin signal (om den är grön).
• Filerna lane_west och lane_south stegas.
• Ett fordon omedelbart till höger om X flyttas till lane_west eller lane_south beroende på dess destination (W eller S). Om platsen på destinationsfilen inte är ledig står fordonet kvar och delningspunkten räknas som blockerad.
• Fordonen på lane stegas.
• Ett fordon anländer till systemet vid punkten E och ställs i kön.
• Om sista platsen i lane är ledig och det finns fordon i kön tas första från kön till sista platsen i lane.
• Ljussignalerna stegas.

En simulering består alltså av en tidsstegning där ovanstående saker händer. Det är lämpligt att momenten, precis som i verkligheten, utförs i den ordning de står ovan. Det kan vara praktiskt att låta din step-metod i sin tur anropa olika metoder du själv introducerar för att ta hand om olika delar. Det kan minska mängden upprepad kod i step och göra den mer överskådlig.

Observera att klasserna Lane och Light inte ska behöva ändras - endast TrafficSystem behöver göras om.

Indata till en simulering

Programmet styrs av följande indata:

• takten som fordon anländer till E,
• andelen fordon som skall svänga d.v.s. ha S som destination,
• längderna på filerna och
• ljussignalernas karakteristik (period och grönperiod).

De två första värdena varierar vanligen med tiden. Detta hanteras av klassen Destination. I verkliga simuleringar skulle klassen producera fordon enligt uppmätta intensiteter men, för att ni ska få kontrollerbara resultat, ger denna version samma sekvens varje gång.

Värdena i de två sista punkterna, d.v.s. längderna på filerna och ljussignalernas karakteristik, får du bestämma själv. Prova dock nedanstående och jämför med den statistik som visas längre ner.

Resultat av en körning

1. Statistik innehållande:
   1. Genomsnittliga, minimala och maximala tider (antal tidssteg) för fordon att passera respektive ljussignal (väst/syd).
   2. Andel tidssteg som delningspunkten X varit blockerad. Med blockerad menas att det inte går flytta ett fordon från filen lane på grund av att sista platsen i dess destinationsfil är upptagen.
   3. Andel tidssteg som det funnits fordon i kön vid startpunkten (E).

   Samla tiderna för fordon som lämnar systemet i två list-objekt, ett för vardera utgång, och använd dessa för att ta fram statistiken. Använd antingen en egen modul med statistik-metoder eller standard-modulen statistics.

   Statistiken skall skrivas ut av metoden print_statistics i TrafficSystem. Metoden skall kunna anropas när som helst under simuleringen. Exempel på utskrift:

   Statistics after 100 timesteps: Created vehicles: 48 In system : 8 At exit West South Vehicles out: 21 19 Minimal time: 20 21 Maximal time: 38 53 Mean time : 27.6 39.3 Median time : 27.0 43.0 Blocked : 18.0% Queue : 14.0%
2. Ögonblicksbilder systemet med hjälp av snapshot.

   Exempel på en sekvens av ögonblicksbilder:

   (G) [.....W..] [SWWSWSSSWSW] [] (R) [SSSSS.SS] (R) [....W...] [WWSWSSSWSWW] [] (R) [SSSSSSSS] (R) [...W...W] [WSWSSSWSWWS] [] (R) [SSSSSSSS] (R) [..W...WW] [SWSSSWSWWSW] [] (R) [SSSSSSSS] (R) [.W...WW.]*[SWSSSWSWWSW] ['W'] (R) [SSSSSSSS] (R) [W...WW..]*[SWSSSWSWWSW] ['W'] (R) [SSSSSSSS] (R) [W..WW...]*[SWSSSWSWWSW] ['W', 'S'] (R) [SSSSSSSS]
   I de tre sista stegen är delningspunkten blockerad (indikeras av *-tecknet) och dessutom finns det först ett och sedan två fordon i kön.

Innan du redovisar

1. Se till att koden följer kodningsreglerna!
2. Kontrollera att all efterfrågad statistik finns med och att resultaten är korrekta!
3. Se till att programmet producerar utskrifter enligt ovanstående exempel.

Tillbaka