Navigační server

Probíhá překlad.

Při používání aplikace Waze probíhá neustálá komunikace se servery Waze, které používají sofistikované algoritmy pro určení optimální trasy pro každý okamžik, kdy si to klientské zařízení (mobil/tablet) vyžádá. Mnoho specifických detailů používaných algoritmů není veřejně dostupných a následující text je tak založen na pozorování, spekulacích a částečně informacích přímo od zaměstnanců Waze. Akce, které provádí Waze server, jsou neveřejné a jsou hlavním "obchodním tajemstvím" Waze. Zároveň je třeba připomenout, že použité algoritmy se mohou v budoucnu měnit a text tak nemusí přesně odpovídat aktuálnímu řešení.

Počítání trasy přímo klientským zařízením

Spočítat optimální trasu je obtížný úkol. Výpočetní algoritmus je součástí klientské aplikace, nicméně standardně se nepoužívá a aplikace jej využije pouze tehdy, má-li problém s připojením na Waze server.

Požadavek na určení cesty

Když si v navigaci vyťukáte požadavek na novou cestu, je tento požadavek odeslán na server Waze. Ten na základě vstupních kritérií propočte optimální trasu a odešle ji zpět do vašeho zařízení.

Požadavky na výpočet se mohou měnit podle toho, jaká nastavení máte konkrétně ve vašem navigačním prostředí aktivní. V nastaveních si můžete vybírat volby jako:

• Nejrychlejší nebo nekjratší trasa
• Jestli chcete nebo nechcete využít placené silnice
• Jestli vám nevadí jet po nezpevněných komunikacích (polní cesty), případně jestli jste ochotni tolerovat krátký úsek
• Jestli se chcete vyhnout dálnicím

Nejkratší cestou se rozumí fyzická vzdálenost v metrech. Obvyklým a nejvíce využívaným nastavením je nejrychlejší trasa - 100km po dálnici je lepší než 90km po okreskách.

Chybějící cesty a špatné napojení do křižovatek

Waze zkouší najít optimální cestu mezi výchozím a cílovým bodem, přičemž bere v potaz vaše nastavení. Pochopitelně dokáže počítat pouze s cestami, které zná, takže pokud v reálu existuje lepší trasa, která není zanesena v editoru, případně není zanesena správně, tak nebudete na danou trasu navigováni. Stejně tak můžou způsobit potíže různé místní úpravy v editoru, které se obecně nedoporučují (příliš krátké segmenty atp.).

Aktuální (real-time) rychlosti na silnicích

Výpočetní server používá aktuální rychlosti na silnicích (sbíráné ze všech aktuálně běžících navigací Waze) a kombinuje je s historickými údaji pro každý segment, které si navíc dělí do úseků trvajících 10-15 minut.  Čas potřebný k projetí obou výchozích bodů každého segmentu je sledován v kontextu trasy, po které uživatel právě jede. například pokud segment končí dvěma odbočkami - vlevo a vpravo (a žádné pokračování rovně), potom si Waze server pro daný segment pamatuje dvě rychlosti - jednu pro případ, kdy trasa na konci segmentu odbočuje vlevo a druhou pro případ, kdy trasa odbočuje vpravo. K těmto informacím nemá uživatel přístup, jsou součástí obchodního tajemství Waze. 

Waze upřednostňuje aktuální rychlosti před historicky sledovanými hodnotami.  Stejně tak Waze využívá hlášení o příliš husté dopravě a navrhuje alternativní trasy s cílem vyhnout se ucpanému místu na silnici. Předpokládá se, že pro výpočet vaší trasy se v první řadě použije rychlost Wazera, který projel daný úsek chvilku před vámi (pokud takový Wazer existuje).

Jak houstne počet uživatelů navigace Waze, stávají se aktuální rychlosti více a více důležitějšími. To je v souladu se základní myšlenkou Waze - navrhovat optimální trasy pro každodenní používání. Zároveň s tím, jak je Waze používáno jako všeobecná navigace i pro dálkové a méně využívané trasy, roste důležitost uchovávání historických dat a rychlostí.

Navigační systém Waze "myslí do budoucna" a počítá s tím, že dané segmenty na vaší trase projedete "až v budoucnu - za pár minut". Pro vzdálenější segmenty tedy nemá smysl počítat s aktuální situací.  Navržená trasa delší než cca 15-30 minut je tedy kombinací aktuálních dat a historických dat pro segmenty, ke kterým se předpokládá, že dorazíte později než za těch cca 15-30 minut. Zároveň v takových případech Waze sleduje aktuální dopravní data a pokud z nich vyplyne vhodnější trasa, bude vám nabídnuta.

