Journal of Industrial Engineering and Management

 

Simulation and evaluation of urban rail transit network based on multi-agent approach

Xiang-Ming Yao, Peng Zhao, Ke Qiao

School of Traffic and Transportation, Beijing Jiaotong University (China)

Received November 2012

Accepted February 2013

 

Yao, X,M., Zhao, P., & Qiao, K. (2013). Simulation and evaluation of urban rail transit network based on multi-agent approach. Journal of Industrial Engineering and Management, 6(1), 367-379. http://dx.doi.org/10.3926/jiem.686

---------------------

Abstract:

Purpose: Urban rail transit is a complex and dynamic system, which is difficult to be described in a global mathematical model for its scale and interaction. In order to analyze the spatial and temporal characteristics of passenger flow distribution and evaluate the effectiveness of transportation strategies, a new and comprehensive method depicted such dynamic system should be given. This study therefore aims at using simulation approach to solve this problem for subway network.

Design/methodology/approach: In this thesis a simulation model based on multi-agent approach has been proposed, which is a well suited method to design complex systems. The model includes the specificities of passengers’ travelling behaviors and takes into account of interactions between travelers and trains.

Findings: Research limitations/implications: We developed an urban rail transit simulation tool for verification of the validity and accuracy of this model, using real passenger flow data of Beijing subway network to take a case study, results show that our simulation tool can be used to analyze the characteristic of passenger flow distribution and evaluate operation strategies well.

Practical implications: The main implications of this work are to provide decision support for traffic management, making train operation plan and dispatching measures in emergency.

Originality/value: A new and comprehensive method to analyze and evaluate subway network is presented, accuracy and computational efficiency of the model has been confirmed and meet with the actual needs for large-scale network.

Keywords: urban rail transit network, agent-oriented modeling, dynamic passenger flow distribution, decision support

---------------------

1. Introduction

Urban rail transit has played a key role to people mobility. With expansion of network, it is more important for providing a convenient, secure and economical transport by collaborative organization. As the foundation and core for transportation operations, spatial and temporal characteristics of passenger flow distribution are significant for making operation plans, collaborative organizations, and adjustment in emergency and improvement of network bottlenecks. However, it is very difficult or even impossible to adopt a global mathematical model to make new transportation solutions for such system due to its scale and complexity. Thus, we use computer simulation as a solution for analysis and evaluation of these complex systems.

There are many researches in the field of passenger flow distribution, which mainly focus on the static distribution and can’t reflect the interactions among passengers, trains and environment. Under the condition of one-ticket transfer, Xu, Luo and Gao (2009) puts forward a practical passenger flow distribution model considering multi-route choice, which meets the passenger’s psychology of minimum cost and reflects the fact of path-selecting multiplicity, then proposes an algorithm for available path searching based on depth-first in the graph theory. Si, Mao and Liu (2007) propose a traffic assignment model taking into consideration of travel time and times of transfer influencing the passenger flow assignment pattern, combining with the seamless transfer operation of the domestic urban railway traffic. Based on schedules and under train capacity constraints, Agostino, Umberto and Luca (2012) present a schedule-based dynamic assignment model for transit networks, which takes into account congestion through explicit vehicle capacity constraints. Nguyen, Pallottino and Malucelli (2001) improve the framework of assignment problem which considers the leave time and route choice dimension of rail transportation. Poon, Wong and Tong (2004) adopts a model for crowded network based on timetable, use simulation method for solving the problem. As these static transit assignment models could not reveal the bottleneck induced congestion problem and are not able to properly evaluate the transit network under dramatically changing network conditions (e.g. passenger arrival rate and loading of transit services) during the period of analysis (Schmoecker, Bell & Kurauchi, 2008). So they are commonly adopted for the strategic and long-term planning and evaluation.

It is difficult to make a global mathematical model to reflect the interactions between trains and passengers for its dynamic and complex. With the development of computer simulation, a growing number of simulation models have been applied to traffic analysis and evaluation. A micro simulation model has been proposed for road traffic to analysis the network through single vehicle moving and intersecting (Shang & Lu, 2006). Meignan and Simonin (2007) adopt a multi-agent approach to describe bus network as behaviors of numerous autonomous entities such as bus and travelers, through interaction between the main components to reproduce the passengers’ travel process of entire network, from passenger loads of network and waiting time to evaluate the operational efficiency. However, using simulation to study the dynamic passenger flow distribution for urban rail transit network is still lacking. In this paper, we will adopt a multi-agent simulation model to describe the entire subway system, including the processes of passenger walking in station, waiting to get on and off, transferring and exiting, which can well describe the whole process of passengers travelling in network. In addition, this meets the computation efficiency for large-scale network.

This paper is organized as follows: After a presentation of our simulation model in section 2, the implementation of this model and a real case study are drawn in section 3.Then, a conclusion and some perspective are presented in Section 4.

