# Three Extensions of Tong and Richardson’s Algorithm for Finding the Optimal Path in Schedule-Based Railway Networks

Authors: J. Xie; S. C. Wong; S. M. Lo
Journal: Journal of Advanced Transportation
 (2017)

---

## Abstract

High-speed railways have been developing quickly in recent years and have become a main travel mode between cities in many countries, especially China. Studying passengers’ travel choices on high-speed railway networks can aid the design of efficient operations and schedule plans. The Tong and Richardson algorithm that is used in this model offers a promising method for finding the optimal path in a schedule-based transit network. However, three aspects of this algorithm limit its application to high-speed railway networks. First, these networks have more complicated common line problems than other transit networks. Without a proper treatment, the optimal paths cannot be found. Second, nonadditive fares are important factors in considering travel choices. Incorporating these factors increases the searching time; improvement in this area is desirable. Third, as high-speed railways have low-frequency running patterns, their passengers may prefer to wait at home or at the office instead of at the station. Thus, consideration of a waiting penalty is needed. This paper suggests three extensions to improve the treatments of these three aspects, and three examples are presented to illustrate the applications of these extensions. The improved algorithm can also be used for other transit systems.


---

## Body

## 1. Introduction

Traffic assignment in a transit network is unlike that in a road network, because transit vehicles run on fixed routes and predetermined timetables. Vehicles on roads have more freedom in route selection, and they do not need to depart at specific times [1]. There are two approaches to consider the time dimension and the fixed routes in a transit network, that is, the frequency-based model and the schedule-based model. The frequency-based model [2–4] simplifies the transit network by regarding each line as having many runs and the headway of runs as having a mean. The schedule-based model [1] is based on the real timetable. Thus, in evaluating the characteristics of these two approaches, it seems that the scheduled-based model is more promising for dynamic transit networks. Generally, there are three methodologies for path generation in a schedule-based network.


### 1.1. Branch and Bound Method

Tong and Richardson [1] suggested an optimal path algorithm which combined Dijkstra’s algorithm [5] with the branch and bound method. Later, Tong and Wong [6] extended this algorithm by considering nonadditive fares. Khani et al. [7] improved the searching speed of this algorithm by setting a lower bound to reduce the size of searches.Other researchers have introduced several important variables to limit path searching. These variables include the latest departure time [8], the preset time window between the planned departure time and the arrival time [9–14], the maximum number of transfers [8, 9, 11, 13], the maximum waiting time for transfers [9, 11], and the walking distance [13]. Applying these variables (or bounds) can improve the branch and bound method, but the effectiveness of the bounds depends on their preset values. Compared with Tong and Richardson’s algorithm, these bounds are not tight enough to effectively reduce the searching size.


### 1.2. Event Dominance Method

Florian [15] suggested an event dominance method, which can be used to find optimal paths to one or multiple destinations. However, the optimality of the path found by this method is questionable, because the searching stops after one event associated with the destination is found. In addition, the real optimal path might be ruled out at an earlier stage. This problem was investigated by Nielsen and Frederiksen [16] using a counterexample. They reported using hidden waiting time at the origin point to solve it and explained the method with a two-line example. However, the search size then becomes larger, so they needed to also use the graph cut approach, a modification that may fail to help if the optimal path has more than one transfer, due to the event dominance principle.


### 1.3. Other Methods

Nielsen et al. [17] suggested a specified design method for the Copenhagen suburban rail network. They divided the path choices into two kinds, that is, paths with no transfers and paths with transfers. The optimal path with no transfers was selected as the first train departing at the origin to the destination after the planned departure time. For the path with transfers, the whole path was divided into several segments, according to the transfer points that were planned in advance, based on the network. Each of the segments is treated like the path with no transfer. This method greatly reduces the computation time, but it is only suitable for simple networks with several transfer stations and with full information about passenger choices.Chen and Yang [18] modified the traditional graphic network by adding departure time windows on nodes. That is, if the arrival time at node i is not within the preset departure time window, the passengers will need to wait and decide whether to depart at the next time window. This kind of algorithm provided a way to consider the time dimension, but it is not a real schedule-base algorithm, and it simply treats waiting time in the same way as the in-vehicle time.Compared with the other approaches, Tong and Richardson’s algorithm has an improved capacity for effectively and flexibly handling complex transit networks in real time. However, in its present form it still has three limitations. This paper aims to extend Tong and Richardson’s algorithm to improve its results in dynamic transit networks. This improved algorithm can be used as a tool for information provision. Passengers can plan the best path according to their own preference, such as one without transfer or with less waiting time. In the future, we will develop this algorithm for network assignment and the planning of schedules, but at this stage the algorithm is mainly for transit trip navigation.


## 1.1. Branch and Bound Method

Tong and Richardson [1] suggested an optimal path algorithm which combined Dijkstra’s algorithm [5] with the branch and bound method. Later, Tong and Wong [6] extended this algorithm by considering nonadditive fares. Khani et al. [7] improved the searching speed of this algorithm by setting a lower bound to reduce the size of searches.Other researchers have introduced several important variables to limit path searching. These variables include the latest departure time [8], the preset time window between the planned departure time and the arrival time [9–14], the maximum number of transfers [8, 9, 11, 13], the maximum waiting time for transfers [9, 11], and the walking distance [13]. Applying these variables (or bounds) can improve the branch and bound method, but the effectiveness of the bounds depends on their preset values. Compared with Tong and Richardson’s algorithm, these bounds are not tight enough to effectively reduce the searching size.


## 1.2. Event Dominance Method

Florian [15] suggested an event dominance method, which can be used to find optimal paths to one or multiple destinations. However, the optimality of the path found by this method is questionable, because the searching stops after one event associated with the destination is found. In addition, the real optimal path might be ruled out at an earlier stage. This problem was investigated by Nielsen and Frederiksen [16] using a counterexample. They reported using hidden waiting time at the origin point to solve it and explained the method with a two-line example. However, the search size then becomes larger, so they needed to also use the graph cut approach, a modification that may fail to help if the optimal path has more than one transfer, due to the event dominance principle.


## 1.3. Other Methods

Nielsen et al. [17] suggested a specified design method for the Copenhagen suburban rail network. They divided the path choices into two kinds, that is, paths with no transfers and paths with transfers. The optimal path with no transfers was selected as the first train departing at the origin to the destination after the planned departure time. For the path with transfers, the whole path was divided into several segments, according to the transfer points that were planned in advance, based on the network. Each of the segments is treated like the path with no transfer. This method greatly reduces the computation time, but it is only suitable for simple networks with several transfer stations and with full information about passenger choices.Chen and Yang [18] modified the traditional graphic network by adding departure time windows on nodes. That is, if the arrival time at node i is not within the preset departure time window, the passengers will need to wait and decide whether to depart at the next time window. This kind of algorithm provided a way to consider the time dimension, but it is not a real schedule-base algorithm, and it simply treats waiting time in the same way as the in-vehicle time.Compared with the other approaches, Tong and Richardson’s algorithm has an improved capacity for effectively and flexibly handling complex transit networks in real time. However, in its present form it still has three limitations. This paper aims to extend Tong and Richardson’s algorithm to improve its results in dynamic transit networks. This improved algorithm can be used as a tool for information provision. Passengers can plan the best path according to their own preference, such as one without transfer or with less waiting time. In the future, we will develop this algorithm for network assignment and the planning of schedules, but at this stage the algorithm is mainly for transit trip navigation.


## 2. Tong and Richardson’s Algorithm

### 2.1. Description of Tong and Richardson’s Algorithm

The Tong and Richardson algorithm can be described as follows.Step 1.
The time-dependent quickest path algorithm is developed from Dijkstra’s algorithm [5], and it uses travel time between nodes as the path cost (as based on the timetable) to search for the time-dependent quickest paths from the origin o to all other nodes, if departing at ToDE. The variable ToDE is the actual clock time for departure at the origin o, unit: mins. After the quickest path search, the earliest arrival time at node i, namely, TiEA, can be found.Step 2.
Based on the quickest pathQ from the origin o to the destination d, the total weighted cost WodQ can be calculated. The weighted cost function for path j from node i to node q is(1)Wiqj=ftiqj+Siqj∗PT,where tiqj is the journey time (including waiting time, walking time, and transit time) for path j from node i to q, unit: mins.f t i q j is the weighted function for journey time in using path j, unit: mins:(2)ftiqj=PWK∗tjWK+PW∗tjW+PIV∗tjIV,where(3)tiqj=tjWK+tjW+tjIV,where tjWK is the walking time for path j, unit: mins; tjW is the waiting time at stations for path j, unit: mins; tjIV is the in-vehicle time for path j, unit: mins; PWK is the penalty for walking time; PW is the penalty for waiting time; PIV is the penalty for in-vehicle time; PT is the penalty for transfer, unit: mins; Siqj is the number of transfers for path j from node i to q.Step 3.
Set the upper boundary of the latest arrival time at the destinationd:(4)B1=WodQ+ToDE.Step 4.
Reverse the timetable, and set the reversed upper boundary as the departure time for searching the time-dependent quickest paths from the destination to all other nodes, so that we have the earliest arrival time at nodei from the destination d in the reversed network TiEAR. Then, reverse TiEAR to get the latest departure time to the destination d at node i, TiLD.Step 5.
CompareTiEA and TiLD to check the accessibility of node i, Ai:(5)Ai=1,ifTiLD-TiEA≥0,nodeiis  accessible,0,ifTiLD-TiEA<0,nodeiis  inaccessible.Exclude inaccessible nodes, so that inaccessible nodes are not included in the optimal path search (i.e., in Step  6).Step 6.
The optimal path search finds all of the possible paths by searching all accessible nodes. The weighted time functionWoij is calculated for node i along path j. If Woij>WodQ, the search for path j ends.Step 7.
The smallestWodj∗ is found, and the path j∗ is identified as the optimal path from the origin o to destination d.


