# Schedule-Based Transit Assignment Submission

^{1}School of Traffic and Transportation, Beijing Jiaotong University, No. 3 Shangyuancun, Haidian District, Beijing 100044, China^{2}College of Engineering and Applied Science, University of Cincinnati, 2600 Clifton Avenue, Cincinnati, OH 45220, USA

Received 7 October 2016; Revised 9 January 2017; Accepted 19 January 2017; Published 13 February 2017

Copyright © 2017 Xiangming Yao et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

The online operation management and the offline policy evaluation in complex transit networks require an effective dynamic traffic assignment (DTA) method that can capture the temporal-spatial nature of traffic flows. The objective of this work is to propose a simulation-based dynamic passenger assignment framework and models for such applications in the context of schedule-based rail transit systems. In the simulation framework, travellers are regarded as individual agents who are able to obtain complete information on the current traffic conditions. A combined route selection model integrated with pretrip route selection and entrip route switch is established for achieving the dynamic network flow equilibrium status. The train agent is operated strictly with the timetable and its capacity limitation is considered. A continuous time-driven simulator based on the proposed framework and models is developed, whose performance is illustrated through a large-scale network of Beijing subway. The results indicate that more than 0.8 million individual passengers and thousands of trains can be simulated simultaneously at a speed ten times faster than real time. This study provides an efficient approach to analyze the dynamic demand-supply relationship for large schedule-based transit networks.

#### 1. Introduction

Urban rail transit has developed rapidly in China during the last ten years. By the end of 2015, there were 26 cities operating the rail transit with a total length of 3,618 km [1]. With the travel demand growing radically, some intractable issues emerge for the operation management, such as the recurrent congestion in peak hours and the train schedule construction for the travel demand under extremely unbalanced conditions. It has been conjectured that the development of Dynamic Traffic Management Systems (DTMS) can be a feasible approach for addressing these prominent problems. However, assessing the benefits and influences of such systems are difficult as these strategies are highly dependent on the travel behavior of individual passenger in response to travel information and control actions. Hence, it is necessary to develop useful methods and tools for assessing the DTM policies and control strategies.

