# Temporal Performance Analysis of Bus Transportation Using Link Streams

Authors: J. L. Curzel; R. Lüders; K. V. O. Fonseca; M. O. Rosa
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

Performance analysis of transport systems usually requires transfer of passengers between trains, cars, or buses, among others. This paper proposes a methodology for modeling and analysis of bus transportation using link streams. Link streams are particular cases of stream graphs whose cliques provide information about available time intervals for connecting buses. These cliques are obtained by algorithms of the literature with good scalability. They are used to quantify performance indicators as transfer time, bunching, congestion, and number of transferred passengers. The results are obtained for real-world data of a bus terminal in the city of Curitiba, Brazil. They reveal important issues regarding transfer delays and available capacity for transport. The proposed performance analysis can be used to support urban planners on planning and improving transport operation.


---

## Body

## 1. Introduction

The operation of urban transport systems has been considered in the literature using different approaches [1–6]. These works model and simulate transport systems, particularly for planning schedules to improve system efficiency. The authors of [1, 2] developed a computational framework for modeling a transport system based on planning, station design, integration, and access and evaluated their effects on system performance. In [3] a parallel operation management system has been developed to detect the number of passengers at stations as well as traffic flow and queuing length of vehicles in private lanes. This system provides information to deal with transportation management by improving and optimizing emergency situations or rescheduling vehicles based on conditions detected in videos of traffic. In [4–6] simulation and intelligent support based on artificial intelligence techniques are used to help control center operators to take strategic decisions about a fleet of buses in an urban network.Recently, transportation companies have invested in technologies for online supervision of operations and resources [7, 8]. For instance, a two-way communication in [7] between bus drivers and operators allows solutions using negotiation-based strategies. In [8] a global positioning system (GPS) is integrated with wireless communication to track vehicles in real time. All these approaches utilize information and communication technology (ICT) to predict, simulate, and control different situations in transport system. In this sense, the available online information can be used for planning, controlling, and coordinating transit of buses in a reactive manner. However, formal methodologies are still necessary to analyze and detect issues in advance.This paper aims to analyze multiple connections in a bus terminal. By means of an innovative performance analysis method based on link streams [9], we model a transport system of multiple bus line connections in a bus terminal (or hub). Link streams are particular cases of stream graphs which are graphs whose nodes and edges (links) have a time to live. A link stream is a stream graph in which only edges have a time to live; i.e., nodes are permanent. A detailed introduction of stream graphs and link streams can be found in [10]. Links streams have been used in many applications. For instance, nodes and edges in a graph may represent individuals connected by a phone call which persists for a given period of time. The authors of [11] use link streams to capture dynamics of contacts between individuals. They consider activities as link streams to predict the number of links that occur during a given period of time and show that a combination of structural and temporal characteristics of the link stream leads to performance improvements. In [12] a trace of real-world interactions between individuals captured with RFID sensors technology was collected in a high school in France during approximately 8 days of 2012. The study of links created and destroyed during these days has revealed new patterns of human interaction in a different time scale. Another important issue in link streams is computing cliques. A clique is a set of nodes such that any 2-combination of these nodes is connected by an edge. A first algorithm to compute maximal cliques in a link stream was proposed in [9] and implemented in [13]. Recently, it was improved in [14, 15] by adapting the Bron-Kerbosch algorithm. Moreover, the authors developed an algorithm that detects maximal time intervals during which interactions occur. This notion was initially introduced by [9] using instantaneous link streams and extended to link streams with duration by [16].Our main contribution is to define a set of procedures to represent arrivals and departures of buses in a link stream representation whose cliques provide the necessary information to compute performance indicators as transfer times, bunching, congestion, and number of passengers transferred between buses. To the best of our knowledge, this is the first time link streams are used to model and analyze transport systems.The paper is organized as follows. Section2 presents the background on link streams and cliques. Section 3 shows how link streams and cliques model a bus transportation system and defines indicators for the performance analysis. Section 4 presents the case study of Curitiba’s public transportation with conclusions in Section 5.


## 2. Link Streams

A simple undirected graphG=(V,E) is an ordered pair with a set V of nodes and a set E⊆V⨂V of links with u≠v for uv∈E, and u,v∈VV⨂V means a set of unordered pairs of nodes). In this case, nodes u and v are linked together in G.Stream graphs and link streams are graphs with time information. A comprehensive study on stream graphs and link streams can be found in [10]. A stream graph is a tuple S=(T,V,W,E) such that T⊆R is a time interval, W⊆T×V is a set of temporal nodes, and E⊆T×V⨂V is a set of links. If (t,uv)∈E then (t,u) and (t,v)∈W. This means that nodes u and v and a link uv exist at time t. A stream graph is then a graph whose nodes and links exist at a given time t. If W=T×V then all nodes exist for all times in T, and S=(T,V,E) is a link stream.Links streams are used to model interactions between individuals or objects over time as meetings in social networks or email exchanges [12]. In this paper, we use link streams for modeling transport systems because nodes (bus stops) do exist during the whole period of time considered for analysis. However, links between nodes only occur at given time intervals during which passengers are transferred.In a simple undirected graphG=(V,E), a clique C⊆V of G is a set of nodes which are connected to each other; i.e., for all u,v∈C, there exists a link uv∈E. A clique C is maximal if there is no other clique C′ such that C⊂C′.A similar definition is used for a stream graphS=(T,V,W,E). According to [10], a clique C of S is a subset of W such that all pairs of nodes involved in C are linked in S. Because nodes in stream graphs are not present all the time in general, it is necessary to distinguish compact cliques which are subsets of W whose nodes are linked all together during a given time interval. This is the case for link streams which are compact stream graphs [10] as all nodes are present within T. Therefore, a (compact) clique in a link stream is given by a time interval and a subset of nodes which are linked all together during this time interval. Similarly, a clique C is maximal if there is no other clique C′ such that C⊂C′. Figure 1 shows examples of cliques in a link stream L.Figure 1
Maximal cliques in a link streamL=T,V,E with T=[0,18]⊆N, V={1,2,3,4}, and E=1,8×23∪2,8×12∪2,8×13∪5,8×14∪5,8×24∪5,10×34∪11,13×23∪16,18×{23}. A maximal clique of L is [5,8]×{1,2,3,4} because [5,8] is the largest time interval during which nodes {1,2,3,4} interact all together. There is no other maximal clique in L with four nodes, but there are other maximal cliques in L as [5,10]×{3,4} and 1,8×{2,3}, for instance.An algorithm has been proposed in [17] to detect maximal cliques in link streams. It is used here to compute operational performance metrics of bus transport in a terminal as described in the following. It is also important to note that T can be a continuous or discrete time interval without loss of generality [10].


## 3. Modeling Bus Transportation Systems with Link Streams

Based on bus timetables we identify time intervals during which buses are in the terminal for boarding and alighting of passengers. Several buses arrive at and departure from the terminal within this time interval, and a common time interval can be built to characterize the transfer time between connecting buses. This relationship between buses at the terminal is the basic information we need to build a link stream and compute maximal cliques according to Figure2. It is important to emphasize that the relationship between buses of a terminal is established since a bus is detected at the terminal in a given time interval. Link streams capture only the relationship between buses present in the terminal at the same time. The GPS data of buses (in the case of online monitoring systems) is only used to filter the time intervals when a bus is at the terminal as explained in Section 4.Figure 2
Procedure to build a link stream and compute maximal cliques.The first two steps of Figure2 generate Tables 1 and 2. They represent an example of arrivals and departures of buses for lines 1, 2, and 3 during a time interval of 30 minutes in the terminal. The data set of arrivals and departures is shown in Table 1.Table 1
Arrivals and departures of buses for lines 1, 2, and 3 in the terminal between 7:00 and 7:30 am.
Line 1 Line 2 Line 3 Arrival Departure Arrival Departure Arrival Departure 07:00 7:04 07:03 07:06 07:07 07:11 07:07 7:08 07:16 07:18 07:21 07:27 07:08 7:12 07:26 07:30 07:08 7:16 07:09 7:20 07:16 7:24 07:20 7:28 07:22 7:30Table 2
Time interval when more than one bus is in the terminal (link stream information).
Time (min) Bus lines (nodes) Time (min) Bus lines (nodes) 3 1,2 21 1,3 4 1,2 22 1,3 7 1,3 23 1,3 8 1,3 24 1,3 9 1,3 25 1,3 10 1,3 26 1,2,3 11 1,3 27 1,2,3 16 1,3 28 1,2 17 1,2 29 1,2 18 1,2 30 1,2The information of Table1 is then used to build Table 2 which contains only minutes when more than one bus is in the terminal. According to Table 2, there are buses from lines 1 and 2 in minutes 3 to 4, 16 to 18, and 26 to 30. A similar reasoning is made for lines 1 and 3. Actually, all three lines have buses in the terminal during minutes 26 and 27. This is exactly the information of link stream needed to compute cliques. The information of Table 2 is then used as input to the algorithm of computing cliques.The corresponding link stream can be visualized in Figure3 using a computational tool [18]. Nodes in Figure 3 correspond to buses of lines 1 to 3 (vertical axis), and edges connect two buses in the terminal at the same time (horizontal axis). The correspondence between the information of Table 2 and the visualization of Figure 3 is straightforward.Figure 3
Link streamL=(0,30,1,2,3,E) for Table 2 with E=3,4×12∪7,11×13∪16,18×12∪21,27×13∪26,27×23∪26,30×12.The maximal cliques shown in Table3 are then obtained by the algorithm presented in [17]. The clique C=26,27×1,2,3 is the largest time interval having buses from lines 1, 2, and 3 all together in the terminal. There is no other maximal clique inL involving 3 nodes (lines), but there are other maximal cliques with less than three nodes as C1=16,18×1,2 or C2=7,11×1,3, for instance.Table 3
Maximal cliques for lines 1, 2, and 3 from 7:00 to 7:30 am.
Set of nodes (bus lines) Time interval (min) Duration (min) { 1,2 } [ 3,4 ] 2 { 1,3 } [ 7,11 ] 5 { 1,2 } [ 16,18 ] 3 { 1,3 } [ 21,27 ] 7 { 1,2 , 3 } [ 26,27 ] 2 { 1,2 } [ 26,30 ] 5It should be noted that the time interval of cliqueC=[26,27]×{1,2,3} is the intersection of intervals of cliques C1=[26,30]×{1,2} and C2=[21,27]×{1,3}. It means that cliques are useful for both local analysis involving transfers between two lines and global analysis with more than two lines as detailed below.A clique is the right structure to capture all relationships between buses in the terminal from a common structure (link stream) that contains only information about a 2-combination of buses during a given time interval. A clique provides information about not only which buses are present in the terminal but also during which time interval. It is important to emphasize that computing cliques is computationally intensive, and some of the performance metrics proposed below could be obtained with less complex structures (congestion, for example) than cliques. However, cliques are computed only once for a given set of lines and time horizon. The proposed performance measures are then filtered from clique information as explained below.


### 3.1. Performance Metrics