### 2.2. Limitations of the Existing Tong and Richardson Algorithm

This algorithm can be used for most transit networks. However, it cannot deal with the following three common situations in railway networks.


#### 2.2.1. Nonadditive Fare

Tong and Richardson’s algorithm does not consider travel fares. If the fare is link-based and additive (i.e., the fare proportionally increases with the distance or travel time), Tong and Richardson’s algorithm still works when adding an additional linear extension for the weighted time function (such as that provided by Friedrich et al. [9]) along the optimal path search. However, the fare system for the railway is usually nonadditive, so the additive-fare function [9] cannot be used. A later improvement by Tong and Wong [6] allowed for the consideration of the nonadditive fare. However, introducing the fare into the weighted cost function enlarged the bounding (i.e., the searching size), so Tong and Wong used the cheapest fare to tighten the bound. Nevertheless, due to the gap between the fare for the quickest path and the cheapest fare, the searching size can still be large. Therefore, treatments are needed to accelerate the searching process. This paper suggests an effective way to include nonadditive fares.


#### 2.2.2. Common Lines Problem

A line has a sequence ofN stations and can be separated into (N-1) sections. Each line section consists of two successive stations with an arc connecting these two nodes. According to Tong and Richardson’s algorithm, arcs with the same starting stations, end stations, and running times can be aggregated into a link with a unique transit time. The arcs of a link are listed in the time sequence. During the path search, for each link only the first arc having a departure time later than the train’s arrival time at node i is used. However, this found path may not be the optimal path. An example of this problem is shown in Figure 1.Figure 1
An example network for the common lines problem.In the problem illustrated in Figure1, the passenger arrives at A at 8:55 and wants to go to C. There are two train lines:Line 1: it starts from A at 9:00 and ends at B at 10:00.Line 2: it starts from A at 9:10, stops at B at 10:10, and finally ends at C at 11:00.Hence, there are two possible paths:Path 1: first use Line 1, and then transfer to Line 2.Path 2: directly use Line 2.These two paths have the same arrival time, but Path 2 has no transfer. Thus, Path 2 may be more attractive to passengers. However, Path 2 is not found when using Tong and Richardson’s algorithm, because only one link is built between A and B, and the first arc that meets the time requirement belongs to Line 1. As this kind of line structure is common in railway systems, Tong and Richardson’s algorithm needs to be modified if it is to be useful for these systems.


#### 2.2.3. Waiting Time at Home

Tong and Wong [6] proved that all of the coefficients in the weighted cost function should be at least 1. If one of the coefficients is smaller than 1, the optimal path may not be found. However, the real situation is more complex. Passengers want to begin their trip at ToDE:(6)ToDE=ToED,where ToED is the actual clock time for the earliest departure time at the origin o, unit: mins.However, the passengers usually need to wait for a while, because the trains run based on their timetables. If the waiting time at the origin station exceeds the tolerance of passengers,tT, the passengers will choose to leave their homes or offices later. A smaller penalty PWH (1>PWH≥0) should be given for their time waiting at home or the office, because people can use that time for other activities. To consider this condition, a modification of Tong and Richardson’s algorithm is needed.This paper extends Tong and Richardson’s algorithm to solve these limitations, so that the algorithm can better analyze dynamic railway networks.


## 2.1. Description of Tong and Richardson’s Algorithm

The Tong and Richardson algorithm can be described as follows.Step 1.
The time-dependent quickest path algorithm is developed from Dijkstra’s algorithm [5], and it uses travel time between nodes as the path cost (as based on the timetable) to search for the time-dependent quickest paths from the origin o to all other nodes, if departing at ToDE. The variable ToDE is the actual clock time for departure at the origin o, unit: mins. After the quickest path search, the earliest arrival time at node i, namely, TiEA, can be found.Step 2.
Based on the quickest pathQ from the origin o to the destination d, the total weighted cost WodQ can be calculated. The weighted cost function for path j from node i to node q is(1)Wiqj=ftiqj+Siqj∗PT,where tiqj is the journey time (including waiting time, walking time, and transit time) for path j from node i to q, unit: mins.f t i q j is the weighted function for journey time in using path j, unit: mins:(2)ftiqj=PWK∗tjWK+PW∗tjW+PIV∗tjIV,where(3)tiqj=tjWK+tjW+tjIV,where tjWK is the walking time for path j, unit: mins; tjW is the waiting time at stations for path j, unit: mins; tjIV is the in-vehicle time for path j, unit: mins; PWK is the penalty for walking time; PW is the penalty for waiting time; PIV is the penalty for in-vehicle time; PT is the penalty for transfer, unit: mins; Siqj is the number of transfers for path j from node i to q.Step 3.
Set the upper boundary of the latest arrival time at the destinationd:(4)B1=WodQ+ToDE.Step 4.
Reverse the timetable, and set the reversed upper boundary as the departure time for searching the time-dependent quickest paths from the destination to all other nodes, so that we have the earliest arrival time at nodei from the destination d in the reversed network TiEAR. Then, reverse TiEAR to get the latest departure time to the destination d at node i, TiLD.Step 5.
CompareTiEA and TiLD to check the accessibility of node i, Ai:(5)Ai=1,ifTiLD-TiEA≥0,nodeiis  accessible,0,ifTiLD-TiEA<0,nodeiis  inaccessible.Exclude inaccessible nodes, so that inaccessible nodes are not included in the optimal path search (i.e., in Step  6).Step 6.
The optimal path search finds all of the possible paths by searching all accessible nodes. The weighted time functionWoij is calculated for node i along path j. If Woij>WodQ, the search for path j ends.Step 7.
The smallestWodj∗ is found, and the path j∗ is identified as the optimal path from the origin o to destination d.


## 2.2. Limitations of the Existing Tong and Richardson Algorithm

This algorithm can be used for most transit networks. However, it cannot deal with the following three common situations in railway networks.


### 2.2.1. Nonadditive Fare

Tong and Richardson’s algorithm does not consider travel fares. If the fare is link-based and additive (i.e., the fare proportionally increases with the distance or travel time), Tong and Richardson’s algorithm still works when adding an additional linear extension for the weighted time function (such as that provided by Friedrich et al. [9]) along the optimal path search. However, the fare system for the railway is usually nonadditive, so the additive-fare function [9] cannot be used. A later improvement by Tong and Wong [6] allowed for the consideration of the nonadditive fare. However, introducing the fare into the weighted cost function enlarged the bounding (i.e., the searching size), so Tong and Wong used the cheapest fare to tighten the bound. Nevertheless, due to the gap between the fare for the quickest path and the cheapest fare, the searching size can still be large. Therefore, treatments are needed to accelerate the searching process. This paper suggests an effective way to include nonadditive fares.


### 2.2.2. Common Lines Problem

A line has a sequence ofN stations and can be separated into (N-1) sections. Each line section consists of two successive stations with an arc connecting these two nodes. According to Tong and Richardson’s algorithm, arcs with the same starting stations, end stations, and running times can be aggregated into a link with a unique transit time. The arcs of a link are listed in the time sequence. During the path search, for each link only the first arc having a departure time later than the train’s arrival time at node i is used. However, this found path may not be the optimal path. An example of this problem is shown in Figure 1.Figure 1
An example network for the common lines problem.In the problem illustrated in Figure1, the passenger arrives at A at 8:55 and wants to go to C. There are two train lines:Line 1: it starts from A at 9:00 and ends at B at 10:00.Line 2: it starts from A at 9:10, stops at B at 10:10, and finally ends at C at 11:00.Hence, there are two possible paths:Path 1: first use Line 1, and then transfer to Line 2.Path 2: directly use Line 2.These two paths have the same arrival time, but Path 2 has no transfer. Thus, Path 2 may be more attractive to passengers. However, Path 2 is not found when using Tong and Richardson’s algorithm, because only one link is built between A and B, and the first arc that meets the time requirement belongs to Line 1. As this kind of line structure is common in railway systems, Tong and Richardson’s algorithm needs to be modified if it is to be useful for these systems.