Dynamic traffic assignment (DTA) models are regarded as a valuable tool to evaluate the DTM performance for its capabilities in capturing the dynamic nature of traffic flows and describing the formation and propagation of traffic congestions. DTA models can be divided into two categories: the mathematic-based DTA models and simulation-based DTA models. Mathematic-based DTA models, such as optimization programmes [2], variational inequalities [3], and optimal control [4], have solid theory foundations and perfect analyzability. However, few of them are implemented in real-world traffic networks because of their limitations in computation efficiency and complex parameter requirements. Simulation-based DTA models are considered more suitable for real-world applications [5, 6]. There have been several DTA simulators developed and applied to road networks, such as DYNAMIT (https://its.mit.edu/software/dynamit) and DYNASMART (http://mctrans.ce.ufl.edu/featured/dynasmart/). Unfortunately, the previous models and tools are mainly developed for road traffic networks. The traffic flow characteristics in transit system are much different within road traffic, where the passenger flows are highly nonlinear. Hence, DTA models in road traffic systems are not suitable for transit system. The DTA tools for the specific schedule-based rail transit networks are underdeveloped.

In the sphere of transit assignment, the DTA models also can be divided into two categories, the frequency-based models and the schedule- or timetable-based models [7]. Frequency-based approaches consider services in terms of sets of lines, where the run scheduled times are not considered explicitly, while the schedule-based approach refers to services in terms of runs, using the real vehicle arrival/departure time to obtain attributes that can be explicitly considered in the run choice. With the development of transit modelling, the DTA approaches have gradually changed from frequency-based models to schedule-based models. The capacity limitation of vehicles is a critical point that should be considered in transit systems, because passengers can only travel through sections by trains that have strict capacity constraints. However, previous approaches, whether frequency- or schedule-based, have mainly focused on line capacities not vehicle capacities [8]. The “fail-to-board probabilities” is usually used to describe the approximate congestion conditions of vehicles [9, 10]. In this work, the train is seen as an individual agent and its capacity constraints can be strictly described by limiting the number of boarding passengers. Therefore, queuing processes for passengers waiting on platforms can be captured. For the schedule-based transit assignment models, the space-time or diachronic graph is usually used to represent the transit services network, which contains the service, demand, and access/egress subgraphs [11–14]. However, this kind of space-time network is extremely complex when transit lines and transit services (train runs) are large. It is difficult to find a shortest path quickly in the networks. In order to enhance the computation efficiency of the DTA models, a two-stage path choice process is constructed in this work. First, search the shortest paths for each OD pair without considering the passenger flows and train services. This process seeks to establish the interrelationship between links and ODs. Second, update the cost of each route with the simulation clock advancing by considering the real-time passenger flows and services. When passengers enter the transit system, they can choose the “best” path immediately through the current traffic conditions. The two-stage path choice process has high efficiency because the speed for updating route cost is much quicker than searching a new route.

This work aims to propose an efficient and practical simulation-based DTA framework and models for the schedule-based rail transit network. The characteristics of the proposed approaches include (1) describing the travel behavior at the level of individual passengers and presenting the detail travel processes for passengers travelling through the network, such as walking within the station, waiting, transferring, boarding, and alighting; (2) integrating the pretrip and enroute path choice behavior together, which not only allows describing the route selection processes in normal conditions but also enables to capture the enroute switch behavior under exceptional conditions; (3) the capacity which is considered by the accurate train load capacity instead of the line capacity and the train runs which can adapt to different types of timetable; (4) the simulation models having high computational efficiency for large scale (large number of passengers and trains) rail transit networks.

The remainder of the paper is organized as follows. The simulation-based modelling framework for DTA in the schedule-based transit network is given first. Following are the major models under the simulation framework, mainly including passenger generation, route selection, and network-loading models. Then, model implementation in the Beijing subway networks are presented in Section 4. Finally, Section 5 presents the conclusion and future works.

#### 2. Modelling Framework

Generally, any simulation-based DTA systems consist of two critical components: a route selection module and a network-loading module [16]. The route selection module describes the principle for travellers choosing their route and then determines the macroscopical flow status on the network. The network-loading module attempts to represent the temporal-spatial evolution of traffic flows on the network after the routes of passengers are determined. Figure 1 presents the simulation-based DTA framework and model structure for a schedule-based transit network, where the major parts are highlighted.

**Figure 1: **Simulation-based DTA framework and model structure for a schedule-based transit system.

In the simulation framework, travellers are regarded as individual agents who can obtain the current traffic conditions on the network and always select the best path. Trains are operated strictly with the preset timetable, which allows considering the strict arrival/departure time. The simulation processes for obtaining the macroscopical network flow status are to describe the whole travel procedures of all individual passengers in microscopic view, such as egress/access, waiting for the train, and transferring through passageways. The detailed introduction of these two critical components is provided in the next section. Additionally, the network structure and the travel demand generation that produces the input for DTA models are important and will also be introduced in Section 3.

##### 2.1. Route Selection Module

There are several types of route choice models for different applications, such as equilibrium-based or information-based, pretrip or enroute, and within-day or day-to-day. Detail descriptions of passenger choice models can infer to the review of Szeto and Wong [17]. In this work, the within-day dynamic user equilibrium (DUE) is used to describe the principle for traveller route choice, which can be seen as follows: when travelling, travellers should always select their “best” path at each decision point, and the cost of used routes is no larger than the unused routes. In a rail transit network, passengers usually have no secondary route when they are at the enroute decision points (transfer stations) because of the low connectivity of the network. Hence, the pretrip user equilibrium principle can be suitable in normal conditions. However, passengers should change their routes in some special conditions, such as switching their routes when they cannot go to the end for incidents. In order to enhance the capability of models in describing the passengers routing behavior under different situations, a combined route selection method which integrated the pretrip and enroute models is used in this work. The pretrip route selection model which follows the dynamic user equilibrium is established under normal conditions. Moreover, the enroute path switch model based on a bounded rational rule is applied for special situations. This combined model is consistent well with the path selection behaviors of rail transit passengers.

Though the rail transit network has low connectivity, there may also exist alternative route in an OD pair. The -shortest paths are used to describe the discrepancy in route choice behavior of different passengers. How to find the “best” route immediately for each traveller is of great influence on the computation efficiency of a simulation system. For a large-scale network, it is almost impossible to search the routes online. A two-stage path choice process is established in this work, which contains (1) initial -shortest paths search and (2) the real-time route cost update. The process of initial -shortest paths search is to establish the interconnections between links and OD paths, and the route cost updating procedure aims to describe the real-time traffic conditions on the network. The route cost will be refreshed in a small preset time interval (such as two minutes). When a passenger enters the station, he/she can choose the “best” path quickly by considering the approximate real-time traffic conditions. Hence, the flow state of the network is not a rigorous but an approximate user equilibrium status.

##### 2.2. Network-Loading Module

Once the traveller’s route is determined, the network-loading module is to simulate the movement of travellers through the network, with the output of dynamic flow distributions of nodes (stations/platforms) and sections (trains). In this work, the continues-time-driven simulation approach is utilized to simulate the processes of all passengers moving on the network. The network-loading module contains three major components: (1) passenger walking within the station, such as access, egress, and transfer; (2) train movement operation; and (3) interactions between passengers and trains on platforms. The detailed description of these components will be presented in Section 3.

#### 3. Traffic Simulation Modelling

##### 3.1. Network and Train Schedule

The rail transit network is represented by a directed graph , where is the node set, is the link set, and is the set of transit lines. The nodes consist of two types: source and sink nodes (entrance and exit gates) for passenger arriving and leaving, and transit nodes (platforms) for train stopping. A station is composed of several interconnected nodes including the source/sink nodes and the transit nodes. According to the connected node type, the links connecting two neighbouring nodes are divided into two types. The first one is the walk link for passenger walking and transferring and the second one is the transit link for a train running between two stations. A transit line is a fixed path along which vehicles periodically run, corresponding to the train route. Note that more than one transit line may exist on a physical line, such as for long and short train routes. Figure 2 presents the topology structure for rail transit networks.

**Figure 2: **Topology structure for a rail transit network.

Let in be a transit line where is a set of transit nodes and is a set of links,. Denote and as the th transit node and th transit link in the transit line , is the arrival time for vehicle at th transit node (station), and is the departure time for vehicle at th transit node. The timetable for vehicle running on transit line can be represented by groups of arrival time and departure time , . The dwell time for vehicle is given as (1). The relationship among arrival time, departure time, and link running time is shown in (2). Table 1 provides an example of a train schedule (timetable).where is the time for a vehicle running through link and link connects nodes and .

**Table 1: **An example of a train schedule.

##### 3.2. Individual Passenger Generation

There are two types of traffic demand information which can be used as input for generating individual passengers in the DTA simulation system. The first one is the time-dependent origin-destination (OD) matrixes that are usually for online traffic management applications. The method of dynamic OD estimation and prediction can be inferred to the works of Yao et al. [18, 19]. The second one is the automatic fare collection (AFC) data that is primarily for offline policy evaluations. The generation processes in the simulation system should be as consistent as possible with the actual passenger flow characteristics in arrival time and spatial distributions. When a passenger is generated, the origin station, destination station, and departure time (arrival station time) should be produced.

###### 3.2.1. Generation from Time-Dependent O-D Tables

Let be the set of source and sink nodes, , is the travel demand from station to during time interval , and is the time duration of the OD table. The OD table in time interval can be described as , , . Suppose that passengers arrive uniformly if the time span is very short, for example, no more than five minutes. Then the passenger arriving rate of source node (belonging to station ) in time interval can be calculated as

The number of passengers arriving at node during a simulation time step iswhere represents the time step of the simulation clock and represents the down rounding computation.

However, while the simulation time step is very small (such as 1 second), there may not be a single passenger arriving at the station in a simulation step. Referring to other related simulation works [20], we assume that the time intervals between two consecutive passengers follow the negative exponential distributions. Hence, the probability of a passenger arriving in time is as follows:where represents the arrival time of the previous passenger.

When a passenger is generated at station , his/her destination can be determined from the trip distribution fractions calculated from the O-D tables. The probability of selecting node as the destination station is

###### 3.2.2. Generation from Automatic Fare Transaction Records

The AFC system has been used widely in public transport and records accurate trip information for each passenger, including origin and destination stations, check-in and check-out times, and card type. The AFC data provides a new and massive data source for traffic planning and management. When the AFC records are used as the input for the simulation system, the passenger agents can be generated accurately whose arrival patterns follow the nature of the actual travel demand. Unfortunately, it can only be used to analyze the historical traffic status or evaluate the traffic policies corresponding to offline applications. Table 2 presents the data structure of the AFC record information used for generating passengers.

**Table 2: **Data structure of AFC record information.

##### 3.3. Route Selection

For the particular structure of the rail transit network, passengers can only change their route at transfer stations, and usually they are unable to choose a secondary route once they start their trip. Hence, in this work, a combined route selection procedure is used to achieve the dynamic network equilibrium conditions: passengers follow the predetermined equilibrium principles under normal circumstances, and a bounded rational rule is adopted for passenger route changes under emergencies. The advantages of the combined route selection model are (1) high computational efficiency, (2) conformance to the route choice behavior for rail transit travellers, and (3) ability to capture the behavior change under special conditions.

###### 3.3.1. Equilibrium-Based Pretrip Path Choice

Assume that all travellers can obtain all of the information on the current traffic conditions and each traveller will select the best (usually the lowest cost) path. The travel pattern of pretrip dynamic equilibrium is defined as follows: for all travellers who leave their origin at any time in any O-D pair, the costs of any used routes are equal and minimal and smaller or equal to the cost of unused routes. The route cost is represented by a generalized cost function which is composed of four parts: (1) access and egress walk time; (2) on-board time; (3) waiting time; and (4) transfer time.

The walk time contains access and egress walk time, which is calculated by the distance corresponding to the walk link and the average walking speed of travellers. The total walk time can be represented aswhere represents the access walk time and is the egress walk time.

Normally, the on-board time for passengers travelling through sections is constant, which can be fixed with the train schedules. Define as the total on-board time of passengers travelling through all sections within a route. The waiting time includes three components: (1) waiting time at the origin station; (2) waiting time at the transfer station if a transfer is required; and (3) the delay waiting time due to overloaded trains. The average waiting time at an origin/transfer station is equal to half of the train headway time corresponding to travel line. However, the rail transit system has strict capacity restraints; some passengers cannot board the first train that arrives because it is overloaded. This delayed waiting time should be considered if there is no sufficient capacity. Assume that passengers who fail to board the first arriving train will wait for the next train. Thus, the total waiting time can be represented as

^{1}School of Architecture and Civil Engineering, Xiamen University, Xiamen 361005, China^{2}Research Center for Modern Logistics, Graduate School at Shenzhen, Tsinghua University, Shenzhen 518055, China^{3}Department of Systems and Industrial Engineering, The University of Arizona, Tucson, AZ 85721, USA

Copyright © 2012 Wangtu Xu et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

This paper proposes a stochastic user equilibrium (SUE) assignment model for a schedule-based transit network with capacity constraint. We consider a situation in which passengers do not have the full knowledge about the condition of the network and select paths that minimize a generalized cost function encompassing five components: (1) ride time, which is composed of in-vehicle and waiting times, (2) overload delay, (3) fare, (4) transfer constraints, and (5) departure time difference. We split passenger demands among connections which are the space-time paths between OD pairs of the network. All transit vehicles have a fixed capacity and operate according to some preset timetables. When the capacity constraint of the transit line segment is reached, we show that the Lagrange multipliers of the mathematical programming problem are equivalent to the equilibrium passenger overload delay in the congested transit network. The proposed model can simultaneously predict how passengers choose their transit vehicles to minimize their travel costs and estimate the associated costs in a schedule-based congested transit network. A numerical example is used to illustrate the performance of the proposed model.

#### 1. Introduction

Transit assignment is an approach used for predicting the way in which passengers choose routes traveling from origins to destinations. Much progress has been made in the past three decades [1], and the assignment model can be broadly divided into three types: transport system-based, frequency-based, and schedule-based.

In a transport system-based network, the all-or-nothing assignment method in which passengers choose the quickest route without considering headways of line routes as well as timetables is adopted. The result provides an overview of the structure of travel demand for long-distance planning purposes. Generally, the transport system-based assignment procedure does not require any line frequencies or timetables as input data. The early transit assignment approaches such as Dial’s algorithm [2, 3] and the method by Fearnside and Draper [4] are also based on the transport system in a way similar to road traffic assignment.

In a frequency-based network, each transit line is assumed to operate on a constant headway. The assignment procedure encompasses three steps: route search, route choice, and demand split. The first step searches for possible paths between all origin-destination (OD) pairs. The second step compares the individual routes and eliminates the unreasonable routes. Then the final step evaluates the remaining routes and assigns the trips of an OD matrix to these routes.

During the route choice step, for at least some OD pairs, there are sections in a path with more than one parallel service offered and passengers can choose the one they perceive as the best, which leads to the common lines problem [5], often regarded as the most complex problem for transit assignment. De Cea et al. [6] proposed an alternative method of generating minimum cost routes, as well as the partial paths from different lines using a common route section with a nonlinear programming method. Following the ideas of Chriqui and Robillard [5], Spiess [7], Spiess and Florian [8] introduced a strategy for choosing an attractive route set of lines at boarding stop points. This idea was further extended by Wu et al. [9] who proposed the strategy-based asymmetric transit link cost function and the hyperpath concept. These models assumed no capacity limit for links of a network. Gendreau [10] was the first to formulate a general transit assignment with the capacity constraint, and following by Lam et al. [11], Cominetti and Correa [12] and Kurauchi et al. [13]. Lam et al. advanced a stochastic user equilibrium assignment model for congested transit networks with a solution algorithm that can simultaneously predict how passengers choose their optimal routes and estimate the total passenger travel cost [11]. Cominetti and Correa proposed a model based on the common lines paradigm, which was applied to general networks using a dynamic programming approach, and congestion was treated by means of a simplified bulk queue model [12]. Kurauchi et al. proposed a model in which passengers unable to board due to the capacity constraint were then routed through spill-links [13]. These algorithms considered the congestion situation by introducing a volume-dependent link cost function with the capacity constraint. Consequently the resulting equilibrium models could be solved by standard algorithms for convex minimization. Another important topic on frequency-based transit assignment is the common line problem based on the hyperpath approach. Nguyen et al. [14] investigated the application of a nested logit model to trip assignment on urban transit networks where every set of competitive transit lines is described by a hyperpath. Schmöcker [15] also employed the hyperpath concept to the transit assignment problem with the capacity constraint.

In general, the frequency-based transit assignment algorithm assumes that the passenger demand is constant within the specified time period of interest. The transfer time is not explicitly calculated but to be estimated based on the headway of the transit vehicle. This means that the impact of timetable is not considered, and the waiting time is usually assumed to be equal to the half of the headway.

On a schedule-based transit network, the assignment considers the exact timetable and therefore the procedure needs to model the spatial and temporal structure of travel demand. The resulting assignment would show explicitly the exact number of passengers apportioned to each scheduled vehicle. Recently, this method becomes more and more popular, Florian [16] firstly proposed a deterministic schedule-based transit assignment method and applied it to the EMME/2 software package, in which the weight factors and non-time-based cost elements in determining the optimal path were used to evaluate the feasibility of a path and its attractiveness, and the shortest path algorithm was employed to assign trips. Tong and Wong [17, 18] formulated a dynamic transit assignment model. In their model, passengers were assumed to travel on a path with minimum generalized costs. These algorithms could be applied over a period in which both passenger demands and vehicle headways are varying. Friedrich and Wekeck [19] constructed a transit path choice method using the branch and bound technique, which reduced further the computation time. Friedrich [20] made an extension of their algorithm from a single-day to a multiday situation, which allowed considering changes in supply and demand within the course of a multiday time period. Nielsen [21] developed a stochastic schedule-based transit assignment model considering the utility of different passengers and optimized the stochastic assignment model based on the method of successive averages (MSA) [22]. Nuzzolo also developed algorithms for the transit assignment problem [23, 24]. Xu et al. proposed the -shortest path searching algorithm in a schedule-based transit network [25]. This algorithm could be used in the flow assignment when the time-space path is taking part in the flow split between the OD pair. In all those algorithms developed, the attractive connection in a schedule-based network is not considered. Besides, the stochastic path choice behavior in the congested situation has not been studied.

Previous studies involved in flow assignment methods in the schedule-based transit network are extremely limited, let alone the consideration of capacity constraint in a stochastic user equilibrium (SUE) transit assignment model. In this paper, a schedule-based SUE transit assignment algorithm for a similar common line problem is presented. We consider the schedule-based transit network described in Friedrich and Wekeck [19]. In our work, however, we assume that passengers do not necessarily have full knowledge of the schedule of transit service. A stochastic user equilibrium assignment method with the congested situation is proposed, which is an extension of the work by Lam et al. [11]. The latter considers the problem in the context of a frequency-based transit network. The purpose of this paper is to formulate a model to determine exactly the load of vehicle on a transit line at a given time period. Moreover, we examine whether the passenger volume on a transit line exceeds the designed capacity.

This paper is organized as follows. In the next section, some useful concepts for a transit network are briefly reviewed. Notations and basic assumptions of the mathematical model are given. In Section 3, the attractive connection set is defined. In Section 4, a generalized travel cost function is formulated to choose the best routes between OD pairs on the schedule-based transit network firstly. Then a SUE assignment model is proposed, as well as its solution algorithm. The numerical example of this model is presented in Section 5 to illustrate the validity of the algorithm. Conclusions are given in Section 6 as well as the direction for future research.

#### 2. Concepts, Notations, and Basic Assumptions

##### 2.1. Concepts

We provide here an overview of terms used in this paper such as line, line section, and line route before embarking on a discussion of the common lines problem and SUE transit assignment. We adopt the definitions of these terms from the previous work: definitions of the transit line, transit arc, and line segment from Lam et al. [11], definitions of route segment, connection and connection segment from Friedrich and Wekeck [19].

A connection is a line that a passenger chooses to travel from his/her origin node to the destination node. In the schedule-based transit network, each connection is composed of origin node, destination node, walking link, transfer nodes, departure time, arrival time, in-vehicle time, transfer time, number of transfers, and the total travel time.

A connection segment is a portion of a connection which describes a part of a journey and is also endowed with a departure and arrival time, and which is the building block of a connection. In this paper, the connection segments using access and egress walk links would not be considered.

The example network (shown in Figure 1) used by Friedrich and Wekeck [19] is adopted here to explain the definition of line (segment), line route (segment) and connection (segment). In this example, the given network consists of a bus line and a train line, passengers traveling from origin A-Village to destination X-City may choose between direct bus connections and faster bus-train connections.

**Figure 1: **An example schedule-based transit network (Friedrich and Wekeck [19]).

Since a transit line is characterized by an initial stop node, a terminal stop node, length and running time, the connection segments can be calculated from a set of line sections. For the example network given in Figure 1, bus line 1 from node A-Village to station has three connection segments, that is, boarding and departing at node A-Village at 6:10, arriving at station at 6:22; or departing at 6:55, arriving at 7:07; or departing at 7:25 and arriving at 7:37. A given transit line with stations would include line sections and consequently include a total of connection segments (where *k* is the total number of vehicle runs). The connections of the example transit network of Figure 1 are shown in Table 1.

**Table 1: **Connections of example schedule-based transit network.

From the above example, we can conclude that in a schedule-based transit network a connection is a route path plus a series of time strategies, including the departure time, arrival time and transfer time. When an incoming bus is operating at its capacity level, passengers may choose not to board but opt to wait for the next one with successor connections. In this situation, we can call this attractive connection problem for a schedule-based transit network with capacity constraints. Namely, passengers choose their journey strategy at a station from an attractive connection set.

##### 2.2. Notations

:Set of OD pairs:An element of set :Passenger demand between OD pair :Set of attractive connections associated with OD pair :Index of connection:Set of connection segments of the attractive connections:Index of connection segment:Passenger flow on connection :Passenger flow on connection segment :Passenger overload delay, that is, the time that passengers spend on waiting for vehicle of another connection segment when they cannot board the first coming vehicle of the first connection segment because of insufficient vehicle capacity:Passenger overload delay on connection segment :Travel time on connection :Travel time on connection segment :Departure time of connection :Departure time of connection segment :Expected departure time of a trip:Arrival time of connection :Arrival time of connection segment :Generalized cost of connection : Generalized cost of connection segment :Analysis time span :Waiting time on connection :Waiting time on connection segment :In-vehicle time on connection :In-vehicle time on connection segment :Riding time on connection :Riding time on connection segment :Number of transfers of connection :Number of transfers of connection segment : The minimum (maximal) transfer wait time :Passenger overload delay on connection :Passenger overload delay on connection segment :Monetary cost of connection :Monetary cost of connection segment :A nonnegative function of , which represents the functions of difference between the real departure time and the expected departure time DTE:The vehicle capacity of transit line :0-1 variable, if connection *c* connects between OD pair , it equals to 1 and otherwise 0.: 0-1 variable, it equals to 1 if connection associating OD pair consists of connection segment , and 0 otherwise.

##### 2.3. Basic Assumptions

Assume that (a) the transit service considered has a schedule but passengers do not know exactly the schedule. The service behaves as if it was frequency based, (b) the OD demand is fixed, at any given time interval (e.g., the peak hour), and (c) all vehicles strictly operate under the sequence defined by the timetable without overtaking each other. (d) Other assumptions are drawn as Lam et al. [11].

#### 3. The Attractive Connection Set

De Cea and Fernandez [26] indicated that in a congested transit network, there exists more than one type of route segments between a given pair of nodes representing the set of desirable lines. However, in a schedule-based network, there would also be more than one type of connection segments which would result in an attractive connection set as described above. Different from the determination of different classes of route types of uncongested network by solving the hyperbolic common lines problem [26], an important process needs to be emphasized to determine the most attractive connection set. This will be discussed as follows.

According to the timetable, the frequency of a transit vehicle is fixed. Assume that the preceding vehicle would not be overrun, the set of attractive connections based on some specific rules could be determined. The algorithm used by Friedrich and Wekeck [19] is employed to build a connection tree. Every connection segment is described by departure time and arrival time , travel time , cost , and number of transfer . If connection *c* is made up of connection segments, the number of its transfers is . As shown in Figure 2 [19], let be the current processed connection segment from station to station , let be the new connection between the original station *A* and station *C* formed by adding *s* to some connection *c* arriving at *B*, finally let be the set of all known connections to stop . Connection segment is inserted into the tree as an successor of *c*, if and only if the following conditions hold.

**Figure 2: **Structure of connection.

(1)Temporal suitability: The connection segment departs from node *B* only after the arrival of connection *c* plus a minimum transfer wait time , and before the maximum transfer wait time has elapsed, namely. (2) Dominance: there is no known connection , such that (3) Tolerance constraints: none of the following rules are violated: