Sweden/Hur Waze beräknar rutter

From waze
Revision as of 20:12, 17 January 2013 by Sverkernordlund (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Översättning pågår!

Klientbaserad navigering

Beräkna en optimal rutt är en svår uppgift. Trots att klienten (din app) har en integrerad algoritm används den inte annat än när det inte finns någon kontakt med Waze-servern.

Spekulation

Beräkningsalgoritmen som används av Waze-servern är inte offentliggjord varför följande är baserat på observationer, spekulationer och en del information avslöjad av anställda på Waze. Vi kan anta att beräkningarna som görs på servern anses vara patentskyddad och en konkurrenskraftig fördel för Waze. Vi kan också anta att den kommer förändras, och att information som har avslöjats kan vara felaktig eller föråldrad.

Begäran om rutt

När du söker efter en rutt, skickas det en begäran till Waze-servern, som beräknar och tar fram den mest optimala rutten. Den rutten returneras sedan till klienten och visas på din skärm.

Begäran om rutt kan variera beroende på inställningar som du gjort i din klient. I menyn Navigering kan du välja:

  • Snabbast eller kortast rutt
  • Tillåta småvägar, aldrig tillåta småvägar eller undvika långa småvägar
  • Minimera antalet svängar
  • Undvika motorvägar (i möjligaste mån)
  • Undvika vägtullar

Den kortaste rutten refererar till fysisk distans. Det är alltid bättre att välja Snabbast rutt; 10 mil motorväg är bättre än 9 mil landsväg.

Saknade vägar eller felaktiga korsningar

Waze försöker alltid hitta den snabbaste rutten från dig till din destination. Uppenbarligen kan den bara basera beräkningarna på vägar som den känner till, så din rutt blir inte optimal om en bättre rutt inte har alla korsningar korrekt inställda.

Aktuell hastighet

Vi kan vara säkra på att Waze använder realtidsrapporter av aktuella hastigheter framför gamla medelhastigheter. Vi vet att Waze använder trafikrapporter för att hänvisa runt trafikstockningar. Tidiga versioner av klienten rapporterade också när det flöt på bra - det togs bort då det blev svårt att tyda kartan. Men Waze tar fortfarande emot denna information. Därför kan vi anta att den hastighet en Wazare har som befinner sig framför dig används för att beräkna din rutt.

Allt eftersom antalet Wazare ökar kommer det tas större hänsyn till denna information i beräkningen. Denna avvägning är en del av reflektionen av Waze ursprungsmål att optimera pendling. Men då Waze har utvecklats till att bli en mer generell GPS-navigator på vägar som inte trafikeras lika mycket, blir tidigare medelhastighet på vägen viktigare i beräkningen.

Då Waze använder den tidpunkt som du förväntas befinna dig på en sträcka för att beräkna den förväntade hastigheten på sträckan, kan den inte använda aktuell realtidsdata när den tidpunkten flyttas till ett senare tidsintervall. Så resor på mer än 30 min (eller i medeltal 15 min) kommer att innefatta senare tidsintervall än det finns aktuell data rapporterad för. När du kommer in i ett nytt tidsintervall, kan realtidsdata finnas som kan få din klient att räkna om din ankomsttid och hänvisa en ny rutt.

Snabbaste rutt

Waze vet medelhastigheten på varje bekräftad väg mellan dig och din destination. Servern kan beräkna vilka vägar som skall användas för att minimera den totala restiden.

Trots att varje förfrågan bearbetas i realtid, verkar det som att Waze sparar vissa efterfrågade rutter och vanligare destinationer. Det betyder att om den redan vet den bästa rutten från B till C, och du frågar efter en rutt från A till C, behöver den bara beräkna bösta rutten från A till B, förutsatt att det inte finns en bättre rutt förbi B. Det betyder att när kartan uppdateras kan vissa rutter bli mindre optimala upp till en dag medan rutterna sparas och bearbetas.

Trots en komplex beräkning är det möjligt att beräkna en optimal rutt. Komplexiteten ligger i medelhastigheten på vägarna.

Förändrad rutt beroende på annan utgångspunkt

Föreställ dig en resa från A till Ö. Den föreslagna rutten kan då bli från A till B till C till D till Ö. Föreställ dig sedan en resa från B till Ö. Du kan då få en föreslagen rutt från B till C till E till Ö. En första inblick kan då tyda på att en rutt inte är optimal.

Vi kan ana olika anledningar till detta. Det kan finnas ett problem asocierat med det eventuella sparandet av rutter. Eller så kan det vara en "tidsfönster"-effekt. Skillnaden i ankomsttid till C kan ändra den bästa rutten till Ö. Eller så kan det vara en finjustering av rutten, kanske för att undvika för många vägbyten. Så genom att hoppa över sträckan A till B, kanske sträckorna C till E till Ö inte längre överskrider något tröskelvärde.

Denna effekt kan observeras under körning. Om du frågar efter en rutt till samma destination medan du kör på en redan angiven rutt, kan du få en helt ny rutt.

Enligt gamla rapporter, där Wazare inte fått någon ny hänvisning för att passera trafikstockning, men fått en ny rutt genom att manuellt fråga efter det. Det kan vara så att de skulle fått en ny rutt ändå, även om det inte var trafikstockning längre fram. Det stärker frågan om när och hur Waze söker en ny rutt, men det kan ha ändrats i den aktuella versionen. Dock kan vi konstatera att Waze verkligen söker efter nya rutter ibland.

Förändrad rutt beroende på ruttens längd

Ytterligare är det känt att Waze inte kan beräkna varje möjlig väg mellan två avlägsna platser, och tar därmed genvägar för längre resor, vilket kan medföra att rutten förändras avsevärt om den förlängs något. Enligt Waze support (jan 2013): på sträckor längre än 15 km från varje ändpunkt undviks vägtypen Street. antagligen för att förkorta beräkningstiden.

Från supporten hur vägtyper prioriteras:

0-15 km - Alla vägtyper används.
15-20 km - Alla vägtyper används utom Street.
20-30 km - Alla vägtyper utom Street och Primary street.
30-200 km - Endast vägtyperna Minor highway, Major highway och Freeway

I vissa fall kan resultatet bli, av att förlänga rutten en liten bit, att Waze föreslår en helt annan (och mycket längre, både avseende sträcka och tid) rutt.

Problem med medelhastighet

Om medelhastigheten inte är korrekt kommer inte rutten bli optimal. I följande situationer kan det vara fel att använda medelhastigheten som avgörande värde.

Variationer under dagen

Föreställ dig en väg där de flesta Wazare kör klockan 7 på morgonen och medelhastigheten då är 20 km/h. Du väljer din rutt klockan 10 när vägen är fri och medelhastigheten är 70 km/h. Det är den bästa vägen, men Waze väljer en annan rutt då den inte har någon information om hastigheten klockan 10 och antar att hastigheten alltid är 20 km/h hela dagen.

Du kan, förstås, köra vägen ändå och Waze kommer då till slut att lära sig. Vi vet inte hur många värden Waze använder i sin beräkning. Men om Waze bortser från äldre information kan du inte tillföra nya värden snabbare än de gamla försvinner. Det är också möjligt att din hastighet kommer anses vara onormal och därmed inte tas med ändå.

Fler användare av Waze skulle förbättra detta.

Hastigheten genom korsningar

Föreställ dig en väg som är 1 mil lång där du kör 100 km/h och rakt fram genom en korsning, vilket då tar 36 sekunder, och hela sträckan på ca 6 minuter. Jämför om du i slutet på vägen sitter och väntar i 5 minuter vid en korsning för att få svänga av. I första fallet blir din medelhastighet 100 km/h och i det andra fallet blir din medelhastighet ca 54 km/h.

Om nu 9/10 Wazare kör rakt fram, blir medelhastigheten på vägen 95 km/h. Waze kommer att rekommendera denna väg, även om det innebär att du ska svänga av i din rutt, och rutten blir därmed inte optimal.

Motsatsen, om 9/10 Wazare svänger av i korsningen, blir medelhastigheten på vägen 60 km/h, och även om din rutt fortsätter rakt fram i korsningen kommer Waze inte att föreslå den då den ser medelhastigheten på vägen som 60 km/h.

Vi kan anta att Waze är medveten om detta problem. Du kan välja Undvik svängar i navigeringsinställningarna.

Waze samlar in tillräckligt med information för att ge rätt hänvisningar om detta skulle implementeras i systemet. Både medelhastigheten för de som kör rakt fram och de som svänger av i korsningen är registrerad. Rätt medelhastighet kan användas vid beräkningen av just din rutt. Det gör beräkningen betydligt svårare, men inte omöjlig. För tillfället görs det dock inte.

WME redigering

Medelhastigheten på en väg kan avsevärt förändras genom att redigera kartan i WME. Ta en 50 meter lång väg som körs på 36 sekunder. En användare redigerar kartan och förlänger vägen till hela 10 km. Waze räknar nu den vägen som 10 km lång men fortfarande avverkad på 36 sekunder vilket ger en medelhastighet på 1000 km/h. Det har varit ett speciellt förekommande problem när användare ändrar längden på på-/avfarter (Ramps). På-/avfarterna får så hög medelhastighet att Waze föredrar en rutt på dessa mot den mest riktiga rutten på motorvägen.

Trafikljus och stopplikt

Waze sparar ingen information om var det finns trafikljus. Medans andra GPS-navigatorer kan ge direktiv som "sväng höger vid nästa trafikljus" är den informationen ofta ofullständig och föråldrad. Därför bör heller inte Waze spara sådan information.

Waze tar dock ändå hänsyn till trafikljus och stopskyltar genom att notera effekten de har på trafiken. En vägsträcka som leder fram till ett trafikljus med långa väntetider får en låg medelhastighet. Om medelhastigheten blir tillräckligt låg kommer en rutt som undviker trafikljusen att vara en bättre rutt.

Gammal och onormal hastighet

Vägstandarden förändras, vägarbeten kommer och går, och medelhastigheten kan förändras dramatiskt. En dag kanske du hamnar bakom en traktor, en annan dag kanske du kryper fram kl 2 på natten med din guldfisk. Eller så beter sig din GPS konstigt åt och visar en hastighet på 1000 km/h.

Alltså, medelhastigheter förändras med tiden och sparade tider kan vara onormala eller helt fel. Och kan vara fel rätt länge. Vi kan anta att Waze tar hänsyn till detta. Det finns vissa bevis för att onormala och gamla hastigheter tas bort, eller används åtminstone inte i beräkningen av medelhastigheten.

Medelhastighet för olika tider

Om det är tillräckligt många hastigheter sparade på en sträcka delar Waze upp dem beroende på när på dygnet de gäller. Så varje sträcka (i båda riktningarna) kan ha intervall ner till 30 minuter, dvs 48 hastigheter per dygn. Om det sedan inte finns tillräckligt många hastigheter förlängs intervallen, upp till en dag.

Vi kan vidare spekulera i att det kan finnas ytterligare information baserat på tex veckodag. Det finns observationer som ger belägg för att en väg som är vältrafikerad under veckan, och då undviks, ändå kan väljas som optimal rutt på helgen.

Waze använder den medelhastighet som sparats för det tidsintervall som du beräknas anlända till sträckan.

Waze kommer därmed välja olika rutter olika tider på dygnet. Det beror dock på hur många hastigheter som sparats för sträckan. Om alla hämtats ungefär samma tid, så kommer detta inte hjälpa. Om 1000 hastigheter hämtas runt 17 och 2 vid 10 så kommer ändå medelhastigheten vid 10 mest baseras på hastigheter från 17.

Förbättring av beräkningsalgoritmen

Ruttval

Det är enkelt att se hur man kan införa olika val. Tex för att minimera antalet svängar kan man göra ett tidstillägg för varje sväng vid beräkning av den snabbaste rutten. Och ett avståndstillägg för varje sväng vid beräkning av den kortaste rutten.

Tillägg vid korsningar

För närvarande använder Waze ett 5 sekunders tidstillägg när den beräknar en rutt genom en korsning. Ett inte helt otänkbart sätt att hantera korsningar, men det har orsakat vissa felaktiga rutter och är under granskning.

En viktig fråga uppstår på långa motorvägar som kan bestå av hundratals sammankopplade segment, eftersom detta kan göra ett tidstillägg på så mycket som fem minuter till en resa, även om korsningarna inte finns i verkligheten. Detta stödjer argumenten från dem som siktar på att ha en ren redigering av kartor där korsningar endast användas vid behov.

Problemet kan lösas på flera sätt. Man kan låta bli tillägg när:

  • det inte finns andra vägar som möts i korsningen
  • båda vägarna har samma namn
  • vägen man färdas på är av högre klass, där vi kan anta att alla andra vägar har väjningsplikt
  • man färdas på motorvägar, länsvägar och huvudleder.

Även om en väg är korrekt ansluten, utan onödiga segment, kan tidstillägget fortfarande ge felaktiga resultat. Till exempel en motorväg kan vara rätt ansluten till på-/avfarterna längs vägen. Om en lugn landsväg löper parallellt och kanske inte har alla de mindre anslutande vägarna, ser det ut som en rak vägsträcka utan korsningar. Waze kan välja landsvägen som den föredragna vägen på grund av bristen på korsningar.

Vad du ska göra om du tror att den föreslagna rutten är fel

Först, använd valet att generera alternativa rutter. Det kan ge dig några ledtrådar till varför Waze väljer just den rutten.

Sen, om du ändå tror att det finns en bättre rutt, kontrollera i WME att alla vägar är rätt anslutna utmed rutten.

Till sist, gör ett inlägg i forumet, där du anger utgångspunkt, destination och en Permalink till WME. Andra kan söka problemet, och kanske finner en miss i algoritmen. Kan den fixas blir det bättre för alla.

Ändring av rutt

När Waze tar emot rapporter om läget på vägarna används den aktuella hastigheten utmed din rutt, snarare än medelhastigheten. Den baseras dock endast på de automatiska rapporterna. Manuella rapporter av trafikstockning och olyckor är bara som information, de påverkar inte din rutt.

Det kan dock också vara så att trots de automatiska rapporterna så hittar Waze ändå ingen bättre rutt.

Du är föraren

Waze kan aldrig se att trafikljuset är grönt, eller vet att det en helgdag idag. Waze kan ge dig vägledning om vad som är den bästa vägen under genomsnittliga förhållanden. Men du är föraren och du är i den bästa positionen att fatta beslut om idag utifrån dagens förhållanden.

Om alla följer Waze och aldrig kör nya vägar, kan Waze aldrig lära sig en bättre väg. När Waze följer dina resor, hjälper varje resa till att göra Waze bättre för alla. Det inkluderar då du tror att du vet bättre. Ibland kommer du att ha rätt, och ibland kommer du att ha fel. Men det är bättre att ta reda på att du har fel så du kan välja den bättre vägen nästa gång. Och när du har rätt, kommer alla andra användare dra fördel av att kunna dela din kunskap.