# Estimation Method of Path-Selecting Proportion for Urban Rail Transit Based on AFC Data

Authors: Feng Zhou; Jun-gang Shi; Rui-hua Xu
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

With the successful application of automatic fare collection (AFC) system in urban rail transit (URT), the information of passengers’ travel time is recorded, which provides the possibility to analyze passengers’ path-selecting by AFC data. In this paper, the distribution characteristics of the components of travel time were analyzed, and an estimation method of path-selecting proportion was proposed. This method made use of single path ODs’ travel time data from AFC system to estimate the distribution parameters of the components of travel time, mainly including entry walking time (ewt), exit walking time (exwt), and transfer walking time (twt). Then, for multipath ODs, the distribution of each path’s travel time could be calculated under the condition of its components’ distributions known. After that, each path’s path-selecting proportion can be estimated. Finally, simulation experiments were designed to verify the estimation method, and the results show that the error rate is less than 2%. Compared with the traditional models of flow assignment, the estimation method can reduce the cost of artificial survey significantly and provide a new way to calculate the path-selecting proportion for URT.


---

## Body

## 1. Introduction

As the basis of network flow assignment calculation, the path-selecting proportion is directly related to the operation and management of urban rail transit (URT), including operation indicators calculating, train plan making, and fare clearing. Currently, there have been many research results on flow assignment for URT under the condition of network operation, most of which are multipath models based on path utility.Nguyen et al. [1] developed a graph-theoretic framework for the passenger assignment problem, which encompassed simultaneously the departure time and the route choice dimensions. Also, a passenger equilibrium flow model was defined and a mathematical formulation was suggested. The research results can be used to solve the passenger flow distribution problem of URT network.Poon et al. [2] also studied the dynamic traffic assignment model for congested networks and used time-increment simulation to calculate the passenger flow on the network. The model assumed that the vehicle was running in full accordance with the schedule and the passengers had full predictive information about the present and future network conditions, so the model can be used to simulate the performance of an existing transit system operating with preannounced schedules or to evaluate the effects of changes in schedules, lines, or passenger demand on system performance.Xu et al. [3] established a multipath assignment model of URT network, using travel time as paths’ impedance. The basic characteristics of rail network and passenger travel behavior are fully considered in the model. With its high accuracy and strong practicality, the model has been successfully applied in Beijing Subway network. The survey results show that its error rate of section flow is less than 5%.Si et al. [4] constructed the generalized cost function of URT network, considering the major factors (including the travel time and times of transfer) influencing the passenger flow assignment, and then proposed a mathematical optimization model of passenger flow assignment based on the stochastic user equilibrium principle. The results of numerical example using Beijing URT network data showed that the model was feasible and effective.The basic idea of such models above can be summarized as follows:(1)
determine the impedance of each path, which can be time costs or mileage;(2)
design the utility function based on the path impedance;(3)
calculate the flow assignment proportion of each path;(4)
distribute each OD’s total passenger flow of one day to paths between the origin stations and the destination stations (OD).Such models can basically guarantee the accuracy of flow assignment. However, the parameters of these models, including the entry and exit walking time at stations and transfer time, are calibrated by manual survey, which is really a time-consuming and costly work. In addition, when the network structure or operation organization changes, the parameters need to be recalibrated in order to keep accurate. Therefore, it is necessary to study a new method of network flow assignment.In recent years, the AFC system is widely used in URT, which can accurately record the passengers’ entry time at the origin stations and the exit time at the destination stations. With many years of application, the AFC system has accumulated vast amounts of passengers’ travel information. However, such information has rarely been used to study the behavior of travelling and path-selecting.Chapleau et al. [5] and Rahbee [6] used the AFC data to predict OD matrices and network flow distribution, but only the entry records were used, which could not support the analysis of passengers’ path-selecting behavior.Lee and Hickman [7] analyzed large amount of AFC data and found that activity and travel patterns differ significantly across the different farecard types, such as travel period, travel time, travel region (urban areas to the suburbs, urban areas to urban areas, etc.). The research results can be used to grasp the characteristics of different travel cardholders.Kusakabe et al. [8] developed a methodology and an algorithm for estimating which train is boarded by each smart card holder based on long-term transaction data. The proposed method made a number of assumptions and distributed the uncertain smart card data to each possible train evenly, which needed further research.Zhou and Xu [9] considered the process of the passenger travelling with the train running together and set up a model of calculating each passenger’s path by AFC data. The proposed method could estimate each passenger’s travel route and train choice. But the model needed a lot of manual investigation work to be also further verified by mathematical statistics.Sun and Xu [10] analyzed the travel time reliability and estimated passenger route choice behavior by AFC data. The proposed model could be used to calibrate the parameters of traditional passenger flow distribution models. But the model needed all the stations’ walking time obtained by artificial survey and lacked further excavation of AFC data, such as ticket type and travel period.Based on the above background, this paper works on analyzing passengers’ travel time data recorded by AFC system with the theory of mathematical statistics and proposes a new estimation method of path-selecting proportion. This method provides a new idea of network flow assignment for URT.


## 2. Analysis of Travel Time

Travel time of passengers in URT network mainly consists of the following six parts:(1)
entry walking time (the time of passengers walking from the AFC gate to the platform in the origin station, denoted byewt);(2)
entry platform waiting time (the time of passengers waiting for the train on the platform in the origin station, denoted byepwt);(3)
on-train time (the time of passengers travelling on the train, denoted byott);(4)
transfer walking time (the time of passengers walking from the arrival platform to the departure platform in the transfer station, denoted bytwt);(5)
transfer platform waiting time (the time of passengers waiting for the train on the platform in transfer station, denoted bytpwt);(6)
exit walking time (the time of passengers walking from the platform to the AFC gate in the destination station, denoted byexwt).twt and tpwt only occur in the transfer station. The components of travel time are shown in Figure 1.Figure 1
Components of travel time.Lots of random factors can affect passengers’ travel time, so this paper makes the following assumptions:(1)
passengers arrive at the station randomly, dispersedly, and stably;(2)
all passengers can board the first train after arriving at the platform;(3)
the trains run according to the plan strictly with a certain speed level and no abnormal condition occurs.


### 2.1. Walking Time (ewt, twt, and exwt)

For one station, suppose the walk distances for different passengers are the same, and then the distribution of walking time only depends on the walking speed. For walking speed, most research results [11, 12] show that it can be considered to follow normal distribution. Thus, walking time follows a normal distribution as well; that is,(1)ewt~Nμewt,σewt2,twt~Nμtwt,σtwt2,exwt~Nμexwt,σexwt2,where μewt, μtwt, and μexwt are the mean of ewt,twt,exwt and σewt2, σtwt2, σexwt2 are the variance of ewt, twt, and exwt.


### 2.2. Entry Platform Waiting Time (epwt)

epwt is the random variables between 0 and the interval of the trains. Based on the assumption of passengers arriving at the origin station randomly and dispersedly, they arrive at the platform randomly and dispersedly too. Thus, epwt can be considered to follow a uniform distribution; that is,(2)epwt~U0,H,where H is the interval of the trains.The distribution can be verified by the following simulation experiment. The experimental environment is as follows: the interval of the trains at StationA is 180 s, between 8:00:00 and 10:00:00; ewt~N(145s,202).The experimental procedure is as follows.(
1
) Generate randomly and evenly 20,000 passengers between 8:00:00 and 9:50:00; for passenger i, let TEi be the arriving time of the station and let ewti be the entry walking time and then the time of arriving at the platform is TEi+ewti.(
2
) Search for the first train arriving at Station A after TEi+ewti. Let TDi be the departure time of the first train at Station A, and then epwti=TDi-(TEi+ewti).MATLAB is used to do the simulation experiment. Assumingepwt~U[0,180], use SPSS to do Kolmogorov-Smirnov test (KS test for short) of the waiting time data from simulation, and the significance level α is generally taken to be 0.05. Frequency statistics is shown in Figure 2. The result shows that the significance is 0.626 (>α). So, the assumption epwt~U[0,180] is tenable.Figure 2
KS test.


### 2.3. Transfer Platform Waiting Time (tpwt)

Same asepwt, tpwt is the random variables between 0 and the interval of the trains. However, their distributions are different, that is because passengers arrive randomly and dispersedly at the origin station but intensively at the transfer station.Generally speaking, when the interval of transfer line is big, the faster passengers walk and the longer passengers may wait; when the interval of transfer line is small, the faster passengers walk and the shorter passengers may wait. It can be seen that there is strong correlation betweentpwt and twt. Thus, this paper analyzes the distribution of (twt+tpwt), which is denoted by twt&tpwt hereinafter.The factors affecting distribution oftwt&tpwt are as follows: the interval of the before-transfer line (H1); the interval of the after-transfer line (H2); the coordination time between the before-transfer line L1 and the after-transfer line L2 (Δt), as shown in Figure 3; the distribution of twt.Figure 3
Factors affectingtpwt.Obviously,Δt is related to H1 and H2, and its value has certain periodicity. To facilitate the presentation, let Δt1 be the first coordination time, and it can be calculated by the following formula:(3)Δt1=Δtmin⁡,H1≤H2,Δtmax⁡,H1>H2,where Δtmin⁡ is the minimum coordination time and Δtmax⁡ is the maximum one.LetH1,H2 be the least common multiple of H1, H2. Then, the calculation formula of Δti is designed as follows:(4)Δti=Δt1+i-1H2-H1i=1,2,…,H1,H2H1.Suppose that the passengers arrive at the transfer station with the coordination timeΔti. Then, if the transfer walking time of one passenger is smaller than Δti, his/her twt&tpwt is Δti; otherwise, the passenger will wait for one or some more intervals of Line 2 and his/her twt&tpwt will be Δti+n·H2. As a result of twt~N(μtwt,σtwt2), the probability distribution of twt&tpwt can be obtained by formula (5) as follows:(5)Ptwt&tpwt=k=∫0Δti12πσtwte-x-μtwt2/2σtwt2dxk=Δti∫Δti+n-1·H2Δti+n·H212πσtwte-x-μtwt2/2σtwt2dxk=Δti+n·H2,n=1,2,….In the above formula,n can be infinite theoretically, but, in fact, the probability is almost 0 when n≥5.


### 2.4. On-Train Time (ott)

Based on the assumption, all the trains run according to the timetable strictly with a certain speed level. So, between two certain stations (Stationi, Station j) on the same line, the total running time of different trains is a constant, which is denoted by TT. Obviously, the on-train time of passengers traveling between Station i and Station j is equal to TT and is a constant as well.


### 2.5. Analysis of Independence

Whether the components of travel time are independent is very important to analyze distribution characteristics of the path’s travel time. According to the analysis in the previous section,ott is a constant, so ott is independent of other components. ott divides travel time into three independent parts: ewt and epwt, twt&tpwt, and exwt. Thus, only the independence of ewt and epwt needs to be analyzed. In fact, one passenger’s waiting time is not related to his/her walking speed. As the passengers arrive at the station randomly and dispersedly, they arrive at the platform randomly and dispersedly too, which makes their waiting time random variable. That is the reason why the passengers walking fast may wait longer at the origin station. Therefore, ewt and epwt can be considered independent.Based on the above analysis, all the components of travel time are independent.


## 2.1. Walking Time (ewt, twt, and exwt)

For one station, suppose the walk distances for different passengers are the same, and then the distribution of walking time only depends on the walking speed. For walking speed, most research results [11, 12] show that it can be considered to follow normal distribution. Thus, walking time follows a normal distribution as well; that is,(1)ewt~Nμewt,σewt2,twt~Nμtwt,σtwt2,exwt~Nμexwt,σexwt2,where μewt, μtwt, and μexwt are the mean of ewt,twt,exwt and σewt2, σtwt2, σexwt2 are the variance of ewt, twt, and exwt.


## 2.2. Entry Platform Waiting Time (epwt)

epwt is the random variables between 0 and the interval of the trains. Based on the assumption of passengers arriving at the origin station randomly and dispersedly, they arrive at the platform randomly and dispersedly too. Thus, epwt can be considered to follow a uniform distribution; that is,(2)epwt~U0,H,where H is the interval of the trains.The distribution can be verified by the following simulation experiment. The experimental environment is as follows: the interval of the trains at StationA is 180 s, between 8:00:00 and 10:00:00; ewt~N(145s,202).The experimental procedure is as follows.(
1
) Generate randomly and evenly 20,000 passengers between 8:00:00 and 9:50:00; for passenger i, let TEi be the arriving time of the station and let ewti be the entry walking time and then the time of arriving at the platform is TEi+ewti.(
2
) Search for the first train arriving at Station A after TEi+ewti. Let TDi be the departure time of the first train at Station A, and then epwti=TDi-(TEi+ewti).MATLAB is used to do the simulation experiment. Assumingepwt~U[0,180], use SPSS to do Kolmogorov-Smirnov test (KS test for short) of the waiting time data from simulation, and the significance level α is generally taken to be 0.05. Frequency statistics is shown in Figure 2. The result shows that the significance is 0.626 (>α). So, the assumption epwt~U[0,180] is tenable.Figure 2
KS test.