The performance metrics we are interested in for evaluating a transport system are (i) time interval for transfers between two particular lines, (ii) bunching of buses of the same line, (iii) congestion of buses in the terminal, and (iv) number of passengers who are successfully transferred between local and express lines. These performance metrics can be computed using link streams and cliques as follows.


#### 3.1.1. Time Interval for Transfers

Cliques provide the necessary information about how many and during how much time buses from different lines are in the terminal. They involve the computation of the maximal common interval during which a meeting of one or more buses occurs and allows transfer of passengers. Table4 shows cliques for all eight lines operating in the terminal between 7:00 and 7:30 am. This is the basic information necessary for the performance analysis accomplished here.Table 4
Maximal cliques involving bus lines between 7:00 and 7:30 am.
Set of nodes (bus lines) Time interval (min) Duration (min) { 1,8 } [ 0,4 ] 5 { 1,8 , 2,4 , 7 } [ 3,4 ] 2 { 8,2 , 4,7 } [ 3,5 ] 3 { 2,4 , 7 } [ 3,6 ] 4 { 1,3 , 4 } [ 7,8 ] 2 { 1,3 } [ 7,11 ] 5 { 1,3 , 4,6 } [ 8,8 ] 1 { 1,3 , 6 } [ 8,11 ] 4 { 1,6 } [ 8,14 ] 7 { 1,3 , 4,6 } [ 11,11 ] 1 { 1,4 , 6 } [ 11,14 ] 4 { 1,4 } [ 11,16 ] 6 { 1,8 , 5,4 , 6 } [ 12,14 ] 3 { 1,5 , 4 } [ 12,16 ] 5 { 1,5 } [ 12,17 ] 6 { 1,2 , 5,4 , 7 } [ 16,16 ] 1 { 1,2 , 5,7 } [ 16,17 ] 2 { 1,2 , 7 } [ 16,18 ] 3 { 1,8 , 4 } [ 19,22 ] 4 { 1,4 } [ 19,24 ] 6 { 1,8 , 5,4 , 6 } [ 20,22 ] 3 { 1,5 , 4,6 } [ 20,24 ] 5 { 1,5 , 6 } [ 20,27 ] 8 { 1,5 } [ 20,30 ] 10 { 1,3 , 5,4 , 6,8 } [ 21,22 ] 2 { 1,3 , 5,4 , 6 } [ 21,24 ] 4 { 1,3 , 5,6 } [ 21,27 ] 7 { 1,3 , 5,4 , 6,8 } [ 24,24 ] 1 { 1,8 , 3,5 , 6 } [ 24,27 ] 4 { 1,8 , 5 } [ 24,30 ] 6 { 1,3 , 5,7 , 6,8 } [ 25,27 ] 3 { 1,3 , 2,5 , 7,6 , 8 } [ 26,27 ] 2 { 1,8 , 2,5 } [ 26,30 ] 4 { 1,3 , 2,5 , 4,7 , 6,8 } [ 27,27 ] 1 { 1,8 , 2,5 , 4 } [ 27,30 ] 3The transfer times between lines 1 and 2, for instance, are obtained from Table4 in a two-step procedure. The first step consists of selecting cliques of Table 4 containing only lines 1 and 2 as shown in Table 5.Table 5
Step 1: maximal cliques containing only lines 1 and 2 from 7:00 to 7:30 am.
Set of nodes (bus lines) Time interval (min) Duration (min) { 1,8 , 2,4 , 7 } [ 3,4 ] 2 { 1,2 , 5,4 , 7 } [ 16,16 ] 1 { 1,2 , 5,7 } [ 16,17 ] 2 { 1,2 , 7 } [ 16,18 ] 3 { 1,3 , 2,5 , 7,6 , 8 } [ 26,27 ] 2 { 1,8 , 2,5 } [ 26,30 ] 4 { 1,3 , 2,5 , 4,7 , 6,8 } [ 27,27 ] 1 { 1,8 , 2,5 , 4 } [ 27,30 ] 3The second step obtains maximal nonoverlapping time intervals containing nodes{1,2}. According to Table 6, these intervals are [3,4], [16,18], and [26,30] with durations of 2, 3, and 4 min, respectively. They represent the corresponding transfer times for these lines.Table 6
Step 2: nonoverlapping time intervals from Table6.
Set of nodes (bus lines) Time interval (min) Duration (min) { 1,2 } [ 3,4 ] 2 { 1,2 } [ 16,18 ] 3 { 1,2 } [ 26,30 ] 4This procedure can also be done for lines 1 and 3, or any set of lines. In other words, transfer times for connecting buses can be obtained by filtering cliques computed for all bus lines to select lines of interest and nonoverlapping time intervals.


#### 3.1.2. Bunching

Bunching is a phenomenon characterized by a concentration of buses in a single area. It is detected here when the headway between two consecutive buses of the same line is less than 1 minute. Usually it occurs due to delays in departures or arrivals of buses and reduces the transport efficiency. When bunching occurs, buses eventually leave the terminal almost empty or completely full of passengers. At certain times of the day (peak traffic of buses or passengers), it is observed that bunching events occur due to a large number of passengers to be transported or high frequency of buses. This effect causes performance issues as poor quality of service and excessive waiting time as pointed out by [19–22].In this work, bunching detection is done by distinguishing buses of the same line and assuming that link streams are built using a sampling time rate of 1 min or less. This way, headways equal to or less than 1 min can be captured. A bunching event is then identified by taking cliques of the same line buses.For instance, the link stream shown in Figure4 considers only buses of line 1 in the terminal from 7:00 to 7:30 am with different labels assigned to different buses. Labels begin with a line number followed by two digits of the bus number. For instance, label 104 means bus 04 of line 1. Similarly, labels 107, 109, 111, 120, 121, 126, and 130 represent eight different buses of line 1.Figure 4
Link stream of line 1 showing the bunching effect from 7:00 to 7:30 am.According to Figure4, buses 104, 120, and 126 are in the terminal at 7:08 am causing a bunching event in line 1 during 1 min. All these bunching events are detected by maximal cliques as shown in Table 7. The greatest bunching events are composed by buses 111, 120, and 126 during 4 min between 7:09 and 7:12 am (in bold).Table 7
Bunching events from 7:00 to 7:30 am for bus line 1.
Bunching (set of buses) Time interval (min) Duration (min) { 104,120,126 } [ 8,8 ] 1 { 120,126 } [ 8,12 ] 6 { 111,120,126 } [ 9,12 ] 4 { 111,126 } [ 9,16 ] 8 { 107,111,126 } [ 16,16 ] 1 { 107,111 } [ 16,20 ] 5 { 107,111,121 } [ 20,20 ] 1 { 107,121 } [ 20,24 ] 5 { 107,121,130 } [ 22,24 ] 3 { 121,130 } [ 22,28 ] 7 { 109,130 } [ 29,30 ] 2


#### 3.1.3. Congestion Analysis

The congestion analysis is obtained by the number of buses that are in the terminal at a given time interval. This information is also given by cliques by using different labels for different buses of the same line and computing the maximum number of buses at each time. Table8 shows the number of buses in the terminal minute by minute from 7:00 to 7:30 am by taking the cliques of Table 4 but marking buses of the same line with different labels. This information is used to monitor the terminal occupation as detailed in Section 4.Table 8
Number of buses in the terminal from 7:00 to 7:30 am.
Minute Set of nodes (bus lines) Set of nodes (bus numbers) Number of buses 0 { 1,8 } { 103,807 } 2 1 { 1,8 } { 103,807 } 2 2 { 1,8 } { 103,807 } 2 3 { 1,2 , 4,7 , 8 } { 103,202,402,704,807 } 5 4 { 1,2 , 4,7 , 8 } { 103,202,402,704,807 } 5 5 { 2,4 , 7,8 } { 202,402,704,807 } 4 6 { 2,4 , 7 } { 202,402,704 } 3 7 { 1,3 , 4 } { 104,301,402 } 3 8 { 1,3 , 4,6 } { 104,120,126,301,402,603 } 6 9 { 1,3 , 6 } { 111,120,126,301,603 } 5 10 { 1,3 , 6 } { 111,120,126,301,603 } 5 11 { 1,3 , 4,6 } { 111,120,126,301,401,603 } 6 12 { 1,4 , 5,6 , 8 } { 111,120,126,401,501,603,804 } 7 13 { 1,4 , 5,6 , 8 } { 111,126,401,501,603,804 } 6 14 { 1,4 , 5,6 , 8 } { 111,126,401,501,603,804 } 6 15 { 1,4 , 5 } { 111,126,401,501 } 4 16 { 1,2 , 4,5 , 7 } { 107,111,126,201,401,501,702 } 7 17 { 1,2 , 5,7 } { 107,111,201,501,702 } 5 18 { 1,2 , 7 } { 107,111,201,702 } 4 19 { 1,4 , 8 } { 107,111,404,808 } 4 20 { 1,2 , 4,5 , 6,8 } { 107,111,121,404,502,602,808 } 7 21 { 1,3 , 4,5 , 6,8 } { 107,121,301,404,502,602,808 } 7 22 { 1,3 , 4,5 , 6,8 } { 107,121,130,301,404,502,602,808 } 8 23 { 1,3 , 4,5 , 6 } { 107,121,130,301,404,502,602 } 7 24 { 1,3 , 4,5 , 6,8 } { 107,121,130,301,404,502,602,806 } 8 25 { 1,3 , 5,6 , 7,8 } { 121,130,301,502,602,703,806 } 7 26 { 1,2 , 3,5 , 6,7 , 8 } { 121,130,203,301,502,602,703,806 } 8 27 { 1,2 , 3,4 , 5,6 , 7,8 } { 121,130,203,301,402,502,602,703,806 } 9 28 { 1,2 , 4,5 , 8 } { 121,130,203,402,502,806 } 6 29 { 1,2 , 4,5 , 8 } { 109,130,203,402,502,806 } 6 30 { 1,2 , 4,5 , 8 } { 109,130,203,402,502,806 } 6


#### 3.1.4. Number of Transferred Passengers

