Routes plannen

[RoBBS]

Zo, mijn eerste stappen in dit subforum, Het probleem is als volgt, Ik ben al 2 dagen bezig om uit te vinden hoe een routeplanner zn werk doet,.. Ik heb als voorbeeld de NS routeplanner maar aangehouden,. een stuk minder punten waar je heen kunt en een stuk makkelijker lijkt mij.

Ik wil proberen een dusdanig systeem na te bouwen met PHP/MySQL maar ik kom er maar niet achter hoe dit goed kan gaan werken. Ik heb een werkend systeem uitgedacht maar dit komt absoluut niet in de buurt van een efficiente oplossing.

De data:
Ruim 480 mogelijkheden van station-station, dus de gegevens die ik heb staan als volgt in een database
station1, station2, eenheden prijs, eenheden km

Ik weet dus van ELK ns station waar die aan vast zit

De prijs is nog even niet van toepassing, Wat ik zelf als oplossing had is kijken waar de route heen gepland moet worden door elk station om het vertrekpunt te bekijken, bij de volgende stations weer alle stations hieromheen bekijken enzovoort, totdat je heel nederland door bent, Dan komen daar een aantal mogelijkheden uit (heel veel) en vervolgens tel je alle eenheden KM bij elkaar op, de kortste route moet het dan worden.

Nu is dit absoluut niet slim om te doen, het is traag en bij meer dan 1 user kom je waarschijnlijk grandioos in de problemen, databases niet bereikbaar enz.

Er schijnt een wiskundige formule te zijn die dit soort dingen kan berekenen,. Ik heb alleen geen enig idee hoe deze formule heet of werkt, kan iemand mij hier een beetje op weg helpen,? ik weet dat de uitleg wellicht niet helemaal duidelijk is maar ik heb mn best gedaan, als jullie meer gegevens willen weten, roep maar

[Maasluip]

Grafentheorie. Is voldoende over te vinden als je de term kent

Om het een beetje uit te leggen: je maakt een boomstructuur. Bij elke stap die de boom groeit voeg je aan elk eindpunt alle mogelijke routes naar volgende punten toe. Op gegeven moment bereikt een van de takken de eindbestemming. De kosten van die route ken je dan, op dat moment kun je de rest van de takken waarvan de kosten groter dan die ene route zijn weggooien en je concentreren op de takken met lagere kosten. Uiteindelijk hou je dan de goedkoopste oplossing over.

[ Voor 80% gewijzigd door Maasluip op 08-06-2005 15:30 ]

[Orion84]

Google eens op "dijkstra" en "kortste pad"

[RoBBS]

Kijk, dat komt goed in de buurt,. back to the drawing board

[TrailBlazer]

Orion84 schreef op woensdag 08 juni 2005 @ 15:29:
Google eens op "dijkstra" en "kortste pad"

grr dijkstra het hele internet had niet gedraaid zonder de goede man

[Zoijar]

Dijkstra voldoet niet als je alle routes wilt weten van een willekeurig punt naar een ander willekeurig punt. Dan moet je eens kijken naar het 'all pairs shortest path' proleem, bv. hier http://ai-depot.com/BotNavigation/Path-AllPairs.html

[Rey Nemaattori]

RoBBS schreef op woensdag 08 juni 2005 @ 15:25:
*KNIP*
Er schijnt een wiskundige formule te zijn die dit soort dingen kan berekenen,. Ik heb alleen geen enig idee hoe deze formule heet of werkt, kan iemand mij hier een beetje op weg helpen,? ik weet dat de uitleg wellicht niet helemaal duidelijk is maar ik heb mn best gedaan, als jullie meer gegevens willen weten, roep maar

Zoek maar eens op dijkstra's algoritme het inmiddels al bekende algoritme op google, die hebben wij op school gebruikt om onze robot de korste route te vinden over een 2-dimensionele kaart(array) met verschillende gewichten aan de 4 mogelijk heden van de nodes(de lengte van de routes dus).

Basically telt het alle afstanden tussen putn A en punt b, en rekent dan de kortste weg terug....

Ja dat is rekenintensief, zefs al bij een 'raster' van een punt of 20-40 op een legomindstorms blokje

[ Voor 18% gewijzigd door Rey Nemaattori op 08-06-2005 20:43 ]

