Walking-distance introduced queueing model for pedestrian queueing system: Theoretical analysis and experimental verification
Introduction
Pedestrian queueing system, which we see at cash registers in super markets, ticket-vending machines in stations, and automated teller machines in banks, is one of the important themes in the field of crowd dynamics, pedestrian modeling, and transportation for the following reasons. Firstly, pedestrians become stressful when they wait at a queue for a long time. Secondly, long waiting time in one queueing system affects the starting time of other events, for instance, if some passengers take a long time to pass a security check in an airport due to a long waiting queue, the departure time of the flight may delay (Kazda and Caves, 2007). Lastly, a long queue prevents smooth movement of pedestrians and encourages forming a jam around it. Huge queues are formed at gas stations in Japan after the Great East Japan Earthquake on March 11th, 2011. These queues occupied one side of the streets and interrupted the traffic. (Pedestrian and vehicle queue are considered as similar phenomena since both of them consist of self-driven particles (SDPs), which have excluded volume and move without external forces.) Therefore, we investigate some methods which improve the efficiency of queueing systems by constructing and analyzing a model.
In order to develop a model of pedestrian queueing system, we need to consider two things. One is arrival and departure of pedestrians as a stochastic process, and the other is movement of pedestrians as SDPs. Fortunately, the both topics, i.e., queueing process and pedestrian dynamics, have been vigorously studied by many researchers so far.
The results of research on arrival and departure dynamics as a stochastic process (queueing process) is organized as Queueing Theory (Bolch et al., 1998, Kingman, 2009). Queueing process has been considerably studied since Erlang started designing telephone exchanging system in Erlang (1909). In Erlang (1917), he developed the theory of the loss system, which significantly contributed to the progress of telephones and electric communication systems. After his study, Kendall presented his first paper (Kendall, 1951) and the research on queueing process has been accelerated in the middle of twenty century. Many important results such as Kendall’s notation (Kendall, 1953), Burke’s theorem (Burke, 1956), Jackson networks (Jackson, 1957), and Little’s theorem (Little, 1961) have been obtained. Nowadays, queueing process in one of the basic model to study social systems such as the Internet (Kasahara, 2002, Mukherjee and Manna, 2005, Hassin, 2009) and vehicular and pedestrian traffic systems (Helbing et al., 2005, Helbing et al., 2006, Viti and van Zuylen, 2010). Human behavior is also analyzed by applying it (Oliveira and Barabási, 2005, Barabási, 2005).
In recent years, pedestrian dynamics has been studied by development and analysis of models (Chowdhury et al., 2000, Helbing, 2001, Nagatani, 2002, Schadschneider et al., 2010). There are mainly three kinds of models, namely, macroscopic model, microscopic space-continuous model, and microscopic space-discrete model. In macroscopic model (Helbing, 1992, Piccoli and Tosin, 2009) dynamics of pedestrians is described by modified differential equations of fluid dynamics. Effect of interaction between pedestrians is introduced by additional terms in the equations. In microscopic space-continuous models, pedestrians are represented by particles or agents, and their movement is governed by coupled differential equations which describe interaction between pedestrians. Social force model (Helbing and Molnár, 1995, Helbing et al., 2000) is one of the most successful models in this category. Characteristic collective phenomena such as arching at an bottleneck and lane formation in counter flow are reproduced by these models. Microscopic space-discrete models as represented by floor field model (Burstedde et al., 2001) and lattice gas models (Muramatsu et al., 1999) using stochastic cellular automata (CA) Wolfram (1994), where time and space are discrete, also reproduce the collective phenomena of pedestrians dynamics. Extended models have succeeded to introduce and simulate various features of pedestrian dynamics such as conflict and turning (Kirchner et al., 2003, Yanagisawa et al., 2009), ability of anticipating other pedestrians’ movement (Suma et al., 2012), and proxemic effect (Ezaki et al., 2012). Multi-agent systems (MASs) (Ferber, 1999) include both microscopic space-continuous model and microscopic space-discrete model. They can implement complex rules of movement, and reproduce pedestrian characteristics and behaviors in detail. For instance, the heterogeneity of pedestrians and spatial structures of the environment are well studied in Bandini et al. (2002), and transition of pedestrians’ state by the external signals is considered in Bandini et al. (2009). Furthermore, Vizzari et al. (2008) develops an effective 3D visualization method for simulation in large scale, which comprise several hundreds of pedestrians, and Antonini et al. (2006) performs calibration of the model using video data.
In this paper, we develop a queueing model for pedestrian queueing system by combining a queueing model in the queueing theory and a microscopic space-discrete model in pedestrian dynamics. Our combination model is consistently organized since both models employ stochastic dynamics. It reveals the efficiency of two common queueing systems, which are a parallel-type queueing system (Parallel) and a fork-type queueing system (Fork) by comparing mean waiting time (MWT). Schematic views of Parallel and Fork which are modeled by using the queueing theory, i.e., a normal Parallel (N-Parallel) and a normal Fork (N-Fork), are depicted in Fig. 1.
According to the queueing theory, MWT in N-Fork is always shorter than that in N-Parallel. However, N-Parallel and N-Fork do not reflect the effect of walking distance from the head of the queue to the service windows. The effect of the distance may be possible to neglect in Parallel and small Fork; however, it significantly influences on the MWT of pedestrians in large Fork such as an immigration inspection floor in an international airport since walking distance is very long. Therefore, we analyze Parallel and Fork modeled by our walking-distance introduced queueing model in detail, which were primitively analyzed in Yanagisawa et al. (2008). We focus on a walking-distance introduced Parallel (D-Parallel, Fig. 2) and a walking-distance introduced Fork (D-Fork, Fig. 3). We show, through simulation and theoretical analysis, that MWT becomes shorter in D-Parallel than D-Fork when sufficiently many pedestrians are waiting in the queue and the ratio of walking time to service time is large. Besides, two enhanced Forks which enable us to decrease the MWT in D-Fork are also investigated.
Many researchers consider that validity of pedestrian models should be verified by experimental and observational data. In spite of the difficulty of experiment and observation of pedestrians, data have been continuously accumulated through the coordinated efforts of the researchers, and some of them are collected at the ped-net online database (2008) and the references there in. Recently, the parameters of the models are calibrated by the data, and more realistic models are constructed (Seyfried et al., 2006, Yanagisawa et al., 2012). In order to develop a validated model, we also perform queueing experiments with real pedestrians, whose results are only partially utilized in Yanagisawa et al. (2011), and examined our results obtained from simulation and theoretical analysis.
This paper is organized as follows. In the next section we briefly review the normal queueing models. Then we introduce the walking-distance introduced queueing model in Section 3 and approximately obtain an expression of MWT and some other physical quantities in Section 4. Physical quantities of N-Parallel, N-Fork, D-Parallel, and D-Fork are compared in detail in Section 5. In Sections 6 Combination of D-Parallel and D-Fork, 7 Enhanced Fork-type queueing systems, combination of D-Parallel and D-Fork and two enhanced Forks are investigated, respectively. Furthermore, our theoretical results are verified by queueing experiments with real pedestrians in Section 8. Finally our study is summarized in Section 9.
Section snippets
Normal queueing model
Let us briefly review the normal queueing models, i.e., N-Parallel and N-Fork. N-Parallel (Fig. 1a) is a collectivity of M/M/1 queues, which is a fundamental model in the queueing theory. A pedestrian arrives at the queueing system with the rate λ (>0) and randomly chooses one queue from queues. The pedestrian at the head of each queue, who receives service, leaves the system with the rate μ (>0). N-Fork (Fig. 1b) is as same as M/M/s in the queueing theory. The pedestrian at the head of
Walking-distance introduced queueing model
In reality, pedestrians walk some distance from the head of a queue to the service windows; however, it is not taken into account in the normal queueing models, i.e., N-Parallel and N-Fork (Fig. 1). Therefore, we consider D-Parallel and D-Fork as in Fig. 2, Fig. 3, respectively, by modeling walking distance using cellular lattice. We would like to mention that the original normal queueing models in the queueing theory are continuous-time model; however, our walking-distance introduced queueing
Approximative theoretical analysis on D-Fork
Due to the walking process, the dynamics of D-Fork is difficult to be analyzed exactly; therefore, we analyze it approximately in this section.
Comparison between parallel-type and fork-type queueing system
In this section, we compare N-Parallel, N-Fork, D-Parallel, and D-Fork by the results of both simulation and approximative theoretical analysis in Section 4. The walking probability is set to p = 1 in the following, so that the variance of the walking time becomes 0. In queueing situation, the speed of walking is much larger than that of service, and the variance of walking time is much smaller than that of service time, thus, this simplification does not harm the reality of the model.
Combination of D-Parallel and D-Fork
We have considered perfect D-Parallel and D-Fork so far. Here, we study combination of them as in Fig. 6. We denote a queueing system composed of m queues which contains service windows, respectively, as . Equation is satisfied. Besides, the number of service windows of m queues are commutative, for example, (1, 3) and (3, 1) represent a same queueing system in the case s = 4. Note that D-Parallel is described as (1, 1, … , 1), i.e., m = s and , (i ∈ {1, … , m}),
Enhanced Fork-type queueing systems
In this section, we introduce two enhanced Forks which shorten MWT by decreasing the effect of walking distance in simple ways.
Experiments
We have performed queueing experiments with real pedestrians to verify the following results obtained from our simulation and theoretical analysis in the former sections:
- R1.
Superiority of D-Parallel to D-Fork when both arrival-service ratio (ρ) and ratio of walking time to service time (β) are large (Section 5.2).
- R2.
Superiority of D-Fork-Center to D-Fork (Section 7.4).
- R3.
Superiority of D-Fork-Wait to D-Fork (Section 7.4).
“Superiority” represents that physical quantities such as number of waiting
Conclusion
We have introduced the effect of walking distance from the head of a queue to the service windows and developed D-Parallel and D-Fork to consider realistic pedestrian queueing system. Performances such as waiting probability and mean waiting time are always better in N-Fork than N-Parallel, which do not include the effect of walking distance. However, it is shown that the performances of D-Parallel becomes better than that of D-Fork when there are sufficiently many pedestrians in the system and
Acknowledgments
We thank Dai Nippon Printing Co., Ltd. in Japan for the assistance of the experiments described in Section 8. This work is financially supported by the Japan Society for the Promotion of Science and the Japan Society and Technology Agency.
References (48)
- et al.
Discrete choice models of pedestrian walking behavior
Transportation Research Part B
(2006) - et al.
Simulation of pedestrian dynamics using a two-dimensional cellular automaton
Physica A
(2001) - et al.
Statistical physics of vehicular traffic and some related systems
Physics Reports
(2000) - et al.
Simulation of space acquisition process of pedestrians using proxemic floor field model
Physica A: Statistical Mechanics and its Applications
(2012) Affective dimensions of the waiting experience
Transportation Research Part F: Traffic Psychology and Behaviour
(2010)- et al.
Understanding interarrival and interdeparture time statistics from interactions in queueing systems
Physica A
(2006) - et al.
Jamming transition in pedestrian counter flow
Physica A
(1999) - et al.
Basics of modelling the pedestrian flow
Physica A
(2006) Interaction of Markov processes
Advances in Mathematics
(1970)- et al.
Anticipation effect in pedestrian dynamics: modeling and experiments
Physica A: Statistical Mechanics and its Applications
(2012)