## 2.3. Transfer Platform Waiting Time (tpwt)

Same asepwt, tpwt is the random variables between 0 and the interval of the trains. However, their distributions are different, that is because passengers arrive randomly and dispersedly at the origin station but intensively at the transfer station.Generally speaking, when the interval of transfer line is big, the faster passengers walk and the longer passengers may wait; when the interval of transfer line is small, the faster passengers walk and the shorter passengers may wait. It can be seen that there is strong correlation betweentpwt and twt. Thus, this paper analyzes the distribution of (twt+tpwt), which is denoted by twt&tpwt hereinafter.The factors affecting distribution oftwt&tpwt are as follows: the interval of the before-transfer line (H1); the interval of the after-transfer line (H2); the coordination time between the before-transfer line L1 and the after-transfer line L2 (Δt), as shown in Figure 3; the distribution of twt.Figure 3
Factors affectingtpwt.Obviously,Δt is related to H1 and H2, and its value has certain periodicity. To facilitate the presentation, let Δt1 be the first coordination time, and it can be calculated by the following formula:(3)Δt1=Δtmin⁡,H1≤H2,Δtmax⁡,H1>H2,where Δtmin⁡ is the minimum coordination time and Δtmax⁡ is the maximum one.LetH1,H2 be the least common multiple of H1, H2. Then, the calculation formula of Δti is designed as follows:(4)Δti=Δt1+i-1H2-H1i=1,2,…,H1,H2H1.Suppose that the passengers arrive at the transfer station with the coordination timeΔti. Then, if the transfer walking time of one passenger is smaller than Δti, his/her twt&tpwt is Δti; otherwise, the passenger will wait for one or some more intervals of Line 2 and his/her twt&tpwt will be Δti+n·H2. As a result of twt~N(μtwt,σtwt2), the probability distribution of twt&tpwt can be obtained by formula (5) as follows:(5)Ptwt&tpwt=k=∫0Δti12πσtwte-x-μtwt2/2σtwt2dxk=Δti∫Δti+n-1·H2Δti+n·H212πσtwte-x-μtwt2/2σtwt2dxk=Δti+n·H2,n=1,2,….In the above formula,n can be infinite theoretically, but, in fact, the probability is almost 0 when n≥5.


## 2.4. On-Train Time (ott)

Based on the assumption, all the trains run according to the timetable strictly with a certain speed level. So, between two certain stations (Stationi, Station j) on the same line, the total running time of different trains is a constant, which is denoted by TT. Obviously, the on-train time of passengers traveling between Station i and Station j is equal to TT and is a constant as well.


## 2.5. Analysis of Independence

Whether the components of travel time are independent is very important to analyze distribution characteristics of the path’s travel time. According to the analysis in the previous section,ott is a constant, so ott is independent of other components. ott divides travel time into three independent parts: ewt and epwt, twt&tpwt, and exwt. Thus, only the independence of ewt and epwt needs to be analyzed. In fact, one passenger’s waiting time is not related to his/her walking speed. As the passengers arrive at the station randomly and dispersedly, they arrive at the platform randomly and dispersedly too, which makes their waiting time random variable. That is the reason why the passengers walking fast may wait longer at the origin station. Therefore, ewt and epwt can be considered independent.Based on the above analysis, all the components of travel time are independent.


## 3. Model and Algorithm

### 3.1. AFC Data

In China, smart cards and AFC system are applied in most cities, which can record part of the passengers’ traveling information on the URT network. The basic structure of AFC data is shown in Table1.Table 1
Structure of AFC data.
Records
O station code
Entry time
D station code
Exit time
Ticket type
Record 1
000102
8:05:12
000425
8:45:43
Single card
⋯
⋯
⋯
⋯
⋯
⋯Thus, based on the AFC data structure, any passenger’s travel time can be calculated.


### 3.2. Distribution Parameter Estimation for Components of Travel Time

According to the analysis in Section2, the distribution characteristics and parameters of the components of travel time are shown in Table 2.Table 2
Distribution characteristics and parameters of the components of travel time.
Components of travel time
Probability density function
Parameters to be estimated
Mean
Variance
ewt
ewt
~
N
(
μ
ewt
,
σ
ewt
2
)
μ
ewt
,
σ
ewt
2
μ
ewt
σ
ewt
2
epwt
epwt
~
U
[
0
,
H
]
—
H
/
2
H
2
/
12
ott
—
—
TT
0
twt&tpwt
As formula (5)
μ
twt
,
σ
twt
2
μ
twt
&
tpwt
σ
twt
&
tpwt
2
exwt
exwt
~
N
(
μ
exwt
,
σ
exwt
2
)
μ
exwt
,
σ
exwt
2
μ
exwt
σ
exwt
2From Table2, it can be seen that the parameters to be estimated are the mean and variance of ewt of each station (μewt,σewt2); the mean and variance of twt in each transfer direction of each transfer station (μtwt,σtwt2); the mean and variance of exwt of each station (μexwt,σexwt2).


#### 3.2.1. Estimation Method ofμewt, σewt2 and μexwt, σexwt2

