[PHP] Traject berekening NS

[Eijkb]

Voor een website hebben we het plan opgevat om een traject module te implementeren op basis van alle treinstations in Nederland. Momenteel hebben we 391 stations ingevoerd in een database (deze bestond al).

Het probleem is alsvolgt:

Je vult beginstation en eindstation in. Wat moeten we dan weten om te berekenen wat het traject is? In eerste instantie zonder een tussenstation. Ik zat zelf te denken dat je dan van ieder station moet weten wat de naburige stations zijn. Door deze dan af te lopen kan je uiteindelijk wel bij het eindstation komen:

Van A naar D:

In de database staan de volgende records van naburige stations:

A-B
A-C
B-D
C-E
D-F

Het script gaat vervolgens kijken:

Waar kan ik naar toe vanaf A? Antwoord: B en C.
Waar kan ik naar toe vanaf B? Antwoord: D

Antwoord gevonden: A - B - D

Maar goed, voor 5 stations is dat nog te doen natuurlijk, voor bijna 400 stations is dat wat lastiger.

Kan iemand een beter algoritme / systeem aanraden? Moeten we gewoon alle trajecten gaan opslaan? Dat zijn nogal wat mogelijkheden lijkt me met 391 mogelijke begin en eindstations.

[Verwijderd]

Ik denk dat je moet gaan kijken naar algoritmen met betrekking tot grafen.

Daar is vast en zeker wel wat over te vinden, want dit is een probleem dat even oud is als de computers zelf.

[ Voor 1% gewijzigd door Verwijderd op 12-01-2006 14:24 . Reden: ik graaf, jij graaft wij grafen ]

[LauPro]

Hier zijn algoritmes voor, dit is eigenlijk de basis van elke navigatiesoftware. 400 stations klinkt veel maar de trajecten zijn een stuk minder. Als je eens begint met een query uit te voeren bij het start en het eind station en dan kijken of er overlap is. Als je dan van Groningen naar Zeeland wil dan zal het script wat zwaar worden wellicht, maar in het algemeen valt het wel mee denk ik.

[Boss]

Matrices, graven en het routeprobleem. Zijn een hoop boeken over te vinden, en ik denk zelfs dat je er met een VWO Wiskunde-A (of hoe dat nu ook mag heten) uit kan komen.

Moet je ook nog eens weten dat je sommige stukken beter met een IC dan met een stoptrein kan doen...

[NMe]

Als je het goed wil doen, dan maak je een gewogen graaf, die je als matrix invoert in je systeem. Als gewicht van een lijnstuk lijkt de reistijd me het meest geschikt. Van daaruit kun je gaan werken.

Hou die startmatrix in gedachten, met daarin de reistijd die nodig is om van elk punt naar elk ander punt te komen met 0 tussenstations. Je zult dan alle afstanden krijgen van punten die zonder andere stations bereikbaar zijn. Daarna breid je het uit: 1 tussenstation, 2, 3, enz. Uiteindelijk ga je door tot je van elk punt een idee hebt hoe lang het duurt en welke stations je nodig hebt.

Lineair programmeren kan hier een uitkomst bieden.

offtopic:
Graven doe je met een schep, en andere graven wonen in landhuizen. gerben1986 en Boss, jullie bedoelen grafen.

[Janoz]

LauPro schreef op donderdag 12 januari 2006 @ 13:04:
Hier zijn algoritmes voor, dit is eigenlijk de basis van elke navigatiesoftware. 400 stations klinkt veel maar de trajecten zijn een stuk minder. Als je eens begint met een query uit te voeren bij het start en het eind station en dan kijken of er overlap is. Als je dan van Groningen naar Zeeland wil dan zal het script wat zwaar worden wellicht, maar in het algemeen valt het wel mee denk ik.

mwah, als je geen slimmigheden gebruikt is zelfs 400 al ontiegelijk veel. Dan zijn toch al zo'n 160000 connecties (volledig verbonden graaf waarbij elke edge een route aangeeft).

Een handige optimalisatie is om de stations te verdelen in 2 typen. ALs eerste heb je de knooppunten. Dit zijn de stations waarop meerdere lijnen zijn aangesloten. Als tweede heb je de rest. Dit zijn de stations waarvandaan je amar bij twee andere stations kunt komen. Het hele netwerk bestaat dus uit een graaf van knooppunten en elke edge bestaat uit een lijstje 'rest stations'. Als je nu een route wilt berekenen bepaal je eerst of ze misschien op dezelfde edge zitten. In dat geval is de oplossing immers makkelijk. Als dit niet het geval is genereer je een graaf met hierin alle knooppunten en het start en eind station. De graaf is dan een stuk kleiner dan de genoemde 400 nodes.

