Zone-based public transport route optimisation in an urban network

Abstract

The majority of academic studies on the optimisation of public transport routes consider passenger trips to be fixed between pairs of stop points. This can lead to barriers in the use of the developed algorithms in real-world planning processes, as these usually utilise a zone-based trip representation. This study demonstrates the adaptation of a node-based optimisation procedure to work with zone-to-zone trips. A core element of this process is a hybrid approach to calculate zone-to-zone journey times through the use of node-based concepts. The resulting algorithm is applied to an input dataset generated from real-world data, with results showing significant improvements over the existing route network. The dataset is made publicly available to serve as a potential benchmark dataset for future research.

1 Introduction

1.1 Opening

The efficiency of public transport (PuT) is of vital importance for urban areas worldwide to decrease car dependency and the accompanying pollution and congestion. In general, the task to design efficient PuT networks can be described as five interconnected phases: (1) route design, (2) Vehicle frequency setting, (3) timetable development, (4) vehicle scheduling, and (5) crew scheduling (Ceder and Wilson 1986). Due to the interconnections, the combined task has a very high complexity and researchers typically work with simplifications. One such simplification is the Urban Transit Routing Problem (UTRP). It focuses on optimising the layout of routes while assuming a fixed time penalty for all transfers (instead of varying transfer times resulting from different frequencies and starting times). The work presented in this paper is based on this approach.

Researchers have been working for many decades on automated procedures with which to solve the UTRP. Thus far, however, no results of this research have found widespread real-world application, and most planning processes are still based on experience and published guidelines (Nielsen et al. 2005; Walter 2010). The reasons for this gap have not yet been researched in detail (Walter 2010). However, one possible explanation is that the concepts used in many studies are based on instances (i.e. sets of required input data) which are far removed from real-world planning processes (Kepaptsoglou and Karlaftis 2009).

This study is part of an incremental approach for better applicable UTRP research. The previous publication (Heyken Soares et al. 2019) focused on the generation of more realistic instances. The present paper builds on this work by adapting and extending the concepts used in Heyken Soares et al. (2019) to a zone-based representation of journeys and travel demand. Compared with the node-based concept utilised in the vast majority of research studies (including Heyken Soares et al. 2019), the zone-based concept reduces restrictions for comparing the optimisation results to existing PuT networks, and allows including the effects of mode choice between PuT and other modes more easily in evaluation and optimisation. More importantly, however, it is the concept more commonly used in macroscopic transport modelling processes and, by extension, transport planning. Differences in data requirements between node-based and zone-based approaches can, therefore, create barriers to the practical application of UTRP algorithms.

The primary aim of this study is to adapt the methods used previously in Heyken Soares et al. (2019) to work with zone-based travel demand. This includes:

• Introduction of a hybrid approach for calculating zone-to-zone journey times through the utilisation of established node-based concepts (in Sect. 2).

• Adaptation of the optimisation procedure used in Heyken Soares et al. (2019) to work with zone-based demand (in Sect. 3).

• Extension of the instance generation procedure introduced in Heyken Soares et al. (2019) to data required for zone-based algorithms (in Sect. 4).

This paper further introduces two more general additions to the methods used in Heyken Soares et al. (2019):

• An improvement in the generation of routes under consideration of restricted start and end points (in Sect. 3.3).

• A methodology to include trips across the boundaries of the study area into the generation of demand matrices (in Sect. 4.4.2).

Furthermore, the instances described in Sect. 4 and an evaluation procedure have been published online in order to increase the attractiveness of working with zone-based trip representations for other researchers.

1.2 Problem formulation: node-based and zone-based

Studies on the UTRP are usually based on an undirected graph $G=(N,E)$ representing the available transport infrastructure. Its nodes N represent access and interchange points and are connected by links E, that represent connecting infrastructure (e.g. streets for bus travel).

In such a graph, the public transport network can be represented as a set of routes $R=\{r_1,r_2,...,r_{|R|}\}$. Each route r constitutes a list of directly connected nodes. The routes are considered undirected, assuming that vehicles after finishing one journey start a journey in the opposite direction. In an urban setting, this requires routes to begin and end on one of the designated terminal nodes $U\subseteq N$ which allow the performing of U-turns.

Optimising route sets requires criteria to evaluate the performance of different sets. A criterion used in many studies is the (average) passenger journey time (Iliopoulou et al. 2019). Calculating passenger journey times in a transport model requires estimating the path passengers take through the available network. One of the factors¹ impacting these estimations is the representation of passenger journeys and travel demand. This study compares the two most commonly used concepts, which are illustrated in Fig. 1.

The most common approach in UTRP research is to present travel demand as trips between pairs of nodes. This node-based concept assumes that travellers use the same pair of beginning and end nodes for their PuT journeys (independent of R). Under this approach only in-vehicle travel and transfers of a journey are considered.

The alternative approach is to divide the study area into zones each represented by a centroid. This allows to simplify² a trip with an origin in a zone O and a destination in a zone D as a trip between the centroids of O and D. Travellers use connectors to move between centroids and the nodes of G to board PuT services. As centroids can be connected to several nodes, passengers can often choose where they start/end their PuT journey.

Fig. 1

