Navigating the world just got simpler! These graphing tricks ensure you’ll determine optimal public transit routes throughout cities, and even entire countries.
Welcome back!
In Part 1 of this article, we discussed how to generate public transit routes. This part will focus on optimising the computation time of the process, by knowing the geographical locations of bus stops.
The number of stops (vertices of the graph) is the factor having the greatest impact on the time of generating routes in the described algorithms. The larger the city in which you search the route, the more vertices will be in the graph. Using the example of the city of Wrocław, there are 1,245 bus and tram stops (March 2018 data). For this number of stops, the matrix used to calculate the route will consist of 1,550,025 items.
By knowing the geographical locations of bus stops, you can significantly reduce the amount of data processed by the algorithm. For Graph G with initial and final bus stops, you can estimate such vertices as having no effect on the route. Therefore, by knowing these initial and final bus stops, you can create a second graph based on Graph G.
This new graph will be limited only to vertices from which we expected it will generate a route of similar quality to the routes generated from Graph G.
The number of vertices, from which the second graph will be created, is different for each pair of initial and final transit stops. There are numerous heuristic possibilities to determine which graph is optimal for a given start and end stop, and which will be excluded from the route calculation.
Figure 1 illustrates the topological position of stops in the city of Wrocław. Here, the initial and final bus stops are coloured blue. Based on geographical locations, we marked the areas that consist of stops most likely to create optimal routes.
Graphing Division based on Graphic Topology
Figure 2: An exemplary graph of public transit routes.
Figure 2 demonstrates an example graph of transit routes with eleven bus stops, as shown using the graph vertices, with four transit lines, marked in black, blue, green and red. The graph also includes pedestrian links – marked with dashed lines.
Based on information regarding the location of the vertices (bus stops) on the map, the algorithm can estimate the stops or transit lines to be excluded upon generation of a route.
For example, when searching for a connection between vertex number 1 and point number 9, you can exclude stops 2,3,12,11,10,8, due to their graphic positions indicating they will fail to create optimal connections between initial and final bus stops.
The algorithm specifying a graph with a smaller number of vertices should specify stops that should not affect the route or leave only those that can have this effect or do both.
The method of determining which vertices should be in the graph should not be characterized by high computational complexity. Otherwise, the benefit from reducing the number of vertices will be overcome by the time taken calculating this graph.
Heuristics Based on Area Division
Figure 3: Graph split into grid of rectangles.
We can embed the boundaries of the graphed public transit routes in a geometrical figure, such as a rectangle. Then, we can divide the obtained rectangle into smaller parts of identical surface size, thus dividing the graph into equal parts. This is one of the simplest divisions, as it is characterised primarily by uneven distributions, or even a lack of vertices in some areas.
The algorithm that uses such a division has three main tasks:
- Determining the size of the division – i.e. the size of the areas to be divided by the graph.
- Selecting areas for given start and end points – where optimal routes are expected to be found.
- Creating a graph with vertices within selected areas.
The easiest way to select areas for optimal routes, is to create a straight line between the initial and final points. The next step is to select all rectangles intersected by the created line. For the initial bus stop number 1, and the final bus stop number 9, the division will appear as demonstrated in Figure 4, with division of the graph made into 16 parts.
Figure 4: Bus stops determined based on graph topology
Opting for vertices inside the selected areas, are presented using the graph in Figure 5. The graph consists mostly of vertices required to create the correct route.
Figure 5: Results Graph
Including Interchange Hubs in Graph Selection
The creation of a segment between the initial and final bus stops, and selecting the areas intersected by this section does not consider all possible cases.
In this instance, the vertices 4,5,6 form the so-called ‘interchange hub’. Since they are in close geographical distance one another, they are therefore connected via pedestrian links. Furthermore, these connect three bus lines.
One of the ways to find such hubs, is to find areas with the largest number of vertices and join them to previously selected areas.
Figure 6: ‘Interchange hub’ attached to route search area.
The graph obtained based on Figure 6 additionally features a transit hub, as presented in Figure 7. Including this area results in a graph more likely to demonstrate an optimal route.
Figure 7: Resulting graph, including the ‘Interchange hub’.
Figure 8 presents real-life examples of route generation using heuristics based on the division into areas. What’s notable is that all generated routes are located inside estimated borders. Abandoning the search of the whole matrix allows for the acceleration of calculations – especially on very short routes.
Heuristics using graph topology allow you to receive optimally-timed routes within not just a city, but an entire country. If you wish to calculate the route from City A to City B, you should search the matrix of the minimum number of transfers covering the entire country. This would however result in extensive times of generation.
However, by understanding the topologies of the graph, it is possible to narrow down the space in which the search for a solution will be carried out.
See the GitHub repo
Please see this link for the GitHub repo, concerning an application I wrote for generating Public Transit Routes. I used data from the city of Wrocław. It also includes genetic algorithms which I haven’t covered in this article.
Literature:
- Koszelew J, Ostrowski K, Evolutionary Algorithm with Geographic Heuristics for Urban Public Transportation, Springer-Verlag, Berlin, 2012
- Koszelew J, Ostrowski K, Approximation Method to Route Generation in Public Transportation Network, 2008
- Hartley J, Wu Q, Accommodating User Preferences in the Optimization of Public Transport Travel. 2004
- Koszelew J, An Evolutionary Algorithm for the Urban Public Transportation. Springer, Heidelberg, 2011
- Koszelew J, Ostrowski K, A Genetic Algorithm with Multiple Mutation which Solves Orienteering Problem in Large Networks, 2013
- Wellman M ., Ford M, Larson K, Path planning under time-dependent uncertainty, Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence, 1995
- Koszelew J, The Theoretical Framework of Optimization of Public Transport Travel, 2007