Nejrychlejší cesta

Waze zná průměrnou rychlost z každého potvrzeného segmentu mezi vámi a vaším cílem. Waze server počítá, jaké cesty a segmenty je třeba projet, aby bylo dosaženo co nejkratšího celkového času.

Každý požadavek na trasu je tedy propočítáván v daný okamžik, nicméně z pozorování vyplývá, že Waze má určité hlavní body, mezi kterými má "předpočítané" nejrychlejší trasy a tyto údaje pak využívá ke zrychlení výpočtů. Pokud například systém už zná nejrychlejší trasu z bodu B do bodu C a vy si vyžádáte výpočet trasy z bodu A do bodu C, pak Waze server spočítá pouze trasu z bodu A do bodu B, jakmile zjistí, že není lepší cesta, která by znamenala úplné vyhnutí se bodu B. To mimo jiné znamená, že při aktualizaci mapových podkladů mohou být některé vypočítané trasy během 24 hodin "méně optimální", než si systém dokáže znovu propočítat všechny alternativy mezi svými hlavními body.

Jedná se bezesporu o komplexní výpočty, kdy nicméně je možné optimální trasu spočítat. Komplexnost tohoto úkolu však narůstá díky průměrným rychlostem na silničních segmentech.

Změny v trase při různých výchozích bodech

Představme si výpočet trasy z bodu A do bodu Z. Navržená trasa jde z A do B, do C, do D a do Z. Poté nechme spočítat tasu z bodu B do bodu Z. Možná vám bude navrhnuta trasa z B do C, do E a do Z. Na první pohled se zdá, že jedna z cest nemůže být optimální. 

Můžeme hádat, co se děje. Může se jednat o výše popsanou situaci s "předpočítáním" tras. Může se jednat také o výše uvedenou situaci, kdy délka trasy překročila 15-30 minut a místo aktuálních dat je pro budoucnost Waze nucen použít historicky sledované údaje a rozdílný čas příjezdu do bodu C mohl ovlivnit výpočet trasy do bodu Z. Může se také jednat o dodatečnou optimalizaci trasy, která možná obsahovala již příliš mnoho odbočení a vynechámím trasy z A do B tak navigační systém již nepřekročil nějaký ze svých vnitřních limitů.

Tohoto efektu si můžete při jízdě všimnout. Vyžádáte-li si přepočítání trasy, zatímco už jste nějakou dobu na cestě, je možné, že vám systém nabídne trasu jinou.

Waze občas nabídne novou trasu, která objede dopravní zácpu před vámi. Přesné informace, kdy a jak Waze zvažuje toto přetrasování, nejsou známy.

Změny v trasách díky různým délkám tras

Waze má dlouhodobě problémy s výpočtem optimální trasy u dálkových jízd a nedokáže propočítat každou jednotlivou alternativu. Využívá tedy zjednodušení a předpočítaných tras. To může vést k poměrně významné změně tras už při mírné změně už tak dlouhé trasy.

Podle vyjádření z podpory Waze (rok 2011) navigační systém silně upřednostňuje vyšší třídy silnic (vyšší než ulice/street) v případech, kdy vzdálenost do cíle je větší než 10 km.  Všeobecně se má za to, že navigační server zkrátka ignoruje segmenty typu street/ulice, které jsou od cíle vzdálenější než 10 km, aby urychlil celkový proces výpočtu. 

Problémy s průměrnou rychlostí silnice

Pokud průměrné rychlosti nejsou v pořádku, pak není možné spočítat optimální trasu. Nicméně nikdy se nedoporučuje mazat segmenty za účelem resetu průměrné rychlosti pro daný segment. Waze stále používá data uživatelů projíždějících přes daný segment a průměrnou rychlost zpřesňuje. Máte-li podezření, že systém Waze nevyužívá určité úseky, i když by měl, pak se s největší pravděpodobností jedná o jeden z mnoha dalších důvodů, proč vás navigace danou cestou nesměruje. Rozhodně není dobré začít tím, že smažeme a znovu vytvoříme segmenty, které dle nás působí problém.

Následující odstavce popisují důvody, proč navigační systém nemusí brát ohled na průměrnou rychlost daného segmentu.