Take the OD with single path and no transfer (the origin station and the destination station are on the same line) as the research object, and the travel time is only comprised ofewt, epwt, ott, and exwt. Let m be the origin station and let n be the destination station. Then, large samples of passengers’ travel time data (Tmn=T1mn,T2mn,…,Timn,…,TSmn) can be obtained by AFC system, where Timn is the actual travel time of passengers i and S is the sample size.Based onTmn, the mean and variance of the path’s travel time (Etmn,Dtmn) can be estimated by moment estimation. Moment estimation is a commonly used method of parameter estimation, proposed by K. Pearson in 1894 [13]. According to Wiener-Khinchin law of large numbers, the sample moment converge to the population moment when the sample size is large. The principle of moment estimation is as follows: (1) estimate the corresponding population moment by the sample moment and (2) estimate the parameters by making use of the relationship between the unknown parameters and the population moment.Because the components of travel time are independent, the following equations are established:(6)Etmn=Eewtm+Eepwtm+Eottm+Eexwtn=μewtm+Hm2+TTmn+μexwtn,Dtmn=Dewtm+Depwtm+Dottm+Dexwtn=σewtm2+Hm212+σexwtn2,where μewtm is the mean of ewt of station m; σewtm2 is the variance of ewt of station m; Hm is the interval of station m; TTmn is the train running time between station m and station n; μexwtn is the mean of exwt of station n; σexwtm2 is the variance of exwt of station n; Hm and TTmn can be obtained from the timetable directly.Equation (6) are suitable for any two different stations on the same line and can be converted to the following:(7)μewtm+μexwtn=Etmn-Hm2-TTmnhhhhhhhhhhhh∀m,n∈USL,m≠n,σewtm2+σexwtn2=Dtmn-Hm212hhhhhhhhhhhhh∀m,n∈USL,m≠n,where USL is the station set of line L.Therefore, for any station on the lineL, if its distribution parameters (mean and variance) of ewt or exwt are known (by survey), the distribution parameters of all the stations on line L can be calculated by (7). According to the theory of moment estimation, the larger the sample size is, the more accurate the parameters are estimated. Thus, in order to improve the accuracy of parameter estimation, the sequence of stations on line L for parameters estimation (called PES problem hereinafter) can be made according to the passenger flow.To describe and solve PES problem, defineUPLS as the set of distribution parameters of all stations on line L, and then(8)UPLS=UewtLSta1,UexwtLSta1,…,UewtLStai,UexwtLStai,…,UewtLStak,UexwtLStak,where UewtLStai is the set of ewt’s distribution parameters of station i on line L and UewtLStai={μewtLStai,σewtLStai2}; UexwtLStai is the set of exwt’s distribution parameters of station i on line L and UexwtLStai={μexwtLStai,σexwtLStai2}.Take the five stations of lineL of the network in Figure 4(a); for example, the relationship between the sets of each station’s distribution parameters can be established as the undirected graph in Figure 4(b). In the figure, two sets are connected by an edge if there is only one path between the two stations; otherwise, two sets are unconnected. qij is the passenger flow between station i and station j.Figure 4
Relationship graph of parameter sets.
(a)
Part of URT network
(b)
Undirected graph of parameter sets of lineLIn order to estimate the parameters accurately, the sample size should be as large as possible. Therefore, the PES problem can be summarized to seek the maximum spanning tree in Figure4(b), and the model is described as follows:(9)max⁡⁡qt=max⁡⁡∑u,v∈tqu,v,where t is the spanning tree of the undirected graph and qu,v is the weight value of the edge between vertex u and v.The most common algorithm used to calculate the optimal spanning tree is Kruskal algorithm [14]. Let V be the set of all vertices, let E be the set of all edges, let s be the number of all edges, let T=V,TE be the spanning tree, let TE be the set of edges of the spanning tree, and let x be the number of edges of the spanning tree. Then, the steps of Kruskal algorithm for solving the maximum spanning tree are as follows.Step 1.
SetTE=Φ, x=0.Step 2.
Choose the edgee* with the maximum value in the graph, e*={max⁡⁡qu,v∣u,v∈V}.Step 3.
If there is any loop in the graphT=(V,TE∪e*), then E=E∖e* and then back to Step 2; otherwise, TE=TE∪e*, E=E∖e*, x=x+1.Step 4.
Ifx=s-1, the algorithm ends; otherwise, repeat Step 2.For example, suppose the passenger flows of ODs in Figure4(b) are shown as in Figure 5(a) and the maximum spanning tree calculated by Kruskal algorithm is shown in Figure 5(b).Figure 5
Results of maximum spanning tree.
(a)
Weighted graph of parameter sets of lineL
(b)
Maximum spanning treeAccording to the maximum spanning tree, the nodeUewtLSta2 converges the maximum number of edges, of which the parameters are designed, to be estimated by artificial survey. Then, the parameters of other nodes will be obtained in succession by formula (7). Therefore, the estimation sequence of parameters can be made as shown in Figure 6.Figure 6
Sequence of parameters estimation.Based on the above analysis, the estimation method ofμewt, σewt2, and μexwt, σexwt2 of each station on one line is summarized as follows.Step 1.
Build the relationship graph of parameter sets, of which the value of each edge is the passenger flow between its two vertices collected by AFC system.Step 2.
Use Kruskal algorithm to calculate the maximum spanning tree of the relationship graph.Step 3.
Find the node with the maximum number of edges and use the artificial survey to collect its samples of walking time (ewt or exwt); then, its parameters of (μewt, σewt2) or (μexwt, σexwt2) can be estimated by moment estimation.Step 4.
According to the maximum spanning tree, estimate the parameters (μewt, σewt2, μexwt, and σexwt2) of other stations in succession by formula (7).


#### 3.2.2. Estimation Method ofμtwt, σtwt2

In URT system, transfer path means the path from the platform of one line to the platform of another line at the transfer station. Therefore, for a two-line transfer station, there are four transfer paths in total. Based on the analysis of most URT networks in China, for any transfer path of one transfer station, certain OD with single path and one transfer can be always found to contain the transfer path, of which the travel time only includesewt, epwt, twt&tpwt, ott, and exwt.Suppose that a certain OD (mn) with single path and one transfer contains transfer path i, as the components of travel time are independent. Formulas (10) and (11) are established as follows:(10)Etmn=μewtm+Hm2+TTmi+μtwt&tpwti+TTin+μexwtn,(11)Dtmn=σewtm2+Hm212+σtwt&tpwti2+σexwtn2,where m, n are the origin station and the destination station; Etmn, Dtmn are the mean and the variance of mn’s travel time; μtwt&tpwti, (σtwt&tpwti)2 are the mean and the variance of twt&tpwt of transfer path i; TTmi is the train running time from station m to the transfer station; TTin is the train running time from the transfer station to station n.E
t
m
n, Dtmn can be estimated by moment estimation of AFC data; Hm, TTmi, and TTin can be obtained from the timetable; μewt, σewt2, μexwt, and σexwt2 can be estimated from Section 3.2.1. Therefore, only μtwt&tpwti, σtwt&tpwti2 are unknown in formulas (9) and (10), which can be calculated easily.Under the conditions ofμtwt&tpwti, σtwt&tpwti2 known, μtwt, σtwt2 can be calculated by formulas (5).