### 2.2.3. Waiting Time at Home

Tong and Wong [6] proved that all of the coefficients in the weighted cost function should be at least 1. If one of the coefficients is smaller than 1, the optimal path may not be found. However, the real situation is more complex. Passengers want to begin their trip at ToDE:(6)ToDE=ToED,where ToED is the actual clock time for the earliest departure time at the origin o, unit: mins.However, the passengers usually need to wait for a while, because the trains run based on their timetables. If the waiting time at the origin station exceeds the tolerance of passengers,tT, the passengers will choose to leave their homes or offices later. A smaller penalty PWH (1>PWH≥0) should be given for their time waiting at home or the office, because people can use that time for other activities. To consider this condition, a modification of Tong and Richardson’s algorithm is needed.This paper extends Tong and Richardson’s algorithm to solve these limitations, so that the algorithm can better analyze dynamic railway networks.


## 2.2.1. Nonadditive Fare

Tong and Richardson’s algorithm does not consider travel fares. If the fare is link-based and additive (i.e., the fare proportionally increases with the distance or travel time), Tong and Richardson’s algorithm still works when adding an additional linear extension for the weighted time function (such as that provided by Friedrich et al. [9]) along the optimal path search. However, the fare system for the railway is usually nonadditive, so the additive-fare function [9] cannot be used. A later improvement by Tong and Wong [6] allowed for the consideration of the nonadditive fare. However, introducing the fare into the weighted cost function enlarged the bounding (i.e., the searching size), so Tong and Wong used the cheapest fare to tighten the bound. Nevertheless, due to the gap between the fare for the quickest path and the cheapest fare, the searching size can still be large. Therefore, treatments are needed to accelerate the searching process. This paper suggests an effective way to include nonadditive fares.


## 2.2.2. Common Lines Problem

A line has a sequence ofN stations and can be separated into (N-1) sections. Each line section consists of two successive stations with an arc connecting these two nodes. According to Tong and Richardson’s algorithm, arcs with the same starting stations, end stations, and running times can be aggregated into a link with a unique transit time. The arcs of a link are listed in the time sequence. During the path search, for each link only the first arc having a departure time later than the train’s arrival time at node i is used. However, this found path may not be the optimal path. An example of this problem is shown in Figure 1.Figure 1
An example network for the common lines problem.In the problem illustrated in Figure1, the passenger arrives at A at 8:55 and wants to go to C. There are two train lines:Line 1: it starts from A at 9:00 and ends at B at 10:00.Line 2: it starts from A at 9:10, stops at B at 10:10, and finally ends at C at 11:00.Hence, there are two possible paths:Path 1: first use Line 1, and then transfer to Line 2.Path 2: directly use Line 2.These two paths have the same arrival time, but Path 2 has no transfer. Thus, Path 2 may be more attractive to passengers. However, Path 2 is not found when using Tong and Richardson’s algorithm, because only one link is built between A and B, and the first arc that meets the time requirement belongs to Line 1. As this kind of line structure is common in railway systems, Tong and Richardson’s algorithm needs to be modified if it is to be useful for these systems.


## 2.2.3. Waiting Time at Home

Tong and Wong [6] proved that all of the coefficients in the weighted cost function should be at least 1. If one of the coefficients is smaller than 1, the optimal path may not be found. However, the real situation is more complex. Passengers want to begin their trip at ToDE:(6)ToDE=ToED,where ToED is the actual clock time for the earliest departure time at the origin o, unit: mins.However, the passengers usually need to wait for a while, because the trains run based on their timetables. If the waiting time at the origin station exceeds the tolerance of passengers,tT, the passengers will choose to leave their homes or offices later. A smaller penalty PWH (1>PWH≥0) should be given for their time waiting at home or the office, because people can use that time for other activities. To consider this condition, a modification of Tong and Richardson’s algorithm is needed.This paper extends Tong and Richardson’s algorithm to solve these limitations, so that the algorithm can better analyze dynamic railway networks.


## 3. Three Extensions

### 3.1. First Extension: Nonadditive Fare

To add the nonadditive fare into Tong and Richardson’s algorithm, the total weighted cost should be modified first, as follows:(7)Ciqj=ftiqj+Siqj∗PT+gciqj,where ciqj is the fare for path j from node i to q, unit: yuan, and g(ciqj) is the weighted function of fare converted to time, unit: mins. Also,(8)gciqj=ciqjV,where V is the value of time, unit: yuan/min.In addition,PWK, PW, PIV, and PT should not be less than 1 [6].Second, a new step is needed before setting the upper boundary (i.e., Step3).A time-dependent cheapest path algorithm is developed from Dijkstra’s algorithm [5], which uses fares between nodes as the path cost (based on the fare table) to search for the fare-dependent cheapest path from the origin o to the destination d. Thus, the smallest fare codS can be found.Third, the search boundary is tightened, as follows:(9)B2=CodQ-gcodS+ToDE.Proposition 1.
The optimal path’s arrival time,TdA-O, is less than B2.Proof.
AsPWK, PW, and PIV should be at least 1, we have(10)tiqj≤ftiqj.Hence, for the optimal path O from the origin o to the destination d, we have(11)todO≤ftodO.Adding the transfer penalty for the optimal path SodO∗PT, the weighted fare function for the optimal path gcodO, and ToDE to both the sides of the inequality, we have(12)todO+SodO∗PT+ToDE+gcodO≤ftodO+SodO∗PT+gcodO+ToDE⟺Equation7todO+SodO∗PT+ToDE+gcodO≤CodO+ToDE⟺TdA-O=todO+ToEDTdA-O+SodO∗PT+gcodO≤CodO+ToDEassuming that(13)TdA-O>B2.Therefore, the above-given inequality can be changed to(14)B2+SodO∗PT+gcodO<CodO+ToDE⟺Equation9CodQ-gcodS+ToDE+SodO∗PT+gcodO<CodO+ToDE⟺CodQ+SodO∗PT+gcodO-gcodS<CodO.For the definitions of the transfer penalty and the time-dependent cheapest path algorithm, we have(15)SodO∗PT≥0,gcodO-gcodS≥0.Hence, the above inequality can be changed to(16)CodQ<CodO.This inequality shows that if the assumption is correct, the quickest path’s total weighted cost is smaller than that of the optimal path. This result violates the definition of the optimal path, which should have the smallest total weighted cost. Hence, the optimal path’s arrival time TdA-O is earlier than B2.
Fourth, the optimal path search should be modified as well. There are two possible ways to add nonadditive fares.
One way is to add the fare to the weighted cost after the path search. When finding all of the possible paths,Wodj is calculated. If Wodj>CodQ, the path search ends. After the path search, trace back the path and calculate gcodj. Add gcodj to Wodj to get Codj, and then compare all Codj to find the smallest value. The path that has the smallest value is the optimal path. The searching time for this process mainly depends on the difference between the fare of the quickest path and the cheapest fare. If this difference tends to be zero, then the boundary for searching is tight. Otherwise, the searching time may be very long.
The other way to add in the fare factor is to calculate the temporary cost (CqT-j) along the path j search. When boarding a new line at node i, the cheapest ticket for this line from node i, ci∗s is obtained from the fare table. Using this new line to arrive at node q, the temporary cost is(17)CqT-j=ftoij+Soij∗PT+gcoqj+gcq∗s,staying  onboard,ftoqj+Soqj∗PT+gcoqj,alighting.During the path search, CqT-j is compared with the total weighted cost of the present best path, CodP. This is the condition for the fare:(18)CodP≥CqT-j.If the condition for the fare is not satisfied, the path search ends. Once path j reaches the destination, Codj has been calculated. If Codj<CodP, then path j is presently the best path, and the value of the upper boundary is replaced by Codj-gcodS+ToDE.Proposition 2.
If the condition of the fare is not satisfied, then pathj from the origin o to node q cannot be the optimal path.Proof.
We know that(19)CqT-j≤Codj.That is, if the condition of fare is not satisfied, that is, (20)CodP<CqT-j,then(21)CodP<Codj.Thus, path j cannot be the optimal path.In this paper, the second approach is used to find the optimal path, as the second path provides a tighter bound for searching.


### 3.2. Second Extension: Common Lines Problem