In order to estimate the number of passengers that are successfully transferred from local lines to the express line it is necessary to have a model for passengers’ mobility. This model should take into account the time interval necessary for transferring of passengers between bus stops (required transfer time) as well as the time interval during which buses are currently in the terminal (available transfer time).The required transfer time of passengers is based on three components: (i) passengers’ boarding time, (ii) passengers’ alighting time, and (iii) walking time necessary for passengers moving between alighting and boarding stops inside the terminal.The walking time is computed from the distance between drop-off and boarding areas divided by the standard walking speed of passengers. According to [23], the average reference for walking speed is 1.20 m/s for pedestrians. Boarding and alighting times per passenger depend on bus model [24] as shown in Table 9.Table 9
Boarding and alighting times (in seconds) per passenger (pax).
Bus type Boarding time Alighting time Single decker, step - 1.52 s/pax Single decker, low floor 1.76 s/pax -The transfer timett is then given by the boarding timetb plus walking timetw and alighting timeta as shown in(1)tt=tb+tw+ta.The total number of passengers transferred in a given time interval is computed in four steps:(i) Identify the time interval when the express line is in the terminal(ii) Identify all local lines that are able to transfer passengers to the express line within this time interval(iii) Calculate the required transfer time(iv) Verify how many passengers have been transferred within the available transfer timeThe first step is performed from maximal cliques involving all local and express lines in a given time interval as shown in Table10 for the express line 1 (buses 101 and 110).Table 10
Step 1: maximal cliques for express line1 and local lines 2–8 between 6:00 and 6:10 am.
Set of nodes (bus numbers) Time interval { 201 , 101 } [ 2 , 6 ] { 201 , 101 , 601,808 } [ 4 , 6 ] { 101 , 808 } [ 4 , 7 ] { 201,404,808,601,110 , 101 } [ 5 , 6 ] { 404,110 , 101 , 808 } [ 5 , 7 ]  { 404 , 110 , 808 } [ 5 , 10 ] { 110 , 404 } [ 5 , 12 ] { 108,404,502 , 110 , 808 } [ 8 , 9 ] { 108,404 , 110 , 808 } [ 8 , 10 ] { 108,404 , 110 } [ 8 , 12 ] { 108,404 , 110 , 703,502,806,808 } [ 9 , 9 ] { 404,108,808 , 110 , 806,703 } [ 9 , 10 ] { 108,404,703,806 , 110 } [ 9 , 12 ]The goal of step 1 is to find the time interval during which the express line is at the platform and the corresponding transfer time available for each local line arriving within this time interval. According to Table10, line 1 (101 in boldface) starts a transfer at time 6:02 and ends at time 6:07 (the first five rows of Table 10). It means that line 1 (using bus number 101) is available for transfer during a total time of 6 min (interval [2,7]). Moreover, three events representing arrivals of local lines occur at times 6:02, 6:04, and 6:05 (second column of Table 10 in boldface). They are important to compute how much time each local bus has to transfer passengers until express line departure. This is captured in step 2 according to Table 11.Table 11
Step 2: available transfers to the express line from 6:00 to 6:10 am.
Transfer Transfer time { 201 , 101 } [ 2 , 7 ] { 201 , 101 , 601,808 } [ 4 , 7 ] { 201,404,808,601,110 , 101 } [ 5 , 7 ]  { 108,404,502 , 110 , 808 } [ 8 , 12 ] { 108,404 , 110 , 703,502,806,808 } [ 9 , 12 ] { 604,108,404 , 110 , 703,806,808 } [ 10 , 12 ]In Table11, time intervals are extended to the corresponding express departure time (6:07 am for bus 101 and 6:12 for 110, respectively, in boldface). Moreover, only cliques with the greatest number of nodes are kept among cliques with same initial time. This is equivalent to compute all buses that arrive at same time. For instance, data from cliques [4,6]×{201,101,601,808} and [4,7]×{101,808} reduce to set {201,101,601,808} of buses arriving at 6:04. They have time until 6:07 am to make transfers (second row of Table 11).The final step(3) simply extracts the maximum time interval for each transfer according to Table 12. For instance, the maximum transfer time between buses 201 and 101 is 6 min (first row of Table 12).Table 12
Step 3: final transfer times to the express line from 6:00 to 6:10 am.
Transfer Maximum time interval Available transfer time (min) 101,201 [ 2,7 ] 6 101,601,808 [ 4,7 ] 4 101,404 [ 5,7 ] 3  110,502 [ 8,12 ] 5 110,703,806 [ 9,12 ] 4 110,604 [ 10,12 ] 3Therefore, Table12 shows all available transfers (lines and transfer times) between local and express lines occurring from 6:00 to 6:10 am. This information will be used in Table 13 to compute how many passengers will be successfully transferred to the express line. It is done based on the current number of passengers that arrive at the terminal from local lines, the required transfer time computed by (1), the available transfer time given by Table 12, and the express bus capacity.Table 13
Passengers transferred from local to express lines between 6:00 and 6:10 am.
Express bus number Local bus number Arriving passengers Required transfer time (min) Available transfer time (min) Connecting passengers Express bus capacity (pax) Balance (pax) 101 201 29 1.86 6 151 250 99 601 24 1.59 4 808 49 2.96 4 404 49 2.96 3  110 502 86 4.98 5 134 250 116 703 02 0.39 4 806 40 2.46 4 604 06 0.61 3The first column of Table13 contains the express bus number waiting at the boarding platform. The second column shows the local buses that arrive at the same time with the respective number of passengers in the third column. The next two columns show the required and available times for transferring passengers between local and express lines, respectively. The last three columns show how many passengers need to be transferred to the express line, the express bus capacity, and the corresponding balance of passengers (negative values mean that the express bus is full), respectively.According to Table13, while the express bus 101 is waiting at the boarding platform, a total of 151 passengers from buses 201, 601, 808, and 404 need to be transferred. The next express bus 110 needs to board 134 passengers from buses 502, 703, 806, and 604. Note that both express buses depart with available places. In addition, all passengers are successfully transferred as the available transfer time is greater than the required transfer time. It can be seen from Table 13 that transfers from buses 404 to 101 and 502 to 110 (in boldface) are very sensitive to delays. If bus 404 is delayed for about 1 min, for instance, the available transfer time decreases to 2 min and approximately only 33 passengers will be transferred. The other 16 passengers should wait for the next express bus.


## 3.1. Performance Metrics

The performance metrics we are interested in for evaluating a transport system are (i) time interval for transfers between two particular lines, (ii) bunching of buses of the same line, (iii) congestion of buses in the terminal, and (iv) number of passengers who are successfully transferred between local and express lines. These performance metrics can be computed using link streams and cliques as follows.


### 3.1.1. Time Interval for Transfers

Cliques provide the necessary information about how many and during how much time buses from different lines are in the terminal. They involve the computation of the maximal common interval during which a meeting of one or more buses occurs and allows transfer of passengers. Table4 shows cliques for all eight lines operating in the terminal between 7:00 and 7:30 am. This is the basic information necessary for the performance analysis accomplished here.Table 4
Maximal cliques involving bus lines between 7:00 and 7:30 am.
Set of nodes (bus lines) Time interval (min) Duration (min) { 1,8 } [ 0,4 ] 5 { 1,8 , 2,4 , 7 } [ 3,4 ] 2 { 8,2 , 4,7 } [ 3,5 ] 3 { 2,4 , 7 } [ 3,6 ] 4 { 1,3 , 4 } [ 7,8 ] 2 { 1,3 } [ 7,11 ] 5 { 1,3 , 4,6 } [ 8,8 ] 1 { 1,3 , 6 } [ 8,11 ] 4 { 1,6 } [ 8,14 ] 7 { 1,3 , 4,6 } [ 11,11 ] 1 { 1,4 , 6 } [ 11,14 ] 4 { 1,4 } [ 11,16 ] 6 { 1,8 , 5,4 , 6 } [ 12,14 ] 3 { 1,5 , 4 } [ 12,16 ] 5 { 1,5 } [ 12,17 ] 6 { 1,2 , 5,4 , 7 } [ 16,16 ] 1 { 1,2 , 5,7 } [ 16,17 ] 2 { 1,2 , 7 } [ 16,18 ] 3 { 1,8 , 4 } [ 19,22 ] 4 { 1,4 } [ 19,24 ] 6 { 1,8 , 5,4 , 6 } [ 20,22 ] 3 { 1,5 , 4,6 } [ 20,24 ] 5 { 1,5 , 6 } [ 20,27 ] 8 { 1,5 } [ 20,30 ] 10 { 1,3 , 5,4 , 6,8 } [ 21,22 ] 2 { 1,3 , 5,4 , 6 } [ 21,24 ] 4 { 1,3 , 5,6 } [ 21,27 ] 7 { 1,3 , 5,4 , 6,8 } [ 24,24 ] 1 { 1,8 , 3,5 , 6 } [ 24,27 ] 4 { 1,8 , 5 } [ 24,30 ] 6 { 1,3 , 5,7 , 6,8 } [ 25,27 ] 3 { 1,3 , 2,5 , 7,6 , 8 } [ 26,27 ] 2 { 1,8 , 2,5 } [ 26,30 ] 4 { 1,3 , 2,5 , 4,7 , 6,8 } [ 27,27 ] 1 { 1,8 , 2,5 , 4 } [ 27,30 ] 3The transfer times between lines 1 and 2, for instance, are obtained from Table4 in a two-step procedure. The first step consists of selecting cliques of Table 4 containing only lines 1 and 2 as shown in Table 5.Table 5
Step 1: maximal cliques containing only lines 1 and 2 from 7:00 to 7:30 am.
Set of nodes (bus lines) Time interval (min) Duration (min) { 1,8 , 2,4 , 7 } [ 3,4 ] 2 { 1,2 , 5,4 , 7 } [ 16,16 ] 1 { 1,2 , 5,7 } [ 16,17 ] 2 { 1,2 , 7 } [ 16,18 ] 3 { 1,3 , 2,5 , 7,6 , 8 } [ 26,27 ] 2 { 1,8 , 2,5 } [ 26,30 ] 4 { 1,3 , 2,5 , 4,7 , 6,8 } [ 27,27 ] 1 { 1,8 , 2,5 , 4 } [ 27,30 ] 3The second step obtains maximal nonoverlapping time intervals containing nodes{1,2}. According to Table 6, these intervals are [3,4], [16,18], and [26,30] with durations of 2, 3, and 4 min, respectively. They represent the corresponding transfer times for these lines.Table 6
Step 2: nonoverlapping time intervals from Table6.
Set of nodes (bus lines) Time interval (min) Duration (min) { 1,2 } [ 3,4 ] 2 { 1,2 } [ 16,18 ] 3 { 1,2 } [ 26,30 ] 4This procedure can also be done for lines 1 and 3, or any set of lines. In other words, transfer times for connecting buses can be obtained by filtering cliques computed for all bus lines to select lines of interest and nonoverlapping time intervals.


### 3.1.2. Bunching

Bunching is a phenomenon characterized by a concentration of buses in a single area. It is detected here when the headway between two consecutive buses of the same line is less than 1 minute. Usually it occurs due to delays in departures or arrivals of buses and reduces the transport efficiency. When bunching occurs, buses eventually leave the terminal almost empty or completely full of passengers. At certain times of the day (peak traffic of buses or passengers), it is observed that bunching events occur due to a large number of passengers to be transported or high frequency of buses. This effect causes performance issues as poor quality of service and excessive waiting time as pointed out by [19–22].In this work, bunching detection is done by distinguishing buses of the same line and assuming that link streams are built using a sampling time rate of 1 min or less. This way, headways equal to or less than 1 min can be captured. A bunching event is then identified by taking cliques of the same line buses.For instance, the link stream shown in Figure4 considers only buses of line 1 in the terminal from 7:00 to 7:30 am with different labels assigned to different buses. Labels begin with a line number followed by two digits of the bus number. For instance, label 104 means bus 04 of line 1. Similarly, labels 107, 109, 111, 120, 121, 126, and 130 represent eight different buses of line 1.Figure 4
Link stream of line 1 showing the bunching effect from 7:00 to 7:30 am.According to Figure4, buses 104, 120, and 126 are in the terminal at 7:08 am causing a bunching event in line 1 during 1 min. All these bunching events are detected by maximal cliques as shown in Table 7. The greatest bunching events are composed by buses 111, 120, and 126 during 4 min between 7:09 and 7:12 am (in bold).Table 7
Bunching events from 7:00 to 7:30 am for bus line 1.
Bunching (set of buses) Time interval (min) Duration (min) { 104,120,126 } [ 8,8 ] 1 { 120,126 } [ 8,12 ] 6 { 111,120,126 } [ 9,12 ] 4 { 111,126 } [ 9,16 ] 8 { 107,111,126 } [ 16,16 ] 1 { 107,111 } [ 16,20 ] 5 { 107,111,121 } [ 20,20 ] 1 { 107,121 } [ 20,24 ] 5 { 107,121,130 } [ 22,24 ] 3 { 121,130 } [ 22,28 ] 7 { 109,130 } [ 29,30 ] 2