### 3.3. Estimation Method of Path-Selecting Proportion

Letmn be a multipath OD and let tmn be the variable of travel time. Then, the probability density function of mn’s travel time ftmn can be described as follows:(12)ftmn=∑i=1kwifitmn,∑i=1kwi=1,∀m,n∈UsN,where wi is the path-selecting proportion of the ith path between station m and station n; fitmn is the probability density function of the ith path’s travel time; k is the number of paths between station m and station n; UsN is the set of stations on the URT network.Based on (12) and (13), the following can be deduced as well: (13)Etmn=μmn=∑i=1kwiμmni,Dtmn=σmn2=∑i=1kwiσmni2+μmni22-∑i=1kwiμmni2,where μmn is the mean of mn’s travel time; (σmn)2 is the variance of mn’s travel time; μmni is the mean of the ith path’s travel time; (σmni)2 is the variance of the ith path’s travel time.μ
m
n and (σmn)2 can be estimated from the AFC data; while μmni and (σmni)2 can be estimated by the following equations, in which each parameter can be obtained by the methods described in Section 3.2:(14)μmni=μewtm+Hm2+∑tr⁡∈Uμtr⁡twt&tpwt+μexwtn+TTmn,(σmni)2=σewtm2+Hm212+∑tr⁡∈Uσtr⁡twt&tpwt2+σexwtn2,where μtr⁡twt&tpwt is the mean of transfer station tr⁡’s twt&tpwt; σtr⁡twt&tpwt2 is the variance of transfer station tr⁡’s twt&tpwt; U is the set of transfer stations in the ith path.Combining (13)~(14), each path’s path-selecting proportion can be calculated. It is worth noting that only k-order (k≤2) central moment statistics (mean and variance) are used in the derivation above. So, the estimation method can only apply to the ODs with no more than three paths. When there are more than three paths, the idea in this paper is applicable as well, but k-order (k>2) central moment statistics should be introduced.


## 3.1. AFC Data

In China, smart cards and AFC system are applied in most cities, which can record part of the passengers’ traveling information on the URT network. The basic structure of AFC data is shown in Table1.Table 1
Structure of AFC data.
Records
O station code
Entry time
D station code
Exit time
Ticket type
Record 1
000102
8:05:12
000425
8:45:43
Single card
⋯
⋯
⋯
⋯
⋯
⋯Thus, based on the AFC data structure, any passenger’s travel time can be calculated.


## 3.2. Distribution Parameter Estimation for Components of Travel Time

According to the analysis in Section2, the distribution characteristics and parameters of the components of travel time are shown in Table 2.Table 2
Distribution characteristics and parameters of the components of travel time.
Components of travel time
Probability density function
Parameters to be estimated
Mean
Variance
ewt
ewt
~
N
(
μ
ewt
,
σ
ewt
2
)
μ
ewt
,
σ
ewt
2
μ
ewt
σ
ewt
2
epwt
epwt
~
U
[
0
,
H
]
—
H
/
2
H
2
/
12
ott
—
—
TT
0
twt&tpwt
As formula (5)
μ
twt
,
σ
twt
2
μ
twt
&
tpwt
σ
twt
&
tpwt
2
exwt
exwt
~
N
(
μ
exwt
,
σ
exwt
2
)
μ
exwt
,
σ
exwt
2
μ
exwt
σ
exwt
2From Table2, it can be seen that the parameters to be estimated are the mean and variance of ewt of each station (μewt,σewt2); the mean and variance of twt in each transfer direction of each transfer station (μtwt,σtwt2); the mean and variance of exwt of each station (μexwt,σexwt2).


### 3.2.1. Estimation Method ofμewt, σewt2 and μexwt, σexwt2

