P systems are branch of bio-inspired computing, which takes inspiration from the structure and functioning of a living cell. Current research of P systems focuses mainly on their computational power, applications include biochemical and ecological modeling. In this paper we propose model of passenger flow in metro based on P systems. This model focuses on detailed description of passenger behavior, while retaining simple and robust in description of vehicle flow. Formal description of model is given and simulations using Prague Metro as an example with real traffic flow data from 2008 are presented. Some open problems are discussed and further directions of research are suggested.
? The paper has been completed within the project CZ.1.07/2.2.00/28.0078 InDOG
- Innovation of PhD Geoinformatics and Cartography study with support of
modern technological trends which is co-financed from European Social Fund and State
financial resources of the Czech Republic
which take the form similar to a chemical reaction: a → b, where a and b are
multisets of objects. When a rule is applied, all objects on the left side of a rule
are removed and objects on the right side of a rule are introduced into a system.
Application of rules is exhaustive, maximally parallel and non-deterministic.
For detailed description of P systems please consult [
Most research in the field of P systems focuses on computational power (e.g.[
Aim of the model is to accurately estimate numbers of passengers, who use the transportation system at given time. At every time step, numbers of passengers waiting at stations and numbers of passengers in trains are available. This information can be used to examine the performance of the transportation system and the occupancy of trains, for example in case, when a great number of passengers is introduced into a system, or when the schedule of trains is changed. Model can also be used in evacuation studies, when numbers of people in different parts of the transportation system are needed. On the other hand, this model is not suitable for examination of changes of behavior of passengers. It might be of interest to know, how long are passengers willing to wait for a delayed train, or if they rather wait for next train in case, that the current train is almost fully occupied. This kind of research questions requires agent-based modelling, where passengers will make decisions. P systems do not allow decision making – behavior of passengers is described using predefined set of rules, which do not change during the computation, and therefore passengers can not react to ongoing changes within the system.
Performance of a model is shown on an example of Prague Metro, which is simple network of three intersecting lines. Traffic flow data from 2008 are used in simulations.
The paper is structured as follows: in section 2, a formal description of model is given, in section 3, performance of model is examined, section 4 focuses on some problems, which were encountered during the analysis and future directions of research are suggested. Section 5 contains short conclusion. 2
There exist several levels of traffic modeling, ranging from macro-models,
describing traffic flow only in terms of populations of object, to micro-models,
where every individual object in the system is examined in detail [
Real world system consists of several components, which must be represented
in terms of P systems. Metro stations are considered as membranes. Network of
stations is represented as a graph, similar to neural P systems [
We believe this representation is very expressive – it is easy to see metro stations as membranes, which are entered and left by passengers – objects. Vehicles serve as membranes too – their function, same as function of living membranes – is to protect its content and serve as a mean of selective transportation (not all objects can enter the membrane and membrane can be entered only on specific occasions). This expressiveness (compared to description using i.e. set of differential equations) together with massive parallelism of model – are two main advantages of P systems for transportation modeling.
Formally, P systems for passenger flow simulation in public transportation networks are following construct: Π = (O, l, syn, R), (1) where: – O = {people{a,...,b}, empty}|a, b ∈ {l − {train1, . . . , trainn}}} is a set of objects, where people represents passenger and empty represents empty seat inside a train. To each passenger people, a sequence {a, . . . , b} is assigned. This sequence is an ordered list of all stations, which passenger visits on his route from station a (current station) to station b (end station of an individual route). – l = {1, . . . , k, tram1, . . . , tramn} is a set of membranes with k metro stations and n trains. – syn ⊆ {(i, j, t)|i, j ∈ {l − {train1, . . . , trainn}}, i 6= j, t ∈ N} is a set of synapses, representing topology of a network. Each synapse consists of two labels of metro stations i, j and time t necessary to transport train from station i to station j. – R is a set of rules, which describe the behavior of both membranes and objects inside them. Rules are assigned to membranes, therefore different membranes have different sets of rules and same object in two different membranes can be evolved using different sets of rules. In next section, following notation will be used: train going to station k will be denoted by [k ]k, hence k is label of next, not current station. Each train can be in two states stopped or moving. Membrane polarization is used to distinguish between the two, therefore moving train to station k is denoted as [k+ ]+. Metro stak tion with label m will be denoted as (m )m. Following set of rules is used to describe the evolution of the system. 1. people{a,b,...,x} [a empty ]a− → [a people{b,...,x} ]a− is rule describing passenger entering a train. Passenger, whose next stop is a enters a train going to station a, if there is an empty seat (empty) and the train is stopped (negative polarization). Once inside the train, passengers next station changes to b. 2. [a people{a,b,...,x} ]a− → [a people{b,...,x} ]a− is rule describing passenger staying inside a train. Passenger, whose next stop is a and who is already in a train going to a, stays inside and his next stop changes to b. 3. [a peopleNULL ]a− → [a empty ]a− describes situation, where passenger inside a train has no next station, hence is in his final destination and leaves the system. An empty object is created inside a train. 4. [a people{b,c,...,x} ]a− → [a empty ]a− people{b,c,...,x} describes passenger leaving the train at transfer station. If passenger, whose next stop is b, is inside train going to a, he leaves the train and empty seat appears inside a train. The passenger stays at the current station. 5. (i [j ]j+ )i −→t (j [k ]k− )j is rule describing movement of trains inside a network. Moving train in station i, whose next station is j, is moved to station j, its next station is changed to k and the train stops. 6. (i [j ]j− )i → (i [j ]j+ )i changes train from stopped to moving state. 7. (i [NULL ]N−ULL )i → (i )i is rule describing situation, where train reaches its final destination (i.e. does not have next stop). Such a train is removed from the system. 8. (i )i → (i [a ]a− )i is rule describing generation of trains in start stations – train going to station a is created in station i. The trains is stopped, therefore passengers can enter the train immediately. 9. (i )i → (i people{a,b,...,x} )i describes arrival of people to the station i.
For each passenger, who arrives at the station, a sequence of stations to visit a, b, . . . , x is generated. 3
Application of model is demonstrated on example of Prague Metro. This transportation system consists of three lines, labeled A (Dejvick´a – Depo Hostivaˇr), B (Zliˇc´ın – Cˇ erny´ Most) and C (Letnˇany – H´aje), which intersect at three stations (A–B - M˚ustek, A–C - Muzeum, B–C - Florenc). Prague Metro consists of 53 stations in total and approximately 1.5 millions of people are transported every day. Trains are in service from approximately 4:40 a.m. to 24 a.m. (midnight) and their frequency changes in time. In five-year periods, survey of passenger occupancy is performed with last survey taking place at 2008. Prague Public Transit Company provided detailed data about transit intensity, which were used in this case study. We selected Prague Metro for its importance as a mean of transportation and also relative simplicity of the system, which allows well-designed simulations.
Cˇern´y Most Zliˇc´ın
N´amˇest´ı m´ıru
Current (December 2012) schedule of trains was used as basis for
generation of trains at start stations. Main problem of public transport modeling is
estimation of number of passengers traveling between each pair of stations.
Fortunately, this information was provided by Prague Public Transit Company in
form of so called Origin-Destination Matrix. Intensity of transport varies during
day, which leads to problem with estimation of this intensity. Due to unknown
trend of intensities during a day, the quantity was estimated using train
schedule. It was assumed, that frequency of train arrivals at given station corresponds
with amount of people transported. Kernel density (Epanechnikov kernel,
bandwidth=50 minutes) of train frequency was estimated and used as a basis to
calculate numbers of passengers entering the system at given time. Figure 2
shows estimated intensity. Values on y axis represent estimated intensity of
process, generating ”dots” – times of arrival of trains on x axis. We assume, that the
process generating times of arrival of trains is in fact the transportation demand
of passengers and therefore estimated intensity of this process can be used to
calculate the numbers of passengers using the system at given time. Maximal
capacity of train was set to 1363, which is occupancy of train 81-71, a standard
train in Prague Metro [
Frequence of train arrivals at Dejvická station y it s n e D 2 1 0 0 . 0 8 0 0 0 . 0 4 0 0 0 . 0 0 0 0 0 . 0 0 200 400 600 800 1000 1200
1400 time (minutes from 0:00)
Four interesting variants of stations were identified in the system and further examined: 1. Final stations – Dejvick´a, Depo Hostivaˇr, Ha´je, Letnˇany, Zliˇc´ın, Cˇ erny´ Most 2. Transfer stations – M˚ustek, Muzeum, Florenc 3. Stations between two transfer station – N´amˇest´ı Republiky and Hlavn´ı Na´draˇzi 4. Station next to one transfer stations – Vltavsk´a, Kˇriˇz´ıkova, Na´mˇest´ı M´ıru,
I.P.Pavlova, N´arodn´ı Tˇr´ıda, Staromˇestsk´a 3.1
Final stations are unique, because only one direction of the train line is served. Simulation showed periodic behavior, where after train departure, no passengers ale left at station (Figure 3). This means, that the transportation demand is fully served.
Dejvická station 5:00 − 7:00
Time (minutes from beginning) There are three transfer stations, where always two lines intersect. These stations are very frequently used and numbers of passengers waiting for train show also cyclic, but more irregular pattern. Moreover, at the beginning of the study period, there is elevated number of passengers waiting for the train (Figure 4). It seems, that the system is not able to handle the demand of passengers for short period of time, but later, the frequency of trains increases and the ”wave” of waiting passengers is dissolved. We attribute this behavior not to design of the model, neither we think it represents real behavior of the system, but assume it is caused by incorrectly estimated passenger flow intensity. We will discuss this problem later in chapter 4. 3.3
Both N´amˇest´ı Republiky and Hlavn´ı Na´draˇz´ı stations show similar, but even more evident pattern as transfer stations. The periodic behavior is more regular and ”peak” at the beginning of the study period is more distinctive. Due to high frequency of trains, the numbers of passengers waiting are lower than at most of the other stations (Figure 5).
Muzeum station 5:00 − 7:00 0 0 2 1 0 0 2 0 0 20 40 60 80 100 120 A rather regular periodic pattern with two peaks can be observed at stations next to transfer stations (Figure 6). Rapid rise in number of waiting passengers was not observed at the beginning of the study period, also the number of passengers returns to values close to zero, which indicates, that the schedule is appropriate to the transport demand. The position of peaks (irregular or regularly spaced) is caused by train schedule and is not caused by stations being immediately after transfer station. 4
Possible incorrect performance of the model can result from two types of errors: errors in design of the model and incorrect input values.
Input values of the model are traffic demand and train schedule. Numbers of passengers traveling between all pairs of stations were derived from transportation survey of passenger occupancy and should accurately describe the system. However, only sum of all passengers was available for every station, dynamics of the demand during the day is unknown.
Issue with elevated numbers of passengers at the beginning of the study period
Hlavní nádraží station 5:00 − 7:00 0 0 2 s r ngee 150 s s a frpo 001 e b uNm 05 0 0 20 40 60 80 100 120 we attribute to incorrect estimation of passenger demand quantity. Different estimates (using different kernels and bandwidths) were examined, however none of them led to results, which both copied global trend and did not produce elevated numbers at the beginning. Correct estimation of traffic demand is crucial step and our next research will be pointed at this direction.
The movement of trains is ruled deterministically using real schedule, obtained from world wide web. In reality, this schedule will be rarely kept, therefore and arbitrary constant can be added to travel time between two consequent stations to account for train delays. This time constant should be preferably generated randomly from known distribution of time delays.
Errors in the design of the model can be represented by ommiting important rules in description of the model. Presented model focuses on more detailed description of passenger behavior, while remaining brief in description of vehicle flow.
Passengers, who exit the train are immediately removed from the system, while in real system, they remain at the station for some time. While not important for examining the capacity or occupancy of traffic system, this might be an issue in i.e. evacuation studies. Extending system by new object - passenger, who no longer participates in transportation, and extending current rules would incorporate this extension, while keeping the model robust and simple.
Náměstí Míru 5:00 − 7:00 0 2 1 0 0 1 0 2 0 0 20 40 60 80 100 120 One more possible issue, which is inherent to P systems, should be mentioned. Objects in P systems are not agents, do not posses (artificial) intelligence and do not make decisions. Their behavior is ruled by predefined set of rules, which can be probabilistic and resemble decision making, but essentially, decisions in P systems are not possible and therefore using proposed model for behavioral research of passenger choices would be problematic (i.e. research question ”How long are passengers willing to wait for delayed train” is not appropriate for P systems, because requires passengers to make decisions).
The validity of model will be further examined and subjected to complex simulations. Case study only examined numbers of passengers waiting at stations, however occupancy of trains can be of interest for traffic management as well as examination of time, which is spend by certain groups of passengers in the system. Proposed model is discrete both in time and processing units (every passenger is considered an individual element in the system), therefore can be suitable for more sophisticated simulation. Research questions, which will be explored in the future are: How long time delays of trains are still manageable and which length of delays will cause the system to collapse? In the case of change of travel behavior of passengers, which changes could be made to increase the effectivenes of the system? If an increased number of passengers is introduced to the system (i.e. 1000 sport fans going to the game), how will the system respond? In this paper, a P system based model for passenger flow simulation in public transport systems was proposed. Formal description of model was given and case study using Prague Metro network as example was performed. The case study did not reveal any errors in design of the model, however it became apparent, that correct estimation of numbers of passengers using system at given time is necessary. Cyclic patterns in numbers of passengers waiting at the stations were observed. Open problems associated with usage of P systems for traffic flow simulation were discussed and directions of future research were suggested.