The common lines problem can be solved by redefining the common lines. Here, the common lines are defined as those train lines having the same platform sequence, transit time, stopping time at each intermediate platform, and fare. A line has several arcs connecting each pair of two successive stations. Arcs with the same starting station, end station and running pattern for the whole line and fare, can be aggregated into a link with a unique transit time and fare. The arcs of the link are listed in the time sequence. To illustrate the difference between this new concept of common lines and Tong and Richardson’s concept, the example network in the introduction is rebuilt, as shown in Figure2.Figure 2
The rebuilt example network, using the new concept of common lines.Two links betweenA and B are built and searched. Paths 1 and 2 are identified and compared so the optimal path can be found. This example illustrates that, after using this new concept to build links, the optimal path can be found by selecting only the first train arc, which has a departure time later than the arrival time. The proof is presented in Proposition A.1 in Appendix.This approach increases the searching size by adding more links, due to the stricter definition of common lines. Thus, a time window for searching train arcs is created to decrease the searching size. The lower boundary of the time window at nodei is the arrival time at node i via the present path j, that is, TiA-j. Passengers using the present path j cannot take the train which departs at node i before TiA-j. The upper boundary of the time window at node i is the latest departure time to the destination d at node i, TiLD, calculated in the reversed path search. A similar concept has been suggested by Khani et al. [7], who used the quickest time from node i to the destination d (i.e., the sum of the transit time and walking time) to restrict the search. In fact, this restriction can be made even tighter by using the latest departure time and considering the waiting time, transit time, and walking time. A proof is given in Proposition A.2 in Appendix to show that using TiLD for the optimal path search is sufficient.


### 3.3. Third Extension: Departure Time Choice

As has been proven by Tong and Wong [6], the weighted coefficients for time must be at least 1, to ensure that the optimal path’s ending time is lower than the upper boundary. However, when passengers stay at home or in their offices rather than at the station, they value that time as a relative benefit. Thus, it is reasonable to allow the waiting penalty at home or office (PWH) to be smaller than 1.First, a new concept, departure interval, is introduced to solve this problem. Usually, people tend to depart to the origin station at intervals such as 8:00, 8:15, or 8:30. The time intervals between each departure are defined as the departure interval,tI. In our algorithm, we assume that tI≤tT. The algorithm divides the time window [ToED,TdLA] into different departure time sections, and each section’s duration equals tI, where TdLA is the latest arrival time at the destination d. For each departure time section at the origin station, only the trains departing at [ToDE, ToDE+tT] are considered. The maximum waiting time at the origin station is tT, and the actual waiting time for each path is within the tolerance of the passengers. The waiting time at home is not considered during the path search of each time subsection, but this waiting time is considered after the path search so that the optimal path for each departure time section can be found. After searching all of the departure time sections, the optimal path for the time window [ToED,TdLA] can be found.Another concept, that of the zone, can be introduced into the algorithm to simulate the condition in which passengers are traveling to or from the station. Zone links are built to connect zones and stations with a timetable for departures. Each zone linkl has a unique journey time TzslJ between zone z and station s, and different journey times are used to simulate the congestion effects during the peak and off-peak periods. The penalty for a journey between zones and stations is PZS(PZS≥1).Thus, a new process to find the optimal path is suggested and shown below.Step  0. The line sections outside the time window [ThED,TeLA] do not need to be included in the searching network, and therefore a subnetwork can be created to increase the searching speed, whereThED is the earliest departure time at home zone h, unit: mins, andTeLA is the latest arrival time at the end zone e, unit: mins.Step  1. The passenger departs from home zone h at ThDE, and ThDE=ThED.Step  2. Run the quickest path search. In the origin station, only the trains departing at [ThDE+ThoyJ, ThDE+ThoyJ+tT] are considered, where ThoyJ is the journey time of home zone link y between the home zone h and the origin station o.Step  3. If no path is found, go to Step 11.Step  4. The algorithm stops if TenA-Q>TeLA, where TenA-Q is the actual clock time for the arrival time at the end zone e, using the quickest path Q in the nth departure, unit: mins.Go to Step11 if TenA-Q-ThDE>C′heP, where C′heP is the present best path’s weighted path cost, unit: mins.The new weighted path cost function for pathj is(22)C′hej=ftodj+Sodj∗PT+gcodj+ThoyJ+TedwJ∗PZS,where TedwJ is the journey time for end zone link w, between the end zone e and the destination stationd, unit: mins.Step  5. Run the cheapest path search. In the origin station, only those trains departing at [ThDE+ThoyJ,ThDE+ThoyJ+tT] are considered. Thus, the smallest fare, codS, can be found.Step  6. Calculate the new total weighted cost C′heQ and the upper boundary Bhe, with the departure time for the subsection.If the present best path’s weighted path costC′heP (which is initially infinite) is larger than C′heQ, then(23)Bhe=C′heQ-gcodS+ThDE.If not,(24)Bhe=C′heP-gcodS+ThDE.Step  7. Run the reversed quickest path search, using the boundary Bhe. Compare TiEA and TiLD to check the accessibility of node i, Ai, by using (5). Exclude inaccessible nodes, so that these nodes will not be included in the optimal path search.Step  8. Find the optimal path among the accessible nodes in the time window [ThDE,Bhe], and apply the following set of rules:(1)
In the origin station, only trains departing at [ThDE+ThoyJ, ThDE+ThoyJ+tT] are considered.(2)
Only use the first arc of linkl, in which the departure time is later than the arrival time TiA-j at the starting node i of link l.(3)
If the arc of linkl departs at node i later than TiLD, then the search for link l stops, as the arcs of link l are listed in the time sequence.(4)
In reality, passengers can only afford a certain number of transfers during their journeys. In considering this constraint, a transfer limit (Ltran⁡) is introduced into the algorithm to stop the branch search if the number of transfers exceeds Ltran⁡.(5)
IfTiA-j>TiLD, the search branch stops.(6)
If the condition of fare limitation (i.e., (18)) is not satisfied, the search branch stops.Step  9. Once the optimal path search ends, the waiting time at home should be added:(25)Chej-H=C′odj+n-1∗tI∗PWH,where Chej-H is the total weighted cost of the newly found optimal path j from home zone h to end zone e, considering the waiting time at home or the office and the nonadditive fare, unit: mins.Step  10. If the newly found optimal path has a lower total weighted cost than CheP-H, then record this path as the present best path and replace CheP-H as the new value. Note that, at the start of this process, the total weighted cost CheP-H equals the infinite.Step  11. If n=n+1 (and n is a positive integer), update the departure time:(26)ThDE=ThED+n-1∗tI.If ThDE<TeLA, go to Step  2. If ThDE≥TeLA, the algorithm stops.When all of the possible time sections have been searched, the path with the lowest weighted travel cost can be found. This path is the optimal path for the time window[ThED,TeLA].We have tested this new algorithm using the data provided by Tong and Richardson [1]. However, fare data is not provided, so we set the fare to zero. In addition, as there is no further information about waiting at home, the penalty of this is the same as that of waiting at the platform. The example network of Tong and Richardson is simple, so the abovementioned common line problem does not exist. Our result is consistent with theirs, demonstrating that the new extensions do not violate the ability of the initial algorithm. In the next chapter, three examples are presented to show the advantages of the new extensions.


## 3.1. First Extension: Nonadditive Fare

To add the nonadditive fare into Tong and Richardson’s algorithm, the total weighted cost should be modified first, as follows:(7)Ciqj=ftiqj+Siqj∗PT+gciqj,where ciqj is the fare for path j from node i to q, unit: yuan, and g(ciqj) is the weighted function of fare converted to time, unit: mins. Also,(8)gciqj=ciqjV,where V is the value of time, unit: yuan/min.In addition,PWK, PW, PIV, and PT should not be less than 1 [6].Second, a new step is needed before setting the upper boundary (i.e., Step3).A time-dependent cheapest path algorithm is developed from Dijkstra’s algorithm [5], which uses fares between nodes as the path cost (based on the fare table) to search for the fare-dependent cheapest path from the origin o to the destination d. Thus, the smallest fare codS can be found.Third, the search boundary is tightened, as follows:(9)B2=CodQ-gcodS+ToDE.Proposition 1.
The optimal path’s arrival time,TdA-O, is less than B2.Proof.
AsPWK, PW, and PIV should be at least 1, we have(10)tiqj≤ftiqj.Hence, for the optimal path O from the origin o to the destination d, we have(11)todO≤ftodO.Adding the transfer penalty for the optimal path SodO∗PT, the weighted fare function for the optimal path gcodO, and ToDE to both the sides of the inequality, we have(12)todO+SodO∗PT+ToDE+gcodO≤ftodO+SodO∗PT+gcodO+ToDE⟺Equation7todO+SodO∗PT+ToDE+gcodO≤CodO+ToDE⟺TdA-O=todO+ToEDTdA-O+SodO∗PT+gcodO≤CodO+ToDEassuming that(13)TdA-O>B2.Therefore, the above-given inequality can be changed to(14)B2+SodO∗PT+gcodO<CodO+ToDE⟺Equation9CodQ-gcodS+ToDE+SodO∗PT+gcodO<CodO+ToDE⟺CodQ+SodO∗PT+gcodO-gcodS<CodO.For the definitions of the transfer penalty and the time-dependent cheapest path algorithm, we have(15)SodO∗PT≥0,gcodO-gcodS≥0.Hence, the above inequality can be changed to(16)CodQ<CodO.This inequality shows that if the assumption is correct, the quickest path’s total weighted cost is smaller than that of the optimal path. This result violates the definition of the optimal path, which should have the smallest total weighted cost. Hence, the optimal path’s arrival time TdA-O is earlier than B2.
Fourth, the optimal path search should be modified as well. There are two possible ways to add nonadditive fares.
One way is to add the fare to the weighted cost after the path search. When finding all of the possible paths,Wodj is calculated. If Wodj>CodQ, the path search ends. After the path search, trace back the path and calculate gcodj. Add gcodj to Wodj to get Codj, and then compare all Codj to find the smallest value. The path that has the smallest value is the optimal path. The searching time for this process mainly depends on the difference between the fare of the quickest path and the cheapest fare. If this difference tends to be zero, then the boundary for searching is tight. Otherwise, the searching time may be very long.
The other way to add in the fare factor is to calculate the temporary cost (CqT-j) along the path j search. When boarding a new line at node i, the cheapest ticket for this line from node i, ci∗s is obtained from the fare table. Using this new line to arrive at node q, the temporary cost is(17)CqT-j=ftoij+Soij∗PT+gcoqj+gcq∗s,staying  onboard,ftoqj+Soqj∗PT+gcoqj,alighting.During the path search, CqT-j is compared with the total weighted cost of the present best path, CodP. This is the condition for the fare:(18)CodP≥CqT-j.If the condition for the fare is not satisfied, the path search ends. Once path j reaches the destination, Codj has been calculated. If Codj<CodP, then path j is presently the best path, and the value of the upper boundary is replaced by Codj-gcodS+ToDE.Proposition 2.
If the condition of the fare is not satisfied, then pathj from the origin o to node q cannot be the optimal path.Proof.
We know that(19)CqT-j≤Codj.That is, if the condition of fare is not satisfied, that is, (20)CodP<CqT-j,then(21)CodP<Codj.Thus, path j cannot be the optimal path.In this paper, the second approach is used to find the optimal path, as the second path provides a tighter bound for searching.