Take the OD with single path and no transfer (the origin station and the destination station are on the same line) as the research object, and the travel time is only comprised ofewt, epwt, ott, and exwt. Let m be the origin station and let n be the destination station. Then, large samples of passengers’ travel time data (Tmn=T1mn,T2mn,…,Timn,…,TSmn) can be obtained by AFC system, where Timn is the actual travel time of passengers i and S is the sample size.Based onTmn, the mean and variance of the path’s travel time (Etmn,Dtmn) can be estimated by moment estimation. Moment estimation is a commonly used method of parameter estimation, proposed by K. Pearson in 1894 [13]. According to Wiener-Khinchin law of large numbers, the sample moment converge to the population moment when the sample size is large. The principle of moment estimation is as follows: (1) estimate the corresponding population moment by the sample moment and (2) estimate the parameters by making use of the relationship between the unknown parameters and the population moment.Because the components of travel time are independent, the following equations are established:(6)Etmn=Eewtm+Eepwtm+Eottm+Eexwtn=μewtm+Hm2+TTmn+μexwtn,Dtmn=Dewtm+Depwtm+Dottm+Dexwtn=σewtm2+Hm212+σexwtn2,where μewtm is the mean of ewt of station m; σewtm2 is the variance of ewt of station m; Hm is the interval of station m; TTmn is the train running time between station m and station n; μexwtn is the mean of exwt of station n; σexwtm2 is the variance of exwt of station n; Hm and TTmn can be obtained from the timetable directly.Equation (6) are suitable for any two different stations on the same line and can be converted to the following:(7)μewtm+μexwtn=Etmn-Hm2-TTmnhhhhhhhhhhhh∀m,n∈USL,m≠n,σewtm2+σexwtn2=Dtmn-Hm212hhhhhhhhhhhhh∀m,n∈USL,m≠n,where USL is the station set of line L.Therefore, for any station on the lineL, if its distribution parameters (mean and variance) of ewt or exwt are known (by survey), the distribution parameters of all the stations on line L can be calculated by (7). According to the theory of moment estimation, the larger the sample size is, the more accurate the parameters are estimated. Thus, in order to improve the accuracy of parameter estimation, the sequence of stations on line L for parameters estimation (called PES problem hereinafter) can be made according to the passenger flow.To describe and solve PES problem, defineUPLS as the set of distribution parameters of all stations on line L, and then(8)UPLS=UewtLSta1,UexwtLSta1,…,UewtLStai,UexwtLStai,…,UewtLStak,UexwtLStak,where UewtLStai is the set of ewt’s distribution parameters of station i on line L and UewtLStai={μewtLStai,σewtLStai2}; UexwtLStai is the set of exwt’s distribution parameters of station i on line L and UexwtLStai={μexwtLStai,σexwtLStai2}.Take the five stations of lineL of the network in Figure 4(a); for example, the relationship between the sets of each station’s distribution parameters can be established as the undirected graph in Figure 4(b). In the figure, two sets are connected by an edge if there is only one path between the two stations; otherwise, two sets are unconnected. qij is the passenger flow between station i and station j.Figure 4
Relationship graph of parameter sets.
(a)
Part of URT network
(b)
Undirected graph of parameter sets of lineLIn order to estimate the parameters accurately, the sample size should be as large as possible. Therefore, the PES problem can be summarized to seek the maximum spanning tree in Figure4(b), and the model is described as follows:(9)max⁡⁡qt=max⁡⁡∑u,v∈tqu,v,where t is the spanning tree of the undirected graph and qu,v is the weight value of the edge between vertex u and v.The most common algorithm used to calculate the optimal spanning tree is Kruskal algorithm [14]. Let V be the set of all vertices, let E be the set of all edges, let s be the number of all edges, let T=V,TE be the spanning tree, let TE be the set of edges of the spanning tree, and let x be the number of edges of the spanning tree. Then, the steps of Kruskal algorithm for solving the maximum spanning tree are as follows.Step 1.
SetTE=Φ, x=0.Step 2.
Choose the edgee* with the maximum value in the graph, e*={max⁡⁡qu,v∣u,v∈V}.Step 3.
If there is any loop in the graphT=(V,TE∪e*), then E=E∖e* and then back to Step 2; otherwise, TE=TE∪e*, E=E∖e*, x=x+1.Step 4.
Ifx=s-1, the algorithm ends; otherwise, repeat Step 2.For example, suppose the passenger flows of ODs in Figure4(b) are shown as in Figure 5(a) and the maximum spanning tree calculated by Kruskal algorithm is shown in Figure 5(b).Figure 5
Results of maximum spanning tree.
(a)
Weighted graph of parameter sets of lineL
(b)
Maximum spanning treeAccording to the maximum spanning tree, the nodeUewtLSta2 converges the maximum number of edges, of which the parameters are designed, to be estimated by artificial survey. Then, the parameters of other nodes will be obtained in succession by formula (7). Therefore, the estimation sequence of parameters can be made as shown in Figure 6.Figure 6
Sequence of parameters estimation.Based on the above analysis, the estimation method ofμewt, σewt2, and μexwt, σexwt2 of each station on one line is summarized as follows.Step 1.
Build the relationship graph of parameter sets, of which the value of each edge is the passenger flow between its two vertices collected by AFC system.Step 2.
Use Kruskal algorithm to calculate the maximum spanning tree of the relationship graph.Step 3.
Find the node with the maximum number of edges and use the artificial survey to collect its samples of walking time (ewt or exwt); then, its parameters of (μewt, σewt2) or (μexwt, σexwt2) can be estimated by moment estimation.Step 4.
According to the maximum spanning tree, estimate the parameters (μewt, σewt2, μexwt, and σexwt2) of other stations in succession by formula (7).


### 3.2.2. Estimation Method ofμtwt, σtwt2

In URT system, transfer path means the path from the platform of one line to the platform of another line at the transfer station. Therefore, for a two-line transfer station, there are four transfer paths in total. Based on the analysis of most URT networks in China, for any transfer path of one transfer station, certain OD with single path and one transfer can be always found to contain the transfer path, of which the travel time only includesewt, epwt, twt&tpwt, ott, and exwt.Suppose that a certain OD (mn) with single path and one transfer contains transfer path i, as the components of travel time are independent. Formulas (10) and (11) are established as follows:(10)Etmn=μewtm+Hm2+TTmi+μtwt&tpwti+TTin+μexwtn,(11)Dtmn=σewtm2+Hm212+σtwt&tpwti2+σexwtn2,where m, n are the origin station and the destination station; Etmn, Dtmn are the mean and the variance of mn’s travel time; μtwt&tpwti, (σtwt&tpwti)2 are the mean and the variance of twt&tpwt of transfer path i; TTmi is the train running time from station m to the transfer station; TTin is the train running time from the transfer station to station n.E
t
m
n, Dtmn can be estimated by moment estimation of AFC data; Hm, TTmi, and TTin can be obtained from the timetable; μewt, σewt2, μexwt, and σexwt2 can be estimated from Section 3.2.1. Therefore, only μtwt&tpwti, σtwt&tpwti2 are unknown in formulas (9) and (10), which can be calculated easily.Under the conditions ofμtwt&tpwti, σtwt&tpwti2 known, μtwt, σtwt2 can be calculated by formulas (5).


## 3.2.1. Estimation Method ofμewt, σewt2 and μexwt, σexwt2

