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:

- Initialbusstop
- Terminalbusstop
- Travel startingtime
- Maximum time that the user is willing to spend ontransferring betweenbusstops(as part of a change)

Bus stopgeographical location datasetsmust consist of:

- Longitude
- Latitude
- IDofabusstop
- Type oftransitstop (tram,bus,tram-bus)

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:

- Nameof thebusstop
- Correspondingstreet
- Bus stop’sIDcorresponding to theoneof thebarin the list oftransitstops
- List of timetables for a given day (Weekdays, Saturday,andSunday)
- Alist of departuretimesfrom a giventransitstopfor each day(tram or bus)

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:

- The first route assumesatransferbetweenbusesat
*transit stop**4*from the*B**lue**L**ine*to the*R**ed**L**ine*. - The second route assumes that the passenger willtravel alongthe
*B**lue**L**ine*to*transit**stop**6*,wheretheywillproceedon-footto*transit**stop 5*, from where they willcontinuetheir journey alongthe*R**ed**L**ine*. - Route number three is one of the leastidealin terms of the number of stops. This routeadoptsa circular route,consisting oftravel along
*Blue*and*Black Lines*,witha final interchangeat*transit**stop 11*onto the*G**reen**L**ine*. 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 the*Q 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 the*Q matrix*is to create a
square*T-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 fromthe*start*bus stop
to the*terminal*bus stop. If the
directjourneydoes not occur, thena value 0 isinsertedinto the
cell*T*[*start, stop*]. When such ajourney doesoccur,then avalue 1 is
insertedinto thecell*T*[*start,
stop*].

*Example:*

From*transit stop 1*you cantravelto*transit**stops 2, 3, 12, 11*using the*B**lack**L**ine*andto*transit**stops
7, 4, 5, 9*using the*R**ed**L**ine*.

Therefore, the firstrowdemonstrates the following:

*T [1,2] =
1**– Journey**along the
B**lack**L**ine*

*T [1,3] = 1
–**Journey along the B**lack**L**ine*

*T [1.4] = 1
–**Journey along the Red**L**ine*

*T [1.5] = 1
–**Journey along the Red**L**ine*

*T [1.7] = 1
–**Journey along the Red**L**ine*

*T [1.9] = 1
–**Journey along the Red**L**ine*

*T [1.11] = 1
–**Journey along the Black**L**ine*

*T [1.12] = 1
–**Journey along the Black**L**ine*

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 asshownin*Table**3*, for
users who do notwishto travel on
foot,in addition torelated tables of theT-Matrix ,e.g.*T5min*– for a maximum of 5minutes–walking,*T10min*for
a maximum of 10 minutes–walking.

Assuming
walkingtimesbetween*transit**stop**s**4, 5,*and*6*is the
same,each taking 4 minutes, you can create
a*T5min*table. It will be similar to
the*T 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 the*Q**M**atrix*is tocalculatebased oneach
oftheexponents(powers)*p*for
the*T Matrix*in the range[*p = 1*…*maxt**]*, with*maxt*representingthe
maximum number of possiblebusinterchanges.

After calculating
the*T Matrix*to each of the
exponents*p*, its subsequent
elements*T*[i, j] are then verified. If this value is greater than
zero, then it is entered into the*Q Matrix*in the corresponding element*Q*[*i**,
j*]. The new value is entered into the element*Q*[i, j] only if the given element*Q*[i, j] is currently equal
to zero. The only exception is the diagonal of the*Q Matrix*, as all elements in it remain zero.

Thegeneratedrangeis the
representation of the matrix of the smallest number of transfers. In every cell*Q*[*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 of*transit stops 1*and*transit stop 6*was established because, from the initial bus stop you can travel to the terminal bus stop
along the*Red Line,*then changing to
the*Blue Line*.

In the second row, three
new values were created (in relation to theT-Matrix).As such, from*transit**stop
2*youare grantedone change to*transit**stops*(*5,
6,*and*9*).Thisis
possiblebecause:

*Bus Stops 2 -> 9 –
travel**along the**B**lack**L**ine, chang**ing**to**the
G**reen**L**ine*

*Bus Stops 2 -> 6
–**travel**along the
B**lack**L**ine, chang**ing**to**the G**reen**L**ine*

*Bus Stops 2 -> 5
–**travel**along the
B**lack**L**ine, chang**ing**to**the G**reen**L**ine*

In*Table**6*, 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 of*4*. It means thatbyusingall4possible*Lines*(withthree transfers), you cantravelfrom*transit**stop 3*to*transit**stop
2*. This can be achieved by travelingalongthe*Black
Line*, then*G**reen*,*B**lue*,before returning to the*B**lack**Line*.

## 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 the*Q*table 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,
in*Table*7;fortheinitial*transit**stop 10*andterminal*transit**stop**9*,bycheckingthe value of*Q*[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 from*transit**stop 9*.You mustrecognize all interchangesleading backto the initial stop [5]. This can be donethrougha few steps:

- For final stops (in the first iteration, this can only be
*transit**stop 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). - Theretrievedstops are added to the route collection. If they are also a start-stop,thenthe algorithmwillcomplete the search.
- Theretrievedstops are treated as final stops,and the first stepwill beperformed for them.

The operation of the
algorithm can beviewedon the example
QTable,onstops numbered*10*and*9*.

- For the first step of the algorithm, the finaltransitstop
*number 9*is found. The corresponding column in the QTableis searched for all rows with the value equal to 1. These are*L**ines*:*1, 4, 5, 7,*and*11* - Retrievedbus stops are added to the route collection

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

- Allretrievedtransitstops (
*1,4,5,7,11*)will return to Step 1. For each of these, their QTable column is searched for direct connections (value 1)

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.*Figure**4.3*belowcontains 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.*Figure**6*belowshows 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 the*Google Maps*service.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: **

- KoszelewJ, Ostrowski K,
*Evolutionary Algorithm with Geographic Heuristics for Urban Public Transportation*, Springer-Verlag, Berlin, 2012 - KoszelewJ, 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 - KoszelewJ, Ostrowski K,
*A Genetic Algorithm with Multiple Mutation which Solves Orienteering Problem in Large Networks*, 2013 - WellmanM ., 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