### 3.1.3. Congestion Analysis

The congestion analysis is obtained by the number of buses that are in the terminal at a given time interval. This information is also given by cliques by using different labels for different buses of the same line and computing the maximum number of buses at each time. Table8 shows the number of buses in the terminal minute by minute from 7:00 to 7:30 am by taking the cliques of Table 4 but marking buses of the same line with different labels. This information is used to monitor the terminal occupation as detailed in Section 4.Table 8
Number of buses in the terminal from 7:00 to 7:30 am.
Minute Set of nodes (bus lines) Set of nodes (bus numbers) Number of buses 0 { 1,8 } { 103,807 } 2 1 { 1,8 } { 103,807 } 2 2 { 1,8 } { 103,807 } 2 3 { 1,2 , 4,7 , 8 } { 103,202,402,704,807 } 5 4 { 1,2 , 4,7 , 8 } { 103,202,402,704,807 } 5 5 { 2,4 , 7,8 } { 202,402,704,807 } 4 6 { 2,4 , 7 } { 202,402,704 } 3 7 { 1,3 , 4 } { 104,301,402 } 3 8 { 1,3 , 4,6 } { 104,120,126,301,402,603 } 6 9 { 1,3 , 6 } { 111,120,126,301,603 } 5 10 { 1,3 , 6 } { 111,120,126,301,603 } 5 11 { 1,3 , 4,6 } { 111,120,126,301,401,603 } 6 12 { 1,4 , 5,6 , 8 } { 111,120,126,401,501,603,804 } 7 13 { 1,4 , 5,6 , 8 } { 111,126,401,501,603,804 } 6 14 { 1,4 , 5,6 , 8 } { 111,126,401,501,603,804 } 6 15 { 1,4 , 5 } { 111,126,401,501 } 4 16 { 1,2 , 4,5 , 7 } { 107,111,126,201,401,501,702 } 7 17 { 1,2 , 5,7 } { 107,111,201,501,702 } 5 18 { 1,2 , 7 } { 107,111,201,702 } 4 19 { 1,4 , 8 } { 107,111,404,808 } 4 20 { 1,2 , 4,5 , 6,8 } { 107,111,121,404,502,602,808 } 7 21 { 1,3 , 4,5 , 6,8 } { 107,121,301,404,502,602,808 } 7 22 { 1,3 , 4,5 , 6,8 } { 107,121,130,301,404,502,602,808 } 8 23 { 1,3 , 4,5 , 6 } { 107,121,130,301,404,502,602 } 7 24 { 1,3 , 4,5 , 6,8 } { 107,121,130,301,404,502,602,806 } 8 25 { 1,3 , 5,6 , 7,8 } { 121,130,301,502,602,703,806 } 7 26 { 1,2 , 3,5 , 6,7 , 8 } { 121,130,203,301,502,602,703,806 } 8 27 { 1,2 , 3,4 , 5,6 , 7,8 } { 121,130,203,301,402,502,602,703,806 } 9 28 { 1,2 , 4,5 , 8 } { 121,130,203,402,502,806 } 6 29 { 1,2 , 4,5 , 8 } { 109,130,203,402,502,806 } 6 30 { 1,2 , 4,5 , 8 } { 109,130,203,402,502,806 } 6


### 3.1.4. Number of Transferred Passengers

In order to estimate the number of passengers that are successfully transferred from local lines to the express line it is necessary to have a model for passengers’ mobility. This model should take into account the time interval necessary for transferring of passengers between bus stops (required transfer time) as well as the time interval during which buses are currently in the terminal (available transfer time).The required transfer time of passengers is based on three components: (i) passengers’ boarding time, (ii) passengers’ alighting time, and (iii) walking time necessary for passengers moving between alighting and boarding stops inside the terminal.The walking time is computed from the distance between drop-off and boarding areas divided by the standard walking speed of passengers. According to [23], the average reference for walking speed is 1.20 m/s for pedestrians. Boarding and alighting times per passenger depend on bus model [24] as shown in Table 9.Table 9
Boarding and alighting times (in seconds) per passenger (pax).
Bus type Boarding time Alighting time Single decker, step - 1.52 s/pax Single decker, low floor 1.76 s/pax -The transfer timett is then given by the boarding timetb plus walking timetw and alighting timeta as shown in(1)tt=tb+tw+ta.The total number of passengers transferred in a given time interval is computed in four steps:(i) Identify the time interval when the express line is in the terminal(ii) Identify all local lines that are able to transfer passengers to the express line within this time interval(iii) Calculate the required transfer time(iv) Verify how many passengers have been transferred within the available transfer timeThe first step is performed from maximal cliques involving all local and express lines in a given time interval as shown in Table10 for the express line 1 (buses 101 and 110).Table 10
Step 1: maximal cliques for express line1 and local lines 2–8 between 6:00 and 6:10 am.
Set of nodes (bus numbers) Time interval { 201 , 101 } [ 2 , 6 ] { 201 , 101 , 601,808 } [ 4 , 6 ] { 101 , 808 } [ 4 , 7 ] { 201,404,808,601,110 , 101 } [ 5 , 6 ] { 404,110 , 101 , 808 } [ 5 , 7 ]  { 404 , 110 , 808 } [ 5 , 10 ] { 110 , 404 } [ 5 , 12 ] { 108,404,502 , 110 , 808 } [ 8 , 9 ] { 108,404 , 110 , 808 } [ 8 , 10 ] { 108,404 , 110 } [ 8 , 12 ] { 108,404 , 110 , 703,502,806,808 } [ 9 , 9 ] { 404,108,808 , 110 , 806,703 } [ 9 , 10 ] { 108,404,703,806 , 110 } [ 9 , 12 ]The goal of step 1 is to find the time interval during which the express line is at the platform and the corresponding transfer time available for each local line arriving within this time interval. According to Table10, line 1 (101 in boldface) starts a transfer at time 6:02 and ends at time 6:07 (the first five rows of Table 10). It means that line 1 (using bus number 101) is available for transfer during a total time of 6 min (interval [2,7]). Moreover, three events representing arrivals of local lines occur at times 6:02, 6:04, and 6:05 (second column of Table 10 in boldface). They are important to compute how much time each local bus has to transfer passengers until express line departure. This is captured in step 2 according to Table 11.Table 11
Step 2: available transfers to the express line from 6:00 to 6:10 am.
Transfer Transfer time { 201 , 101 } [ 2 , 7 ] { 201 , 101 , 601,808 } [ 4 , 7 ] { 201,404,808,601,110 , 101 } [ 5 , 7 ]  { 108,404,502 , 110 , 808 } [ 8 , 12 ] { 108,404 , 110 , 703,502,806,808 } [ 9 , 12 ] { 604,108,404 , 110 , 703,806,808 } [ 10 , 12 ]In Table11, time intervals are extended to the corresponding express departure time (6:07 am for bus 101 and 6:12 for 110, respectively, in boldface). Moreover, only cliques with the greatest number of nodes are kept among cliques with same initial time. This is equivalent to compute all buses that arrive at same time. For instance, data from cliques [4,6]×{201,101,601,808} and [4,7]×{101,808} reduce to set {201,101,601,808} of buses arriving at 6:04. They have time until 6:07 am to make transfers (second row of Table 11).The final step(3) simply extracts the maximum time interval for each transfer according to Table 12. For instance, the maximum transfer time between buses 201 and 101 is 6 min (first row of Table 12).Table 12
Step 3: final transfer times to the express line from 6:00 to 6:10 am.
Transfer Maximum time interval Available transfer time (min) 101,201 [ 2,7 ] 6 101,601,808 [ 4,7 ] 4 101,404 [ 5,7 ] 3  110,502 [ 8,12 ] 5 110,703,806 [ 9,12 ] 4 110,604 [ 10,12 ] 3Therefore, Table12 shows all available transfers (lines and transfer times) between local and express lines occurring from 6:00 to 6:10 am. This information will be used in Table 13 to compute how many passengers will be successfully transferred to the express line. It is done based on the current number of passengers that arrive at the terminal from local lines, the required transfer time computed by (1), the available transfer time given by Table 12, and the express bus capacity.Table 13
Passengers transferred from local to express lines between 6:00 and 6:10 am.
Express bus number Local bus number Arriving passengers Required transfer time (min) Available transfer time (min) Connecting passengers Express bus capacity (pax) Balance (pax) 101 201 29 1.86 6 151 250 99 601 24 1.59 4 808 49 2.96 4 404 49 2.96 3  110 502 86 4.98 5 134 250 116 703 02 0.39 4 806 40 2.46 4 604 06 0.61 3The first column of Table13 contains the express bus number waiting at the boarding platform. The second column shows the local buses that arrive at the same time with the respective number of passengers in the third column. The next two columns show the required and available times for transferring passengers between local and express lines, respectively. The last three columns show how many passengers need to be transferred to the express line, the express bus capacity, and the corresponding balance of passengers (negative values mean that the express bus is full), respectively.According to Table13, while the express bus 101 is waiting at the boarding platform, a total of 151 passengers from buses 201, 601, 808, and 404 need to be transferred. The next express bus 110 needs to board 134 passengers from buses 502, 703, 806, and 604. Note that both express buses depart with available places. In addition, all passengers are successfully transferred as the available transfer time is greater than the required transfer time. It can be seen from Table 13 that transfers from buses 404 to 101 and 502 to 110 (in boldface) are very sensitive to delays. If bus 404 is delayed for about 1 min, for instance, the available transfer time decreases to 2 min and approximately only 33 passengers will be transferred. The other 16 passengers should wait for the next express bus.


## 3.1.1. Time Interval for Transfers