Take the OD with single path and no transfer (the origin station and the destination station are on the same line) as the research object, and the travel time is only comprised ofewt, epwt, ott, and exwt. Let m be the origin station and let n be the destination station. Then, large samples of passengers’ travel time data (Tmn=T1mn,T2mn,…,Timn,…,TSmn) can be obtained by AFC system, where Timn is the actual travel time of passengers i and S is the sample size.Based onTmn, the mean and variance of the path’s travel time (Etmn,Dtmn) can be estimated by moment estimation. Moment estimation is a commonly used method of parameter estimation, proposed by K. Pearson in 1894 [13]. According to Wiener-Khinchin law of large numbers, the sample moment converge to the population moment when the sample size is large. The principle of moment estimation is as follows: (1) estimate the corresponding population moment by the sample moment and (2) estimate the parameters by making use of the relationship between the unknown parameters and the population moment.Because the components of travel time are independent, the following equations are established:(6)Etmn=Eewtm+Eepwtm+Eottm+Eexwtn=μewtm+Hm2+TTmn+μexwtn,Dtmn=Dewtm+Depwtm+Dottm+Dexwtn=σewtm2+Hm212+σexwtn2,where μewtm is the mean of ewt of station m; σewtm2 is the variance of ewt of station m; Hm is the interval of station m; TTmn is the train running time between station m and station n; μexwtn is the mean of exwt of station n; σexwtm2 is the variance of exwt of station n; Hm and TTmn can be obtained from the timetable directly.Equation (6) are suitable for any two different stations on the same line and can be converted to the following:(7)μewtm+μexwtn=Etmn-Hm2-TTmnhhhhhhhhhhhh∀m,n∈USL,m≠n,σewtm2+σexwtn2=Dtmn-Hm212hhhhhhhhhhhhh∀m,n∈USL,m≠n,where USL is the station set of line L.Therefore, for any station on the lineL, if its distribution parameters (mean and variance) of ewt or exwt are known (by survey), the distribution parameters of all the stations on line L can be calculated by (7). According to the theory of moment estimation, the larger the sample size is, the more accurate the parameters are estimated. Thus, in order to improve the accuracy of parameter estimation, the sequence of stations on line L for parameters estimation (called PES problem hereinafter) can be made according to the passenger flow.To describe and solve PES problem, defineUPLS as the set of distribution parameters of all stations on line L, and then(8)UPLS=UewtLSta1,UexwtLSta1,…,UewtLStai,UexwtLStai,…,UewtLStak,UexwtLStak,where UewtLStai is the set of ewt’s distribution parameters of station i on line L and UewtLStai={μewtLStai,σewtLStai2}; UexwtLStai is the set of exwt’s distribution parameters of station i on line L and UexwtLStai={μexwtLStai,σexwtLStai2}.Take the five stations of lineL of the network in Figure 4(a); for example, the relationship between the sets of each station’s distribution parameters can be established as the undirected graph in Figure 4(b). In the figure, two sets are connected by an edge if there is only one path between the two stations; otherwise, two sets are unconnected. qij is the passenger flow between station i and station j.Figure 4
Relationship graph of parameter sets.
(a)
Part of URT network
(b)
Undirected graph of parameter sets of lineLIn order to estimate the parameters accurately, the sample size should be as large as possible. Therefore, the PES problem can be summarized to seek the maximum spanning tree in Figure4(b), and the model is described as follows:(9)max⁡⁡qt=max⁡⁡∑u,v∈tqu,v,where t is the spanning tree of the undirected graph and qu,v is the weight value of the edge between vertex u and v.The most common algorithm used to calculate the optimal spanning tree is Kruskal algorithm [14]. Let V be the set of all vertices, let E be the set of all edges, let s be the number of all edges, let T=V,TE be the spanning tree, let TE be the set of edges of the spanning tree, and let x be the number of edges of the spanning tree. Then, the steps of Kruskal algorithm for solving the maximum spanning tree are as follows.Step 1.
SetTE=Φ, x=0.Step 2.
Choose the edgee* with the maximum value in the graph, e*={max⁡⁡qu,v∣u,v∈V}.Step 3.
If there is any loop in the graphT=(V,TE∪e*), then E=E∖e* and then back to Step 2; otherwise, TE=TE∪e*, E=E∖e*, x=x+1.Step 4.
Ifx=s-1, the algorithm ends; otherwise, repeat Step 2.For example, suppose the passenger flows of ODs in Figure4(b) are shown as in Figure 5(a) and the maximum spanning tree calculated by Kruskal algorithm is shown in Figure 5(b).Figure 5
Results of maximum spanning tree.
(a)
Weighted graph of parameter sets of lineL
(b)
Maximum spanning treeAccording to the maximum spanning tree, the nodeUewtLSta2 converges the maximum number of edges, of which the parameters are designed, to be estimated by artificial survey. Then, the parameters of other nodes will be obtained in succession by formula (7). Therefore, the estimation sequence of parameters can be made as shown in Figure 6.Figure 6
Sequence of parameters estimation.Based on the above analysis, the estimation method ofμewt, σewt2, and μexwt, σexwt2 of each station on one line is summarized as follows.Step 1.
Build the relationship graph of parameter sets, of which the value of each edge is the passenger flow between its two vertices collected by AFC system.Step 2.
Use Kruskal algorithm to calculate the maximum spanning tree of the relationship graph.Step 3.
Find the node with the maximum number of edges and use the artificial survey to collect its samples of walking time (ewt or exwt); then, its parameters of (μewt, σewt2) or (μexwt, σexwt2) can be estimated by moment estimation.Step 4.
According to the maximum spanning tree, estimate the parameters (μewt, σewt2, μexwt, and σexwt2) of other stations in succession by formula (7).


## 3.2.2. Estimation Method ofμtwt, σtwt2

In URT system, transfer path means the path from the platform of one line to the platform of another line at the transfer station. Therefore, for a two-line transfer station, there are four transfer paths in total. Based on the analysis of most URT networks in China, for any transfer path of one transfer station, certain OD with single path and one transfer can be always found to contain the transfer path, of which the travel time only includesewt, epwt, twt&tpwt, ott, and exwt.Suppose that a certain OD (mn) with single path and one transfer contains transfer path i, as the components of travel time are independent. Formulas (10) and (11) are established as follows:(10)Etmn=μewtm+Hm2+TTmi+μtwt&tpwti+TTin+μexwtn,(11)Dtmn=σewtm2+Hm212+σtwt&tpwti2+σexwtn2,where m, n are the origin station and the destination station; Etmn, Dtmn are the mean and the variance of mn’s travel time; μtwt&tpwti, (σtwt&tpwti)2 are the mean and the variance of twt&tpwt of transfer path i; TTmi is the train running time from station m to the transfer station; TTin is the train running time from the transfer station to station n.E
t
m
n, Dtmn can be estimated by moment estimation of AFC data; Hm, TTmi, and TTin can be obtained from the timetable; μewt, σewt2, μexwt, and σexwt2 can be estimated from Section 3.2.1. Therefore, only μtwt&tpwti, σtwt&tpwti2 are unknown in formulas (9) and (10), which can be calculated easily.Under the conditions ofμtwt&tpwti, σtwt&tpwti2 known, μtwt, σtwt2 can be calculated by formulas (5).


## 3.3. Estimation Method of Path-Selecting Proportion

