NS Tarieven minimaliseren, prijs-/routetabel beschikbaar?

[Wolfboy]

Aangezien de prijzen van de NS niet perse vast staan voor een bepaalde route (variaties kunnen bijvoorbeeld goedkoper zijn ook al is het een langere rit) leek het me leuk dit probleem eens te optimaliseren.

Nu de vraag... hoe zou je dit het beste kunnen aanpakken.

De mogelijkheden die ik zo even bedacht heb...

• Brute-force de volledige tabel berekenen en met de hongaarse methode de meest optimale oplossingen berekenen. Beetje flauw, maar door het zeer beperkte probleemgebied een prima optie.
• Vanaf beide eindpunten met een variatie op een A* algoritme mogelijke alternatieven zoeken.
• Iets anders...?

Ter illustatrie, volgens de NS reisplanner kost een retourtje van Dordrecht naar Amsterdam Centraal € 18,10 met korting.
Een retourtje van Dordrecht naar Amsterdam Amstel (waarbij je langs Amsterdam Centraal komt) kost maar € 17,40.

Zie de http://www.ns.nl/reisplanner-v2/index.shtml als je het zelf eens wil proberen.

Mijn vragen:

1. is de prijs-/routetabel ergens te downloaden? Ik denk niet dat de NS het kan waarderen als ik het ga scrapen oid.
2. Wat voor andere algoritmes zouden hier goed werken

[Matis]

Bruteforcen lijkt me niet zo'n goed idee. Aangezien er in Nederland (volgens de reisplanner) 540 stations zijn.
De mogelijkheden zijn praktisch eindeloos.

Dat neemt niet weg dat het een leuk project lijkt

[Erwin]

Interessant! Overigens wel bezopen dat die "omweg" goedkoper is

[Wolfboy]

Matis schreef op maandag 08 november 2010 @ 16:01:
Bruteforcen lijkt me niet zo'n goed idee. Aangezien er in Nederland (volgens de reisplanner) 540 stations zijn.
De mogelijkheden zijn praktisch eindeloos.

Dat neemt niet weg dat het een leuk project lijkt

Nu vergeet je natuurlijk dat je een vaste begin en eindbestemming hebt. Je kan dus al heel snel een lading stations wegstrepen die niet relevant zijn.

Als je van Dordrecht naar Amsterdam gaat heeft het geen nut om routes naar Groningen of Den Helder te proberen aangezien je dan een grotere afstand krijgt en dus een hogere prijs. Helaas betekend die variabele wel dat je direct ook coordinaten van de stations moet hebben zodat je de afstand kan berekenen (of zouden ze de afstand op basis van spoorlengte berekenen?)

[Matis]

Elluminatie schreef op maandag 08 november 2010 @ 16:04:
Interessant! Overigens wel bezopen dat die "omweg" goedkoper is

Dat kwam vorige jaar ook ter sprake in diverse programma's. Dat is een zogenaamde omrijd-vergoeding.

Een kaartje Groningen naar Groningen-Oost via Amsterdam Centraal was goedkoper dan een kaartje Groningen Amsterdam.
Dit omdat het systeem toen dacht dat je om moest rijden over Amsterdam en daardoor dus korting kreeg. Ik meen overigens dat dat al verholpen is.

Edit; @ Wolfboy, mijn bovenstaande verhaal heeft dus wel degelijk gewerkt. Soms is een ander eindstation kiezen goedkoper. Zoals je zelf in de TS ook al aangaf.
De prijs op het spoor wordt (afaik) per spoorlengte berekend. Dat zie je ook bij de 9292ov-site. Daar staat de spoorlengte er vaak bij vermeld. De prijs wordt daarvan afgeleid.

[Voor 23% gewijzigd door Matis op 08-11-2010 16:11]

[Get!em]

Nog meer leuke voorbeelden:
Reis:
Ede - Wageningen --> Driebergen Zeist

Gepland met als eindstation:
Maarn: 2e klas enkeltje vol tarief: €4,-
Driebergen-Zeist: €5,20

[Get!em]

Zie hier voor de tarief eenheden:

http://trein-kaart.nl/

[Mad Marty]

Get!em schreef op maandag 08 november 2010 @ 16:28:
Nog meer leuke voorbeelden:
Reis:
Ede - Wageningen --> Driebergen Zeist

Gepland met als eindstation:
Maarn: 2e klas enkeltje vol tarief: €4,-
Driebergen-Zeist: €5,20

Maarn ligt nog altijd voor Driebergen-Zeist als je vanaf Ede-Wageningen komt, dus dan reis je vanaf Maarn gewoon zonder geldig vervoersbewijs.

[Wolfboy]

Mad Marty schreef op maandag 08 november 2010 @ 17:18:
[...]