2. Agent-oriented modeling

As presented before that urban rail transit is a complex and dynamic system, including multiple components: passengers, stations, trains, sections, etc. This complexity is due to the interactions in different components. The multi-agent approach is a well suited method to design such complex system. We see every component in the system as autonomous entity, which called agent and interact to deal with local or global tasks. In this section we will adopt a multi-agent simulation model to describe the urban rail transit network, and focus on the basic and core agent of passenger.

2.1. Framework of simulation model

A multi-agent system (MAS) is defined as a set of interaction agents, two types of MAS can be defined following the agent architecture which is used: deliberative and reactive architecture. Deliberative agents have generally a symbolic representation of their environment and cooperate thanks to high level communication protocols (Rao & Georgeff, 1995). At the opposite, reactive agents do not have representation of their environment. They act following their perceptions, which are very limited. Reactive agents can cooperate and communicate through their interactions with the environment (called indirect communication). As a consequence, such reactive systems present some global intelligent behaviors that result from the numerous interactions between agents and their environment (e.g. self-organization and emergent phenomenon) (Ferber, 1999). The model we present for Urban rail transit relies on the reaction approach. Passengers and trains are considered as deliberative entities and other components such us stations and sections are describe as environment. Interactions of main agents are shown in figure 1.

Figure 1. Interactions of main agents

The environment, where passengers and trains move, is the composition of train running network and passenger travelling network. In our case, the environment is not only a shared common space where agents are loaded, which exhibits dynamic properties as traffic constraints. The main role of environment is to constraint perceptions and interactions of agents. For example, passenger agents and train agents can interact only when they are located at the same stop. These constraints are provided by the environment.

The passenger agent is the core entity of this system, which has a strong adaptability and intelligence. It can achieve all process of a passenger travelling in network, such as entering station, waiting for train, and transferring from one line to another; even they can change their behavior under traffic policy changing. Whether the characterizations of the behavioral model are accurate and intelligent or not directly determine the accuracy of simulation results.

The train agent also is a move agent in system, which runs according with operation routes and timetable. The main purpose is to load passengers from one station to another, control the process of passengers boarding and alighting.

2.2. Passenger generated rules

In the MAS, passenger is seen as independent agent, so how to generate these agents is very important. According to practical needs we can generate different type of passengers mainly through methods as follows:

-Generating random passengers: As it is difficult to predict or know passenger flow structure of network, we can generate passengers randomly. The number of passengers entranced station and the OD information of passenger are generated by some probability distribution such as normal distribution.

-Generating passengers with OD table: The flow of Urban rail transit is relatively stable, so we can analysis the passenger flow law as well as passenger flow structure (OD structure) based on historical data, and then generate passenger agents obeyed this kind of structure.

-Generating passengers with metro card data from AFC (Auto Fare Collection) system: The card data contains accurate passenger’s entrance time, origin and destination station, card type and so on. So this is the most accurate way to generate agents.

2.3. Passenger route choice model

Passenger route choice is divided into two processes: a feasible path searching and path selection. It is difficult to achieve real-time path searching for single travelers by restrictions due to network scale and the number of travelers, so this article combines off-line path searching and on-line path selecting. Feasible paths of each OD are searched in the network while initializing the simulation. When the passengers generated, they can find their own path in the path collection according to their travel information and attributions. Under normal circumstances, once a passenger selects his own path, the path will not change through the entire travel process. If there is a failure of network or transport organization changing caused by emergencies, the affected passengers will re-select their route, then path changing behavior occurred.

Generally passengers choose the route with the least cost. However, due to the complexity of network, the judgment of "shortest path" may appear differently. Route choice behavior has a certain degree of randomness in particularly with the increase of loop line. The route choice model based on probability fits more the behavioral characteristics of travelers. Therefore in this thesis we assume that the random error obeys the distribution of Gumbel. We build a route choice model based on Logit model, the probability of a passenger to select the n_th path in OD pair rs is as follows:

 

p_n^rs: The probability of a passenger to select the n_th path in OD pair rs;

V_n^rs: The travel utility of the n_th path in OD pair rs;

C_n^rs: The comprehensive cost of the n_th path in OD pair rs;

e_n^rs: The random error of the n_th path in OD pair rs;

Y_n^rs(t): The additional cost of the n_th path for congestion, to characterize the behavior of passenger route changing in crowded conditions, during simulation, we need to update the impedance values of sections with certain intervals of simulation clock. We use BPR formula which has a broad use in urban transit to reflect the crowded situation.