[MSalters]

Dijkstra rekent niet *alle* paden uit. Sowieso zijn dat er oneindig veel op grafen waarbij je in cirkels kunt lopen. In het algemeen reken je geen paden uit die zeker langer zijn dan het kortste pad tot dan toe gevonden, of paden die zeker langer zullen zijn als het kortste pad. (in het normale geval dat alle afstanden positief zijn)

Als je meer a priori weet, kun je soms efficienter werken. vb. als alle afstanden tussen knopen 1 zijn, dan helpt dat. Ook kun je met trucjes de gemiddelde zoektijd naar beneden krijgen bij gelijke worst-case performance. Voor de NS kun je bijvoorbeeld stations met 1 of 2 verbindingen (circa 80%) handiger vinden door te kijken tussen welke twee knooppunten ze liggen, en alleen routes te zoeken tussen die grote knooppunten. Het laatste stukje zoek je dan in een tabel (vb Rodeschool altijd via Groningen)

[Verwijderd]

En om het probleem voor de NS nog wat moeilijker te maken: als op een traject maar 1x per uur een verbinding is, moeten de andere verbindingen hier tijdsgewijs gebruik van maken. Ofwel: als deze verbinding niet gehaald kan worden, kan een langere, niet-logische weg alsnog sneller zijn.
Van eenzelfde orde is dat niet alle treinen overal stoppen.

En nog twee stappen verder: de psychologie van de reis: mensen willen helemaal niet de kortste weg, maar de snelste. Of de gemakkelijkste, dwz minste aantal overstappen of minste aantal minuten wachttijd op de overstappunten.

Bij bijvoorbeeld wegen-routeplanners (en in mindere mate voor spoor-planners), liggen er vooral bij het begin- en het eindpunt veel mogelijkheden. Het middenstuk van de reis (=verzameling ritten), ligt over het algemeen redelijk vast op een spoorlijn of snelweg. En niet-rationeel gezien liggen er bij het beginpunt nog iets meer mogelijkheden dan bij het eindpunt, omdat je bij je beginpunt (zeg: je huis) de (sluip)wegen beter kent dan bij je bestemming.

[Verwijderd]

Rey Nemaattori schreef op woensdag 08 juni 2005 @ 20:40:
[...]


Zoek maar eens op dijkstra's algoritme het inmiddels al bekende algoritme op google, die hebben wij op school gebruikt om onze robot de korste route te vinden over een 2-dimensionele kaart(array) met verschillende gewichten aan de 4 mogelijk heden van de nodes(de lengte van de routes dus).

Basically telt het alle afstanden tussen putn A en punt b, en rekent dan de kortste weg terug....

Ja dat is rekenintensief, zefs al bij een 'raster' van een punt of 20-40 op een legomindstorms blokje

Op zich is het best te doen, ook met de hand. Zeker als je er een zekere handigheid in hebt.

Beginnen in punt A, vanuit daar de afstanden bepalen tot alle punten waar je vanaf A naar toe kunt. Kom je dan in punt B uit, doe je het zelfde. Terug naar A is zinloos want afstand A-B-A > AA. Zo kom je bijvoorbeeld in punt C. Is op dat punt nog geen kortste route (ofwel A-B-C < A-C of A-C bestaat niet), ga je door. Is er al wel een kortere route, is de verbinding A-B-C niet relevant.

En zo ga je je hele netwerk af. Wat voor een node of 10 binnen een paar minuten met de hand te doen is.

Leuker wordt het als je capaciteiten toe gaat kennen aan je verbindingen. Dat bij PAE (personenautoequivalent)<800 iedereen over route A-B-C gaat en niemand over A-D-C, en daarboven weer een percentage over A-D-C afhankelijk van het aantal PAE over link A-B-C, wat weer afhankelijk is van A-D-C. Oftewel een vreselijk iteratief proces waar je je met de hand helemaal een lamme poot aan rekent. En dat is dan nog maar het Logit-model, terwijl er nog vele manieren zijn om een dergelijke situatie door te rekenen.

Mocht je hier nog verder op in willen gaan, kan ik het boek 'Modelling Transport' van Ortuzar en Willumsen aanraden.

[Karel V]

