Waarom is de route heen en terug in Google maps soms verschillend?

[jkien]

Waarom is de route heen en terug in Google Maps soms verschillend? Ik heb hier een voorbeeld in Amsterdam, van Amsteldijk 105 naar het Haarlemmermeerstation. Heen is de aanbevolen fietsroute 4,4 km, en terug 5,5 km.

[king nero]

Zitten er enkel-richtings-straten tussen? Of iets anders, dat je weerhoudt de heen-route (4.4 km) in de andere richting te nemen?
Google houdt ook soms rekening met afgesloten stukken (wegens wegeniswerken, ...), maar dan staat er een rood symbooltje bij. Dat lijkt hier niet het geval.

[jkien]

Er zijn hier geen stukken met eenrichtingsverkeer, je kunt beide routes ook omgekeerd afleggen. Er zijn geen afsluitingen.

[irArjan]

Het algoritme dat de route bepaalt kan niet alle routes overwegen zonder vele jaren aan het rekenen te zijn. Dus het algoritme zoekt naar een 'goede' oplossing ipv 'de beste'. En omdat er dus verschillende uitgangsposities zijn, kan de route dus verschillen heen en terug.

[king nero]

Google houdt naast afstand ook met de tijd rekening, als voornaamste parameters. Misschien is er iets daarmee (meer verkeerslichten, lagere gemiddelde snelheid, een ophaalbrug, ...)

Ik ben het in principe niet eens met Arjan. Google geeft je de meest efficiënte oplossing. In dit geval zal je enkel moeten zoeken waarom die als meest efficiënt wordt beschouwd, dus op welke parameters er beoordeeld wordt.
Ik ga niet op de letter spelen, "de beste" of "de meest efficiënte" is voor interpretatie vatbaar, maar ze gaan voor zoiets ook geen wegen via Rome overwegen, dus die jaren rekenwerk valt weg. Ik vind het al een behoorlijke prestatie dat ze met het verkeer rekening houden, ook al plan je een route voor binnen 3 maand. Er moet in dit geval een verklaarbare reden zijn, ik geloof niet dat het zomaar "een goede" oplossing is in plaats van de beste.

[jkien]

Misschien dat google maps bij een stadsroute meeweegt dat een fietser bij een kruispunt liever rechtsaf slaat dan linksaf, omdat linksaf een stoplicht meer is, of omdat linksaf gevaarlijker is, met een grotere kans op een botsing met tegenliggers. Dan zou je verwachten dat google maps een heen-en-weer lus maakt die in wijzerrichting doorlopen wordt. Denk bijvoorbeeld aan een heen-en-weer route die vierkant is met op elke hoek een kruispunt.

Maar in een land met linksrijdend verkeer in tegenwijzerrichting.

[irArjan]

Ik ben het in principe niet eens met Arjan. Google geeft je de meest efficiënte oplossing. In dit geval zal je enkel moeten zoeken waarom die als meest efficiënt wordt beschouwd, dus op welke parameters er beoordeeld wordt.
Ik ga niet op de letter spelen, "de beste" of "de meest efficiënte" is voor interpretatie vatbaar, maar ze gaan voor zoiets ook geen wegen via Rome overwegen, dus die jaren rekenwerk valt weg.

Ok, schrijf jij maar een algoritme dat zegt: "ok, geef me de kortste route van A naar B, maar die hele lange omwegen hoef je niet te beschouwen". Ok, zegt de computer "geef me de lange omwegen zodat ik weet welke ik niet hoef te beschouwen". En rekenen maar...

Wat voor een mens overduidelijk is, is dat voor een computer niet per se. Wat ik probeer te zeggen is dat het algoritme niet feilloos is, het neemt dingen aan zodat het vele opties niet hoeft te beschouwen. Ik weet helaas niet precies hoe die algoritmes werken, maar blijkbaar is het een combinatie van een Greedy algoritme (dat gewoon alleen kijkt naar de kortste volgende node) en iets dat A* algoritme heet, zie hier

[Math-E-Mad-X]

Ik ben het in principe niet eens met Arjan. Google geeft je de meest efficiënte oplossing. In dit geval zal je enkel moeten zoeken waarom die als meest efficiënt wordt beschouwd, dus op welke parameters er beoordeeld wordt.
Ik ga niet op de letter spelen, "de beste" of "de meest efficiënte" is voor interpretatie vatbaar, maar ze gaan voor zoiets ook geen wegen via Rome overwegen, dus die jaren rekenwerk valt weg.