Cliques provide the necessary information about how many and during how much time buses from different lines are in the terminal. They involve the computation of the maximal common interval during which a meeting of one or more buses occurs and allows transfer of passengers. Table4 shows cliques for all eight lines operating in the terminal between 7:00 and 7:30 am. This is the basic information necessary for the performance analysis accomplished here.Table 4
Maximal cliques involving bus lines between 7:00 and 7:30 am.
Set of nodes (bus lines) Time interval (min) Duration (min) { 1,8 } [ 0,4 ] 5 { 1,8 , 2,4 , 7 } [ 3,4 ] 2 { 8,2 , 4,7 } [ 3,5 ] 3 { 2,4 , 7 } [ 3,6 ] 4 { 1,3 , 4 } [ 7,8 ] 2 { 1,3 } [ 7,11 ] 5 { 1,3 , 4,6 } [ 8,8 ] 1 { 1,3 , 6 } [ 8,11 ] 4 { 1,6 } [ 8,14 ] 7 { 1,3 , 4,6 } [ 11,11 ] 1 { 1,4 , 6 } [ 11,14 ] 4 { 1,4 } [ 11,16 ] 6 { 1,8 , 5,4 , 6 } [ 12,14 ] 3 { 1,5 , 4 } [ 12,16 ] 5 { 1,5 } [ 12,17 ] 6 { 1,2 , 5,4 , 7 } [ 16,16 ] 1 { 1,2 , 5,7 } [ 16,17 ] 2 { 1,2 , 7 } [ 16,18 ] 3 { 1,8 , 4 } [ 19,22 ] 4 { 1,4 } [ 19,24 ] 6 { 1,8 , 5,4 , 6 } [ 20,22 ] 3 { 1,5 , 4,6 } [ 20,24 ] 5 { 1,5 , 6 } [ 20,27 ] 8 { 1,5 } [ 20,30 ] 10 { 1,3 , 5,4 , 6,8 } [ 21,22 ] 2 { 1,3 , 5,4 , 6 } [ 21,24 ] 4 { 1,3 , 5,6 } [ 21,27 ] 7 { 1,3 , 5,4 , 6,8 } [ 24,24 ] 1 { 1,8 , 3,5 , 6 } [ 24,27 ] 4 { 1,8 , 5 } [ 24,30 ] 6 { 1,3 , 5,7 , 6,8 } [ 25,27 ] 3 { 1,3 , 2,5 , 7,6 , 8 } [ 26,27 ] 2 { 1,8 , 2,5 } [ 26,30 ] 4 { 1,3 , 2,5 , 4,7 , 6,8 } [ 27,27 ] 1 { 1,8 , 2,5 , 4 } [ 27,30 ] 3The transfer times between lines 1 and 2, for instance, are obtained from Table4 in a two-step procedure. The first step consists of selecting cliques of Table 4 containing only lines 1 and 2 as shown in Table 5.Table 5
Step 1: maximal cliques containing only lines 1 and 2 from 7:00 to 7:30 am.
Set of nodes (bus lines) Time interval (min) Duration (min) { 1,8 , 2,4 , 7 } [ 3,4 ] 2 { 1,2 , 5,4 , 7 } [ 16,16 ] 1 { 1,2 , 5,7 } [ 16,17 ] 2 { 1,2 , 7 } [ 16,18 ] 3 { 1,3 , 2,5 , 7,6 , 8 } [ 26,27 ] 2 { 1,8 , 2,5 } [ 26,30 ] 4 { 1,3 , 2,5 , 4,7 , 6,8 } [ 27,27 ] 1 { 1,8 , 2,5 , 4 } [ 27,30 ] 3The second step obtains maximal nonoverlapping time intervals containing nodes{1,2}. According to Table 6, these intervals are [3,4], [16,18], and [26,30] with durations of 2, 3, and 4 min, respectively. They represent the corresponding transfer times for these lines.Table 6
Step 2: nonoverlapping time intervals from Table6.
Set of nodes (bus lines) Time interval (min) Duration (min) { 1,2 } [ 3,4 ] 2 { 1,2 } [ 16,18 ] 3 { 1,2 } [ 26,30 ] 4This procedure can also be done for lines 1 and 3, or any set of lines. In other words, transfer times for connecting buses can be obtained by filtering cliques computed for all bus lines to select lines of interest and nonoverlapping time intervals.


## 3.1.2. Bunching

Bunching is a phenomenon characterized by a concentration of buses in a single area. It is detected here when the headway between two consecutive buses of the same line is less than 1 minute. Usually it occurs due to delays in departures or arrivals of buses and reduces the transport efficiency. When bunching occurs, buses eventually leave the terminal almost empty or completely full of passengers. At certain times of the day (peak traffic of buses or passengers), it is observed that bunching events occur due to a large number of passengers to be transported or high frequency of buses. This effect causes performance issues as poor quality of service and excessive waiting time as pointed out by [19–22].In this work, bunching detection is done by distinguishing buses of the same line and assuming that link streams are built using a sampling time rate of 1 min or less. This way, headways equal to or less than 1 min can be captured. A bunching event is then identified by taking cliques of the same line buses.For instance, the link stream shown in Figure4 considers only buses of line 1 in the terminal from 7:00 to 7:30 am with different labels assigned to different buses. Labels begin with a line number followed by two digits of the bus number. For instance, label 104 means bus 04 of line 1. Similarly, labels 107, 109, 111, 120, 121, 126, and 130 represent eight different buses of line 1.Figure 4
Link stream of line 1 showing the bunching effect from 7:00 to 7:30 am.According to Figure4, buses 104, 120, and 126 are in the terminal at 7:08 am causing a bunching event in line 1 during 1 min. All these bunching events are detected by maximal cliques as shown in Table 7. The greatest bunching events are composed by buses 111, 120, and 126 during 4 min between 7:09 and 7:12 am (in bold).Table 7
Bunching events from 7:00 to 7:30 am for bus line 1.
Bunching (set of buses) Time interval (min) Duration (min) { 104,120,126 } [ 8,8 ] 1 { 120,126 } [ 8,12 ] 6 { 111,120,126 } [ 9,12 ] 4 { 111,126 } [ 9,16 ] 8 { 107,111,126 } [ 16,16 ] 1 { 107,111 } [ 16,20 ] 5 { 107,111,121 } [ 20,20 ] 1 { 107,121 } [ 20,24 ] 5 { 107,121,130 } [ 22,24 ] 3 { 121,130 } [ 22,28 ] 7 { 109,130 } [ 29,30 ] 2


## 3.1.3. Congestion Analysis

The congestion analysis is obtained by the number of buses that are in the terminal at a given time interval. This information is also given by cliques by using different labels for different buses of the same line and computing the maximum number of buses at each time. Table8 shows the number of buses in the terminal minute by minute from 7:00 to 7:30 am by taking the cliques of Table 4 but marking buses of the same line with different labels. This information is used to monitor the terminal occupation as detailed in Section 4.Table 8
Number of buses in the terminal from 7:00 to 7:30 am.
Minute Set of nodes (bus lines) Set of nodes (bus numbers) Number of buses 0 { 1,8 } { 103,807 } 2 1 { 1,8 } { 103,807 } 2 2 { 1,8 } { 103,807 } 2 3 { 1,2 , 4,7 , 8 } { 103,202,402,704,807 } 5 4 { 1,2 , 4,7 , 8 } { 103,202,402,704,807 } 5 5 { 2,4 , 7,8 } { 202,402,704,807 } 4 6 { 2,4 , 7 } { 202,402,704 } 3 7 { 1,3 , 4 } { 104,301,402 } 3 8 { 1,3 , 4,6 } { 104,120,126,301,402,603 } 6 9 { 1,3 , 6 } { 111,120,126,301,603 } 5 10 { 1,3 , 6 } { 111,120,126,301,603 } 5 11 { 1,3 , 4,6 } { 111,120,126,301,401,603 } 6 12 { 1,4 , 5,6 , 8 } { 111,120,126,401,501,603,804 } 7 13 { 1,4 , 5,6 , 8 } { 111,126,401,501,603,804 } 6 14 { 1,4 , 5,6 , 8 } { 111,126,401,501,603,804 } 6 15 { 1,4 , 5 } { 111,126,401,501 } 4 16 { 1,2 , 4,5 , 7 } { 107,111,126,201,401,501,702 } 7 17 { 1,2 , 5,7 } { 107,111,201,501,702 } 5 18 { 1,2 , 7 } { 107,111,201,702 } 4 19 { 1,4 , 8 } { 107,111,404,808 } 4 20 { 1,2 , 4,5 , 6,8 } { 107,111,121,404,502,602,808 } 7 21 { 1,3 , 4,5 , 6,8 } { 107,121,301,404,502,602,808 } 7 22 { 1,3 , 4,5 , 6,8 } { 107,121,130,301,404,502,602,808 } 8 23 { 1,3 , 4,5 , 6 } { 107,121,130,301,404,502,602 } 7 24 { 1,3 , 4,5 , 6,8 } { 107,121,130,301,404,502,602,806 } 8 25 { 1,3 , 5,6 , 7,8 } { 121,130,301,502,602,703,806 } 7 26 { 1,2 , 3,5 , 6,7 , 8 } { 121,130,203,301,502,602,703,806 } 8 27 { 1,2 , 3,4 , 5,6 , 7,8 } { 121,130,203,301,402,502,602,703,806 } 9 28 { 1,2 , 4,5 , 8 } { 121,130,203,402,502,806 } 6 29 { 1,2 , 4,5 , 8 } { 109,130,203,402,502,806 } 6 30 { 1,2 , 4,5 , 8 } { 109,130,203,402,502,806 } 6


## 3.1.4. Number of Transferred Passengers