Rey Nemaattori schreef op woensdag 08 juni 2005 @ 20:40:
[...]


Zoek maar eens op dijkstra's algoritme het inmiddels al bekende algoritme op google, die hebben wij op school gebruikt om onze robot de korste route te vinden over een 2-dimensionele kaart(array) met verschillende gewichten aan de 4 mogelijk heden van de nodes(de lengte van de routes dus).
[...]

lol, dit doet me aan deze opdracht denken:

Bereken de korts mogelijke route door een een verzameling van 50 punten die random op een X-Y grid zijn geplaatst. Hierbij mag elk punt maar 1 keer worden bezocht.

[rml][ All Languages]Alternatieve Programmeer Webstrijd[/rml]

[Zoijar]

Karel V schreef op donderdag 09 juni 2005 @ 08:54:
lol, dit doet me aan deze opdracht denken:
[rml][ All Languages]Alternatieve Programmeer Webstrijd[/rml]

Dat is wel compleet iets anders, een kortste hamilton cykel/pad En veel lastiger dan een kortste pad...

[Rey Nemaattori]

Verwijderd schreef op donderdag 09 juni 2005 @ 00:03:
En nog twee stappen verder: de psychologie van de reis: mensen willen helemaal niet de kortste weg, maar de snelste. Of de gemakkelijkste, dwz minste aantal overstappen of minste aantal minuten wachttijd op de overstappunten.

Lijkt me vrij logisch, wat is het nut van de kortste weg als de andere de snelste is? je wilt toch zsm van punt A naar punt B? Je betaalt toch wel(of niet als student )

Karel V schreef op donderdag 09 juni 2005 @ 08:54:
[...]

lol, dit doet me aan deze opdracht denken:

[...]

[rml][ All Languages]Alternatieve Programmeer Webstrijd[/rml]

Mja alleen had onze kaart slechts 15 knooppunten, wat al een hele boel scheelt. Ook moesten we van A naar B, niet een willekeurige routen oid.

[ Voor 29% gewijzigd door Rey Nemaattori op 09-06-2005 10:58 ]

[RoBBS]

MSalters schreef op woensdag 08 juni 2005 @ 23:34:
Dijkstra rekent niet *alle* paden uit. Sowieso zijn dat er oneindig veel op grafen waarbij je in cirkels kunt lopen. In het algemeen reken je geen paden uit die zeker langer zijn dan het kortste pad tot dan toe gevonden, of paden die zeker langer zullen zijn als het kortste pad. (in het normale geval dat alle afstanden positief zijn)

Als je meer a priori weet, kun je soms efficienter werken. vb. als alle afstanden tussen knopen 1 zijn, dan helpt dat. Ook kun je met trucjes de gemiddelde zoektijd naar beneden krijgen bij gelijke worst-case performance. Voor de NS kun je bijvoorbeeld stations met 1 of 2 verbindingen (circa 80%) handiger vinden door te kijken tussen welke twee knooppunten ze liggen, en alleen routes te zoeken tussen die grote knooppunten. Het laatste stukje zoek je dan in een tabel (vb Rodeschool altijd via Groningen)

Dat is wel een goed idee, Dus een tabel opstellen van de grootste knooppunten, wat wellicht dan handig is om dan om meerdere niveau's aan te houden, De grootste knooppunten, de wat kleinere stations, en daarna de plaatselijke (eind) stations. Als je dan eerst de route over de hoofdknooppunten globaal bepaald, daarna de daar aan liggende tussenknooppunten bekijken en als je dat weet dan alle stations om die route heen bekijken,.. Dat is een stuk efficienter dan heel nederland doorrekenen... Zou dit te realiseren zijn?

[MSalters]

Verwijderd schreef op donderdag 09 juni 2005 @ 00:03:
En om het probleem voor de NS nog wat moeilijker te maken: als op een traject maar 1x per uur een verbinding is, moeten de andere verbindingen hier tijdsgewijs gebruik van maken. Ofwel: als deze verbinding niet gehaald kan worden, kan een langere, niet-logische weg alsnog sneller zijn.

Irrelevant. Dit betekent alleen dat je weegfactoren anders zijn, en in minuten ipv kilometers worden uitgedrukt. (minuten na vertrek, om precies te zijn)