Letmn be a multipath OD and let tmn be the variable of travel time. Then, the probability density function of mn’s travel time ftmn can be described as follows:(12)ftmn=∑i=1kwifitmn,∑i=1kwi=1,∀m,n∈UsN,where wi is the path-selecting proportion of the ith path between station m and station n; fitmn is the probability density function of the ith path’s travel time; k is the number of paths between station m and station n; UsN is the set of stations on the URT network.Based on (12) and (13), the following can be deduced as well: (13)Etmn=μmn=∑i=1kwiμmni,Dtmn=σmn2=∑i=1kwiσmni2+μmni22-∑i=1kwiμmni2,where μmn is the mean of mn’s travel time; (σmn)2 is the variance of mn’s travel time; μmni is the mean of the ith path’s travel time; (σmni)2 is the variance of the ith path’s travel time.μ
m
n and (σmn)2 can be estimated from the AFC data; while μmni and (σmni)2 can be estimated by the following equations, in which each parameter can be obtained by the methods described in Section 3.2:(14)μmni=μewtm+Hm2+∑tr⁡∈Uμtr⁡twt&tpwt+μexwtn+TTmn,(σmni)2=σewtm2+Hm212+∑tr⁡∈Uσtr⁡twt&tpwt2+σexwtn2,where μtr⁡twt&tpwt is the mean of transfer station tr⁡’s twt&tpwt; σtr⁡twt&tpwt2 is the variance of transfer station tr⁡’s twt&tpwt; U is the set of transfer stations in the ith path.Combining (13)~(14), each path’s path-selecting proportion can be calculated. It is worth noting that only k-order (k≤2) central moment statistics (mean and variance) are used in the derivation above. So, the estimation method can only apply to the ODs with no more than three paths. When there are more than three paths, the idea in this paper is applicable as well, but k-order (k>2) central moment statistics should be introduced.


## 4. Numerical Example

The OD “NSta1→MSta5” in Figure 4(a) is used as an example to verify the model and algorithm. Obviously, there are two paths between the OD, as shown in Figure 7 and Table 3.Table 3
Detailed information of paths: “NSta1→MSta5.”
Paths
Stations
Transfer stations
Path 1
NSta1, LSta1, NSta3, MSta3, LSta3, MSta5
NSta3
Path 2
NSta1, LSta1, LSta2, LSta3, MSta5
LSta1, LSta3Figure 7
Part of URT network.Based on the method proposed in this paper, the process for estimating the proportion of two paths is as follows.Step 1 (estimate the distribution parameters of each station’s walking timeμewt, σewt2 and μexwt, σexwt2).
Build the relationship graph of parameter sets and use Kruskal algorithm to calculate the maximum spanning tree of the graph. Based on the maximum spanning tree, the parameter estimation sequence of stations is obtained.
Take lineL and its five stations; for example, as shown in Figure 6, UewtLSta2 of LSta2 should be estimated by artificial survey, and then other parameters can be estimated by formula (7).
To verify the parameter estimation method, a simulation of stationLSta2 and LSta4 is designed as follows: generate randomly 10,000 passengers from LSta2 to LSta4 with the entry time between 8:00:00 and 9:50:00; ewt~N(145s,202); the interval of line L is 150 s; train running time is 320 s; exwt~N(165s,202).
MATLAB is used to do the simulation experiment. The entry walking time data are collected to be theewt data of artificial survey, and the entry and exit time data of simulation are collected to be AFC data. The parameters of LSta2 are estimated by moment estimation method, while the ones of LSta4 are calculated by formula (7). The results are shown in Table 4.
From Table4, we can see that the error rate of parameter estimation is less than 0.2%, and the estimation method is verified.Table 4
Results of parameter estimation.
Parameters
L
Sta2
L
Sta4
Actual value
Estimation value
Error rate
Actual value
Estimation value
Error rate
Mean
145
144.91
−0.06%
165
165.21
0.13%
Standard deviation
20
19.93
−0.35%
20
19.81
−0.95%Step 2 (estimateμtwt, σtwt2 of each transfer path of all transfer stations concerned).
With the walking time parameters of all the stations on the URT network known, calculateμtwt&tpwt, σtwt&tpwt2 of each transfer path of transfer stations using the travel time data of AFC system by (10), (11). Then, μtwt, σtwt2 can be estimated by (5). The parameter estimation method in this step can also be verified by similar simulation experiments in Step1.Step 3 (estimate each path’s path-selecting proportion).
Suppose the values of parameters estimated in Step 1 and Step 2 are partly shown in Table5.
Design the simulation experiment as follows: generate randomly 10,000 passengers fromNSta1 to MSta5 with the entry time between 8:00:00 and 9:50:00; the interval of each line is 180 s; the train running time of Path 1 is 21 min, while 18 min of Path 2.
Do the simulation three times with different path-selecting proportions between Path 1 and Path 2 (0.7 : 0.3, 0.5 : 0.5, 0.3 : 0.7). Also, the entry and exit time data of simulation are collected to be AFC data.
Then, each path’s path-selecting proportion can be estimated by formula (13)~(14). The results are shown in Table 6.
The results in Table6 shows that the error rate of path’s path-selecting proportion estimation is less than 2%, which verifies the model and algorithm in this paper.Table 5
Values of parameters.
Parameters
Mean(s)
Standard deviation
ewt ofNSta1
125
20
2
exwt ofMSta5
145
20
2
twt ofNSta3 (transfer path: from the platform of line N’s up direction to the one of line M’s down direction)
205
20
2
twt ofLSta1 (transfer path: from the platform of line N’s up direction to the one of line L’s up direction)
170
20
2
twt ofLSta3 (transfer path: from the platform of line L’s up direction to the one of line M’s down direction)
192
20
2Table 6
Estimation results of path-selecting proportion.
Path-selecting proportion
Error rate  of path 1
Actual value
Estimation value
Path 1
Path 2
Path 1
Path 2
Simulation 1
0.7
0.3
0.6884
0.3116
−1.66%
Simulation 2
0.5
0.5
0.5050
0.4950
0.10%
Simulation 3
0.3
0.7
0.2954
0.7046
−1.53%


## 5. Conclusion

In the network operation phase of URT, path-selecting proportion is the key to network flow assignment and fare clearing. This paper analyzed the distribution characteristics of the components of travel time and then proposed an estimation method of path-selecting proportion, making use of the travel time data from the AFC system. Also, simulation experiments were created to verify the estimation method, and the results show that the error rate is less than 2% and the method is reliable.Compared with the traditional models based on path utility, the estimation method of path-selecting proportion has the following advantages:(1) by making full use of the AFC data, the sample size for parameter estimation is large and the results have the good feature of accuracy and (2) the estimation method relies on data analysis and processing, reducing the cost of artificial survey significantly.In fact, the estimation method in this paper is being used to analyze and validate the URT network flow assignment results in Shanghai.



---

*Source: 350397-2015-09-07.xml*