greatkingrat wrote: ↑19 Mar 2019, 17:21
Why is it making an extra change onto the Bakerloo at the beginning instead of just going straight to Edgware Road (Circle)?
I thought this would come up...
It makes the extra change because it calculates the route between each pair of stations separately and in isolation. This is known as the "travelling salesman problem". Imagine a salesman has a set of clients to visit in one day. In what order should he visit the clients to have the minimum amount of travelling? Because he's stopping to visit the client, it's the total travelling time or distance that he's interested in. In tube running terms, it's like us having to leave the station each time before you can catch the next train. For a Random 15, I've added a "Continuous journey?" tick box so that it will add a "changing time" when ending one "leg" and starting the next requires changing lines. So, it should find the quickest way to "join the dots" when there are fewer changes at the "dots".
In this case, because it is heading towards Marble Arch, "Great Portland Street to Paddington via Edgware Road" is best. If a station further up the Bakerloo line like Maida Vale was also on the list, it would have to consider visiting that after Paddington and then "Great Portland Street to Paddington via Baker Street" would be better. To summarise, "It's not easy!"
In isolation, according to the times I got from the working timetables, that is the quickest way from Great Portland Street to Paddington (B/C/D).
Start at Great Portland Street
Circle / Hammersmith & City / Metropolitan to Baker Street, towards Hammersmith (Circle / H&C) / Amersham / Uxbridge / Watford / Chesham [2min]
Bakerloo to Paddington (Bakerloo / Circle / District), towards Harrow & Wealdstone [3min 30sec + 2min for changing]
= 7min 30sec
Start at Great Portland Street
Circle / Hammersmith & City / Metropolitan to Edgware Road, towards Hammersmith (Circle / H&C) / Amersham / Uxbridge / Watford / Chesham [4min 30sec]
Circle / District to Paddington (Bakerloo / Circle / District), towards Notting Hill Gate [2min + 2min for changing]
= 8min 30sec
RJSRdg wrote: ↑19 Mar 2019, 23:08
Especially considering that neither changing from the westbound H&C to the Bakerloo at Baker Street, or the Bakerloo to the District at Paddington are particularly easy changes.
The program has no idea what an "easy change" is. At the moment you can enter a overall "time for changing" which should include time for changing platforms and the time you should expect to wait for the next train. As alexmcmotor points out, to represent "easy changes", I would probably have to include walking distances between each combination of pairs of platforms at stations. For expected waiting times, I would have to at least do it by line, to allow for the different frequencies of, for example, the Victoria line and the Overground.
alexmcmotor wrote: ↑20 Mar 2019, 10:54
I would be interested to see the algorithms that your program uses to come up with its solution though
, as I recently spent several weeks implementing Dijkstra's algorithm over a graph in C for my degree.
Warning: maths-geekery incoming!
For calculating the route from A to B, it does use Dijkstra's algorithm. For multi-stop routes like Random 15, it effectively uses Dijkstra but where "A having visited B but not C and D" and "A having visited C but not B and D" are separate nodes. To simplify things, only stations that are interchanges are nodes in the network. For example, Baker Street and Euston Square (because you can walk to Euston) are nodes and "H&C/Circle/Met" is an edge between them. If you want to calculate a route from (or to) Great Portland Street, it temporarily adds that as a node on that edge.
