Route planning

[Linus Norton]

Hi,

This may be a bit random. But I was thinking about route planning for
trains and what would be the most efficient was of planning a shortest
journey.

My graph knowledge has decayed quite badly so I was wondering if
anyone could offer me pointers on this problem.

So some obvious things: A station is a node and a journey between two
stations is an edge.

There are many train services (sub-graphs), which make up all the
possible journeys of the whole graph.

So given that a train service may be travelling from A to C via B and
another service is running from D to E via B

E
|
A --- B --- C
|
D

and that they have different departure times and travel times (edge
weights) what would be the best way to calculate the fastest way from
A to D?

I have experience with some shortest path algorithms but I am
struggling to find ways to apply them to this problem.

Any advice would be appreciated.

[wilk916]

> So given that a train service may be travelling from A to C via B and
> another service is running from D to E via B

I assume you mean E to D via B; otherwise there is no solution to get
to D with the above specified routes.

>
> E
> |
> A --- B --- C
> |
> D
>
> and that they have different departure times and travel times (edge
> weights) what would be the best way to calculate the fastest way from
> A to D?
>
> I have experience with some shortest path algorithms but I am
> struggling to find ways to apply them to this problem.
>
> Any advice would be appreciated.

It seems to me that challenge of this problem is that there are
variable weights associated with each graph node to accompany the
fixed weights assigned to the edges. A route from A-to-D via B is a
function of the time spent on the edges (edge weights) and the time
spent sitting at the station waiting to transfer trains (node
weights). The latter time is a function of both routes mentioned
above. Thus, when posing this as an optimization problem you must
consider this additional variable in the optimization. Due to the
dependence between routes, closed-form solutions to this problem may
be really difficult (if not impossible) to find. Perhaps try Monte
Carlo methods to compute the solution numerically. If the graph is
small and number of routes is reasonable, such brute force approaches
may not be so bad.

Just my two cents.

Hope this helps,
Rob

[Linus Norton]

On Sep 2, 3:58 pm, wilk916 <wilk...@gmail.com> wrote:
> > So given that a train service may be travelling from A to C via B and
> > another service is running from D to E via B
>
> I assume you mean E to D via B; otherwise there is no solution to get
> to D with the above specified routes.

This is correct, sorry about the mix up.

Thanks very much for your reply. I feel I probably did not emphasize
how bad my graph theory knowledge is now. I should not have posed the
question as one of optimization but rather just how to find a
solution.

I have (well, once had) a good enough understanding of Dijkstra's
shortest path algorithm to implement it successfully on a weighed
graph. But I just cannot wrap my head around how I would implement
something like this based on set routes (sub graphs), with different
starting times and changing between routes.

OK so here is what I am thinking (I'm sorry this sort of thing is
better with diagrams) but I will try my best:

Given all the nodes above. We have edges AB, BC, BE, DB.

Let's say they are weighted (in minutes) as

AB = 5
BC = 5
BE = 7
DB = 7

(These are completely arbitrary)

So lets say the train going from E-D leaves 9 minutes after the one
from A to C. Does this mean I should calculate the node weight of B as

sum of the route from E to B - sum of the route from A to B plus the
number of minutes E to D departed after A to C.

B = 7 - 5 + 9

So a trip from A to D would be AB + B + BD or

AD = 5 + 11 + 7

How does my shortest path algorithm know when to apply the node weight
as this only happens when changing train?

Thanks very much for your feedback, I guess this is probably a bit
above my understanding so if it is not possible to explain or offer
suggestions would you have any recommended reading for me. Thanks for
pointing me towards http://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo
(well I hope thats what you meant!) I'm not so much concerned with
optmizations, just wondering how it works in general.

Once again your feedback is greatly appreciated.

[Robert Wilkerson]

> Thanks very much for your reply. I feel I probably did not emphasize
> how bad my graph theory knowledge is now. I should not have posed the
> question as one of optimization but rather just how to find a
> solution.
>
> I have (well, once had) a good enough understanding of Dijkstra's
> shortest path algorithm to implement it successfully on a weighed
> graph. But I just cannot wrap my head around how I would implement
> something like this based on set routes (sub graphs), with different
> starting times and changing between routes.

Well, I think you are having trouble because I don't believe
Dijkstra's algorithm applies to your problem. Read below.

>
> OK so here is what I am thinking (I'm sorry this sort of thing is
> better with diagrams) but I will try my best:
>
> Given all the nodes above. We have edges AB, BC, BE, DB.
>
> Let's say they are weighted (in minutes) as
>
> AB = 5
> BC = 5
> BE = 7
> DB = 7
>
> (These are completely arbitrary)
>
> So lets say the train going from E-D leaves 9 minutes after the one
> from A to C. Does this mean I should calculate the node weight of B as
>
> sum of the route from E to B - sum of the route from A to B plus the
> number of minutes E to D departed after A to C.
>
> B = 7 - 5 + 9
>
> So a trip from A to D would be AB + B + BD or
>
> AD = 5 + 11 + 7

Yes. For your simple example, the time it takes to travel from A to D
would be 23 minutes as computed above. However, the value for B
computed above is not general and will change when considering other
solutions (for example traveling from A to D via transferring to a
different train that travels from C to D). In general, the value of B
is specific to the particular solution being examined.

> How does my shortest path algorithm know when to apply the node weight
> as this only happens when changing train?

Well, I don't think the Dijkstra algorithm applies here because of the
varying weights within the graph structure. Dijkstra applies to a
static graph with static weights for each of the elements in the
graph. Your graph is static, but your weights aren't. This is why I
mentioned a different method for computing an optimal solution in the
graph (which is what Dijkstra does for simpler problems).

> Thanks very much for your feedback, I guess this is probably a bit
> above my understanding so if it is not possible to explain or offer
> suggestions would you have any recommended reading for me. Thanks for
> pointing me towards http://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo
> (well I hope thats what you meant!) I'm not so much concerned with
> optmizations, just wondering how it works in general.

I didn't mean the MCMC algorithm specifically. Just that you will
likely need a numeric approach to solve the optimization. Again,
Dijkstra is an algorithm that solves this optimization for a problem
unlike your own. You need another algorithm that solves your specific
optimization problem. Figuring out what algorithm you need is beyond
my free time. Good luck.