Occurrence of unexpected events not only cause inconvenience to passengers, but also make troubles for traffic operations. Once stations and sections suffer a temporary breakoff due to emergencies, passenger’s route choice behavior will change greatly. According to different situations, the affected passengers are often divided into three categories: delay passengers, detour passengers and loss passengers. Delay passengers and detour passengers will continue to travel in network, the loss passengers will give up to ride because delay time or bypassing distances is too long (Ling & Xu, 2011).

Considering the complexity of passenger behavior in emergencies, we simplify that delay passengers and detour passengers will change to re-select the "shortest" path from current station to their destination and loss passengers will exit from current station directly.

2.4. Passenger transfer queue model

The behavior of passenger walking in station is very complex; there have lots of researches using micro-simulation approach. Our work mainly focuses on passenger flow distribution of network, so is difficult to take into account of passenger micro-behaviors in station. We propose a simple queue model to describe passenger walking in station. The queues include: enter queue, wait queue, remain queue (failure to board passengers), get off queue, transfer queue (if station is a transfer station), and exit queue. The process of passenger walking in station is simplified as tourists transfer from one queue to another queue. Transfer queue model is as follow:

Figure 2. Queue models of passengers walking in station

2.5. Passengers get on and off model

When a train stops at platform, train agent will “inform” on-aboard passengers of the stop information, such as station name and station type. Then on-board passengers decide whether to get off or not according to their OD information and selected path. At the same time, waiting passengers get train information, such as direction and next stop and then decide whether to get on or not. These two processes are complied with the principle of “first alight then aboard”.

(1) Passengers get off model

-Step1: Train agent “informs" on-board passengers of the stop’s information;

-Step2: The passengers determine whether to get off or not according to their OD information and selected path;

-Step3: Transfer passengers who will get off from passenger queue in train to exit queue or transfer queue according to their purpose;

-Step4: The process of passenger getting off is ended.

(2) Passengers get on model

-Step1: After train stops, the train agent will “informs” waiting passengers on platform of the train’s information (direction and next-stop) in order to help travellers decide whether to get on or not;

-Step2: The passengers who were failure to get on last train will have a priority to get on train, so they are added to queue in train under the train’s capacity constraint;

-Step3: Add other waiting passengers who want to get on to passenger queue in train also under the capacity constraint;

-Step4: Transfer passengers who can’t get on from waiting queue to stranded queue, and then they need to wait for next train.

-Step5: The process of passenger getting on is ended.

 

3. Simulation and evaluation

 

Considering the previous specification of agent-oriented simulation model, we develop a dynamic simulation system (named URT-DPSS) for urban rail transit to analyze and evaluate the operation effectiveness and status of network. In this section, we describe the simulation software firstly and then present a case study.

 

3.1. An overview of the simulation system

 

The proposed model has been entirely implemented in a decision support system (figure 3) dedicated to the analysis and evaluation of subway network. The system is developed in C# language and has several modules, including basic data management, graphics control, train operation control, generating passengers, passenger walking in station control, real-time monitoring, and statistics and analysis module. The main components and features are as follows:

Figure 3. Screen shot of URT-DPSS system

-Graphics control module is to visualize and edit network, including graphical display and real-time passenger flow information display;

-Train operation control module is to control train running with established schedules and timetable, including parking, running in section and control passengers getting on and off;

-Generate Passenger module is to generate passengers according to historical passenger flow data or with other rules presented in section 2.2;

-Passenger walking control module is to control passengers walking in station, including walking from entrance door to platform, transferring from one line to another;

-Real-time monitoring module is to monitor specific station or train in real-time for a better control and analysis;

-Statistics and analysis module is to analyze simulation data and graphical display.

 

3.2. Case study

 

The simulation system has been applied for analysis and evaluation of a subway network of Beijing city. By the year of 2011 the transit network includes 12 lines with about 300km. We select a day of December, 2011 to simulate, passenger flow data comes from the AFC system, which includes individual traveller’s information (such as entry time and OD information). The network tested in the study just contains lines connecting with others as shown in figure 4. The results show that the above studied model can well depict passengers’ traveling process in station and network. Moreover, it meets the large-scale network simulation efficiency. The basic information of simulation is shown in table 1.

Table 1. Basic information of the simulation

A significant number of measures have been produced by this simulation system to support the collaborative transportation operations for organizers. We will focus on some representative results: load passengers of network, inflow and outflow of station, load passengers of train, board and alight passengers at each stop, remainder passengers and section passenger flow.

The load passengers of network correspond to the number of passengers travelling on network at a given time, including passengers in station. Figure 5 plots the load passenger distribution from 7:00 to 12:00 in 15 minutes interval. We can see the maximum appears in 8:30-8:45. The indicators will help dispatchers to determine appropriate number of trains and headway time.

Figure 4. Tested subway network of Beijing

Inflow and outflow means the number of passengers entering and exiting station. Figure 6 shows the flow distribution of BJNZ station. Through the number of inflow and outflow passengers, we can find high-load stations. If passenger flow exceeds station’s capacity, some measures must be taken to lower the pressure, such as controlling the number of passengers entering station.