In order to estimate the number of passengers that are successfully transferred from local lines to the express line it is necessary to have a model for passengers’ mobility. This model should take into account the time interval necessary for transferring of passengers between bus stops (required transfer time) as well as the time interval during which buses are currently in the terminal (available transfer time).The required transfer time of passengers is based on three components: (i) passengers’ boarding time, (ii) passengers’ alighting time, and (iii) walking time necessary for passengers moving between alighting and boarding stops inside the terminal.The walking time is computed from the distance between drop-off and boarding areas divided by the standard walking speed of passengers. According to [23], the average reference for walking speed is 1.20 m/s for pedestrians. Boarding and alighting times per passenger depend on bus model [24] as shown in Table 9.Table 9
Boarding and alighting times (in seconds) per passenger (pax).
Bus type Boarding time Alighting time Single decker, step - 1.52 s/pax Single decker, low floor 1.76 s/pax -The transfer timett is then given by the boarding timetb plus walking timetw and alighting timeta as shown in(1)tt=tb+tw+ta.The total number of passengers transferred in a given time interval is computed in four steps:(i) Identify the time interval when the express line is in the terminal(ii) Identify all local lines that are able to transfer passengers to the express line within this time interval(iii) Calculate the required transfer time(iv) Verify how many passengers have been transferred within the available transfer timeThe first step is performed from maximal cliques involving all local and express lines in a given time interval as shown in Table10 for the express line 1 (buses 101 and 110).Table 10
Step 1: maximal cliques for express line1 and local lines 2–8 between 6:00 and 6:10 am.
Set of nodes (bus numbers) Time interval { 201 , 101 } [ 2 , 6 ] { 201 , 101 , 601,808 } [ 4 , 6 ] { 101 , 808 } [ 4 , 7 ] { 201,404,808,601,110 , 101 } [ 5 , 6 ] { 404,110 , 101 , 808 } [ 5 , 7 ]  { 404 , 110 , 808 } [ 5 , 10 ] { 110 , 404 } [ 5 , 12 ] { 108,404,502 , 110 , 808 } [ 8 , 9 ] { 108,404 , 110 , 808 } [ 8 , 10 ] { 108,404 , 110 } [ 8 , 12 ] { 108,404 , 110 , 703,502,806,808 } [ 9 , 9 ] { 404,108,808 , 110 , 806,703 } [ 9 , 10 ] { 108,404,703,806 , 110 } [ 9 , 12 ]The goal of step 1 is to find the time interval during which the express line is at the platform and the corresponding transfer time available for each local line arriving within this time interval. According to Table10, line 1 (101 in boldface) starts a transfer at time 6:02 and ends at time 6:07 (the first five rows of Table 10). It means that line 1 (using bus number 101) is available for transfer during a total time of 6 min (interval [2,7]). Moreover, three events representing arrivals of local lines occur at times 6:02, 6:04, and 6:05 (second column of Table 10 in boldface). They are important to compute how much time each local bus has to transfer passengers until express line departure. This is captured in step 2 according to Table 11.Table 11
Step 2: available transfers to the express line from 6:00 to 6:10 am.
Transfer Transfer time { 201 , 101 } [ 2 , 7 ] { 201 , 101 , 601,808 } [ 4 , 7 ] { 201,404,808,601,110 , 101 } [ 5 , 7 ]  { 108,404,502 , 110 , 808 } [ 8 , 12 ] { 108,404 , 110 , 703,502,806,808 } [ 9 , 12 ] { 604,108,404 , 110 , 703,806,808 } [ 10 , 12 ]In Table11, time intervals are extended to the corresponding express departure time (6:07 am for bus 101 and 6:12 for 110, respectively, in boldface). Moreover, only cliques with the greatest number of nodes are kept among cliques with same initial time. This is equivalent to compute all buses that arrive at same time. For instance, data from cliques [4,6]×{201,101,601,808} and [4,7]×{101,808} reduce to set {201,101,601,808} of buses arriving at 6:04. They have time until 6:07 am to make transfers (second row of Table 11).The final step(3) simply extracts the maximum time interval for each transfer according to Table 12. For instance, the maximum transfer time between buses 201 and 101 is 6 min (first row of Table 12).Table 12
Step 3: final transfer times to the express line from 6:00 to 6:10 am.
Transfer Maximum time interval Available transfer time (min) 101,201 [ 2,7 ] 6 101,601,808 [ 4,7 ] 4 101,404 [ 5,7 ] 3  110,502 [ 8,12 ] 5 110,703,806 [ 9,12 ] 4 110,604 [ 10,12 ] 3Therefore, Table12 shows all available transfers (lines and transfer times) between local and express lines occurring from 6:00 to 6:10 am. This information will be used in Table 13 to compute how many passengers will be successfully transferred to the express line. It is done based on the current number of passengers that arrive at the terminal from local lines, the required transfer time computed by (1), the available transfer time given by Table 12, and the express bus capacity.Table 13
Passengers transferred from local to express lines between 6:00 and 6:10 am.
Express bus number Local bus number Arriving passengers Required transfer time (min) Available transfer time (min) Connecting passengers Express bus capacity (pax) Balance (pax) 101 201 29 1.86 6 151 250 99 601 24 1.59 4 808 49 2.96 4 404 49 2.96 3  110 502 86 4.98 5 134 250 116 703 02 0.39 4 806 40 2.46 4 604 06 0.61 3The first column of Table13 contains the express bus number waiting at the boarding platform. The second column shows the local buses that arrive at the same time with the respective number of passengers in the third column. The next two columns show the required and available times for transferring passengers between local and express lines, respectively. The last three columns show how many passengers need to be transferred to the express line, the express bus capacity, and the corresponding balance of passengers (negative values mean that the express bus is full), respectively.According to Table13, while the express bus 101 is waiting at the boarding platform, a total of 151 passengers from buses 201, 601, 808, and 404 need to be transferred. The next express bus 110 needs to board 134 passengers from buses 502, 703, 806, and 604. Note that both express buses depart with available places. In addition, all passengers are successfully transferred as the available transfer time is greater than the required transfer time. It can be seen from Table 13 that transfers from buses 404 to 101 and 502 to 110 (in boldface) are very sensitive to delays. If bus 404 is delayed for about 1 min, for instance, the available transfer time decreases to 2 min and approximately only 33 passengers will be transferred. The other 16 passengers should wait for the next express bus.


## 4. Case Study

Our methodology models the transport system by means of link streams considering bus lines running all day long. Cliques are then obtained from link streams which allow carrying out several analyses. This is an advantage in terms of scalability as described in the following.Our case study is taken from Curitiba’s public transportation. Curitiba is a city in Southern Brazil with approximately 2 million people and around 2,200,000 passengers transported daily. Curitiba’s public transportation has become known due to its Bus Rapid Transit (BRT) system [3]. In BRT, buses run in private lanes connecting terminals which are served by local bus lines connecting neighborhoods. There are five types of bus lines: fast express lines, express lines, direct lines, interneighborhood lines, and local lines. Express lines are mainly used to connect terminals and local lines connect the neighborhoods of terminals. About 2,145 buses run every day in the city serving 615 lines and 9,684 stops. Terminal Centenário was taken for analysis. Eight lines and 61 buses operate in this terminal every weekday according to Table 14. Link streams are obtained for June 06, 2016, from bus schedules provided by [25]. In Table 14, line number 1 is an express line which connects terminal Centenário to terminal Campo Comprido. The other lines 2 to 8 are local lines connecting the neighborhood of terminal Centenário.Table 14
Bus lines for terminal Centenário.
Line number Line name Line type Number of buses 1 A Express line 31 2 B Local line 4 3 C Local line 1 4 D Local line 4 5 E Local line 3 6 F Local line 4 7 G Local line 4 8 H Local line 10


### 4.1. Available Transfer Time for Connecting Buses

Figure5 shows the corresponding link streams generated by lines 1 to 8 for the peak periods of 6:00 to 8:00 am, 12:00 to 2:00 pm, and 5:00 to 7:00 pm, corresponding to 120 min in Figures 5(a)–5(c), respectively. It can be seen from Figure 5 that buses are more concentrated in the morning than in the evening or afternoon in the terminal. This behavior is also highlighted in Section 4.3.Figure 5
Link streams: (a) 6:00 to 8:00 am, (b) 12:00 to 2:00 pm, and (c) 5:00 to 7:00 pm.
(a) (b) (c)The corresponding cliques obtained for all bus lines during the day according to Section3.1.1 provide the necessary information to build the transfer time distribution between connecting buses (from 2 to 8 buses) as shown in Figure 6.Figure 6
Transfer time for connecting 2, 3, 4, 5, 6, 7 and 8 lines all day long.According to Figure6, most connections occur with transfer time of 1 min involving 2 to 6 lines. There are two transfers of 1 and 2 min involving eight lines and 41 transfers of 1 min involving 5 lines. Transfers of more than 7 min occur but they are not relevant. Table 15 shows the average transfer time and respective standard deviation of data in Figure 6.Table 15
Average transfer time and respective standard deviation.
2 lines 3 lines 4 lines 5 lines 6 lines 7 lines 8 lines Average (min.) 2.98 2.45 2.65 1.88 1.88 2.26 1.5 Std. deviation (min) 1.25 1.08 1.41 1 1.15 1.05 0.5Two particular transfers of passengers are important as they connect the current terminal with two other terminals. Figure7 shows the distribution of transfer times between lines 1 and 6 for the period of all day long. It can be seen that transfer times of 3 min are more often with mean of 4.8 min and standard deviation of 2.26 min. The cumulative distribution shows that 50% of transfer times are below 4 min.Figure 7
Distribution (blue) and cumulative distribution (red) of transfer time between lines 1 and 6.Figure8 shows the distribution of transfer times between lines 1 and 8 for the period of all day long. It can be seen that transfer times of 3 and 7 min are more often with mean of 6 min and standard deviation of 3.29 min. The cumulative distribution shows that 50% of transfer times are below 6 min.Figure 8
Distribution (blue) and cumulative distribution (red) of transfer times between lines 1 and 8.These transfer times will be used to compute the number of transferred passengers between local and express lines as described in Section4.4.


### 4.2. Bunching

The analysis of bunching was made for the express line 1. This line serves passengers who are transferring from neighborhood lines to the central city. Moreover, bunching in line 1 should be avoided as the platform does not allow more than one express bus at the same time. It means that if an express bus is boarding/dropping off passengers and a new bus arrives then it must wait for using the platform. Although there are 31 buses in line 1 according to Table14, only 24 buses are running between 6:00 and 8:00 am. Figure 9 shows the corresponding link stream for this time interval of 120 min, and Table 16 presents the bunching events according to Section 3.1.2.Table 16
Bunching events for line 1 from 6:00 to 8:00 am.
Bunching (set of buses) Time interval (min) Duration (min) Boarding bus Holding bus { 101,110 } [ 5,7 ] 3 101 110 { 110,108 } [ 8,12 ] 5 110 108 { 110,108,115 } [ 12,12 ] 1 110 108,115 { 108,115 } [ 12,17 ] 6 108 115 { 108,115,128 } [ 13,17 ] 5 108 115,128 { 115,128 } [ 13,21 ] 9 115 128 { 115,128,105 } [ 21,21 ] 1 115 128,105 { 115,105 } [ 21,26 ] 6 115 105 { 115,105,129 } [ 23,26 ] 4 115 105,129 { 105,129 } [ 23,31 ] 9 105 129 { 129,124 } [ 32,38 ] 7 129 124 { 127,117 } [ 55,55 ] 1 127 117 { 104,120,126 } [ 68,68 ] 1 104 120,126 { 120,126 } [ 68,72 ] 5 120 126 { 120 ,  126,111 } [ 69,72 ] 4 120 126,111 { 126,111 } [ 69,76 ] 8 126 111 { 126,111,107 } [ 76,76 ] 1 126 111,107 { 111,107 } [ 76,80 ] 5 111 107 / 5 { 111,107,121 } [ 80,80 ] 1 111 107,121 { 107,121 } [ 80,84 ] 5 107 121 { 107,121,130 } [ 82,84 ] 3 107 121,130 { 121,130 } [ 82,88 ] 7 121 130 { 130,109 } [ 89,92 ] 4 130 109 { 109,125 } [ 95,96 ] 2 109 125 { 125,112 } [ 99,102 ] 4 125 112 { 112,113 } [ 104,107 ] 4 112 113 { 113,116 } [ 109,110 ] 2 113 116 { 116,102 } [ 114,116 ] 3 116 102 { 102,114 } [ 117,119 ] 3 102 114Figure 9
Bunching for line 1 between 6:00 and 8:00 am.According to Table16, two bunching events last for 9 min and a bunching of three buses lasts for 4 min (in bold). According to timetables provided by URBS [25], buses 101, 128, 104, 120, 130, 125, and 102 are extra buses; i.e., they are scheduled to increase the transport capacity at given times as shown in Section 4.4.By removing extra buses 101, 128, 104, 120, 130, 125, and 102, Table17 shows the remaining bunching events. This might indicate that a reschedule of timetables is necessary.Table 17
Bunching events without extra buses for line 1 from 6:00 to 8:00 am.
Bunching Time interval (set of buses) (min) { 108,110 } [ 8,12 ] { 108,110 ,  115 } [ 12,12 ] { 108,115 } [ 12,17 ] { 105,115 } [ 21,26 ] { 105,115,129 } [ 23,26 ] { 105,129 } [ 23,31 ] { 124,129 } [ 32,38 ] { 127,117 } [ 55,55 ] { 126,111 } [ 69,76 ] { 126,111,107 } [ 76,76 ] { 111,107 } [ 76,80 ] { 111,107,121 } [ 80,80 ] { 107,121 } [ 80,84 ] { 112,113 } [ 104,107 ] { 113,116 } [ 109,110 ]