## 3.2. Second Extension: Common Lines Problem

The common lines problem can be solved by redefining the common lines. Here, the common lines are defined as those train lines having the same platform sequence, transit time, stopping time at each intermediate platform, and fare. A line has several arcs connecting each pair of two successive stations. Arcs with the same starting station, end station and running pattern for the whole line and fare, can be aggregated into a link with a unique transit time and fare. The arcs of the link are listed in the time sequence. To illustrate the difference between this new concept of common lines and Tong and Richardson’s concept, the example network in the introduction is rebuilt, as shown in Figure2.Figure 2
The rebuilt example network, using the new concept of common lines.Two links betweenA and B are built and searched. Paths 1 and 2 are identified and compared so the optimal path can be found. This example illustrates that, after using this new concept to build links, the optimal path can be found by selecting only the first train arc, which has a departure time later than the arrival time. The proof is presented in Proposition A.1 in Appendix.This approach increases the searching size by adding more links, due to the stricter definition of common lines. Thus, a time window for searching train arcs is created to decrease the searching size. The lower boundary of the time window at nodei is the arrival time at node i via the present path j, that is, TiA-j. Passengers using the present path j cannot take the train which departs at node i before TiA-j. The upper boundary of the time window at node i is the latest departure time to the destination d at node i, TiLD, calculated in the reversed path search. A similar concept has been suggested by Khani et al. [7], who used the quickest time from node i to the destination d (i.e., the sum of the transit time and walking time) to restrict the search. In fact, this restriction can be made even tighter by using the latest departure time and considering the waiting time, transit time, and walking time. A proof is given in Proposition A.2 in Appendix to show that using TiLD for the optimal path search is sufficient.


## 3.3. Third Extension: Departure Time Choice

As has been proven by Tong and Wong [6], the weighted coefficients for time must be at least 1, to ensure that the optimal path’s ending time is lower than the upper boundary. However, when passengers stay at home or in their offices rather than at the station, they value that time as a relative benefit. Thus, it is reasonable to allow the waiting penalty at home or office (PWH) to be smaller than 1.First, a new concept, departure interval, is introduced to solve this problem. Usually, people tend to depart to the origin station at intervals such as 8:00, 8:15, or 8:30. The time intervals between each departure are defined as the departure interval,tI. In our algorithm, we assume that tI≤tT. The algorithm divides the time window [ToED,TdLA] into different departure time sections, and each section’s duration equals tI, where TdLA is the latest arrival time at the destination d. For each departure time section at the origin station, only the trains departing at [ToDE, ToDE+tT] are considered. The maximum waiting time at the origin station is tT, and the actual waiting time for each path is within the tolerance of the passengers. The waiting time at home is not considered during the path search of each time subsection, but this waiting time is considered after the path search so that the optimal path for each departure time section can be found. After searching all of the departure time sections, the optimal path for the time window [ToED,TdLA] can be found.Another concept, that of the zone, can be introduced into the algorithm to simulate the condition in which passengers are traveling to or from the station. Zone links are built to connect zones and stations with a timetable for departures. Each zone linkl has a unique journey time TzslJ between zone z and station s, and different journey times are used to simulate the congestion effects during the peak and off-peak periods. The penalty for a journey between zones and stations is PZS(PZS≥1).Thus, a new process to find the optimal path is suggested and shown below.Step  0. The line sections outside the time window [ThED,TeLA] do not need to be included in the searching network, and therefore a subnetwork can be created to increase the searching speed, whereThED is the earliest departure time at home zone h, unit: mins, andTeLA is the latest arrival time at the end zone e, unit: mins.Step  1. The passenger departs from home zone h at ThDE, and ThDE=ThED.Step  2. Run the quickest path search. In the origin station, only the trains departing at [ThDE+ThoyJ, ThDE+ThoyJ+tT] are considered, where ThoyJ is the journey time of home zone link y between the home zone h and the origin station o.Step  3. If no path is found, go to Step 11.Step  4. The algorithm stops if TenA-Q>TeLA, where TenA-Q is the actual clock time for the arrival time at the end zone e, using the quickest path Q in the nth departure, unit: mins.Go to Step11 if TenA-Q-ThDE>C′heP, where C′heP is the present best path’s weighted path cost, unit: mins.The new weighted path cost function for pathj is(22)C′hej=ftodj+Sodj∗PT+gcodj+ThoyJ+TedwJ∗PZS,where TedwJ is the journey time for end zone link w, between the end zone e and the destination stationd, unit: mins.Step  5. Run the cheapest path search. In the origin station, only those trains departing at [ThDE+ThoyJ,ThDE+ThoyJ+tT] are considered. Thus, the smallest fare, codS, can be found.Step  6. Calculate the new total weighted cost C′heQ and the upper boundary Bhe, with the departure time for the subsection.If the present best path’s weighted path costC′heP (which is initially infinite) is larger than C′heQ, then(23)Bhe=C′heQ-gcodS+ThDE.If not,(24)Bhe=C′heP-gcodS+ThDE.Step  7. Run the reversed quickest path search, using the boundary Bhe. Compare TiEA and TiLD to check the accessibility of node i, Ai, by using (5). Exclude inaccessible nodes, so that these nodes will not be included in the optimal path search.Step  8. Find the optimal path among the accessible nodes in the time window [ThDE,Bhe], and apply the following set of rules:(1)
In the origin station, only trains departing at [ThDE+ThoyJ, ThDE+ThoyJ+tT] are considered.(2)
Only use the first arc of linkl, in which the departure time is later than the arrival time TiA-j at the starting node i of link l.(3)
If the arc of linkl departs at node i later than TiLD, then the search for link l stops, as the arcs of link l are listed in the time sequence.(4)
In reality, passengers can only afford a certain number of transfers during their journeys. In considering this constraint, a transfer limit (Ltran⁡) is introduced into the algorithm to stop the branch search if the number of transfers exceeds Ltran⁡.(5)
IfTiA-j>TiLD, the search branch stops.(6)
If the condition of fare limitation (i.e., (18)) is not satisfied, the search branch stops.Step  9. Once the optimal path search ends, the waiting time at home should be added:(25)Chej-H=C′odj+n-1∗tI∗PWH,where Chej-H is the total weighted cost of the newly found optimal path j from home zone h to end zone e, considering the waiting time at home or the office and the nonadditive fare, unit: mins.Step  10. If the newly found optimal path has a lower total weighted cost than CheP-H, then record this path as the present best path and replace CheP-H as the new value. Note that, at the start of this process, the total weighted cost CheP-H equals the infinite.Step  11. If n=n+1 (and n is a positive integer), update the departure time:(26)ThDE=ThED+n-1∗tI.If ThDE<TeLA, go to Step  2. If ThDE≥TeLA, the algorithm stops.When all of the possible time sections have been searched, the path with the lowest weighted travel cost can be found. This path is the optimal path for the time window[ThED,TeLA].We have tested this new algorithm using the data provided by Tong and Richardson [1]. However, fare data is not provided, so we set the fare to zero. In addition, as there is no further information about waiting at home, the penalty of this is the same as that of waiting at the platform. The example network of Tong and Richardson is simple, so the abovementioned common line problem does not exist. Our result is consistent with theirs, demonstrating that the new extensions do not violate the ability of the initial algorithm. In the next chapter, three examples are presented to show the advantages of the new extensions.