Example of the impact of different trip representations on trip options. Assumed is a trip between two zone centroids O and D. Two PuT routes can be used: “orange” over nodes 1 and 3, and “blue” over nodes 2 and 3. In a zone-based approach (left), travellers can choose from three options: a walk from O to 1, ride on route “orange” to 3, and walk from 3 to D; b walk from O to 2, ride on route “blue” to 3, walk on from 3 to D; c use the direct walking connection from O to D. In the node-based approach (right) the trip is assigned to nodes based on their catchment areas (grey circles). Travellers have only one option: travelling on route “blue” from 2 to 3. Walking is not considered. (The zones displayed in the figure were taken from the sets of zones described in Sect. 4.1. The map underlying the image is taken from https://www.openstreetmap.org.)

In the present study the zonal division is carried out in two separate layers³ for origin zones $Z^O$ and destination zones $Z^D$ (with connectors also being separated into $C^O$ and $C^D$). To include a simple form of mode choice modelling, direct walking connections W between origin and destination centroids are added. All network objects are summarised in info box 1.

1.3 Background

Zone-based approaches are the most common concept in macroscopic transport modelling and the basis of many real-world planning processes. On the one hand, zone demand matrices can be generated in a relatively simple way, e.g. from mobile phone data (see e.g. Golding 2018), or survey data (see Sect. 4.4). Further, trip distribution models and mode choice models require a zonal set-up as a common base of trips with all modes. Such models are an integral part of many more complex transport modelling processes, e.g. the standard four-step model (McNally 2000; Rich 2015; Schlaich et al. 2013).

Nevertheless, the majority of researchers working on the UTRP prefer the node-based concept. Surveying more than a hundred publications on the UTRP using journey time calculation in their evaluation revealed that more than 80% of them use node-based travel demand. For the full list please see “Appendix A”.

The main advantage of the node-based concept is that they are less complex and allow efficiently calculating the transit times through the use of standard shortest path algorithms [e.g. Floyd’s algorithm (Floyd 1962) or Dijkstra’s algorithm (Dijkstra 1959)]. However, the fact that travel demand is assigned to the nodes themselves, leads to parts of the demand being unserved if the designed PuT network does not include all nodes. Such unserved demand complicates the calculation of average journey times and almost all⁴ studies instead constrain route sets to include all nodes. Unfortunately, this constraint can exclude otherwise advantageous route sets and restricts comparisons between optimised and existing PuT networks.⁵

For determining the path and journey times of zone-to-zone trips, the literature knows several different approaches (for the respective publications see “Appendix A”). A favourable option is to utilise professional transport modelling software,⁶ such as EMME (INRO 2018) or PTV VISUM (PTV AG 2018). Unfortunately, not all researchers or planners have access to such software packages or the resources to replicate the complex assignment algorithms used in them.

Many UTRP studies with zone-based trip representations calculate journey times by using a “travel graph”. This extends on the graph G by including zone centroids and connectors as special types of nodes and links. Such a setup allows employing the same shortest path algorithms as commonly used in node-based approaches.

The present study takes a slightly different approach by introducing a new procedure to calculate zone-to-zone journey times. Its main advantage is in the way it can be utilised for the adaptation of the optimisation procedure (see Sect. 3.3). Additionally, it is straightforward to implement as it is based in established node-based concepts.

One other possible reason why UTRP researchers prefer using node-based demand is the availability of instances. Many researchers prefer to use publicly available instances. Doing so also allows a direct comparison of results and avoids the time-consuming work of generating own datasets. There are several published node-based instances (see, e.g. Ahmed et al. 2019b; Heyken Soares et al. 2019; Mandl 1979 or Mumford 2013). However, to the best of the author’s knowledge, no zone-based instance has yet been made publicly available. This issue will be addressed by publishing the instance described in Sect. 4 of this paper.

2 Calculating journey time

2.1 Defining journey time

The calculation of zone-to-zone journey times introduced in the following assumes that passengers will always use the path they perceive as the shortest. They also will choose the mode (walking or PuT) after this criterion.

The perceived length of a PuT journey can be expressed via a weighted sum. In professional modelling software (e.g. INRO 2018; PTV AG 2018) a multitude of different walking-, in-vehicle-, and waiting times is considered. However, in line with the simplifications mentioned in Sect. 1.1, the present study uses a reduced formulation: in the following the perceived PuT journey time $\theta ^{PuT}_{a,b}$ between an origin zone $z^O_a$ and a destination zone $z^D_b$ is defined as

$$\begin{aligned} \theta ^{PuT}_{a,b} = q_1\cdot t^{O}_{a,i} + q_2\cdot t^{InV}_{i,j} + q_3\cdot t^{TP}_{i,j} + q_1\cdot t^{D}_{j,b} \end{aligned}$$

(1)

where $t^{O}_{a,i}$ is the walking time from $z^O_a$ to a graph node $n_i$, $t^{InV}_{i,b}$ is the (total) in-vehicle travel time for the shortest PuT journey between nodes $n_i$ and $n_j$, $t^{TP}_{i,j}$ is a cumulative time penalty for transfers necessary on that journey, and $t^{D}_{j,b}$ is the walking time from a graph node $n_j$ to $z^D_b$. The factors $q_1$, $q_2$ and $q_3$ reflect that different time factors are weighted differently in the travellers’ perception.⁷

Once $\theta ^{PuT}_{a,b}$ is calculated (see Sect. 2.2), the final journey time $\theta _{a,b}$ can be determined by comparing $\theta ^{PuT}_{a,b}$ to the direct walking time $t^W_{a,b}$:

$$\begin{aligned} \theta _{a,b} = {\left\{ \begin{array}{ll} \theta ^{PuT}_{a,b}, &{}\text { if } \theta ^{PuT}_{a,b} \; < \; q_1 t^W_{a,b} \\ q_1 \cdot t^W_{a,b}, &{}\text { if } \theta ^{PuT}_{a,b} \; \ge \; q_1 t^W_{a,b} \end{array}\right. } \end{aligned}$$

(2)

This process is repeated for every non-zero demand pair⁸ to create a matrix $\varTheta$ of size $|Z^O|\times |Z^D|$. Thereafter, $\varTheta$ is then used in the calculation of the average journey time (as described in Sect. 3.1).

2.2 Calculating zone-to-zone journey time

The first step in calculation $\theta ^{PuT}_{a,b}$ is the generation of the node-to-node transit time matrix $\varLambda (R)$. The transit time $\lambda _{i,j}$ is defined as the combination of in-vehicle and transfer time for the shortest possible PuT transit between two nodes $n_i$ and $n_j$:

$$\begin{aligned} \lambda _{i,j}= q_2t^{InV}_{i,j} + q_3t^{TP}_{i,j} \end{aligned}$$

(3)

In a node-based concept, the transit time is the only travel time considered. Therefore, suitable methods to determine $\varLambda (R)$ are available in the literature. The present study uses the method from Fan et al. (2009) (also used e.g. in Ahmed et al. 2019a; Heyken Soares et al. 2019; Mumford 2013). This approach is based on the extended graph ${\tilde{G}}(R)=({\tilde{N}}(R),{\tilde{E}}(R))$ (illustrated in Fig. 2). The nodes ${\tilde{N}}(R)$ are equal to those in N; however, they are multiplied every time they are used in a route $r\in R$. The links ${\tilde{E}}(R)$ represent all connections within R plus the transfer connections between the duplicate versions of nodes in ${\tilde{N}}$. While the length of the regular edges is as given in the travel time matrix $T^N$, the length of the transfer links is equal to the fixed transfer penalty. In this study, it is set as $t^{trans}=5\text { min}$.⁹ This graph extension allows calculating $\varLambda (R)$ as the all-pairs shortest path matrix

$$\begin{aligned} \varLambda (R) = S\left( {\tilde{G}}(R)\right) \end{aligned}$$

(4)

Fig. 2

A simple example of an extended transit graph ${\tilde{G}}(R)$, as described in Fan et al. (2009). The left side shows a regular graph G with seven nodes, used by a route set R with two routes (green: [1-2-3-4], blue: [5-3-2-7]). The right side shows the resulting extended graph ${\tilde{G}}(R)$. The nodes used in both routes are duplicated, and transfer links of length $t^{trans}$ are inserted inbetween them (dashed lines). The nodes and links which are not used by any route, do not exist in ${\tilde{G}}(R)$

After calculating $\varLambda (R)$ it can be used to construct the all-combinations journey time matrix $H_{a,b}(\varLambda (R))$, which gives the combined walking and transit times for a trip between zones $z^O_a$ and $z^D_b$ for all possible zone-node combinations:

$$\begin{aligned} H_{a,b}(\varLambda (R)) = \begin{bmatrix} q_1t^{O}_{a,1}+\lambda _{1,1}+q_1t^{D}_{1,b} &{} &{}\dots &{} &{} q_1t^{O}_{a,|N|}+\lambda _{|N|,1}+q_1t^{D}_{1,b} \\ q_1t^{O}_{a,1}+\lambda _{1,2}+q_1t^{D}_{2,b} &{} &{}\dots &{} &{} q_1t^{O}_{a,|N|}+\lambda _{|N|,2}+q_1t^{D}_{2,b} \\ \vdots &{} &{}\ddots &{} &{} \vdots \\ q_1t^{O}_{a,1}+\lambda _{1,|N|}+q_1t^{D}_{|N|,b} &{} &{}\dots &{} &{}q_1t^{O}_{a,|N|}+\lambda _{|N|,|N|}+q_1t^{D}_{|N|,b} \\ \end{bmatrix} \end{aligned}$$

This equation can be written as a sum of three matrices:

$$\begin{aligned} H_{a,b}(\varLambda (R)) = \left( q_1{\tilde{T}}^O_a + \varLambda (R) + q_1{\tilde{T}}^D_b \right) \end{aligned}$$

(5)

where the matrix ${\tilde{T}}^O_a$ is composed of |N| copies of the a’th row vector of the connector matrix $T^O$, and the matrix ${\tilde{T}}^D_b$ of |N| copies of the b’th column vector of the connector matrix $T^D$:

$$\begin{aligned} {\tilde{T}}^O_a=\begin{bmatrix} t^O_{a,1} &{} &{}\dots &{} &{} t^O_{a,|N|}\\ &{} &{} \vdots &{} &{}\\ t^O_{a,1} &{} &{}\dots &{} &{} t^O_{a,|N|} \end{bmatrix} \, , {\tilde{T}}^D_b=\begin{bmatrix} t^D_{1,b} &{} &{} &{} &{} t^D_{1,b}\\ \vdots &{} &{}\dots &{} &{} \vdots \\ t^D_{|N|,b} &{} &{} &{} &{} t^D_{|N|,b}\\ \end{bmatrix} \end{aligned}$$

(6)

With this all three matrices (${\tilde{T}}^O_a$, ${\tilde{T}}^D_b$, and $\varLambda (R)$) are of size $|N|\times |N|$.

The PuT journey time can then be determined as the minimal value in $H_{a,b}$:

$$\begin{aligned} \theta ^{PuT}_{a,b}(R)= \min \left( H^{a,b}(\varLambda (R)) \right) \end{aligned}$$

(7)

Once determined, $\theta ^{PuT}_{a,b}(R)$ is compared to $q_1t^W_{a,b}$ in order to obtain the final value for the journey time $\theta _{a,b}(R)$ (see Eq. 2). The execution of Eqs. 7 and 2 are repeated for every non-zero demand pair to generate the complete zone-to-zone journey travel matrix $\varTheta (R)$. However, $\varLambda (R)$ has to be calculated only once per R. A brief discussion on the resulting run times can be found in “Appendix B”.

3 Optimisation procedure

The zone-based optimisation procedure described in the following is derived from the node-based approach utilised by the author and others in Heyken Soares et al. (2019). It centres on a genetic algorithm (GA) optimising route sets generated by a heuristic initialisation procedure.

The main adaptations are based on selecting the pair of nodes which form the beginning and end of the optimal PuT journey between two nodes. The basic process for this is a variation of the journey time calculation described in Sect. 2.2. It is outlined in Sect. 3.3. Additional adaptations were carried out to the route selection in step three of the initialisation procedure (Sect. 3.4.3) and in the crossover operation of the GA (Sect. 3.5.1), as well as to the repair operations (Sect. 3.5.3).

3.1 Optimisation objectives

The optimisation procedure described here uses two competing objectives. Their formulation is, in principle, identical to (Heyken Soares et al. 2019) and other studies (e.g. Ahmed et al. 2019a; Mumford 2013; John et al. 2014).

The first objective, i.e. the passenger objective, is to reduce the average passenger journey time,¹⁰ which is given by:

$$\begin{aligned} C_{P}^{\varTheta }(R) = {{{\sum _{a,b=1}^{|N|} d^Z_{o,d}\theta _{a,b}(R)}} \over {\sum _{a,b=1}^{|N|} d^Z_{a,b}}} \end{aligned}$$

(8)

where $d^Z_{a,b}$ is the number of passengers travelling from zone $z^O_a$ to zone $z^D_b$ and $\theta _{a,b}(R)$ is the journey time between $z^O_a$ and $z^D_b$.

The second objective, i.e. the operator objective, is to reduce the length of all routes as a simple¹¹ proxy for the cost of the operator:

$$\begin{aligned} C_{O}(R) = \sum _{j=1}^{|R|}\sum _{i =1}^{|r_j|-1} t_{i,i+1}(r_j) \end{aligned}$$

(9)

with $t_{i,i+1}(r_j)$ referring to the travel time between two adjacent nodes i and $i+1$ in the route $r_j$. This formulation does not depend on the used demand representation.

3.2 Optimisation constraint

There is a list of constraints that all route sets R and their routes r have to fulfil during both the generation and the optimisation processes:

• 1. A route set R consists of a predefined number of routes |R|.

• 2. Each route r has minimal $l_{min}$ and maximal $l_{max}$ nodes.

• 3. No route r fully overlaps with any other route in R.

• 4. R is connected - every node in R is connected to all other nodes in R.

• 5. Nodes appear only once in any route r - there are no loops or cycles.

• 6. The first and last nodes of each route is a terminal node $\in U$.

• 7. Each zone centroid is connected to at least one node in R.

Besides constraint 7, these constraints are identical to those used in Heyken Soares et al. (2019).

3.3 Determining optimal node pairs for shortest zone-to-zone travel

On several occasions during the optimisation process it is required to determine the nodes forming the beginning and end of the shortest path between two demand sources, e.g. to establish a new route between them. When adopting a node-based approach this is trivial as nodes and demand sources are identical. For a zone-based approach it is required to first identify the node pair $(n_i,n_j)_{a,b}$ for the beginning and end of the overall optimal PuT journey between two zones $z_a^O$ and $z_b^D$. Utilising the journey time calculation procedure introduced in Sect. 2.2, this can be carried out by determining the indices of the smallest entry of the all-combinations journey time matrix $H_{a,b}$:

$$\begin{aligned} (n_i,n_j)^G_{a,b} ={\left\{ \begin{array}{ll} \underset{i,j \in [0,|N|]}{{{{\,{\arg \min }\,}}}}\left( H_{a,b}(S(G)) \right) &{}\quad \text {if }q_1 t^W_{a,b} > \min \left( \, H_{a,b}(S(G))\, \right) \\ \emptyset &{}\quad \text {if }q_1 t^W_{a,b} \le \min \left( \, H_{a,b}(S(G))\, \right) \\ \end{array}\right. } \end{aligned}$$

(10)

where S(G) is a matrix with shortest path node-to-node travel times on graph G.¹² If the minimum of $H_{a,b}(S(G))$ is larger than the direct walking connection ($q_1 \cdot t^W_{a,b}$), no optimal node pair exists.

One use of $(n_i,n_j)^G_{a,b}$ is the generation of a route $r_{a,b}$ optimally connecting the zones $z_a^O$ and $z_b^D$. This route is then established as the shortest path between $(n_i,n_j)^G_{a,b}$ on G. In case at least one of the nodes is not a terminal node, $r_{a,b}$ is extended to a close terminal node using a guided random walk.¹³

This technique to generate routes between non-terminal nodes, which complies with constraint 6, marks a general improvement from the approach presented in Heyken Soares et al. (2019) where routes could only be generated between terminal nodes. It does not depend on the demand representation used.

Further, it is relatively straightforward to transfer the technique described here to other models, as Eq. 10 is independent of the way S(G) is calculated. For example, it can be used to add operations generating new routes to the optimisation procedure described in Heyken Soares et al. (2020) which is interfaced with the transport modelling software PTV Visum.¹⁴

3.4 Heuristic construction of route sets

Before starting the GA optimisation, an initial population of |P| route sets needs to be generated. For this, the construction heuristic introduced in Heyken Soares et al. (2019) is adapted for the zone-based approach. The process can be divided into the following steps:

3.4.1 1st step: Constructing the reversed usage graph $\varOmega$

The process begins by noting the usage of each link, assuming that all travellers can travel on their shortest path. This is done by determining the shortest paths between the optimal node pairs $(n_i,n_j)^G_{a,b}$ of each origin-destination pair $(z^O_a,z^D_b)$. Next, the reversed usage graph $\varOmega$ is constructed as a copy of G with the travel times of the links being replaced by the total demand minus the usage of the links. Thus, the most used link becomes the shortest in reversed usage distance, and vice versa.

3.4.2 2nd step: Generating candidate routes

The second step is to generate a palette of candidate routes. For this, the algorithm iterates through the zone pairs in order of demand, starting with the highest. For each pair $(z^O_a,z^D_b)$, a route is generated as the shortest path on $\varOmega$ between $(n_i,n_j)^G_{a,b}$.

Following the creation of each potential candidate route, the reversed usage distance of the links that it used is increased by 10%. This increases the likelihood of routes created later using less high-demanding links. If the generated route fulfils constraint 2, it enters the palette. The generation of routes continues until every zone is connected to at least $c_z$ routes in the palette.¹⁵

3.4.3 3rd Step: Forming route sets by combining routes from the palette of candidate routes

In this final step, |P| route sets are assembled from the palette of candidate routes. For the first route set $R_1$, the procedure begins by selecting the first route in the palette. The second route is chosen from all other routes in the palette which have at least one node in common with the first. Of these, the route with the highest coverage extension ratio $c_e(r)$ is selected.

For the node-based approach in Heyken Soares et al. (2019) $c_e(r)$ is defined as ratio between $|n_{new}(r)|$ (the number of nodes in r which are not yet part of any other route in $R_1$) and |r| (the length of a route r in number of nodes) to spread the network coverage while maintaining a balance between shorter and longer routes in $R_1$. For the zone-based approach the definition of $c_e(r)$ is modified to

$$\begin{aligned} c_{e}(r) = \frac{|n_{new}(r)|}{|r|}\cdot \frac{|z^O_{new}(r)|+|z^D_{new}(r)|}{|Z^o|+|Z^d|} \end{aligned}$$

(11)

where $|z^O_{new}(r)|$ and $|z^D_{new}(r)|$ is the number of origin and destination zones connected to r but not to any other route in $R_1$.

The process to select new routes repeats, adding one route at a time until all zones are connected to $R_1$. Further routes are added at random until $R_1$ contains |R| routes. After $R_1$ has been successfully generated, the same process is repeated for the second route set $R_2$, however starting from the second route in the palette. This continues until |P| route sets are assembled.

3.5 Genetic algorithm optimisation

The general structure of the genetic algorithm used in this study is that of Non-dominated Sorting Genetic Algorithm II (NSGAII). This genetic algorithm optimises a population of solutions (i.e. route sets) for two competing objectives simultaneously. It was first introduced in Deb et al. (2002) and has since been used in multiple UTRP studies (e.g. Ahmed et al. 2019b; Heyken Soares et al. 2019; John et al. 2014). Figure 3 presents a flow diagram of NSGAII. All changes are within the crossover and mutation operations and described in the following sections.

Fig. 3

Flow diagram of the NSGAII genetic algorithm setup. The |P| route sets in the initial population form the first parent population $P_0$. In the reproduction phase, route sets from $P_0$ are selected in binary tournaments in order to generate the offspring populations $Q_0$ (also of size |R|) via crossover and mutation operations (as described in Sects. 3.5.1 and 3.5.2.) $Q_0$ is then combined with $P_0$ to form $M_0$. For the selection of the next parent population $P_1$, $M_0$ is divided into sets f based on domination amongst one another. Starting with the nondominated solutions, these sets are then added to $P_1$ until one set $f_x$ cannot be added completely. The remaining route sets are selected from $f_x$ in such a way as to achieve a more even spread of solutions. The process will repeat for a predetermined number of generations. Further details can be found in Deb et al. (2002)

3.5.1 Crossover step

During the crossover step an offspring population $Q_k$ of size |R| is generated. Each offspring route set $Q_k^i$ is either a directly copied parent route set or, with a probability of $\rho _{cross}=0.9$, constructed in a crossover operation from two parent route sets.

In the crossover operation, route sets are selected from both parents in alternation. The first route is selected at random from one parent. In the following, the routes of the other parent which include at least one node that is already part of $Q_k^i$ are ranked according to their coverage extension ratio $c_e$ (see Sect. 3.4.3) and the route with the highest $c_e$ is added to $Q_k^i$. This process repeats until all zones are connected to $Q_k^i$. Thereafter, routes are selected at random until $Q_k^i$ consists of |R| routes. After its generation, $Q_k^i$ undergoes a feasibility test (see Sect. 3.5.3). If it passes, it is inserted into $Q_k$. Otherwise, the crossover step restarts.

3.5.2 Mutation operations

After their generation in the crossover phase, each offspring route set undergoes mutations. The number of mutations in each route set is determined by a binomial distribution $B(|R|,\frac{1}{|R|})$. For every mutation, one of the following mutation operations is selected at random:

• “Delete nodes”:¹⁶ deletes nodes from the end of randomly selected routes until they again end on a terminal node. In total, at least C nodes are deleted¹⁷

• “Add nodes”$^{16}$: adds nodes at the end of randomly selected routes until a new terminal node is reached. In total, at least C nodes are added$^{17}$

• “Exchange”:¹⁸ splits two randomly selected routes at a common vertex. The divided parts are recombined into two new routes replacing the originals.

• “Merge”:¹⁹ randomly selects two routes with a common terminal node and merges them into one route. Thereafter, a new route is generated.

• “Replace”:$^{19}$ replaces the route satisfying the lowest demand with a new route.

After every mutation, the changed route set needs to pass a feasibility test (see Sect. 3.5.3). If it fails, the mutation is undone and a new mutation operation is selected. More information on the mutation operations can be found in Heyken Soares et al. (2019).

The mutation operations “Delete nodes”, “Add nodes” and “Exchange” do not require any changes for use in a zone-based optimisation. In “Merge” and “Replace” new routes are generated as described in Sect. 3.3. The routes are generated between the pair of not optimally connected zones with the highest demand. A pair of zones ($z^O_a$, $z^D_b$) is considered to be not optimally connected in a route set R if no single route includes its optimal node pair $(n_i,n_j)^G_{a,b}$.

3.5.3 Feasibility test

Every route set generated in a crossover or changed in a mutation operation is subject to a feasibility test in order to check whether all of the constraints listed in Sect. 3.2 are obeyed. Repair operations are called in case of two common constraint violations:

• “Replace overlapping”:²⁰ Called by a violation of constraint 3. It replaces the overlapped route with a new route generated as described in Sect. 3.3.

• “Add missing nodes”:$^{16}$ Called by a violation of constraint 7. It connects unconnected nodes to randomly selected routes terminating once all zones are connected. (In Heyken Soares et al. 2019 the process first stopped when all nodes were included in R.)

4 Instance datasets

4.1 Study area and data sources

An instance dataset for the zone-based optimisation described in this paper includes the instance matrices listed in info box 2 as well as information on terminal nodes. The following sections describe how these data can be generated. The primary study area for this process is the southern part of the metropolitan area of Nottingham, UK (including the areas of Clifton and West Bridgford and the village of Ruddington). It is presented in Fig. 4. Travel patterns in this area are significantly influenced by trips across boundaries, especially to the north to Nottingham city centre. To capture this cross-boundary flow, origins and destinations in an extended study area are also taken into account, as described in Sect. 4.4.2. This extended study area is the travel-to-work area²¹ of Nottingham and is presented in Fig. 6.

Corresponding to the demand data used in Sect. 4.4.1, the zonal division of the study area is taken from datasets of 2011 UK Census conducted by the UK Office for National Statistics (ONS). The low-level Census geography types²² “Output Areas” (OA) and “Workplace Zones”(WZ) are used to divide the study area into origin zones and destination zones, respectively. Both are designed by the ONS by aggregating postcode areas for spatial analysis of Census results. OAs are designed for residential statistics with each zone including between 40 and 250 households. WZs are designed for employment statistics and based on workplace counts (UK Office for National Statistics 2016a). In addition to the zone layout, the ONS also generates population-weighted centroids for every zone, which here are used as zone centroids.

The primary study area contains 248 Output Areas and 56 Workplace Zones, and the extended study area 2390 Output Areas and 647 Workplace Zones.

Fig. 4

Maps of the study area with boundaries and centroids of Output Areas (left) and Workplace Zones (right). Streets used as basis for the graph G are highlighted in black. (Sources: street data, zone layout, and centroid locations from UK Ordnance Survey. Underlying map from https://www.openstreetmap.org)

4.2 Node travel time matrix and terminal nodes

The primary study area is a section of the study area used in Heyken Soares et al. (2019). Therefore, the respective subset of the instance generated and published in Heyken Soares et al. (2019) provides the nodes and links of the graph G as well as information on the terminal nodes U. Heyken Soares et al. (2019) the positions of the nodes were mainly determined by street junctions and the distances between them. Adjacency relations between the nodes and travel times along the links were determined via shortest path searches. Further, terminal nodes U were identified using data on existing bus services. For the study area, the graph G includes 60 nodes and 94 edges, with 28 nodes being classified as terminal nodes (see Fig. 5).

Also converted from the dataset generated in Heyken Soares et al. (2019) is a set of routes representing existing bus services in the primary study area. In order to fit with the travel-to-work data used to generate the demand (see Sect. 4.4.1), only services in operation during the morning rush hour (7:30 a.m. to 10:30 a.m.) are considered. This “real-world route set” includes 54 nodes in 18 routes, the shortest of which has three nodes and the longest 12 nodes. It will be used in Sect. 5 for comparisons with the optimisation results.

Details of all procedures used to generate these data, as well as the underlying data sources can be found in Heyken Soares et al. (2019).

Fig. 5

Graph G generated by application of the generation procedure from Heyken Soares et al. (2019) to the primary study area presented in Fig. 4 (terminal nodes marked in blue, regular nodes in white). Also displayed are the locations of origin centroids (purple squares), destination centroids (green circles) and the connectors. The direct walking connections between centroids are not displayed for the sake of clarity

4.3 Zone connectors and walking matrix

Connector matrices $T^O$ and $T^D$, and the walking matrix $T^W$ need to be generated based on walking accessibility of the zones and nodes. For this the 2011 version of the UK Ordnance Survey’s urban path layer²³ was used. It allows calculating the shortest path distance between zone centroids and nodes through the use of specialised geographic information systems.²⁴

The entries of matrices $T^O$,$T^D$ and $T^W$ are determined by taking the calculated shortest path distances and dividing them by a walking speed of $1.4 \text {m/s}$ (as recommended in Highways England (2019)). All entries which are above a cap distance $d_c$ are set as $\infty$. For $T^O$ and $T^D$ the cap distance is set to $d_c=758\text {m}$ (approx. 9 minutes walking time). This is the largest distance between a zone and its nearest node in the study area. For $T^W$ the cap distance is set as twice that of the connector matrices.

4.4 Travel demand

4.4.1 Data sources and classification

The demand data for this study are taken from the travel-to-work flow data.²⁵ of the 2011 UK Census.²⁶. This dataset contains the number of commuters travelling from OAs to WZs. The considered trips can be grouped into four segments:

• 1. Both origin and destination inside of the primary study area.

• 2. Origin inside of the primary study area and destination inside of the extended study area (Fig. 6).

• 3. Origin inside of the extended study area and destination inside of the primary study area.

• 4. Both origin and destination inside of the extended study area.

Using OAs as origin zones and WZs as destination zones, the trips in segment 1 can be filled directly in the demand matrix $D^Z$. The process for trips in the other segments is discussed in the following.

Fig. 6

Map of the extended study area with the locations of OA centroids (purple squares) and WZ centroids (green dots) (sources as in Fig. 4). The primary study area with the graph G is shown black, the eight gate nodes beeing marked in yellow

4.4.2 Cross-boundary flow

The PuT services outside of the primary study area are not part of the optimisation process. Therefore, a trip between two zones, $z^p_l$ inside of the primary study area and $z^e_k$ inside of the extended study area, can be treated as a trip between $z^p_l$ and the point at which this trip crosses the boundary. In theory, this point would need to be determined based on R, which would add another layer of complexity to the evaluation process.²⁷ However, if primary- and extended study area are sufficiently separated²⁸ and there is only a small number of distinct crossing points, as is the case here, the following simplification can be made: every zone $z^e_k$ in the extended study area, independent of origin or destination zone, can be associated with a “gate node” $n^g_{k}\in N$, where all trips from/to $z^e_k$ enter/leave the graph G and thereby the study area. This allows simplifying every trip between a zone $z^p_l$ in the primary study area and zone $z^e_k$ as a trip between $z^p_l$ and $n^g_{k}$.

To use this concept in the generation of a zone-demand matrix, every gate node $n_{k}^g$ generates a virtual origin zone $z^O_{k*}$ and a virtual destination zone $z^D_{k*}$. Each virtual origin zone expands the matrix $D^Z$ by one row, and each virtual destination zone by one column. Concerning the connector times, virtual zones are instantly connected to their respective gate nodes ($t^O_{k*,k}=0$ and $t^D_{k,k*}=0$), while connectors to all other nodes do not exist. The direct walking times between regular zones and virtual zones are identical to the connector times from regular zones to the gate node.

The concept of virtual zones allows inserting the demand of segments 2 and 3 as trips between zones inside of the primary study area and the virtual zones representing zones in the extended study area. Which node is the gate node for which zone is determined by a shortest path search on the Real-World Routes Graph (RWRG). The RWRG is a graph structure representing the public transport network in the extended study area. It is described in detail in “Appendix C”.

Moreover, the RWRG can be used to filter out all trips from segment 4 which do not pass over the primary study area (also described in “Appendix C”.). The remaining trips in segment 4 can be assigned to the demand matrix as follows: a trip from a zone $z^{O}_k$, with gate node $n^g_{k}$, to a zone $z^{D}_l$, with gate node $n^g_{l}$, is represented as a trip between the two virtual zones $z^O_{k*}$ and $z^D_{l*}$.

For the presented study areas this process results in a demand matrix with of size 256$\times$64 (248 origin zones, 56 destination zone, and 8 virtual zones each). In total, it has 5751 non-zero entries.

The gate-node approach can, of course, also be used to include cross-border demand in a node-based demand matrix. In this case, trips of segments 2 and 3 are considered to go between gate nodes and the nodes associated to the respective origins/destinations inside of the primary study area. Trips of segment 4 can be represented as trips between two gate nodes.

5 Experimental results

The following sections present the results of the optimisation procedure described in Sect. 3 and applied to the instance generated in Sect. 4. All experiments were conducted with a population size of $|P|=50$ route sets. Each route set includes $|R|=18$ routes, i.e. the same number as real-world route set. The minimal and maximal numbers of nodes in a route is set as $l_{min}=2$ and $l_{max}=14$. The genetic algorithm runs for 200 generations.

5.1 The base optimisation

For the first experiment, the weighting factors in Eq. 1 are set as $q_1=q_2=q_3=1$. The results of this optimisation are shown in Fig. 7. Each of the displayed points gives the evaluation of one route set for total route length ($C_{O}$) and the average journey time ($C_{P}^{\varTheta }$). The evaluation results form a clear non-dominated front with several route sets surpassing the performance of the real-world route set²⁹ (circle) in both objectives. Although such comparisons are limited by the assumptions made for the study set-up and instance generation, they indicate that the described optimisation procedure can generate route networks superior to those of pre-existing services.

Fig. 7

Evaluation of the route sets resulting from zone-based optimisation with $q_1=q_2=q_3=1$ (dots) in comparison with the performance of the real-world route set (circle). Four results are highlighted: at the extremes, the one with the lowest average journey time (red, R) and the one with the lowest total route length (blue, B); from those route sets which surpass the real-world route set in both objectives, the one with the lowest average journey time (yellow, Y) and the one with the lowest total route length (green, G)

To simplify the discussion, four critical positions are highlighted: at the extremes, the route sets with the lowest $C_{P}^{\varTheta }$ in red and the one with the lowest $C_O$ in blue; as for, the route sets which surpass the real-world route set in both objectives, the one with the lowest $C_{P}^{\varTheta }$ in yellow, and the one with the lowest $C_O$ in green.

The evaluation results of the route sets highlighted are shown in more detail in Table 1 as the base case. In addition to the values displayed in Fig. 7, the table also presents the number of nodes included and the transfer statistic. The latter gives the percentage of travellers reaching their destination without transfers, with one, two or more transfers, or who do not use the service at all. The table shows, for example, that for the yellow route set, 74.1% of passengers undertake direct trips, 2.5 times that of the real-world route set. Furthermore, $C_{P}^{\varTheta }$ reduced by 23.8%, while $C_O$ is almost identical. The green route set has a 2.9% lower $C_{P}^{\varTheta }$ than the real-world route set, while $C_O$ is reduced by 51.5%.

Table 1 Evaluation results of selected route sets resulting from optimisation with zone-based demand and different weighting factors. Categories are as follows: $C_{P}^{\varTheta }$: average journey time; $C_{O}$: total route length; K: number of nodes included; $d_0$: $\%$ of direct trips; $d_1$: $\%$ of trips with one transfer; $d_{2}$: $\%$ of trips with two transfers; $d_{3+}$: $\%$ of trips with three or more transfers $d_W$: $\%$ of pure walking trips. Route sets are selected as highlighted in Fig. 7 (only the base case) and Fig. 8. Results for the real-world route set are evaluated with the respective parameter combination

5.2 The impact of different weighting factors

The other results listed in Table 1 are from optimisation experiments under variations $q_1$ and $q_3$ and selected after the same criteria as described above. The full results are shown in Fig. 8. Also displayed are the evaluation results of the real-world route set under the respective parameters, showing that, for all setups, the optimisations generated results which were superior .

Fig. 8

Evaluations of the resulting route sets optimised for different weighting factors. The left side shows variations of $q_1$ (weight of walking time), the right side variations of $q_3$ (weight of transfer penalty). Evaluations of the real-world route sets are presented as empty markers. Base case ($q_1=q_2=1$) and highlighting of route sets is identical to Fig. 7

The left-hand side of Fig. 8 shows the results of different weightings for the walking time. As expected, the fronts move farther to the right with higher values for $q_1$. By contrast, the evaluation results of optimisations with an increased transfer penalty on the right-hand side are closer together. This indicates that the optimisation algorithm effectively constructed more direct connections. However, the blue route sets show sharp increases in the average perceived journey time, as their low $C_O$ comes at the cost of more transfers for passengers.

Figure 9 presents all transfer statistics of route sets resulting from the base case and the optimisation with $q_1=3$ and $q_3=4$. All these graphics show that the percentage of passengers undertaking direct trips increases with higher $C_O$. The percentages of trips with more transfers are consequently reduced, leading to the percentage of single-transfer trips peaking first, then decreasing. This basic dynamic is the same for all setups. However, when $q_1$ is increased the percentages of trips with transfers decrease much more slowly, as passengers prefer less direct trips over longer walking times. By contrast, an increase of $q_3$ results in a general shift towards fewer transfers. Not only does the percentage of direct trips itself increase, the percentage of single-transfer trips peaks at a significantly lower level and decreases more quickly. Figure 9 further shows that the real-world route set offers significantly less direct travel than the optimised route sets with similar $C_O$ under all configurations.

Fig. 9

Transfer statistics for the experiment with $q_1=q_3=1$ (top left), $q_1=3$ (bottom left), and $q_3=4$ (bottom right). Markers show the percentage of travellers reaching their destination with direct trips, with one transfer, two transfers, or three or more transfers. The empty markers show the transfer statistics for the real-world route set evaluated with the respective configurations

5.3 Comparison with node-based optimisation

The following section attempts to compare the results generated with the zone-based optimisation procedure presented in this study with those resulting from an equivalent node-based approach. For this, the procedure used in Heyken Soares et al. (2019) is modified to include the generation of routes between non-terminal nodes, as described in Sect. 3.3. The required node-based demand matrix is generated with the procedure described in Heyken Soares et al. (2019), using the same data as used in Sect. 4.4. Cross-border demand flow is included as described at the end of Sect. 4.4.2.

The left-hand side of Fig. 10 shows the results of the zone-based optimisation from Sect. 5.1 and of the node-based optimisation with the same parameters. Both are evaluated for their total route length $C_O$ and average journey time $C_{P}^{\varTheta }$. This is possible because route sets resulting from node-based optimisation are required to include all nodes and, consequently, also all zones. The right-hand side of Fig. 10 shows the same results evaluated for average transit time. For each node-based result, two markers are displayed: one where the average transit time was calculated with zone-based demand,³⁰ the other where node-based demand³¹ was used.

Fig. 10

Comparison of zone-based and node-based optimisation results for both the total route length vs. average journey time (left) and the total route length vs. average transit time (right). For the average transit time the route sets from node-based optimisation were evaluated two times: with the zone-based demand matrix (triangles) and with the zone-based demand matrix (pluses). Zone-based results (dots) are identical to those presented in Fig. 7

The average transit times calculated with zone-based demand are, on average, 1.43 minutes (13.6%) longer than the one calculated with node-based demand.³² These deviations are a result of the differences in aggregating trips between the two concepts (see Fig. 1 on page 4) and do not indicate the superiority of any concept. However, they highlight the importance of carefully choosing the used trip representation based on the available data.

The differences in the average transit time limit the conclusiveness of comparing both approaches for the given scenario. However, the results indicate that both approaches perform similarly well for small values of $C^\varTheta _P$, while for low $C_O$ the results generated by zone-based optimisation are superior. This is expected as the constraint to always include all nodes hinders the node-based optimisation in reducing $C_O$.

6 Summary and conclusion

Different concepts for the representation of journeys and travel demand exist in the literature on automatic optimisation of public transport routes. The node-based concept, which considers only in-vehicle and transfer times, is used in the majority of studies because it is more straightforward to implement and has several input datasets that are publicly available. Zone-based concepts, which also take access times into account and are more often used in practical planning applications, however, feature in much fewer research studies.

This paper presented an adaptation of the methods used in Heyken Soares et al. (2019), i.e. previous work by the author and others, from a node-based to zone-based approach. For this, it first introduced a hybrid procedure for the calculation of zone-based journey times. It first calculates the transit times between all node pairs and then identifies the connection offering the shortest overall zone-to-zone journey time for every zone pair.

This procedure can further be used to determine the “optimal node pair” for each zone pair. These form the beginning and end of the PuT journey with the shortest overall journey time between a specific pair of zones. These optimal node pairs form the basis of the majority of adaptations necessary to use the construction heuristic and genetic algorithm from Heyken Soares et al. (2019) with zone-based demand. For example, they can be used to generate routes optimally connecting specific zone pairs. In cases where these nodes cannot be route terminals, the route is extended until a possible terminal node is reached.

Further, this paper described procedures with which to generate the required input data based on freely available data sources. Included in this procedure is a method that considers cross-border demand flow in the generation of demand matrices. The procedure was applied to a section of the metropolitan area of Nottingham, UK.

Experimental results demonstrated the ability of the optimisation procedure to generate efficient route networks for different setups, as given by different weighting factors for walking and transfer times. Comparisons between optimisation results and representations pre-existing services are limited by the assumptions made; however, they indicate that the presented optimisation procedure can generate superior route networks.

Independent of the results obtained, the methods presented bring about several advantages over the approach presented in Heyken Soares et al. (2019). These include the improved route generation and the ability to compare optimisation results and pre-existing routes without the need for reducing the instance. Further, the use of zone-based trip representation allows to more easily interface the presented optimisation procedure with macroscopic transport modelling software, which has the potential to drastically reduce barriers for practical application.

Further improvements are possible in several aspects. For example, it would be sensible to improve the calculation of the operator cost or to change the mutation operations to allow for a changing number of route sets. Moreover, the instance generation procedure can be further enhanced, potentially by measuring the connector length to existing stop points which can then be mapped to the graph nodes. However, additional research has to show whether such an approach is viable.

The instance dataset generated in this paper, the results presented, and a Python program for route set evaluation with the procedure presented can be downloaded under https://data.mendeley.com/datasets/jkz4bkb5j5.

Appendices

Appendix A: List of publications using node-based and zone-based demand

All publications listed in the following are dealing with the optimisation of PuT route networks (as defined in Sects. 1.1 and 1.2 ) and use the passenger journey time as one of its evaluation criteria. This includes publications which extend the optimisation to other phases of PuT network design (e.g. frequency setting). In total 112 publication were found which meet these criteria.

91 of these studies use a node-based approach: Afandizadeh et al. (2013), Agrawal and Mathew (2004), Ahmed et al. (2019a, (2019b) Amiripour et al. (2014a), Amiripour et al. (2014b), Amiripour et al. (2014),Arbex and da Cunha (2015), Baaj and Mahmassani (1991), Baaj et al. (1995), Bachelet and Yon (2005), Barra et al. (2007), Beltran et al. (2009), Bielli and Carotenuto (1998), Blum and Mathew (2010), Borndörfer et al. (2008), Buba and Lee (2016), Buba and Lee (2018), Cancela et al. (2015), Carrese and Gori (2002), Ceder and Wilson (1986), Ceder and Israeli (1998), Chakroborty and Wivedi (2002), Chakroborty (2003), Chew and Lee (2012), Chew et al. (2013), Chu (2018), Cooper et al. (2014), Dubois et al. (1979), Duran et al. (2019), Fan et al. (2009), Fan and Mumford (2010), Feng et al. (2019), Fusco et al. (2002), Gao et al. (2004), Guan et al. (2006), Gutierrez-Jarpa et al. (2017), Gutiérrez-Jarpa et al. (2013), Heyken Soares et al. (2019), Hu et al. (2005), Huang et al. (2018), Iliopoulou and Tassopoulos (2019), Islam et al. (2019), Israeli and Ceder (1995), Jha et al. (2019), Jiang et al. (2013), John et al. (2014), John (2016), Kechagiopoulos and Beligiannis (2014), Kiliç and Gök (2014), Kim et al. (2019), Lampkin and Saalmans (1967), Lee and Vuchic (2005), Liu et al. (2015), López-Ramos et al. (2017), Mahdavi Moghaddam et al. (2019), Mandl (1979), Marwah et al. (1984), Mauttone and Urquhart (2009a, (2009b), Müller (1967), Mumford (2013), Nayeem et al. (2014), Nebelung (1961), Ngamchai and Lovell (2003), Nikolic and Teodorovic (2013, (2014), Owais et al. (2014), Owais and Osman (2018), Owais et al. (2016), Pacheco et al. (2009), Pattnaik et al. (1998), Pternea et al. (2015), Quak (2003), Rahman et al. (2015), Shih et al. (1998), Shimamoto et al. (2012), Silman et al. (1974), Soehodo and Koshi (1999), Sonntag (1979), Szeto and Wu (2011), Tom and Mohan (2003), Walteros et al. (2013), Wu and Wang (2016), Xiong and Schneider (1992), Xu et al. (2014), Zhao (2006), Zhao and Zeng (2006), Zhao and Zeng (2007), Zhao and Zeng (2008) and Zhao et al. (2015).

The remaining studies can be separated into three groups based on the methods used to calculate the passenger journey times:

• Nine studies employ a professional transport modelling software (EMME (INRO 2018)) or PTV VISUM (PTV AG 2018)): Alt and Weidmann (2011), Bagloee and Ceder (2011), Cipriani et al. (2005), Cipriani et al. (2006), Cipriani et al. (2012), Heyken Soares et al. (2020), Petrelli (2004), Poorzahedy and Safari (2011) and Sadrsadat et al. (2012)

• Three studies use specialised assignment algorithms: (Bielli et al. 2002) (using Spiess and Florian 1989; Szeto and Jiang 2012) (using Nguyen and Pallottino 1988; Bourbonnais et al. 2019) (using Dibbelt et al. 2013)

• Nine studies use more regular shortest path algorithms (e.g Floyd’s algorithm (Floyd 1962), or Dijkstra’s Algorithm (Dijkstra 1959)): Chien and Schonfeld (1997), Chien and Spasovic (2002), Enrique Fernández et al. (2008), Fan and Machemehl (2006a), Fan and Machemehl (2006b), Fan and Machemehl (2008), Fan and Machemehl (2011), Roca-Riu et al. (2012) and Marín and Jaramillo (2009)

Further discussion on this literature review can be found in Heyken Soares (2020).

Appendix B: Concerning run times

The computing time required for the evaluation is important as it needs to be executed many times during the optimisation process. In studies using node-based demand, the evaluation is typically dominated by the time $\tau (\varLambda )$, i.e. required for the generation of the transit time matrix $\varLambda$. The runtime of the hybrid-process described in Sect. 2.2 requires additional time to calculate the journey time matrix $\varTheta$. It can, therefore, be described as $\tau (\varLambda +\varTheta )=\tau (\varLambda )+\tau (\varTheta )$.

Executed with Floyd’s algorithm (Floyd 1962), the generation of $\varLambda$ has a time complexity of $O(|{\tilde{N}}|^3)$. The time required to generate $\varTheta$ depends largely on two factors. One is the number of non-zero demand pairs $|\Delta |$ (with $|\Delta |\le |Z^O|\cdot |Z^D|$) which gives the number of times Eq. 5 needs to be executed. The other is the number of regular nodes |N|, which define the size of the matrices ${\tilde{T}}^O_a$, $\varLambda (R)$, and ${\tilde{T}}^O_b$ (see Eq. 5). As summing matrices has a (worst case) time complexity of $O(|N|^2)$,³³ the time complexity of the complete process is

$$\begin{aligned} O\left( ~ |{\tilde{N}}|^3 \, + \, |N|^2 \cdot |\Delta | ~ \right) \end{aligned}$$

(12)

The ratio $\tau (\varLambda +\varTheta )/\tau (\varLambda )$, therefore, depends on both the number of zone pairs and the relation between the number of regular nodes |N| and the number of extended nodes $|{\tilde{N}}|$. The latter depends on the individual route set R. On one side, every node which is not included in R can be excluded from ${\tilde{G}}$ reducing $|{\tilde{N}}|$. On the other side, more transfer possibilities between routes increase $|{\tilde{N}}|$ (see Sect. 2.2).

Figure 11 presents the runtime increase as ratio $\tau (\varLambda +\varTheta )/\tau (\varLambda )$ for different values $\gamma =\frac{|\Delta |}{|N|^2}$, i.e. the number of non-zero demand pairs normalised by the number of node pairs. Every data point shows the average values for 50 calculations³⁴ of $\varLambda$ and $\varTheta$.

As can be seen, the ratio increases linearly with the number of zone-pairs and the gradient of the increase depends largely on the relation between $|{\tilde{N}}|$ and |N|. The instance presented in Sect. 4 is titled “SouthOfTrent” and has 5751 non-zero node pairs ($\gamma =1.6$), resulting in $\tau (\varLambda +\varTheta )/\tau (\varLambda )\approx 2$. This is consistent with the run times of the genetic algorithm.³⁵

Fig. 11

Results of runtime experiments (See footnote 34) with the graphs of different publicly available instances. Experiments were executed for different values of $\gamma$ the ratio between zone- and node pairs. The y-axis gives the ratio between run times of the hybrid-process $\tau (\varLambda +\varTheta )$ and only calculating transit times $\tau (\varLambda )$. The table on the right side shows source, number of regular nodes (|N|), size of the used route sets (|R|), and average number of extended nodes $(\left<|{\tilde{N}}|\right>)$ for each instance. ^aThese instances can be downloaded from https://data.mendeley.com/datasets/kbr5g3xmvk/1

For instances such as the one presented in Sect. 4, run-times are in general sufficiently short $^{35}$. For larger instances the procedure presented here can only be considered relatively efficient when $|\Delta |\gg |{\tilde{N}}|^2$ . In other cases, it would be sensible to employ a different algorithm (e.g. Dijkstra’s algorithm, Dijkstra 1959) for the evaluation and use the hybrid procedure only for the process described in Sect. 3.3. This would not impact the results of the optimisation0.

It should further be noted that the individual executions of the Eq. 7 are independent from each other. This theoretically allows to significantly reduce the runtime of the hybrid-approach by parallelising the calculation of $\varTheta$.

Appendix C: The real-world routes graph

The Real-World Routes Graph (RWRG) is a graph structure constructed with data on the existing PuT routes³⁶ in service in the extended study area during the morning rush hour. Nodes of the RWRG represent existing stop points, and two nodes are connected via a link if a direct connection between them exists within the selected PuT routes. Additional links are added between vertices which are closer than 100 metres together representing possible interchanges. The RWRG does not allow for an accurate calculation of journey times; however, it is sufficient for the tasks outlined in the following

The gate node $n_k^g$ of zone $z^e_k$ in the extended study is determined by calculating the shortest paths on the RWRG from $z^e_k$ to all nodes $n_i\in N$. The $n_i$ which is closest to $z^e_k$ is selected as $n_k^g$.

The shortest path calculation can be carried out by building the RWRG as a shapefile through the use of Python library ArcPy or PyQGIS and converting it into a network dataset for use with the Network Analyst toolbox.³⁷ The Network Analyst function “Closest Facility” is then used to determine which node n_i of the graph G is the closest to zone z_i in the extended study area through the use of the RWRG.

The RWRG can also be used to filter the trips in the fourth demand segment (trips between outer zones) into those that go over the study area and those that do not. To do so, Network Analyst function “Closest Facility” is used to find the shortest paths from all origin zones outside of the study area to all destination zones outside of the study area. As a second step, ArcGIS Linear referencing tool “Locate Features along routes” is used to determine which of these shortest paths lead over nodes of the graph G. All origin–destination pairs in which this is not the case will be deleted and not considered further.