Maarn ligt nog altijd voor Driebergen-Zeist als je vanaf Ede-Wageningen komt, dus dan reis je vanaf Maarn gewoon zonder geldig vervoersbewijs.

Je begrijpt hem verkeerd. Stel dat je doel is vanaf Ede-Wageningen naar Driebergen-Zeist te reizen. Dan is het goedkoper een kaartje naar Maarn te halen dan een kaartje naar Driebergen-Zeist. Terwijl het eigenlijk verder is.

[Eris]

Wolfboy schreef op maandag 08 november 2010 @ 18:07:
[...]
Je begrijpt hem verkeerd. Stel dat je doel is vanaf Ede-Wageningen naar Driebergen-Zeist te reizen. Dan is het goedkoper een kaartje naar Maarn te halen dan een kaartje naar Driebergen-Zeist. Terwijl het eigenlijk verder is.

Je hebt eerst Ede-Wageningen -> Veenedaal - De Klomp -> Maarn en daarna pas Driebergen-Zeist. Volgens mij kom je dan wat te kort

Ede-Wageningen --> Maarn = 4,00
Maarn --> Driebergen-zeist = 2,20

Totaal = 6,20

[Voor 13% gewijzigd door Eris op 08-11-2010 18:16]

[Wolfboy]

@Eris: je begrijpt het niet, het doel is om in Driebergen-Zeist terecht te komen nadat je van Ede-Wageningen vertrokken bent. Voor de duidelijkheid hier de hele routetabel met de kosten.

Leg maar eens uit waarom de eerste (kortere) reis duurder is dan de 2e.

Ede-Wageningen - Driebergen-Zeist (alle tussengelegen stations erbij)
Kosten: € 5,20 voor een enkele reis

Tijd	Station / Halte	Spoor	Richting	Reisdetails
19:57	Ede-Wageningen	3	Utrecht Centraal	Intercity (NS)
20:12	Driebergen-Zeist	2

Ede-Wageningen - Maarn (alle tussengelegen stations erbij)
Kosten: € 4,00 voor een enkele reis

Tijd	Station / Halte	Spoor	Richting	Reisdetails
19:57	Ede-Wageningen	3	Utrecht Centraal	Intercity (NS)
20:12	Driebergen-Zeist	2
20:25	Driebergen-Zeist	1	Rhenen	Sprinter (NS)
20:31	Maarn	2

[CoolGamer]

Wolfboy schreef op maandag 08 november 2010 @ 19:37:
Leg maar eens uit waarom de eerste (kortere) reis duurder is dan de 2e.

Duidelijk te zien aan de hand van de kaart: http://trein-kaart.nl/

Naar:

• Driebergen-Zeist kost 7+14 eenheden
• Maarn kost 7+14+8 eenheden

Ik neem aan dat hij de prijs bepaald aan de hand van de route met het minst aantal tariefeenheden.

[Borizz]

Dit heeft volgens mij wel wat weg van het Traveling salesman problem.

[Woy]

Borizz schreef op maandag 08 november 2010 @ 19:46:
Dit heeft volgens mij wel wat weg van het Traveling salesman problem.

Dat is toch wel een conceptueel ander probleem. Daar heb je n plaatsen waar je langs wilt gaan, maar waarvan je de ideale volgorde wil bepalen?

Doet dit fenomeen zich eigenlijk alleen voor als je met een intercity langs een station gaat, en daarna met een stop-trein terug moet? Dan zou je als basis gewoon je eindbestemming kunnen nemen, en dan eenvoudig kijken of de eerstvorige/volgende stations goedkoper zijn.

[CoolGamer]

Woy schreef op maandag 08 november 2010 @ 20:31:
Doet dit fenomeen zich eigenlijk alleen voor als je met een intercity langs een station gaat, en daarna met een stop-trein terug moet?

Of als je andere route pakt.

Voorbeeld: Als je van Utrecht naar Brummen gaat geeft de reisplanner twee verschillende routes, aan de hand van welke tijd je wilt vertrekken/aankomen. De ene gaat via Arnhem (de kortste), terwijl de andere over Zutphen gaat. Utrecht->Brummen kost €12,60 (enkeltje), terwijl Utrecht->Zutphen €12,70 kost.

[Matis]

TheCoolGamer schreef op maandag 08 november 2010 @ 20:39:
Of als je andere route pakt.

Voorbeeld: Als je van Utrecht naar Brummen gaat geeft de reisplanner twee verschillende routes, aan de hand van welke tijd je wilt vertrekken/aankomen. De ene gaat via Arnhem (de kortste), terwijl de andere over Zutphen gaat. Utrecht->Brummen kost €12,60 (enkeltje), terwijl Utrecht->Zutphen €12,70 kost.

