In this post, I’m going to take a look into some of the journey planners that exist that you might have used, what their limitations are and how I can simplify them.
This has been something I’ve wanted to look into for a while now as I’ve recently been implementing the second version of my journey planner for my LiveTramsMCR project.
What is a journey planner in this context?
In this context, I need the journey planner to identify a route between two stops on the network. For simplicity, I don’t currently need to worry about outside factors such as engineering works, or other sections of a journey such as travel to or from a stop.
Existing techniques and solutions
Many existing solutions for journey planning that I would be able to consume for an API exist as paid-for services, that will either have a base monthly cost or are paid for on a per-request basis with a few free requests a month.
As this is for a free API and app however, the key factor will be cost. As a result of this, I decided to create my own solution, as the Metrolink network is reletively simple in its layout, and as I only needed to be interested in a route between two stops, I did not need to worry about using a maps API to determine the walking distance for example.
This led me to mainly consider shortest path solutions for the problem, such as A* search and Dijkstra’s algorithm.
While these algorithms would usually be perfect for my problem, as this network has a relatively simple structure and few nodes, there are a few properties of the Metrolink network that mean I can’t utilise these. The main of which is the layout of the network in the “core” section between Cornbrook and St Peter’s Square, as can be seen in [1].
As this section has several links between each of these nodes, the algorithm may not choose a path that remains on the same route. While this would make sense from a shortest path perspective, as the distance between the stops on each route is 1, it does not make sense for a journey planner. This could potentially result in a journey planner that suggests an end user changes tram at each of these stops before then continuing on to their destination.
While the core section is the most significant example of this, the issue would still occur between stops where there are multiple lines that run between stops. As there are multiple parts of the network where multiple lines run, this could lead to a large amount of changes being required for what would otherwise be a relatively simple and direct journey. For example, travelling from Altrincham to Trafford Bar, which could be done direct with zero changes on either the purple or green lines, could potentially require 7 changes.
An alternative approach
Because of this, I instead decided to take a different approach that utilises an interesting property of the network.
As the network is a hub and spoke network, with the centre ‘hub’ being the section between Cornbrook and Piccadilly Gardens / Victoria, there is a section of the network that all lines pass through. Becuase of this, a journey between any two stops can be done with at most one change.
This significantly simplifies the problem, as I now only need to determine where the best interchange point is for a given route, if an interchange is indeed required.
I can also use this route information to add more helpful information about a journey, for example, adding the next live service for the first part of a journey.
I can also use this information to identify the zones travelled through in a journey.
Identifying travel zones for a journey
On the surface, this may seem like a complex problem to solve as there a partial zone, where the stop can be classified as being in multiple zones, for example, zone 1/2 would be considered to be in zone 1 if this was the final stop and the journey started in zone 1, but would be in zone 2 if this was the final stop and the journey started in zone 2.
This leaves me with a useful property as I only need to consider a side of the zone if the route travels through any further stops in that zone.
This means that to solve the problem, all I need to do is remove any partial zones from the zones traversed. If there is another stop in the zone and it needs to be considered, it will be covered by the next or previous stop. I can do this by converting the list of the traversed stops into a set, which will remove duplicates, and then removing any that feature a / character, denoting a partial stop. I can also order the stops in ascending order as this brings it closer to how they are displayed for tickets.
Limitations of this approach
There are several limitations to this approach. Primarily, as this approach is built on top of properties of the network, if the network layout changes or a new extension is added, and these properties no longer stand, the journey planner will not work for any journeys between any existing stops and stops on the new section.
This approach also lacks any integration with engineering work information, meaning that, when there is either service alterations because of disruption or engineering works, the information returned from the route planner will be incorrect, as it is not updated in either of these scenarios.
Options for improvement
There are a few options to improve my approach. The main of which will be to include any engineering works or disruption information into how journeys are planned. This would ensure up to date information is always returned, and would provide far more accurate journey information. This could also be used to help user determine if an alternative mode of transport may be faster.
It may also be useful to include timetable data in the response if no service information is available. This would ensure the user has at least some idea when the next service may be. This could also be included when retrieving service information for a stop, but would need to be differentiated from live service data.