Rozdíly podle denní doby

Představte si silnici, po které většina Wazerů jezdí v pět odpoledne a na níž je průměrná rychlost 20 km/h. Vy se na cestu vydáte v deset ráno, kdy je silnice prázdná a průměrná rychlost dosahuje 100 km/h. Je to nejvhodnější cesta, ale systém Waze vám nabídne jinou, protože nemá informaci o tom, jaká je rychlost kolem desáté hodiny dopolední a automaticky tak předpokládá, že průměr 20 km/h je platný po celý den.

V t akovém případě můžete samozřejmě rychlejší cestu projet na základě vlastního rozhodnutí a systém Waze se nakonec naučí, jaká rychlost je v daný čas pro danou silnici průměrná. Je logické, že v tomto případě nejen že nepomůže smazání a opětovné vytvoření dané silnice, ale navíc to uškodí ostatním Wazerům, kteří profitují z faktu, že systém již zná rychlost v pět odpoledne. Je také možné, že vaše vysoká rychlost bude ignorována, protože ji systém Waze bude považovat za abnormální.

Větší množství Wazerů projíždějící danou silnici v dopolední dobu by problém vyřešilo.

Zpoždění při změně směru jízdy

Rychlost pro určité segmenty může být velmi odlišná v závislosti na tom, co má řidič udělat na konci segmentu (typicky na křižovatce). Pokud pokračuje rovně, projede pravděpodobně celý segment rychle, zatímco pokud odbočuje vlevo, zdrží se na stejném segmentu velmi dlouho. Podobně také např. u dálničních sjezdů - jízdní pruh přecházející ve sjezd bude velmi rychlý, zatímco pruh pokračující rovně po dálnici bude beznadějně zacpaný. 

SegmentTraffic1.png

Systém Waze umí tyto situace odlišit a zaznamenává průměrnou rychlost pro segment v  závislosti na tom, jaká akce se dále koná na konci segmentu. Sitauce je zachycena na obrázku vlevo, kdy doprava přes Seg4 se rozdvojuje do Seg5 a Seg6. V dané situaci tedy systém Waze sleduje dvě průměrné rychlosti::

• Seg4 - Jnct2 - Seg5

• Seg4 - Jnct2 - Seg6

Prodlužující se čas pro Seg4 u vozidel odbočujících na Seg6 nemá žádný vliv na čas pro vozidla, která ze Seg4 odbočují na Seg5. Z tohoto důvodu je důležité dělat pokud možno delší segmenty vedoucí ke křižovatkám (zde konkrétně Seg4), aby systém co možná nejpřesněji zachytil dlouhé čekací doby pro všechny odjezdové směry.

Abychom tomuto lépe porozuměli, představme si, že přidáme ještě krátký segment navíc, konkrétně na druhém obrázku je to Seg8, který jme "vmáčknuli" mezi rozdvojení a Seg7. Řekněme, že provoz do Seg10 je tak hustý, že ve chvilce stojí kolona přes Seg8 až do Seg7. To díky krátkému Seg8 nastane velmi brzy. V ten okamžik nastává naše problémová situace: protože Seg7 má jediný odjezdový bod (a to do Seg8), nedokáže už v tento okamžik systém Waze sledovat více než jednu průměrnou rychlost a nemůže tedy zohlednit, jestli řidič stojící na Seg7 bude pokračovat do Seg9 nebo Seg10. Díky tomu se v naší modelové situaci systém Waze domnívá, že doprava směřující do Seg9 je zpomalena už v Seg7, zatímco v reálu tomu tak není. Přinejmenším to ovlivní předpokládaný čas dojezdu do cíle - nicméně může to také vyvolat přepočítání celé trasy a navržení méně optimální alternativy. Takže platí: pokud je na křižovatce reálné, že různé směry jízdy budou mít různě dlouhou "čekací dobu", než mohou opustit křižovatku, pak je třeba udělat vjezdové segmenty co nejdelší.

Tyto údaje nicméně ve Waze Map Editoru neuvidíte, počítá s nimi pouze navigační server.

Waze Map Editor changes

The average speed of a road can be dramatically altered by editing in Waze Map Editor (WME). Consider a 50m length of road driven in 36 seconds. An editor extends this length of road the full 10km length. WME now records this road as 10km long, but also driven in 36 seconds for an average road speed of 1000km/hour. Therefore be cautious of significantly changing the length of roads. Instead consider drawing new roads and linking them.