Station Gilze-Rijen is ook net het omslagpunt als je naar Amsterm (Airport) moet. Je hebt daar de keuze OF over Dordrecht en Rotterdam OF over Den Bosch en Utrecht.
We hebben een keertje aan de conducteur gevraagd of het uitmaakt. Hij zei dat dat niet het geval was, aangezien de ene rit beduidend sneller is (over Den Bosch) en de andere rit (over Dordrecht) korter qua kilometers.
Echter is een kaartje naar Schiphol daarvandaan wel goedkoper over Dordrecht, alleen scheelt het (de laatste keer dat ik met de trein ging) niet heel veel geld. Maar je zit er wel weer langer door in de trein.

[Voor 11% gewijzigd door Matis op 08-11-2010 20:56]

[Borizz]

Woy schreef op maandag 08 november 2010 @ 20:31:
[...]

Dat is toch wel een conceptueel ander probleem. Daar heb je n plaatsen waar je langs wilt gaan, maar waarvan je de ideale volgorde wil bepalen?

Ik zie dat ik me inderdaad vergist heb. Ik denk dat het Shortest path problem dichter in de buurt komt. In plaats van de afstand reken je dan natuurlijk wel met de kosten.

[Wolfboy]

Borizz schreef op maandag 08 november 2010 @ 21:30:
[...]


Ik zie dat ik me inderdaad vergist heb. Ik denk dat het Shortest path problem dichter in de buurt komt. In plaats van de afstand reken je dan natuurlijk wel met de kosten.

Het probleem is alleen iets complexer dan dat. Je hebt hierbij in principe geen vast start of stoppunt.

Het probleem heeft wat dat betreft meer weg van een Wikipedia: Minimum spanning tree

[marrabel]

Voor het berekenen van de kostprijs gaat de NS uit van de kortste theoretische afstand tussen begin- en eindstation, zonder te kijken naar de daadwerkelijke dienstregeling (route treinen ; soort trein stoptrein/sneltrein/intercity).

Soms mag je via 2 of meer verschillende trajecten reizen. Dit is het geval als je via een andere route dan de kortst mogelijke route sneller op je eindbestemming aankomt (dat kan voor een bepaalde reis altijd zo zijn, of alleen afhankelijk van het tijdstip van reizen), of als je minder moet overstappen. Dan mag je die trein ook nemen.

Bijvoorbeeld: van Breda naar Amsterdam. Dit kan via:

• [1a] Dordrecht-Rotterdam-DenHaag-Leiden-Haarlem (geen overstap, 136 eenheden)
• [1b] Dordrecht-Rotterdam-DenHaag-Leiden-Schiphol (1 overstap, 133 eenheden)
• [2] Tilburg-DenBosch-Utrecht (1 of 2 overstap; 130 eenheden)

Ook al is de reisafstand niet precies gelijk, je betaalt altijd voor de kortst mogelijke afstand tussen Breda en Amsterdam (130 eenheden).
[2] is zowel de kortste afstand als ook de snelst mogelijke verbinding, maar als [1a] of [1b] de eerstvolgende trein is die gaat dan ben je daarmee sneller op je eindbestemming dan wachten op de eerstvolgende [2] dus mag je die ook nemen.
[1a] vertrekt gelijk met [1b] maar doet er 10 minuten langer over, dus [1a] komt nooit eerder aan dan [1b], maar omdat je bij [1a] niet/minder hoeft over te stappen mag je die ook nemen (dus ondanks zowel langere reistijd als langere afstand).