Ok, schrijf jij maar een algoritme dat zegt: "ok, geef me de kortste route van A naar B, maar die hele lange omwegen hoef je niet te beschouwen". Ok, zegt de computer "geef me de lange omwegen zodat ik weet welke ik niet hoef te beschouwen". En rekenen maar...

Wat voor een mens overduidelijk is, is dat voor een computer niet per se. Wat ik probeer te zeggen is dat het algoritme niet feilloos is, het neemt dingen aan zodat het vele opties niet hoeft te beschouwen. Ik weet helaas niet precies hoe die algoritmes werken, maar blijkbaar is het een combinatie van een Greedy algoritme (dat gewoon alleen kijkt naar de kortste volgende node) en iets dat A* algoritme heet, zie hier

Ik ben het eens met King Nero. De computer hoeft helemaal niet alle lange omwegen te berekenen. Bijvoorbeeld, zodra je één willekeurige route van 5 km hebt gevonden, kun je je gelijk beperken tot alle kruispunten die binnen een straal van 5 km liggen van je vertrekpunt liggen. Alle wegen die naar een kruispunt verder dan dat leiden kun je dan wegstrepen, en dus hou je nog maar een heel beperkt aantal mogelijke wegen over. De computer zou dat zonder al teveel problemen helemaal door moeten kunnen rekenen.

Dat is ook ongeveer het principe waar algoritmes zoals A* en Dijkstra op gebaseerd zijn.

[king nero]

Ik ben het in principe niet eens met Arjan. Google geeft je de meest efficiënte oplossing. In dit geval zal je enkel moeten zoeken waarom die als meest efficiënt wordt beschouwd, dus op welke parameters er beoordeeld wordt.
Ik ga niet op de letter spelen, "de beste" of "de meest efficiënte" is voor interpretatie vatbaar, maar ze gaan voor zoiets ook geen wegen via Rome overwegen, dus die jaren rekenwerk valt weg.

Ok, schrijf jij maar een algoritme dat zegt: "ok, geef me de kortste route van A naar B, maar die hele lange omwegen hoef je niet te beschouwen". Ok, zegt de computer "geef me de lange omwegen zodat ik weet welke ik niet hoef te beschouwen". En rekenen maar...

Wat voor een mens overduidelijk is, is dat voor een computer niet per se. Wat ik probeer te zeggen is dat het algoritme niet feilloos is, het neemt dingen aan zodat het vele opties niet hoeft te beschouwen. Ik weet helaas niet precies hoe die algoritmes werken, maar blijkbaar is het een combinatie van een Greedy algoritme (dat gewoon alleen kijkt naar de kortste volgende node) en iets dat A* algoritme heet, zie hier

Als
Vertrekpunt en eindpunt beide in Nederland liggen

Dan
Negeer wegen die in India, Botswana en Ijsland liggen

Verder ga ik het woord aan gis-programmeurs laten, want ik heb er zelf geen idee van. Maar aangezien Google geen jaren rekenwerk heeft aan een dergelijk traject te bepalen, ga ik ervan uit dat lange omwegen van bij het begin geschrapt worden...

[irArjan]

Als
Vertrekpunt en eindpunt beide in Nederland liggen

Dan
Negeer wegen die in India, Botswana en Ijsland liggen

Klinkt lekker belerend, dank u... Maar dit is natuurlijk niet generiek en daarmee geen oplossing... De gebruikte algoritmes werken anders, maar dat is niet het punt...

Verder ga ik het woord aan gis-programmeurs laten, want ik heb er zelf geen idee van. Maar aangezien Google geen jaren rekenwerk heeft aan een dergelijk traject te bepalen, ga ik ervan uit dat lange omwegen van bij het begin geschrapt worden...

Klopt, natuurlijk klopt dit, dat heb ik ook nooit ontkend. Routeren kan op kleine computers juist omdat veel opties worden weggelaten...

Mijn punt is enkel en alleen dat het verzinnen van een algoritme dat die opties weg laat per definitie ervoor zorgt dat je niet meer met absolute zekerheid kan zeggen dat de gevonden route ook inderdaad de meest optimale is. Het zal inderdaad zo zijn dat door toevoeging van allerlei heuristiek Google erg dicht bij of in relatief simpele gevallen zelfs op het optimum uit komt, zoals Math-E-Mad-X ook al suggereert.

