Android Question Generic programing question - how to code a route planner (for train networks)

[nemethv]

Hi,

This is a generic question, not specifically b4a. I'm trying to get my head around the overall logic to program a route planner for a train network. There are 400 or so stations and 14 or so lines that use the network, so interchanges are important. How is this done?
The only thing I'd really need in it is stations and time distances, optimally zone information (zone 1, 2 etc) and disability-friendly info but that latter aren't a requirement.
Any suggestions please?
Thanks

 

[nwhitfield]

There is a well known algorithm for this, called the Dijkstra algorithm. This page describes it in some detail

http://nptel.ac.in/courses/105104098/TransportationII/mod13/15slide.htm

It may be fairly intensive, but on the other hand, if the network doesn't change often, you could do all the calculations and provide them in a database that's included as part of an app.

 

[CidTek]

There is a well known algorithm for this, called the Dijkstra algorithm. This page describes it in some detail

http://nptel.ac.in/courses/105104098/TransportationII/mod13/15slide.htm

It may be fairly intensive, but on the other hand, if the network doesn't change often, you could do all the calculations and provide them in a database that's included as part of an app.

One thing I have noticed in transit trip planning is that the shortest routes aren't always the fastest routes based on schedules and frequency of trips for individual connections.

 

[nemethv]

There is a well known algorithm for this, called the Dijkstra algorithm. This page describes it in some detail

http://nptel.ac.in/courses/105104098/TransportationII/mod13/15slide.htm

It may be fairly intensive, but on the other hand, if the network doesn't change often, you could do all the calculations and provide them in a database that's included as part of an app.

Thanks - seems pretty advanced. Any thoughts on how to implement this in b4a?

 

[nwhitfield]

Yep; and sometimes things like zonal fares can make quite a big difference, too; to get to one of my favourite bars, if I take the train via zone 1, I pay 2.20 (2.80 peak), whereas avoiding zone 1 is 1.50 (1.60); Sometimes, to cross town, the quickest route for me is to head out of town to pick up a faster line coming back in. And that's before you consider real time info on delays, closures, etc, which can make it even trickier.

I don't know what algorithm they use, but unless you're thinking of somewhere very peculiar, or absolutely have to code this yourself, the Metro app probably already covers it - metro.nanika.net

 

[sorheim]

One way I can think of would be to represent the stations in a matrix. List the stations across the columns and the rows. The cell where two stations intersect will hold a number (referred to as cost). If there is no connection between the two then set cost as 0 or -1. If there is a connection even if via other stations then set the cost to a positive integer. You will have to decide how to determine cost. If you are looking to find shortest time and it is a quick route then the cost will be a smaller number. If it is a route that will take longer then set the cost to a higher number.
Hopefully this will give you some ideas.

 

[nemethv]

One way I can think of would be to represent the stations in a matrix. List the stations across the columns and the rows. The cell where two stations intersect will hold a number (referred to as cost). If there is no connection between the two then set cost as 0 or -1. If there is a connection even if via other stations then set the cost to a positive integer. You will have to decide how to determine cost. If you are looking to find shortest time and it is a quick route then the cost will be a smaller number. If it is a route that will take longer then set the cost to a higher number.
Hopefully this will give you some ideas.

Thanks for that, I'll experiment with it!