[joepP]

Zoek eens op Dijkstra's kortste pad algoritme.

[prototype]

Zoals joepP en -NMe- al zeggen kan je het beste met een gewogen graaf werken, en daar de dijkstra algoritme op toepassen. Het punt echter is dat je hierbij zelf de gewichten moet bepalen; hoe definieer jij de 'meest efficiente route'? Dit kan terugkomen in reistijd, aantal keren overstappen, of afstand in km en daarmee in kosten. Je zult dergelijke factoren moeten betrekken in het bepalen van de gewichten van de edges van de graaf, om de dijkstra algo zinnig te gebruiken

[ Voor 6% gewijzigd door prototype op 12-01-2006 16:40 ]

[joepP]

Het is niet helemaal zo straightforward als jij doet voorkomen, omdat de factor tijd ook nog een rol speelt. Bijvoorbeeld, je kan om 15.15 in Utrecht zijn, maar de trein naar Amsterdam rijdt om 15.14 en 15.44. Om naar Amsterdam te komen moet je dan nog wel rekening houden met die wachttijd. Een normale graafrepresentatie met gewichten op de kanten is niet genoeg.

Maar toegegeven, het algoritme is natuurlijk simpel aan te passen aan deze details.

[prototype]

joepP schreef op donderdag 12 januari 2006 @ 17:41:
Het is niet helemaal zo straightforward als jij doet voorkomen, omdat de factor tijd ook nog een rol speelt. Bijvoorbeeld, je kan om 15.15 in Utrecht zijn, maar de trein naar Amsterdam rijdt om 15.14 en 15.44. Om naar Amsterdam te komen moet je dan nog wel rekening houden met die wachttijd. Een normale graafrepresentatie met gewichten op de kanten is niet genoeg.

Maar toegegeven, het algoritme is natuurlijk simpel aan te passen aan deze details.

Hehe, mijn post nog een keer lezen zou je goed doen. Ik zeg JUIST schijnbaar onbelangrijke factoren als tijd, afstand (en daarmee ook prijs van het kaartje) betrokken moeten worden in het bepalen van de gewichten.

[Jurgle]

offtopic:
Als je om 15.15 in Utrecht kan zijn, haal je die trein van 15.14 met weet ik veel hoeveel vertraging makkelijk!

[Eijkb]

Maar goed, heeft de NS ook een algoritme gebruikt bij de aanleg van het spoor? Ik moet dus ook rekening houden met de bestaande sporen en aansluitingen. Dat is toch niet te berekenen met een bestaand algoritme?

[Mithrandir]

Eijkb > natuurlijk wel, je moet alleen goed weten waar je mee bezig bent.

Dit probleem is op te lossen met een hoop algoritmes: Dijkstra's, A*, Greedy Best First search... Allemaal met hun voor- en nadelen. Misschien is het voor de topicstarter interessant om niet óf deze dingen te onderzoeken, of een extern iemand die bijvoorbeeld Kunstmatige Intelligentie heeft gestudeerd inhuren om zoiets snel en eenvoudig op te lossen...

[SchizoDuckie]

offtopic:
Weet je zeker dat je dit project niet uit wil stellen tot na 10 december? ze gaan de complete dienstregeling overhoop gooien, kan je je hele graaf weer overnieuw maken...

[ Voor 14% gewijzigd door SchizoDuckie op 19-01-2006 02:19 ]

[alienfruit]

Ach, je weet dat als je een bus of trein niet altijd het busstation/centraal als laatste halte neemt, dat je minder bussen of buslijnen hoeft in te zetten. Waardoor er efficienter en goedkoper kan worden gewerkt

[Eijkb]

Het valt nog niet mee. Beter dat we de gebruikers gewoon alle stations die ze passeren laten invullen (het gaat om forenzen, dus steeds dezelfde route) ipv alleen een begin en eindstation In ieder geval is de vader van een vriend (wiskunde leraar) er mee bezig icm met een kaart van de NS lijnen

Dank voor jullie hulp zover en ik ga al die algoritmes zeker eens bekijken. Tevens een vriend van me inschakelen die toevallig AI gestudeerd heeft!