How to Generate Public Transit Routes

Themarket forsearch enginesofferingpublic transport connections is already quitesaturated. In Poland, services such asGoogleMaps,jakdojade.pl,e-podróżnik.pl,androzkladzik.plhave beenoperatingformany years.

However, if you wantto learn how to implement a much simpler version of such algorithms, this article is for you.

Iwilldescribewhatthe network model looks like, what to consider as input data, what output data should be expected,and how the algorithm calculatingtheroutes works.

Inthesecondpart ofthisarticle, Iwillshow you how to optimize this processknowing the geographical locations ofbusstops. 

Prerequisites for Generating Public Transit Routes

First, let’s discussthe input data.Thisconsistsof data entered by the user,as well asbus timetabledataalongsideinformationofthe geographicallocationof the routes. The datasetsprovided by the user can include: 

 Bus stopgeographical location datasetsmust consist of: 

Timetable datamust be composed of avariancelist ofeachbusline (there may be many variants of one line, e.g.a varianttaking into accounta detour ofcertainstreets). 

Each variant of the journey contains its list ofbusstops,withthebusstopinformationincluding: 

Another issue is themock-upof the transport network model. One of the easiest and most frequently used modelspresentingthis networkisa directed graph.In this model, bus stops act as vertices, and the transit network connectionsmake upthe edges of the graph. 

For example, bus travel from transit stop A to transit stop B or pedestrian journeys.On-foot journeys, as the name implies, are those that can be reached on-foot within a short time, e.g. 5 minutes. 

Below you can see an exemplary graphic displaying the vertices of such a graph superimposed on a map ofWrocław, Poland.

ProblemSpecification 

To illustrate the problem, I created an example graphoftransitlinks: 

The graph corresponds with a sample public transport timetable: 

If the passenger intends to travel from transit stop 10 to transit stop 9, they can take three possible routes: 

1. The first route assumesatransferbetweenbusesattransit stop4from theBlueLineto theRedLine. 
2. The second route assumes that the passenger willtravel alongtheBlueLinetotransitstop6,wheretheywillproceedon-foottotransitstop 5, from where they willcontinuetheir journey alongtheRedLine. 
3. Route number three is one of the leastidealin terms of the number of stops. This routeadoptsa circular route,consisting oftravel alongBlueandBlack Lines,witha final interchangeattransitstop 11onto theGreenLine. Such a‘roundabout’route canberun, for example, through the citybeltwayand despite thegreaternumber oftransitstopsalong the route, it mayprovefaster thananalternative trip through city centertraffic. 

We can illustrate eachroute alongsidebus arrivaltimesat given stops. We can see thatroutes 1and2,despitebeing separate journeys, take the sameamount oftime. The‘roundabout’journeyon route number 3expends considerablymore time. 

To enable faster route finding, we can create an algorithmbased on the generation of two-dimensional arrays. 

The generation of arrays is a process thatties upresources, but it is a one-off operation. Simply searching for routes using the previously generated matrix allows you to findroutesin a time acceptableforthe user. 

Minimum Change Number Matrix 

First, we need a two-dimensional matrix of the minimum number of transfers. For this example, we can call it theQ matrix. Each cell value Q [start, end] corresponds to the minimum number of transfers on the route that should be made to get from the Initial bus stop to the Terminal bus stop.

Creating aMatrix

Step 1. 

The first step in obtaining theQ matrixis to create a squareT-Matrix. The easiest way to implement it, would be as a two-dimensional array, whereby the size of the T Matrix is equal to the number of vertices in the graph. Rows and columns in this matrix label the specific vertices. Initially, the matrix consists only of zero. 

Step 2.

The second step is to check whether you cantravel fromthestartbus stop to theterminalbus stop. If the directjourneydoes not occur, thena value 0 isinsertedinto the cellT[start, stop]. When such ajourney doesoccur,then avalue 1 is insertedinto thecellT[start, stop]. 

Example: 

Fromtransit stop 1you cantraveltotransitstops 2, 3, 12, 11using theBlackLineandtotransitstops 7, 4, 5, 9using theRedLine. 

Therefore, the firstrowdemonstrates the following: 