### 4.3. Congestion Analysis

The congestion analysis is made by counting the number of buses in the terminal at certain times according to the procedure of Section3.1.3. Figures 10–12 show the congestion generated by buses of lines 1 to 8 for the peak periods of 6:00 to 8:00 am, 12:00 am to 2:00 pm, and 5:00 to 7:00 pm (periods of 120 min), respectively.Figure 10
Congestion in the terminal between 6:00 and 8:00 am.Figure 11
Congestion in the terminal between 12:00 am and 2:00 pm.Figure 12
Congestion in the terminal between 5:00 and 7:00 pm.As mentioned in Section4.1, buses are more concentrated in the morning with a maximum of 10 buses at 06:25 am. This behavior does not repeat in the afternoon or evening when maximums of 6 and 8 buses are observed, respectively. Moreover, a total of 674, 371, and 537 buses pass through the terminal in the morning, afternoon, and evening, respectively.


### 4.4. Number of Transferred Passengers

In this section we check if the number of buses at the terminal can handle the passenger demand arriving from local bus lines. This is accomplished by computing the difference between the number of passengers coming from local buses and the capacity provided by the express line as explained in Section3.1.4. The express bus capacity is 250 passengers. We are considering 20 m of distance between the boarding and alighting points. The intervals for analysis are also set according to peak times of 6:00 to 8:00 am, 12:00 to 2:00 pm, and 5:00 to 7:00 pm. The number of passengers in local lines is given by historical data provided by URBS. Passengers arriving at the terminal by walking are not considered in this analysis as they represent a small part of passengers passing through the terminal.Figure13 shows the link stream for buses between 6:00 and 8:00 am. It is possible to visualize all connections between buses minute by minute during this time interval.Figure 13
Link stream for buses between 6:00 and 8:00 am.Figure14 presents an illustrative detail (marked by an arrow in Figure 13) to show the information provided within time interval [46,50] min after 6:00 am. During this time interval, passengers are able to make transfers among six buses (123, 401, 501, 601, 703, and 809) as shown in Figure 14.Figure 14
Link stream detail for interval[46,50] min after 6:00 am.Table18 shows the number of passengers transferred from local to express lines between 6:00 and 8:00 am. It is obtained from the link stream and corresponding cliques of Figure 13 as presented in Section 3.1.4.Table 18
Passengers transferred from local to express buses between 6:00 and 8:00 am.
Express bus number Express bus capacity (pax) Connecting passengers Balance (pax) 101 250 151 99 110 250 134 116 108 250 122 128 115 250 365 -115 105 250 67 68 129 250 166 84 124 250 113 137 123 250 312 -62 127 250 118 70 117 250 42 208 103 250 163 45 104 250 60 190 120 250 193 57 126 250 50 200 111 250 133 117 107 250 75 175 121 250 64 186 130 250 0 250 109 250 38 212 125 250 197 53 112 250 71 179 113 250 39 211 116 250 168 82 102 250 3 247According to Table18, some passengers cannot board the express bus as it is full (negative numbers in bold). The most critical event occurs when bus 115 is ready for boarding 365 passengers. In this case, 115 passengers (in bold) must wait for the next express bus 105. When it arrives, 115 plus 67 passengers that newly arrived from local buses should be boarded. This also occurs for express bus 123 which cannot board all 312 passengers, and 62 passengers (negative number in bold) must wait for the next bus 127.Table19 shows connecting buses in detail for express buses 115 and 127. Note that not all passengers from local buses 502 and 805 are successful as the required transfer time is greater than the available time (in bold). Only 36 passengers are successful, and 26 passengers from bus 502 and 23 passengers from bus 805 cannot make the transfer, according to (1). A similar case occurs for transferring passengers from buses 502 to 127 (in bold) when 35 passengers cannot make the transfer.Table 19
Unavailable transfer time for express buses 115 and 127 between 6:00 and 8:00 am.
Express bus number Local bus number Arriving passengers Required transfer time (min) Available transfer time (min) 115 701 4 0.50 9 301 30 1.92 8 810 43 2.63 7 401 60 3.56 6 603 25 1.64 4 801 49 2.96 3 202 33 2.08 2 502 62 3.67 2 805 59 3.50 2  127 404 65 3.83 4 502 53 3.18 1Table20 shows the number of passengers transferred from local to express lines between 12:00 am and 2:00 pm. There are no capacity issues; i.e., no passengers must wait for the next express bus due to lack of available places. However, the required transfer time is an issue for connecting buses 807 with 112 and 808 with 116 according to Table 21.Table 20
Passengers transferred from local to express buses between 12:00 and 2:00 pm.
Express bus number Express bus capacity (pax) Connecting passengers Balance (pax) 114 250 50 200 131 250 83 167 110 250 58 192 108 250 60 190 115 250 91 159 105 250 99 151 129 250 97 153 124 250 106 144 123 250 66 184 117 250 102 148 103 250 55 195 126 250 47 203 111 250 122 128 107 250 25 225 121 250 52 198 109 250 43 207 112 250 72 178 113 250 6 244 116 250 102 148Table 21
Unavailable transfer time for express buses 112 and 116 between 12:00 and 2:00 pm.
Express bus number Local bus number Arriving passengers Required transfer time (min) Available transfer time (min) 112 603 17 1.21 6 404 17 1.21 2 807 38 2.36 1  116 301 15 1.10 3 501 12 0.93 2 201 22 1.48 1 808 53 3.18 1Table21 shows in detail that not all passengers of buses 807 and 808 are successful as the required transfer time is greater than the available time (in bold). In both cases, the available transfer time of 1 minute allows 16 passengers to be transferred. Therefore, 22 passengers from bus 807 and 37 from 808 must wait for the next express bus.Similarly to the previous peak period of Table20, there are no capacity issues for transferring passengers between local and express lines between 5:00 and 7:00 pm according to Table 22. However, the required transfer time is an issue for connecting buses 601 with 109 as shown in Table 23.Table 22
Passengers transferred from local to express buses between 5:00 and 7:00 pm.
Express bus number Express bus capacity (pax) Connecting passengers Balance (pax) 117 250 90 160 103 250 83 167 126 250 49 201 119 250 89 161 102 250 104 146 121 250 27 223 109 250 104 146 112 250 11 239 113 250 57 193 116 250 91 159 104 250 21 229 114 250 17 233 131 250 88 162 110 250 30 220 115 250 63 187 105 250 16 234 130 250 35 215 122 250 15 235 128 250 12 238 129 250 19 231Table 23
Unavailable transfer time for express bus 109 between 5:00 and 7:00 pm.
Express bus number Local bus number Arriving passengers Required transfer time (min) Available transfer time (min) 109 401 12 0.93 5 503 9 0.77 4 301 25 1.64 3 601 58 3.45 1Table23 shows in detail that not all passengers of bus 601 are successful (in bold). Thus, the available transfer time of 1 minute allows 16 passengers to be transferred, and 42 passengers cannot make the transfer to bus 109 according to (1) as 2.45 min longer would be necessary.


## 4.1. Available Transfer Time for Connecting Buses

Figure5 shows the corresponding link streams generated by lines 1 to 8 for the peak periods of 6:00 to 8:00 am, 12:00 to 2:00 pm, and 5:00 to 7:00 pm, corresponding to 120 min in Figures 5(a)–5(c), respectively. It can be seen from Figure 5 that buses are more concentrated in the morning than in the evening or afternoon in the terminal. This behavior is also highlighted in Section 4.3.Figure 5
Link streams: (a) 6:00 to 8:00 am, (b) 12:00 to 2:00 pm, and (c) 5:00 to 7:00 pm.
(a) (b) (c)The corresponding cliques obtained for all bus lines during the day according to Section3.1.1 provide the necessary information to build the transfer time distribution between connecting buses (from 2 to 8 buses) as shown in Figure 6.Figure 6
Transfer time for connecting 2, 3, 4, 5, 6, 7 and 8 lines all day long.According to Figure6, most connections occur with transfer time of 1 min involving 2 to 6 lines. There are two transfers of 1 and 2 min involving eight lines and 41 transfers of 1 min involving 5 lines. Transfers of more than 7 min occur but they are not relevant. Table 15 shows the average transfer time and respective standard deviation of data in Figure 6.Table 15
Average transfer time and respective standard deviation.
2 lines 3 lines 4 lines 5 lines 6 lines 7 lines 8 lines Average (min.) 2.98 2.45 2.65 1.88 1.88 2.26 1.5 Std. deviation (min) 1.25 1.08 1.41 1 1.15 1.05 0.5Two particular transfers of passengers are important as they connect the current terminal with two other terminals. Figure7 shows the distribution of transfer times between lines 1 and 6 for the period of all day long. It can be seen that transfer times of 3 min are more often with mean of 4.8 min and standard deviation of 2.26 min. The cumulative distribution shows that 50% of transfer times are below 4 min.Figure 7
Distribution (blue) and cumulative distribution (red) of transfer time between lines 1 and 6.Figure8 shows the distribution of transfer times between lines 1 and 8 for the period of all day long. It can be seen that transfer times of 3 and 7 min are more often with mean of 6 min and standard deviation of 3.29 min. The cumulative distribution shows that 50% of transfer times are below 6 min.Figure 8
Distribution (blue) and cumulative distribution (red) of transfer times between lines 1 and 8.These transfer times will be used to compute the number of transferred passengers between local and express lines as described in Section4.4.


## 4.2. Bunching