Traffic lights and stop signs

Waze does not record the location of traffic lights. While some GPS navigation offers guidance like "turn right at the next traffic light" the information is frequently incomplete, incorrect or outdated. The consensus view is that Waze should not record the location of traffic lights.

Waze does take traffic lights and stop signs into account by noting the effect they have on traffic speed. Consider a traffic light with long waiting times. The road segment leading to that traffic light will have a low average speed. If the average speed (based on the average waiting time) becomes low enough, a longer route that avoids the light becomes the preferred route. This has been observed in practice and is an example of emergent behaviour. Waze isn't programmed to avoid traffic lights but it does avoid slow roads; if the traffic lights make the road slow then Waze avoids them.

Some drivers regularly take longer routes — even winding through side streets — to avoid any stops or traffic lights. Waze has been known to suggest this, and also known to revert to waiting at lights when better average speed information is collected from the side streets. But note that this can be less than optimal due to the turn delays discussed above.

Outdated and abnormal road speeds

Road conditions change, construction work comes and goes, and average road speeds can change dramatically. One day you might be stuck behind a truck, and another day you might be crawling along the roads at 2 a.m. transporting your pet goldfish. Or your GPS might have a glitch and show you travelling at 1,000 mph.

In short, average speeds can change over time, and recorded times can be abnormal or just plain wrong—and can stay wrong for a very long time.

We can assume Waze is aware of this. There is some evidence that abnormal road speeds and old road speeds are discarded, or at least not used in calculating the average speeds of roads.

Average road speed "shrinking window"

If there are enough recorded speeds on a road, then Waze uses a shrinking window of speeds to better estimate the average speed at the time you are travelling on it. Waze uses the speed of each road segment (in both directions) in intervals as small as 30 minutes. So a two-way road might have up to 96 average road speeds. We can assume that when there are insufficient records for an individual time slot, a wider time range is takes up a full day. As the road is driven more, the time slot shrinks down to 30 minutes.

We can speculate that there is additional information used that is based upon the day of the week. There is some observational evidence that a road that is busy on weekdays and not used for routing is chosen as the optimal route on weekends.

At some point, Waze also needs to consider the months of the year as seasonal variations can affect the speed of the roads.

Waze uses the average road segment speed for the time slot that applies at the time you are expected to arrive at that road segment.

Because of this "time window", Waze suggests different routes at different times of day. This is dependent on how many times are recorded on the roads along the route. If they're all recorded at about the same time of day, then the time window does not help. If 1,000 times are recorded at about 5 p.m. and 2 times are recorded at 10 a.m., then your 10 a.m. average speed still is based mostly on times from around 5 p.m.

Routing algorithm refinements

Routing options

It's easy to see how routing options can be implemented. For example, to minimize turns we can add a time penalty for fastest routing or a distance penalty for shortest routing, when calculating the fastest or shortest route.

Junction penalties

For newly created roads, currently Waze applies a five-second time penalty for each junction through which a route passes. Once vehicles drive over that road and generate Waze traffic data, the penalty for these junctions is dropped.

What to do if you think the generated route is wrong

Firstly, use the option to generate alternative routes. This might give you some clues as to why Waze is offering that route.

Secondly, if you think there is a better route, check in WME that the roads are all connected along the route.

Thirdly, post a message detailing the problem route - origin, destination and a WME permalink to the Navigation forum. Other eyes will check it, and you might indeed find a flaw in the Waze routing algorithm. Fixing it might make it better for everyone.

Change of routing

When Waze receives notification of traffic conditions it uses the actual speed of roads on your route, rather than the average speed. This is based only on the automatic traffic condition reports - light, moderate, heavy traffic or complete standstill. Manual reports of traffic jams and accidents are for your information only and do not change routing.

It might be that even with the traffic reports, there is no better route and Waze cannot offer you one.

You are the driver

Waze can never see that the traffic light is green going straight, or know that today is a public holiday. It can offer you guidance as to what is the best route under average conditions. But you are the driver and you are in the best position to make the decision for today under today's conditions.

If everyone followed Waze directions and never drove on a new route, Waze might never learn that route is better. When Waze is recording your travels, every trip helps make Waze better for everyone. That includes when you think you know better. Sometimes you will be right. And sometimes you will be wrong. But it is better to find out you are wrong so you can choose the better route. And when you are right, all Waze users benefits by sharing in your knowledge.