T [1,2] = 1– Journeyalong the BlackLine 

T [1,3] = 1 –Journey along the BlackLine 

T [1.4] = 1 –Journey along the RedLine 

T [1.5] = 1 –Journey along the RedLine 

T [1.7] = 1 –Journey along the RedLine 

T [1.9] = 1 –Journey along the RedLine 

T [1.11] = 1 –Journey along the BlackLine 

T [1.12] = 1 –Journey along the BlackLine 

The remaining valuesin this row willadoptthe value 0asthere is no direct connection between thesetransitstops.As such,the entire T-Matrixlooks as follows: 

During thedesignationof the T-Matrix, we didn’t take the pedestrian linksinto consideration. However, they can be included in this algorithm by treating pedestrian links betweenbusstops like bus routes. So,foron-footrealizedbusjourneys,in the cell T[start, stop]wesimplyneed to insert value 1.  

Additionally, the user cansetthe maximumamount oftimethey wishto spend on-foot. Therefore, it is necessary tocreate multiple T-Matrices. Onesuchmatrix asshowninTable3, for users who do notwishto travel on foot,in addition torelated tables of theT-Matrix ,e.g.T5min– for a maximum of 5minutes–walking,T10minfor a maximum of 10 minutes–walking.  

Assuming walkingtimesbetweentransitstops4, 5,and6is the same,each taking 4 minutes, you can create aT5mintable. It will be similar to theT table, however values in the following cells will change from zero to one: 

T[4,5]= 1 

T[5,4]= 1 

T[4,6]= 1 

T[6,4]= 1 

The table below illustrates the generated T-Matrix including journeys made on-foot. Values that differ from the value in Table4have been underlined. 

Step 3.

Now we’re able to generate the Q-Matrix(based on T-Matrix).

The first step in calculating theQMatrixis tocalculatebased oneach oftheexponents(powers)pfor theT Matrixin the range[p = 1…maxt], withmaxtrepresentingthe maximum number of possiblebusinterchanges.  

After calculating theT Matrixto each of the exponentsp, its subsequent elementsT[i, j] are then verified. If this value is greater than zero, then it is entered into theQ Matrixin the corresponding elementQ[i, j]. The new value is entered into the elementQ[i, j] only if the given elementQ[i, j] is currently equal to zero. The only exception is the diagonal of theQ Matrix, as all elements in it remain zero.  

Thegeneratedrangeis the representation of the matrix of the smallest number of transfers. In every cellQ[start, stop] there is informationconcerningthe minimum number of transfers with which you cantravelfrom theinitialbus stopto theterminalbus stop. 

Table5presents the matrix of the minimum number of bus transfers, with a maximum of one change (in a maximum of two bus journeys). For example, in the first row, it can be observed that a combination oftransit stops 1andtransit stop 6was established because, from the initial bus stop you can travel to the terminal bus stop along theRed Line,then changing to theBlue Line. 

In the second row, three new values were created (in relation to theT-Matrix).As such, fromtransitstop 2youare grantedone change totransitstops(5, 6,and9).Thisis possiblebecause: 

Bus Stops 2 -> 9 – travelalong theBlackLine, changingtothe GreenLine 

Bus Stops 2 -> 6 –travelalong the BlackLine, changingtothe GreenLine 

Bus Stops 2 -> 5 –travelalong the BlackLine, changingtothe GreenLine 

InTable6, a more complex matrix is presented,permittingup to threebus changes. Itsets outthe majority of possible combinations for the graph used asin theexample. E.g., incell[3,2] there is a value of4. It means thatbyusingall4possibleLines(withthree transfers), you cantravelfromtransitstop 3totransitstop 2. This can be achieved by travelingalongtheBlack Line, thenGreen,Blue,before returning to theBlackLine. 

 GeneratingBusRoutes froma CalculatedMatrix

Bus routes are created by finding all (or a sufficient numberof)combinations oftransitstopswhereapassenger needs to changebetweenbus linesin order to get fromtheinitial bus stop tothe terminalbus stop. This is done by recursively searching theQtable containing the matrix of the minimum number of transfers. These combinations are then supplemented with missingtransitstops to createcompleteroutes. 