Blijft het feit dat de OP een voorbeeld laat zien waarbij voor een heen en een terug weg een andere oplossing wordt gevonden. Je kan het antwoord zoeken in argumenten waarom de ene route optimaler is dan de andere, maar je kan het ook in het algoritme zoeken die twee oplossingen vind die heel dicht bij elkaar liggen en als het door toeval (het algoritme zoekt altijd rechtsom, of wat dan ook) één van de twee vind gewoon stopt met verder zoeken, precies omdat het geleerd is vele opties weg te laten.

[Math-E-Mad-X]

Mijn punt is enkel en alleen dat het verzinnen van een algoritme dat die opties weg laat per definitie ervoor zorgt dat je niet meer met absolute zekerheid kan zeggen dat de gevonden route ook inderdaad de meest optimale is.

Maar dit klopt niet wat je hier zegt.

In het voorbeeld wat ik gaf blijf je gewoon met 100% zekerheid de kortste oplossing vinden, ookal laat je een heleboel opties weg.

Wat natuurlijk wel mogelijk is, is dat het probleem ondanks alle heuristiek te moeilijk blijft om binnen een redelijke tijd exact op te lossen, maar ik kan me niet voorstellen dat dat hier het geval is.

[irArjan]

Maar dit klopt niet wat je hier zegt.

Wat ik begrijp is dat het A* algoritme wordt gebruikt. Dit is het Dijkstra algoritme + heuristiek, zie hier en hier. Dit algoritme bepaald niet met 100% zekerheid het de kortste oplossing (maar ws voor kleine afstanden in de meeste gevallen wel met 99% zekerheid of whatever...).

Ik kan me vanuit mijn kant niet voorstellen dat ze een uitzondering gaan maken in hun manier van berekenen voor kleine afstanden. Voor kleine en grote afstanden wordt gewoon hetzelfde algoritme gebuikt, daar gaan ze geen onderscheid in maken. Dat betekent dat ook voor kleine afstanden geen 100% zekerheid hebt.

[Math-E-Mad-X]

Maar dit klopt niet wat je hier zegt.

Wat ik begrijp is dat het A* algoritme wordt gebruikt. Dit is het Dijkstra algoritme + heuristiek, zie hier en hier. Dit algoritme bepaald niet met 100% zekerheid het de kortste oplossing (maar ws voor kleine afstanden in de meeste gevallen wel met 99% zekerheid of whatever...).

Ik kan me vanuit mijn kant niet voorstellen dat ze een uitzondering gaan maken in hun manier van berekenen voor kleine afstanden. Voor kleine en grote afstanden wordt gewoon hetzelfde algoritme gebuikt, daar gaan ze geen onderscheid in maken. Dat betekent dat ook voor kleine afstanden geen 100% zekerheid hebt.

Ik weet niet welke algoritmes en heuristieken ze precies gebruiken, maar dat doet er ook niet toe, want ik reageerde alleen maar op jouw uitspraak:

het verzinnen van een algoritme dat die opties weg laat per definitie ervoor zorgt dat je niet meer met absolute zekerheid kan zeggen dat de gevonden route ook inderdaad de meest optimale is.

en die uitspraak klopt simpelweg niet. Het is prima mogelijk om een algoritme te verzinnen dat allerlei opties weglaat, maar alsnog gegarandeerd de optimale oplossing vindt. Een standaard A* algoritme bijvoorbeeld, doet precies dat (maar dat wil niet zeggen dat dat ook geldt voor de variant die Google gebruikt, want daar weet ik niks vanaf).

[boertje125]

Google stuurt je ook op de fiets vrijwel alleen over de grotere doorgaande wegen.
met de auto is dit effectief
maar op de fiets is dat lang niet zo logische.
maar volgens mij kan je ook teruglezen dat de routeplanner voor de fiets nog enigszins experimenteel is

Je kan vrijwel in een rechte lijn van a naar b in dit geval dan pak je een groot stuk langs de Jozef Israëlskade
(die route staat er bij mij overigens wel op voor de terugreis)

[jkien]

Ja, in de figuur van het startbericht heb ik de routekaarten van heen en terug in elkaar geschoven, maar die twee apart is misschien duidelijker.

Dus je zegt dat de route door het Vondelpark meer 'doorgaand' is dan de alternatieven. Bij de alternatieve routes A en B is vreemd dat B, een omweg die 2 minuten langer duurt dan A, volgens Google Maps een redelijk alternatief is.

Route C (via de Jozef Israelskade) is het kortst qua tijd en afstand, maar je denkt dat hij volgens Google Maps minder 'doorgaand' is dan de blauwe route?