## 4. Case Studies

### 4.1. Description of the Example Network

To test the proposed algorithm, 16 important high-speed railway stations in southern China are selected to form an example network (shown in Figure3). Except for Guangzhounan Station, which has three platforms, each of the other stations has two platforms (as shown in Figure 4). Each platform is considered as a node in the abstract network, and each station serves a zone. In addition, some basic assumptions regarding the passengers are set as follows:The penalty for in-vehicle time isPIV=1.0.The penalty for walking time isPWK=2.0.The penalty for waiting time at the station isPW=1.8.The penalty for transfers isPT=1.0.The value of time isV=0.625 yuan/min (assuming that the average salary is 6000 yuan/month and the working time is 160 hours/month).The departure interval,tI, is 15 mins.The maximum waiting time at the origin station,tT, is 15 mins.The journey timeTzslJ between a zone z and a station s is 5 mins.The penalty for a journey between zones and station is PZS=1.The transfer limit for passengersLtran is 1.These parameters can be obtained by using the state preference method based on real data.Figure 3
Sixteen selected stations in southern China.Figure 4
The abstracted network in southern China.Based on the example network, three extensions for the limitations and their respective examples are presented below.


### 4.2. Example  1, for Extension 1

A passenger wants to travel from Guangzhou to Liuzhou, and the earliest departure time,ToDE, is 9:30. There are two possible paths, as shown in Tables 1 and 2, and their respective cost calculations are shown in Tables 3 and 4.Table 1
The possible pathj1 for a trip from Guangzhou to Liuzhou.
Node Arrival time Departure time Route used at arrival Fare (yuan) 13 9:30 9:36 19 10:21 10:23 Line 1 31 11:18 11:20 Line 1 137.5 27 12:17 12:59 Line 1 25 14:20 — Line 2 48.0Table 2
The possible pathj2 for a trip from Guangzhou to Liuzhou.
Node Arrival time Departure time Route used at arrival Fare (yuan) 13 9:30 9:33 21 11:25 11:27 Line 3 185.0 23 14:55 14:55 Line 3 24 14:56 14:56 Walk 26 14:59 — Line 4 1.0Table 3
Cost calculation for the possible pathj1 for a trip from Guangzhou to Liuzhou.
Actual value Penalty Weighted time IVT-transit time 238 1.0 238.0 IVT-waiting time on train 4 1.0 4.0 Walking time 0 2.0 0.0 Waiting time at platform 48 1.8 86.4 Transfer 1 1.0 1.0 Fare 185.5 0.625 296.8 Sum   626.2Table 4
Cost calculation for the possible pathj2 for a trip from Guangzhou to Liuzhou.
Actual value Penalty Weighted time IVT-transit time 323 1.0 323.0 IVT-waiting time on train 2 1.0 2.0 Walking time 1 2.0 2.0 Waiting time at platform 3 1.8 5.4 Transfer 1 1.0 1.0 Fare 186.0 0.625 297.6 Sum   631.0The quickest path is pathj1, which has a total weighted cost CodP of 626.2 mins and a cheapest fare of 185.5 yuan. Thus, the upper boundary is (27)9:30+626.2-185.50.625=15:01.The possible path j2 is found, because its arrival time at destination is within the upper boundary, if the condition for the fare (i.e., (18)) does not need to be satisfied.If the condition for the fare is used, the temporary cost is calculated along the path search (shown in Figure5). When the path search arrives at Node 24, using path j2, the temporary cost is 626.4>626.2=CodP, as shown in Figure 5.Figure 5
Temporary cost calculation along the possible pathj2.The path search for this section stops at Node 24. This example shows that the searching time is reduced if the condition for the fare is applied.Both the characters of paths and the perceptions of passengers determine the optimal path. Considering this network structure, pathj1 has a shorter in-vehicle time and a cheaper fare, but the waiting time at the platform is much longer than the path j2. The biggest advantage of path j2 is therefore the short waiting time at the platform. Hence, we will use the Monte Carlo method to test the sensitivity of PW under this circumstance.We assume thatPW follows a normal distribution with a mean of 1.8 and a standard deviation of 0.2. A statistical tool based on the real data collected by the state preference method is used to obtain this information. We randomly generated 100 numbers that follow the distribution of PW in Excel. While retaining the other parameters, we put these 100 numbers into the model one by one as the value of PW and then ran the model to find the optimal path. The test result is shown in Figure 6. The path j1 has a higher possibility of being selected due to its shorter in-vehicle time and cheaper fare. However, we also found that when PW is larger than about 1.9, the optimal path is path j2 rather than path j1, so if a passenger really does not want to wait for a train, he or she is very likely to choose path j2.Figure 6
Test result in Example1.


### 4.3. Example  2, for Extension 2

A passenger wants to travel from Shenzhen to Changsha, and the earliest departure time,ToDE, is 9:30. Two possible trains are given in Tables 5 and 6 and illustrated in Figure 7.Table 5
The timetable of the high-speed railway Line 1 in Example  2.
Node Station name Arrival time Departure time Travel time between stations (mins.) 17 Shenzhenbei — 09:35 15 Humen 09:52 09:54 17 13 Guangzhounan 10:11 — 17Table 6
The timetable of the high-speed railway Line 2 in Example  2.
Node Station name Arrival time Departure time Travel time between stations (mins.) 17 Shenzhenbei — 09:40 15 Humen 09:57 09:59 17 13 Guangzhounan 10:16 10:23 17 11 Chenzhouxi 11:48 11:50 85 9 Hengyangdong 12:23 12:25 33 3 Changshanan 13:05 — 40Figure 7
Two abstract networks in Example2.Based on Tong and Richardson’s algorithm, a link from Node 17 to Node 15 should be created with two train numbers, that is, Line 1 and Line 2, with Line 1 used to travel from Shenzhenbei to Guangzhounan. Only the possible pathj1 can be found, as shown in Tables 7 and 8. However, based on the new concept of common lines, there should be two links, that is, one link associated with Line 1 and the other associated with Line 2. Another possible path, j2, is found and is shown in Tables 9 and 10. The weighted cost for j2 is smaller than that for j1, so that the better path is j2, which cannot be found by using Tong and Richardson’s algorithm. In summary, this example shows that the first extension has a better solution than that provided by Tong and Richardson’s algorithm.Table 7
The possible pathj1 using Tong and Richardson’s algorithm in Example  2.
Node Arrival time Departure time Route used at arrival Fare (yuan) 17 9:30 9:35  74.5 15 9:52 9:54 Line 1 13 10:11 10:23 Line 1 11 11:48 11:50 Line 2 314 9 12:23 12:25 Line 2 3 13:05 — Line 2Table 8
The possible pathj1 cost calculation in Example  2.
Actual value Penalty Weighted time IVT-transit time 192 1.0 192.0 IVT-waiting time on train 6 1.0 6.0 Walking time 0 2.0 0.0 Waiting time at platform 17 1.8 30.6 Transfer 1 1.0 1.0 Fare 388.5 0.625 621.6 Sum   851.2Table 9
The possible pathj2 using the second extension in Example  2.
Node Arrival time Departure time Route used at arrival Fare (yuan) 17 9:30 9:40  388.5 15 9:57 9:59 Line 2 13 10:16 10:23 Line 2 11 11:48 11:50 Line 2 9 12:23 12:25 Line 2 3 13:05 — Line 2Table 10
The possible pathj2 cost calculation in Example  2.
Actual value Penalty Weighted time IVT-transit time 192 1.0 192.0 IVT-waiting time on train 13 1.0 13.0 Walking time 0 2.0 0.0 Waiting time at platform 10 1.8 18.0 Transfer 0 1.0 0.0 Fare 388.5 0.625 621.6 Sum   844.6


### 4.4. Example  3, for Extension 3