The first step in this process is to check if there is any connection betweeninitial andterminaltransitstops. For such a connection to exist, the value of Q [start, stop] must be greater than zero.Forexample, inTable7;fortheinitialtransitstop 10andterminaltransitstop9,bycheckingthe value ofQ[10, 9], in the case of the example matrix presented below;thevaluepresentedis 2.Thiskind of connection exists,wherebyyou should travelalongat least two linesin ordertogetfrom the initial stop to theterminalstop. 

If the connection exists,thenthe next step is performed, i.e. finding a combination of stops on which transfers will be made on the route. This search starts from the final stop, in this case fromtransitstop 9.You mustrecognize all interchangesleading backto the initial stop [5]. This can be donethrougha few steps: 

1. For final stops (in the first iteration, this can only betransitstop 9) you should find all thetransitstops from which you can reach the final stop. This can be done by searching the end stop column and search fortransitstops with a value of 1 (direct connection).
2. Theretrievedstops are added to the route collection. If they are also a start-stop,thenthe algorithmwillcomplete the search.
3. Theretrievedstops are treated as final stops,and the first stepwill beperformed for them. 

The operation of the algorithm can beviewedon the example QTable,onstops numbered10and9. 

As none of the routes above contain abus stop number10, the searchwill thereforecontinue. 

Recursion continues until the route is connected to theinitialtransitstop. In practice however, finding all routes by searchingrangesrecursively can be expensive. Therefore, additional restrictions are used, such as searching untilamaximumnumber of connections or time constraints arereached. 

For the example used, you can generate 136 results.Figure4.3belowcontains an example of some of them: 

The above routes contain only interchanges. In order to receivecompleteroutes, you must complete them with the rest of thetransitstops.Since these stops can be connected by more than oneLine, different route variants can be created.Figure6belowshows an example of completing the route for the rest of thetransitstops: 

Results

To determine the quality of the routes generated, Ihad createda test application.You canviewsome examplesof route generation inGIFprovidedbelow.

Additionally,asIwishedtoverifyiftheresults are correct,theresults werethencompared with those from theGoogle Mapsservice.The reason behind this, is becauseGoogleboastsoneof the top search engines for mass transit connections.The point ofthiscomparisonwas only to check if simple algorithmscanbearresults,even close to those produced byGoogleMaps,and if they are correct.

The Drawings below present routes generated by Google Maps and the test application. As you can see, routes of the described application are very similar. They differ only in the place of changing from one line to the other. Furthermore, travel times are also very similar.

Note: this issimplyacheckforroute correctness. Comparing simple algorithmstoGoogleMapsdoesn’tmakesense.

TestCase A

StartingPoint:Stanki, 50-001Wrocław 

FinalPtop:Sołtysowicka, 50-001Wrocław 

StartingTime: Monday 8:00;1st, ofMarch 2018 

TestCase B

StartingPoint:Piramowicza, 50-001Wrocław 

Final stop:Pisarzowice–Odrzańska, 55-330 

Route start time: Monday8:00  1March 2018 

TestCase C

StartingPoint:Kadłubka, 50-001Wrocław 

FinalStop:Bacciarellego, 50-001Wrocław 

RouteStartTime: Monday8:00  1March 2018 

Literature:

1. KoszelewJ, Ostrowski K,Evolutionary Algorithm with Geographic Heuristics for Urban Public Transportation, Springer-Verlag, Berlin, 2012  
2. KoszelewJ, Ostrowski K,Approximation Method to Route Generation in Public TransportationNetwork,  2008  
3. Hartley J, Wu Q,Accommodating User Preferences in the Optimization of Public Transport Travel.2004 
4. Koszelew J,An Evolutionary Algorithm for the Urban Public Transportation. Springer, Heidelberg,2011  
5. KoszelewJ, Ostrowski K,A Genetic Algorithm with Multiple Mutation which Solves Orienteering Problem in Large Networks, 2013 
6. WellmanM ., Ford M, Larson K,Path planning under time-dependent uncertainty, Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence, 1995 
7. Koszelew J,The Theoretical Framework of Optimization of Public Transport Travel, 2007