The analysis of bunching was made for the express line 1. This line serves passengers who are transferring from neighborhood lines to the central city. Moreover, bunching in line 1 should be avoided as the platform does not allow more than one express bus at the same time. It means that if an express bus is boarding/dropping off passengers and a new bus arrives then it must wait for using the platform. Although there are 31 buses in line 1 according to Table14, only 24 buses are running between 6:00 and 8:00 am. Figure 9 shows the corresponding link stream for this time interval of 120 min, and Table 16 presents the bunching events according to Section 3.1.2.Table 16
Bunching events for line 1 from 6:00 to 8:00 am.
Bunching (set of buses) Time interval (min) Duration (min) Boarding bus Holding bus { 101,110 } [ 5,7 ] 3 101 110 { 110,108 } [ 8,12 ] 5 110 108 { 110,108,115 } [ 12,12 ] 1 110 108,115 { 108,115 } [ 12,17 ] 6 108 115 { 108,115,128 } [ 13,17 ] 5 108 115,128 { 115,128 } [ 13,21 ] 9 115 128 { 115,128,105 } [ 21,21 ] 1 115 128,105 { 115,105 } [ 21,26 ] 6 115 105 { 115,105,129 } [ 23,26 ] 4 115 105,129 { 105,129 } [ 23,31 ] 9 105 129 { 129,124 } [ 32,38 ] 7 129 124 { 127,117 } [ 55,55 ] 1 127 117 { 104,120,126 } [ 68,68 ] 1 104 120,126 { 120,126 } [ 68,72 ] 5 120 126 { 120 ,  126,111 } [ 69,72 ] 4 120 126,111 { 126,111 } [ 69,76 ] 8 126 111 { 126,111,107 } [ 76,76 ] 1 126 111,107 { 111,107 } [ 76,80 ] 5 111 107 / 5 { 111,107,121 } [ 80,80 ] 1 111 107,121 { 107,121 } [ 80,84 ] 5 107 121 { 107,121,130 } [ 82,84 ] 3 107 121,130 { 121,130 } [ 82,88 ] 7 121 130 { 130,109 } [ 89,92 ] 4 130 109 { 109,125 } [ 95,96 ] 2 109 125 { 125,112 } [ 99,102 ] 4 125 112 { 112,113 } [ 104,107 ] 4 112 113 { 113,116 } [ 109,110 ] 2 113 116 { 116,102 } [ 114,116 ] 3 116 102 { 102,114 } [ 117,119 ] 3 102 114Figure 9
Bunching for line 1 between 6:00 and 8:00 am.According to Table16, two bunching events last for 9 min and a bunching of three buses lasts for 4 min (in bold). According to timetables provided by URBS [25], buses 101, 128, 104, 120, 130, 125, and 102 are extra buses; i.e., they are scheduled to increase the transport capacity at given times as shown in Section 4.4.By removing extra buses 101, 128, 104, 120, 130, 125, and 102, Table17 shows the remaining bunching events. This might indicate that a reschedule of timetables is necessary.Table 17
Bunching events without extra buses for line 1 from 6:00 to 8:00 am.
Bunching Time interval (set of buses) (min) { 108,110 } [ 8,12 ] { 108,110 ,  115 } [ 12,12 ] { 108,115 } [ 12,17 ] { 105,115 } [ 21,26 ] { 105,115,129 } [ 23,26 ] { 105,129 } [ 23,31 ] { 124,129 } [ 32,38 ] { 127,117 } [ 55,55 ] { 126,111 } [ 69,76 ] { 126,111,107 } [ 76,76 ] { 111,107 } [ 76,80 ] { 111,107,121 } [ 80,80 ] { 107,121 } [ 80,84 ] { 112,113 } [ 104,107 ] { 113,116 } [ 109,110 ]


## 4.3. Congestion Analysis

The congestion analysis is made by counting the number of buses in the terminal at certain times according to the procedure of Section3.1.3. Figures 10–12 show the congestion generated by buses of lines 1 to 8 for the peak periods of 6:00 to 8:00 am, 12:00 am to 2:00 pm, and 5:00 to 7:00 pm (periods of 120 min), respectively.Figure 10
Congestion in the terminal between 6:00 and 8:00 am.Figure 11
Congestion in the terminal between 12:00 am and 2:00 pm.Figure 12
Congestion in the terminal between 5:00 and 7:00 pm.As mentioned in Section4.1, buses are more concentrated in the morning with a maximum of 10 buses at 06:25 am. This behavior does not repeat in the afternoon or evening when maximums of 6 and 8 buses are observed, respectively. Moreover, a total of 674, 371, and 537 buses pass through the terminal in the morning, afternoon, and evening, respectively.


## 4.4. Number of Transferred Passengers

In this section we check if the number of buses at the terminal can handle the passenger demand arriving from local bus lines. This is accomplished by computing the difference between the number of passengers coming from local buses and the capacity provided by the express line as explained in Section3.1.4. The express bus capacity is 250 passengers. We are considering 20 m of distance between the boarding and alighting points. The intervals for analysis are also set according to peak times of 6:00 to 8:00 am, 12:00 to 2:00 pm, and 5:00 to 7:00 pm. The number of passengers in local lines is given by historical data provided by URBS. Passengers arriving at the terminal by walking are not considered in this analysis as they represent a small part of passengers passing through the terminal.Figure13 shows the link stream for buses between 6:00 and 8:00 am. It is possible to visualize all connections between buses minute by minute during this time interval.Figure 13
Link stream for buses between 6:00 and 8:00 am.Figure14 presents an illustrative detail (marked by an arrow in Figure 13) to show the information provided within time interval [46,50] min after 6:00 am. During this time interval, passengers are able to make transfers among six buses (123, 401, 501, 601, 703, and 809) as shown in Figure 14.Figure 14
Link stream detail for interval[46,50] min after 6:00 am.Table18 shows the number of passengers transferred from local to express lines between 6:00 and 8:00 am. It is obtained from the link stream and corresponding cliques of Figure 13 as presented in Section 3.1.4.Table 18
Passengers transferred from local to express buses between 6:00 and 8:00 am.
Express bus number Express bus capacity (pax) Connecting passengers Balance (pax) 101 250 151 99 110 250 134 116 108 250 122 128 115 250 365 -115 105 250 67 68 129 250 166 84 124 250 113 137 123 250 312 -62 127 250 118 70 117 250 42 208 103 250 163 45 104 250 60 190 120 250 193 57 126 250 50 200 111 250 133 117 107 250 75 175 121 250 64 186 130 250 0 250 109 250 38 212 125 250 197 53 112 250 71 179 113 250 39 211 116 250 168 82 102 250 3 247According to Table18, some passengers cannot board the express bus as it is full (negative numbers in bold). The most critical event occurs when bus 115 is ready for boarding 365 passengers. In this case, 115 passengers (in bold) must wait for the next express bus 105. When it arrives, 115 plus 67 passengers that newly arrived from local buses should be boarded. This also occurs for express bus 123 which cannot board all 312 passengers, and 62 passengers (negative number in bold) must wait for the next bus 127.Table19 shows connecting buses in detail for express buses 115 and 127. Note that not all passengers from local buses 502 and 805 are successful as the required transfer time is greater than the available time (in bold). Only 36 passengers are successful, and 26 passengers from bus 502 and 23 passengers from bus 805 cannot make the transfer, according to (1). A similar case occurs for transferring passengers from buses 502 to 127 (in bold) when 35 passengers cannot make the transfer.Table 19
Unavailable transfer time for express buses 115 and 127 between 6:00 and 8:00 am.
Express bus number Local bus number Arriving passengers Required transfer time (min) Available transfer time (min) 115 701 4 0.50 9 301 30 1.92 8 810 43 2.63 7 401 60 3.56 6 603 25 1.64 4 801 49 2.96 3 202 33 2.08 2 502 62 3.67 2 805 59 3.50 2  127 404 65 3.83 4 502 53 3.18 1Table20 shows the number of passengers transferred from local to express lines between 12:00 am and 2:00 pm. There are no capacity issues; i.e., no passengers must wait for the next express bus due to lack of available places. However, the required transfer time is an issue for connecting buses 807 with 112 and 808 with 116 according to Table 21.Table 20
Passengers transferred from local to express buses between 12:00 and 2:00 pm.
Express bus number Express bus capacity (pax) Connecting passengers Balance (pax) 114 250 50 200 131 250 83 167 110 250 58 192 108 250 60 190 115 250 91 159 105 250 99 151 129 250 97 153 124 250 106 144 123 250 66 184 117 250 102 148 103 250 55 195 126 250 47 203 111 250 122 128 107 250 25 225 121 250 52 198 109 250 43 207 112 250 72 178 113 250 6 244 116 250 102 148Table 21
Unavailable transfer time for express buses 112 and 116 between 12:00 and 2:00 pm.
Express bus number Local bus number Arriving passengers Required transfer time (min) Available transfer time (min) 112 603 17 1.21 6 404 17 1.21 2 807 38 2.36 1  116 301 15 1.10 3 501 12 0.93 2 201 22 1.48 1 808 53 3.18 1Table21 shows in detail that not all passengers of buses 807 and 808 are successful as the required transfer time is greater than the available time (in bold). In both cases, the available transfer time of 1 minute allows 16 passengers to be transferred. Therefore, 22 passengers from bus 807 and 37 from 808 must wait for the next express bus.Similarly to the previous peak period of Table20, there are no capacity issues for transferring passengers between local and express lines between 5:00 and 7:00 pm according to Table 22. However, the required transfer time is an issue for connecting buses 601 with 109 as shown in Table 23.Table 22
Passengers transferred from local to express buses between 5:00 and 7:00 pm.
Express bus number Express bus capacity (pax) Connecting passengers Balance (pax) 117 250 90 160 103 250 83 167 126 250 49 201 119 250 89 161 102 250 104 146 121 250 27 223 109 250 104 146 112 250 11 239 113 250 57 193 116 250 91 159 104 250 21 229 114 250 17 233 131 250 88 162 110 250 30 220 115 250 63 187 105 250 16 234 130 250 35 215 122 250 15 235 128 250 12 238 129 250 19 231Table 23
Unavailable transfer time for express bus 109 between 5:00 and 7:00 pm.
Express bus number Local bus number Arriving passengers Required transfer time (min) Available transfer time (min) 109 401 12 0.93 5 503 9 0.77 4 301 25 1.64 3 601 58 3.45 1Table23 shows in detail that not all passengers of bus 601 are successful (in bold). Thus, the available transfer time of 1 minute allows 16 passengers to be transferred, and 42 passengers cannot make the transfer to bus 109 according to (1) as 2.45 min longer would be necessary.


## 5. Conclusions

In this work, we proposed a methodology for modeling and analysis of bus transportation using link streams. Link streams are temporal graphs whose cliques provide information about sets of nodes linked at given times. This concept was used to model transfers between bus lines. Basically, the methodology is divided into three steps: (i) timetables of arrivals and departures of buses in a terminal (or hub) provide information about pairs of buses waiting for boarding or dropping off passengers in a given time interval; (ii) the corresponding link stream is then built; (iii) an efficient algorithm computes the maximal cliques of the link stream. Performance metrics as transfer time, bunching, congestion, and number of transferred passengers are proposed and obtained from cliques. Particularly, the results were obtained from real-world data of a bus terminal in the city of Curitiba, Brazil. This case study revealed transfer times around 1 to 4 min which seem to be suitable for most passengers. However, the available transfer time between local and express lines can be an issue at certain times as not all passengers are successful and must wait for the next express bus. This effect can be combined with excess of passengers from previous arrivals causing a cascade effect which delays passengers’ departures and it takes time to resume the normal operation of the terminal. Bunching events are also evaluated and should be carefully considered as they can be caused either by bad bus schedules or intentionally by extra buses which increase the transport capacity during certain periods of time. It is also clear from congestion metrics of the terminal that there is more traffic of buses and passengers in the morning than in the afternoon or evening. The relevant result is that these performance metrics were obtained from cliques of link streams generated from bus timetables. This methodology has good scalability properties and can also be applied to other modes of transport.



---

*Source: 6139379-2019-02-11.xml*