A passenger wants to travel from Guangzhou to Liuzhou. The time window [ThED,TeLA] = [9:00, 18:00].In the first run, the actual departure time is 9:00. The quickest path’s weighted path cost is 585 mins, and the cheapest fare is 185.5 yuan. Thus, the upper boundary,Bhe, is (28)9:00+585-185.50.625=13:49.After the reversed quickest path search, a network including only accessible nodes can be built (as shown in Figure 8). One possible path is found in the optimal path search (shown in Tables 11 and 12). The present best weighted path cost is updated to 585 mins. As there is no waiting time at home, the present best total weighted cost is also 585 mins.Table 11
The possible path for the first run.
Node Arrival time Departure time Route used at arrival Zone 7 — 9:00 14 9:05 9:12 Zone link 32 10:48 10:56 Line 1 28 12:01 12:01 Line 1 27 12:02 12:09 Walk 25 13:30 13:30 Line 2 Zone 13 13:35 — Zone linkTable 12
The possible path cost calculation for the first run.
Actual value Penalty Weighted time IVT-transit time 242 1.0 242.0 IVT-waiting time on train 8 1.0 8.0 Walking time 1 2.0 2.0 Waiting time at platform 14 1.8 25.2 Waiting time at home 0 0.5 0.0 Travel between zones and stations 10 1.0 10.0 Transfer 1 1.0 1.0 Fare 185.5 0.625 296.8 Sum   585.0Figure 8
Network accessibility and the found optimal path for the first run.In the second run, the actual departure time is 9:15. No path is found.In the third run, the actual departure time is 9:30. The quickest path’s weighted path cost is 564.2 mins, and the cheapest fare is 185.5 yuan. Clearly, 564.2 mins is less than the previous best weighted path cost (of 585 mins). Thus, the upper boundary,Bhe, is (29)9:30+564.2-185.50.625=13:59.After the reversed quickest path search, a network having only accessible nodes can be built (as shown in Figure 9). One possible path is found in the optimal path search (as shown in Tables 13 and 14). The new path cost (579.2 mins) is more than the previous best total weighted cost, so the present best weighted path cost is updated to 579.2-15=564.2 mins.Table 13
The possible path for the third run.
Node Arrival time Departure time Route used at arrival Zone 7 — 9:30 13 9:35 9:41 Zone link 19 10:26 10:28 Line 3 31 11:23 11:25 Line 3 27 12:22 12:24 Line 3 25 13:45 13:45 Line 4 Zone 13 13:50 — Zone linkTable 14
The possible path cost calculation for the third run.
Actual value Penalty Weighted time IVT-transit time 238 1.0 238.0 IVT-waiting time on train 4 1.0 4.0 Walking time 0 2.0 0.0 Waiting time at platform 8 1.8 14.4 Waiting time at home 30 0.5 15.0 Travel between zones and stations 10 1.0 10.0 Transfer 1 1.0 1.0 Fare 185.5 0.625 296.8 Sum   579.2Figure 9
Network accessibility and the found optimal path for the third run.In the fourth run, the actual departure time is 9:45. The quickest path’s weighted path cost is 752 mins and the cheapest fare is 185.5 yuan. 752 mins is more than the previous best weighted path cost (564.2 mins). Thus, the upper boundary,Bhe, is (30)9:45+564.2-185.50.625=14:14.No path can be found. Using 752 mins, the upper boundary, Bhe, is as follows: (31)9:45+752-185.50.625=17:21.After the reversed quickest path search, a network having only accessible nodes can be built (as shown in Figure 10). One possible path is found in the optimal path search (as shown in Tables 15 and 16). The new path cost (774.5 mins) is more than the previous best weighted path cost, so this path cannot be the optimal path. This result indicates that tightening the upper boundary saves computation time.Table 15
The possible path for using 752 mins in the fourth run.
Node Arrival time Departure time Route used at arrival Zone 7 — 9:45 13 9:50 9:53 Zone link 21 11:38 11:42 Line 5 23 13:49 14:19 Line 5 25 15:35 15:35 Line 6 Zone 13 15:40 — Zone linkTable 16
The possible path cost calculation for using 752 mins in the fourth run.
Actual value Penalty Weighted time Transit time 308 1.0 308.0 Waiting time on train 4 1.0 4.0 Walking time 0 2.0 0.0 Waiting time at platform 33 1.8 59.4 Waiting time at home 45 0.5 22.5 Travel between zones and stations 10 1.0 10.0 Transfer 1 1.0 1.0 Fare 231 0.625 369.6 Sum   774.5Figure 10
Network accessibility and the found optimal path using 752 mins in the fourth run.The optimal path for this example is the possible path in the third run. This optimal path cannot be found by using Tong and Richardson’s algorithm, because its arrival time (13:50) is later than the upper boundary of the first run (13:49).


## 4.1. Description of the Example Network

To test the proposed algorithm, 16 important high-speed railway stations in southern China are selected to form an example network (shown in Figure3). Except for Guangzhounan Station, which has three platforms, each of the other stations has two platforms (as shown in Figure 4). Each platform is considered as a node in the abstract network, and each station serves a zone. In addition, some basic assumptions regarding the passengers are set as follows:The penalty for in-vehicle time isPIV=1.0.The penalty for walking time isPWK=2.0.The penalty for waiting time at the station isPW=1.8.The penalty for transfers isPT=1.0.The value of time isV=0.625 yuan/min (assuming that the average salary is 6000 yuan/month and the working time is 160 hours/month).The departure interval,tI, is 15 mins.The maximum waiting time at the origin station,tT, is 15 mins.The journey timeTzslJ between a zone z and a station s is 5 mins.The penalty for a journey between zones and station is PZS=1.The transfer limit for passengersLtran is 1.These parameters can be obtained by using the state preference method based on real data.Figure 3
Sixteen selected stations in southern China.Figure 4
The abstracted network in southern China.Based on the example network, three extensions for the limitations and their respective examples are presented below.


## 4.2. Example  1, for Extension 1

A passenger wants to travel from Guangzhou to Liuzhou, and the earliest departure time,ToDE, is 9:30. There are two possible paths, as shown in Tables 1 and 2, and their respective cost calculations are shown in Tables 3 and 4.Table 1
The possible pathj1 for a trip from Guangzhou to Liuzhou.
Node Arrival time Departure time Route used at arrival Fare (yuan) 13 9:30 9:36 19 10:21 10:23 Line 1 31 11:18 11:20 Line 1 137.5 27 12:17 12:59 Line 1 25 14:20 — Line 2 48.0Table 2
The possible pathj2 for a trip from Guangzhou to Liuzhou.
Node Arrival time Departure time Route used at arrival Fare (yuan) 13 9:30 9:33 21 11:25 11:27 Line 3 185.0 23 14:55 14:55 Line 3 24 14:56 14:56 Walk 26 14:59 — Line 4 1.0Table 3
Cost calculation for the possible pathj1 for a trip from Guangzhou to Liuzhou.
Actual value Penalty Weighted time IVT-transit time 238 1.0 238.0 IVT-waiting time on train 4 1.0 4.0 Walking time 0 2.0 0.0 Waiting time at platform 48 1.8 86.4 Transfer 1 1.0 1.0 Fare 185.5 0.625 296.8 Sum   626.2Table 4
Cost calculation for the possible pathj2 for a trip from Guangzhou to Liuzhou.
Actual value Penalty Weighted time IVT-transit time 323 1.0 323.0 IVT-waiting time on train 2 1.0 2.0 Walking time 1 2.0 2.0 Waiting time at platform 3 1.8 5.4 Transfer 1 1.0 1.0 Fare 186.0 0.625 297.6 Sum   631.0The quickest path is pathj1, which has a total weighted cost CodP of 626.2 mins and a cheapest fare of 185.5 yuan. Thus, the upper boundary is (27)9:30+626.2-185.50.625=15:01.The possible path j2 is found, because its arrival time at destination is within the upper boundary, if the condition for the fare (i.e., (18)) does not need to be satisfied.If the condition for the fare is used, the temporary cost is calculated along the path search (shown in Figure5). When the path search arrives at Node 24, using path j2, the temporary cost is 626.4>626.2=CodP, as shown in Figure 5.Figure 5
Temporary cost calculation along the possible pathj2.The path search for this section stops at Node 24. This example shows that the searching time is reduced if the condition for the fare is applied.Both the characters of paths and the perceptions of passengers determine the optimal path. Considering this network structure, pathj1 has a shorter in-vehicle time and a cheaper fare, but the waiting time at the platform is much longer than the path j2. The biggest advantage of path j2 is therefore the short waiting time at the platform. Hence, we will use the Monte Carlo method to test the sensitivity of PW under this circumstance.We assume thatPW follows a normal distribution with a mean of 1.8 and a standard deviation of 0.2. A statistical tool based on the real data collected by the state preference method is used to obtain this information. We randomly generated 100 numbers that follow the distribution of PW in Excel. While retaining the other parameters, we put these 100 numbers into the model one by one as the value of PW and then ran the model to find the optimal path. The test result is shown in Figure 6. The path j1 has a higher possibility of being selected due to its shorter in-vehicle time and cheaper fare. However, we also found that when PW is larger than about 1.9, the optimal path is path j2 rather than path j1, so if a passenger really does not want to wait for a train, he or she is very likely to choose path j2.Figure 6
Test result in Example1.


## 4.3. Example  2, for Extension 2