Figure 5. Load passengers of network        Figure 6. Inflow and outflow of BJNZ station

Figure 7 shows on-board passengers of a train (train number is 1069) in line1 at each section, which reflects the utilization of train’s transport capacity. This measure can be used to locate overload trains and unused trains. Then, some adjustment of train diagram can be adapted to reduce or avoid overload problems.

Figure 8 shows the number of boarding and alighting passengers of a train (train number is 1069) at each stop. We find that passengers at FXM station, XD station, DD station and JGM station are more than others, because they are transfer stations. This kind of statistical data can provide very basis information for dispatchers to make the stopping station plan in emergency.

Figure 7. Load passenger of a train   Figure 8. Boarding and alighting passengers at stops

Passengers may be difficult to get on train in peak hours by transport capacity constraint and have to wait for next train, which exists regularly in the Beijing subway. This phenomenon brings not only inconvenience to passengers but also security risks to station organization. Figure 9 describes the remainder passengers in XD station. Therefore, we need to take appropriate measures to suppress this phenomenon, such as adjustment of headway time or controlling inflow passengers.

Figure 9. remainder passengers at XD station      Figure 10. Section flow of Line 1

Headway time usually is required to meet the transport needs of the maximum section flow. Figure 10 shows the section flow of Line1, the maximum section flow is between JSBWG station and FXM station, which can help dispatcher to adjust headway time.

4. Conclusions

In this paper, a multi-agent simulation method for urban rail transit network has been presented. We have shown that an agent-based approach allows designing such autonomous, dynamic and interacting system. The model combines the process of passenger walking in station and travelling in network, which can well describe passengers’ entire travelling process in network to obtain the spatial and temporal characteristics of passenger flow. For the verification of the validity and accuracy of this model, we developed an urban rail transit dynamic passenger flow simulation tool. Using real passenger flow data of Beijing subway network to take a case study, results show that our simulation tool can be used to analyze and evaluate the operation effectiveness of network well.

The main perspective of this work is to provide support for traffic management departments. And they are useful to make train operation plan and dispatching measures in emergency. Forthcoming works will consider how to give decision support for operators more comprehensively.

Acknowledgment

The authors gratefully thank the traffic management departments and this research was supported by the Fundamental Research Funds for the Central Universities (2012YJS071).

References

Agostino, N., Umberto, C., Luca, R. (2012). A schedule-based assignment model with explicit capacity constraints for congested transit network. Transportation Research Part C, 20, 16-33. http://dx.doi.org/10.1016/j.trc.2011.02.007

Ferber, J. (1999). Multi-agent Systems: An Introduction to Distributed Artificial Intelligence. Addison Wesley, ISBN: 0-201-36048-9.

Ling, H., Xu, R.H. (2011). Calculation Method of Emergency Passenger Flow in Urban Rail Network. Journal of Tongji University (Natural Science), 10, 1485-1489.

Meignan, D., & Simonin, O. (2007). Simulation and evaluation of urban bus-networks using a multi-agent approach. Simulation Modelling Practice and Theory, 15, 659-671. http://dx.doi.org/10.1016/j.simpat.2007.02.005

Nguyen, S., Pallottino, S., & Malucelli, F. (2001). A modeling framework for passenger assignment on a transport network with timetables. Transportation Science, 35, 238-249. http://dx.doi.org/10.1287/trsc.35.3.238.10152

Poon, M.H., Wong, S.C., & Tong, C.O. (2004). A dynamic schedule-based model for congested transit networks. Transportation research Part B, 38, 343-368. http://dx.doi.org/10.1016/S0191-2615(03)00026-2

Rao, A.S., & Georgeff, M.P. (1995). Bdi agents: from theory to practice. Technical Report, Australian Artificial Intelligence Institute.

Schmoecker, J.D., Bell, M.G.H., & Kurauchi, F. (2008). A quasi-dynamic capacity constrained frequency-based transit assignment model. Transportation Research Part B, 42(10), 925–945. http://dx.doi.org/10.1016/j.trb.2008.02.001

Shang, L., & Lu, H.P. (2006). Urban Microscopic Traffic Simulation System and Its Application. Journal of System Simulation, 18(1), 221-224.

Si, B.F., Mao, B.H., & Liu, Z.L. (2007). Passenger Flow Assignment Model and Algorithm for Urban Railway Traffic Network under the Condition of Seamless Transfer. Journal of the China Railway Society, 29, 12-18.

Xu, R.H., Luo, Q., & Gao, P. (2009). Passenger Flow Distribution Model and Algorithm for Urban Rail Transit Network Based on Multi-route Choice. Journal Of The China Railway Society, 31, 110-114.