Bij het reizen via een andere route dan de kortst mogelijke afstand mag je je eindbestemming niet passeren (met intercity/sneltrein) om daarna weer 1 of 2 stations terug te gaan (langs dezelfde route) met een stoptrein. Als je dit toch wilt, dan moet je een via kaartje kopen (en omdat de minimale reisafstand groter wordt is zo'n kaartje dan ook duurder).

De enige uitzondering is als er geen andere mogelijkheid is. Dit is het geval bij Ede-Wageningen -> Maarn. Ondanks dat er een korte directe spoorrails ligt tussen beide stations rijden er op dit traject geen stoptreinen! In Maarn stopt alleen de stoptrein Driebergen-Zeist <-> Rhenen. Dus de reizigers tussen Ede-Wageningen en Maarn hebben de pech dat er geen directe dienstregeling tussen beide stations is, daardoor zijn de veel langer onderweg t.o.v. een dienstregeling waarbij er wel een directe verbinding zou zijn, maar ze betalen gewoon het normale tarief van E4,00 alsof er wel een directe route mogelijk zou zijn (en niet van de werkelijk route die ze moeten nemen en eigenlijk E7,10 kost). Dus gelukkig hebben zij niet dubbel pech.

• Ede-Wageningen -> Driebergen-Zeist. Afstand is 7+14+8=29 eenheden, dus prijs is E5,20
• Ede-Wageningen -> Maarn Afstand is 7+14=21 eenheden, dus prijs is E4,00
• Ede-Wageningen -> via Driebergen-Zeist -> Maarn Afstand is 7+14+8+8=37 eenheden, dus prijs is E7,10

De eerste reis is niet duurder, maar dat is juist het normale tarief
Je mag alleen voor E4,00 van Ede-Wageningen naar Driebergen-Zeist als je daarna doorreist naar Maarn. Maar omdat je onderweg mag uitstapen (om een reis later op de dag voort te zetten) is dit met een papieren kaartje niet te controleren. Bij de ov-chipkaart moet je dus wel in Maarn uitchecken.

Als variatie hierop:
Als je van Veenendaal-DeKlomp naar Utrecht wilt, dan kun je ook een kaartje kopen Veenendaal-DeKlomp -> Maarn (twee naast elkaar gelegen stations maar er is geen trein die zowel in Veenendaal-DeKlomp stopt als in Maarn). Deze reis gaat namelijk altijd via Utrecht. Dat kost maar E3,00 i.p.v. E6,00. Dus 50% korting

Dordrecht -> Amsterdam Amstel
De reden dat je van Dordrecht via Amsterdam Centraal naar Amsterdam Amstel mag reizen is afhankelijk van het vertrektijdstip (1) of (2)
(1) omdat je via Amsterdam Centraal toch eerder op je eindbestemming aankomt, dan indien je zou wachten op de trein met een kortere reisafstand.
(2) omdat je minder hoeft over te stappen, dan indien je zou wachten op de trein die eerder op de eindbestemming aankomt.
Als je vanuit Dordrecht naar Amsterdam Centraal wilt kun je dus in dit geval goedkoper uit zijn als je kiest voor Amsterdam Amstel als eindbestemming. Maar ook hier kan dit alleen met een papieren kaartje, want als je met de ov-chopkaart niet verder reist dan Amsterdam Centraal dan kun je nooit bij Amsterdam Amstel uitchecken.

Maar terugkomend op de uitdaging in de topicstart...
Afstanden tussen stations zijn gemakkelijk in te voeren (zie eerder geposte link naar tarief eenheden), maar alle mogelijke reizen (reisduur, aankomsttijden vanaf elk vertrektijdstip) tussen een groot aantal stations uitzoeken wordt lastig als je de complete dienstregeling niet hebt. Dus je moet het aantal mogelijke kandidaat eindstations zo klein mogelijk maken, zodat je maar van enkele kandidaat stations de dienstregeling hoeft uit te zoeken.
Je moet dus op zoek gaan naar stations (X) in de buurt van jouw doelstation die voldoen aan de onderstaande voorwaarden:

• afstand vanaf het opstapstation naar station X moet korter zijn dan naar jouw doelstation
• een van de mogelijke routes naar station X moet lopen via jouw doelstation. Maar omdat dit dan niet het kortste traject is moet die reis dan wel sneller zijn (reisduur, aankomsttijd) of minder overstappen hebben t.o.v. het kortste traject. Je mag hierbij onderweg de eindbestemming niet passeren; tenzij er op het traject dat je neemt en waarbij je je eindbestemming voorbij rijdt geen stoptrein rijdt (en wel sneltrein of intercity).

[Voor 19% gewijzigd door marrabel op 09-11-2010 00:48]

[Mad Marty]

I stand corrected: ik had even niet door dat er geen trein is die op zowel Ede-Wageningen als Maarn stopt en dat je dus altijd over Driebergen-Zeist moet. Het voorbeeld dat ik in mijn hoofd had is Leeuwarden - Utrecht Overvecht. Je mag dan niet via Utrecht Centraal, ook al is dat sneller. Je moet dan de stoptrein in Amersfoort (of in Zwolle al) pakken om naar Utrecht Overvecht te gaan.

Dat is ook wat marrabel hierboven bij zijn tweede punt aangeeft.

[Enfer]

Mad Marty schreef op dinsdag 09 november 2010 @ 07:03:
I stand corrected: ik had even niet door dat er geen trein is die op zowel Ede-Wageningen als Maarn stopt en dat je dus altijd over Driebergen-Zeist moet. Het voorbeeld dat ik in mijn hoofd had is Leeuwarden - Utrecht Overvecht. Je mag dan niet via Utrecht Centraal, ook al is dat sneller. Je moet dan de stoptrein in Amersfoort (of in Zwolle al) pakken om naar Utrecht Overvecht te gaan.

Dat is ook wat marrabel hierboven bij zijn tweede punt aangeeft.

Klopt, anders zal iedereen die naar Utrecht moet maar een kaartje tot Overvecht kopen, om zo de prijs te drukken (als dat goedkoper zou zijn)