A passenger wants to travel from Shenzhen to Changsha, and the earliest departure time,ToDE, is 9:30. Two possible trains are given in Tables 5 and 6 and illustrated in Figure 7.Table 5
The timetable of the high-speed railway Line 1 in Example  2.
Node Station name Arrival time Departure time Travel time between stations (mins.) 17 Shenzhenbei — 09:35 15 Humen 09:52 09:54 17 13 Guangzhounan 10:11 — 17Table 6
The timetable of the high-speed railway Line 2 in Example  2.
Node Station name Arrival time Departure time Travel time between stations (mins.) 17 Shenzhenbei — 09:40 15 Humen 09:57 09:59 17 13 Guangzhounan 10:16 10:23 17 11 Chenzhouxi 11:48 11:50 85 9 Hengyangdong 12:23 12:25 33 3 Changshanan 13:05 — 40Figure 7
Two abstract networks in Example2.Based on Tong and Richardson’s algorithm, a link from Node 17 to Node 15 should be created with two train numbers, that is, Line 1 and Line 2, with Line 1 used to travel from Shenzhenbei to Guangzhounan. Only the possible pathj1 can be found, as shown in Tables 7 and 8. However, based on the new concept of common lines, there should be two links, that is, one link associated with Line 1 and the other associated with Line 2. Another possible path, j2, is found and is shown in Tables 9 and 10. The weighted cost for j2 is smaller than that for j1, so that the better path is j2, which cannot be found by using Tong and Richardson’s algorithm. In summary, this example shows that the first extension has a better solution than that provided by Tong and Richardson’s algorithm.Table 7
The possible pathj1 using Tong and Richardson’s algorithm in Example  2.
Node Arrival time Departure time Route used at arrival Fare (yuan) 17 9:30 9:35  74.5 15 9:52 9:54 Line 1 13 10:11 10:23 Line 1 11 11:48 11:50 Line 2 314 9 12:23 12:25 Line 2 3 13:05 — Line 2Table 8
The possible pathj1 cost calculation in Example  2.
Actual value Penalty Weighted time IVT-transit time 192 1.0 192.0 IVT-waiting time on train 6 1.0 6.0 Walking time 0 2.0 0.0 Waiting time at platform 17 1.8 30.6 Transfer 1 1.0 1.0 Fare 388.5 0.625 621.6 Sum   851.2Table 9
The possible pathj2 using the second extension in Example  2.
Node Arrival time Departure time Route used at arrival Fare (yuan) 17 9:30 9:40  388.5 15 9:57 9:59 Line 2 13 10:16 10:23 Line 2 11 11:48 11:50 Line 2 9 12:23 12:25 Line 2 3 13:05 — Line 2Table 10
The possible pathj2 cost calculation in Example  2.
Actual value Penalty Weighted time IVT-transit time 192 1.0 192.0 IVT-waiting time on train 13 1.0 13.0 Walking time 0 2.0 0.0 Waiting time at platform 10 1.8 18.0 Transfer 0 1.0 0.0 Fare 388.5 0.625 621.6 Sum   844.6


## 4.4. Example  3, for Extension 3

A passenger wants to travel from Guangzhou to Liuzhou. The time window [ThED,TeLA] = [9:00, 18:00].In the first run, the actual departure time is 9:00. The quickest path’s weighted path cost is 585 mins, and the cheapest fare is 185.5 yuan. Thus, the upper boundary,Bhe, is (28)9:00+585-185.50.625=13:49.After the reversed quickest path search, a network including only accessible nodes can be built (as shown in Figure 8). One possible path is found in the optimal path search (shown in Tables 11 and 12). The present best weighted path cost is updated to 585 mins. As there is no waiting time at home, the present best total weighted cost is also 585 mins.Table 11
The possible path for the first run.
Node Arrival time Departure time Route used at arrival Zone 7 — 9:00 14 9:05 9:12 Zone link 32 10:48 10:56 Line 1 28 12:01 12:01 Line 1 27 12:02 12:09 Walk 25 13:30 13:30 Line 2 Zone 13 13:35 — Zone linkTable 12
The possible path cost calculation for the first run.
Actual value Penalty Weighted time IVT-transit time 242 1.0 242.0 IVT-waiting time on train 8 1.0 8.0 Walking time 1 2.0 2.0 Waiting time at platform 14 1.8 25.2 Waiting time at home 0 0.5 0.0 Travel between zones and stations 10 1.0 10.0 Transfer 1 1.0 1.0 Fare 185.5 0.625 296.8 Sum   585.0Figure 8
Network accessibility and the found optimal path for the first run.In the second run, the actual departure time is 9:15. No path is found.In the third run, the actual departure time is 9:30. The quickest path’s weighted path cost is 564.2 mins, and the cheapest fare is 185.5 yuan. Clearly, 564.2 mins is less than the previous best weighted path cost (of 585 mins). Thus, the upper boundary,Bhe, is (29)9:30+564.2-185.50.625=13:59.After the reversed quickest path search, a network having only accessible nodes can be built (as shown in Figure 9). One possible path is found in the optimal path search (as shown in Tables 13 and 14). The new path cost (579.2 mins) is more than the previous best total weighted cost, so the present best weighted path cost is updated to 579.2-15=564.2 mins.Table 13
The possible path for the third run.
Node Arrival time Departure time Route used at arrival Zone 7 — 9:30 13 9:35 9:41 Zone link 19 10:26 10:28 Line 3 31 11:23 11:25 Line 3 27 12:22 12:24 Line 3 25 13:45 13:45 Line 4 Zone 13 13:50 — Zone linkTable 14
The possible path cost calculation for the third run.
Actual value Penalty Weighted time IVT-transit time 238 1.0 238.0 IVT-waiting time on train 4 1.0 4.0 Walking time 0 2.0 0.0 Waiting time at platform 8 1.8 14.4 Waiting time at home 30 0.5 15.0 Travel between zones and stations 10 1.0 10.0 Transfer 1 1.0 1.0 Fare 185.5 0.625 296.8 Sum   579.2Figure 9
Network accessibility and the found optimal path for the third run.In the fourth run, the actual departure time is 9:45. The quickest path’s weighted path cost is 752 mins and the cheapest fare is 185.5 yuan. 752 mins is more than the previous best weighted path cost (564.2 mins). Thus, the upper boundary,Bhe, is (30)9:45+564.2-185.50.625=14:14.No path can be found. Using 752 mins, the upper boundary, Bhe, is as follows: (31)9:45+752-185.50.625=17:21.After the reversed quickest path search, a network having only accessible nodes can be built (as shown in Figure 10). One possible path is found in the optimal path search (as shown in Tables 15 and 16). The new path cost (774.5 mins) is more than the previous best weighted path cost, so this path cannot be the optimal path. This result indicates that tightening the upper boundary saves computation time.Table 15
The possible path for using 752 mins in the fourth run.
Node Arrival time Departure time Route used at arrival Zone 7 — 9:45 13 9:50 9:53 Zone link 21 11:38 11:42 Line 5 23 13:49 14:19 Line 5 25 15:35 15:35 Line 6 Zone 13 15:40 — Zone linkTable 16
The possible path cost calculation for using 752 mins in the fourth run.
Actual value Penalty Weighted time Transit time 308 1.0 308.0 Waiting time on train 4 1.0 4.0 Walking time 0 2.0 0.0 Waiting time at platform 33 1.8 59.4 Waiting time at home 45 0.5 22.5 Travel between zones and stations 10 1.0 10.0 Transfer 1 1.0 1.0 Fare 231 0.625 369.6 Sum   774.5Figure 10
Network accessibility and the found optimal path using 752 mins in the fourth run.The optimal path for this example is the possible path in the third run. This optimal path cannot be found by using Tong and Richardson’s algorithm, because its arrival time (13:50) is later than the upper boundary of the first run (13:49).


## 5. Conclusions

This paper suggests three extensions for Tong and Richardson’s algorithm. In the first, instead of only considering the time effect, the fare effect on choosing a path is included, so that the found path is more reasonable. In addition, a method for decreasing computation time is added. This method is demonstrated by using the cheapest fare and the temporary cost. In the second extension, the common lines problem in a schedule-based transit network is solved by redefining the common lines. The common lines should be those train lines that have the same platform sequences, transit times, and stopping times at each intermediate platform and fares. Line selecting rules are also added to reduce the computation complexity. In the third extension, departure time choice is introduced into the algorithm to avoid overly long waiting times at the origin station. This extension can also help to include the congestion effect in travel between the origin and destination stations. Hence, the new algorithm can be used to find the optimal path in a more complicated transit system, such as a real railway network. The examples shown demonstrate that the extended algorithm can work better than Tong and Richardson’s algorithm. However, more extensions can be done, such as including the stochastic effects on the arrival times of passengers or trains, considering the capacity of trains or the fare change. Future work will focus on these additional aspects. The uncertainty related to fares should be particularly considered, as the fare is an important factor in market competition, and rail companies are interested in how passengers change their behavior when the fare changes. Studies [19, 20] in this area have indicated some valuable new directions, and we will develop this algorithm further in the future.



---

*Source: 9216864-2017-01-12.xml*