Simulating Real-Life Events in Python with SimPy
Simulating Real-Life Events in Python with SimPy
Discrete Event Simulation (DES) has tended to be the domain of specialized products such as SIMUL8 [1] and MatLab/Simulink [2]. However, recently while performing data analysis in Python on an unrelated project for which we would have used MatLab in the past, we had the itch to test whether Python has an answer for DES as well. Moreover, with a number of the custom systems we’ve developed generating analyzable operational data, we’re always interested in ways to integrate meaningful analyses into our products.
Discrete Event Simulation is a way to model real-life events using statistical functions, typically for queues and resource usage with applications in health care, manufacturing, logistics and others [3]. The end goal is to arrive at key operational metrics such as resource usage and average wait times in order to evaluate various real-life configurations. SIMUL8 has a video depicting how emergency room wait times can be modelled [4], and MathWorks has a number of educational videos to provide an overview of the topic [5], in addition to a case study on automotive manufacturing [6].
The SimPy [7] library provides support for describing and running DES models in Python. Unlike a package such as SIMUL8, SimPy is not a complete graphical environment for building, executing and reporting upon simulations; however, it does provide the fundamental components, and, as we’ll see in the following sections, it can be connected with familiar Python libraries such as Matplotlib [8] and Tkinter [9] to provide charting and visualization of the process, respectively.
The Scenario
For our demonstration, we will use an example we’re familiar with from our previous work: the entrance queue at an event. However, other examples that follow a similar pattern could be a queue at a grocery store or a restaurant that takes online orders, a movie theatre, a pharmacy, or a train station.
We will simulate an entrance that is served entirely by public transit: on a regular basis a bus will be dropping off several patrons who will then need to have their tickets scanned before entering the event. Some visitors will have badges or tickets they pre-purchased in advance, while others will need to approach seller booths first to purchase their tickets. Adding to the complexity, when visitors approach the seller booths, they will do so in groups (simulating a family/group ticket purchase); however, each person will need to have their tickets scanned separately.
The following depicts the high-level layout of this scenario.
In order to simulate this, we will need to decide on how to represent these different events using probability distributions. The assumptions we’ve made in our implementation include:
- A bus will arrive on average 1 every 3 minutes. We will use an exponential distribution with a λ of 1/3 to represent this
- Each bus will contain 100 +/- 30 visitors determined using a normal distribution (μ = 100, σ = 30)
- Visitors will form groups of 2.25 +/– 0.5 people using a normal distribution (μ = 2.25, σ = 0.5). We will round this to the closest whole number
- We’ll assume that a fixed ratio of 40% of visitors will need to purchase tickets at the seller booths, another 40% will arrive with a ticket already purchased online, and 20% will arrive with staff credentials
- Visitors will take one minute on average to exit the bus and walk to the seller booth (normal, μ = 1, σ = 0.25), and another half minute to walk from the sellers to the scanners (normal, μ = 0.5, σ = 0.1). For those skipping the sellers (tickets pre-purchased or staff with badges), we’ll assume an average walk of 1.5 minutes (normal, μ = 1.5, σ = 0.35)
- Visitors will select the shortest line when they arrive, where each line has one seller or scanner
- A sale requires 1 +/- 0.2 minutes to complete (normal, μ = 1, σ = 0.2)
- A scan requires 0.05 +/- 0.01 minutes to complete (normal, μ = 0.05, σ = 0.01)
With that in mind, let’s start with the output and work backwards from there.
The graph on the left-hand side represents the number visitors arriving per minute and the graphs on the right-hand side represent the average time the visitors exiting the queue at that moment needed to wait before being served. For a more interactive demo, click here to experiment with our HTML5 Canvas visualization as well.
SimPy Simulation Set Up
The repository with the complete runnable source can be found at https://github.com/dattivo/gate-simulation with the following snippets lifted from the simpy example.py file. In this section we will step through the SimPy-specific set up; however, note that the parts that connect to Tkinter for visualization are omitted to focus on the DES features of SimPy.
To begin, let’s start with the parameters of the simulation. The variables that will be most interesting to analyze are the number of seller lines (SELLER_LINES) and the number of sellers per line (SELLERS_PER_LINE) as well as their equivalents for the scanners (SCANNER_LINES and SCANNERS_PER_LINE). Also, note the distinction between the two possible queue/seller configurations: although the most prevalent configuration is to have multiple distinct queues that a visitor will select and stay at until they’re served, it has also become more mainstream in retail to see multiple sellers for one single line (e.g., quick checkout lines at general merchandise big box retailers).
With the configuration complete, let’s start the SimPy process by first creating an “environment”, all the queues (Resources), and run the simulation (in this case, until the 60-minute mark).
Note that we are creating a RealtimeEnvironment which is intended for running a simulation in near real-time, particularly for our intentions of visualizing this as it runs. With the environment set up, we generate our seller and scanner line resources (queues) that we will then in turn pass to our “master event” of the bus arriving. The env.process() command will begin the process as described in the bus_arrival() function depicted below. This function is the top-level event from which all other events are dispatched. It simulates a bus arriving every BUS_ARRIVAL_MEAN minutes with BUS_OCCUPANCY_MEAN people on board and then triggers the selling and scanning processes accordingly.
Since this is the top-level event function, we see that all the work in this function is taking place within an endless while loop. Within the loop, we are “yielding” our wait time with env.timeout(). SimPy makes extensive use of generator functions which will return an iterator of the yielded values. More information on Python generators can be found in [10].
At the end of the loop, we are dispatching one of two events depending on whether we’re going directly to the scanners or if we’ve randomly decided that this group needs to purchase tickets first. Note that we are not yielding to these processes as that would instruct SimPy to complete each of these operations in sequence; instead, all those visitors exiting the bus will be proceeding to the queues concurrently.
Note that the people_ids list is being used is so that each person is assigned a unique ID for visualization purposes. We are using the people_ids list as a queue of people remaining to be processed; as visitors are dispatched to their destinations, they are removed from the people_ids queue.
The purchasing_customer() function simulates three key events: walking to the line, waiting in line, and then passing control to the scanning_customer() event (the same function that is called by bus_arrival() for those bypassing the sellers and going straight to the scanners). This function picks its line based on what is shortest at the time of selection.
Finally, we need to implement the behaviour for the scanning_customer(). This is very similar to the purchasing_customer() function with one key difference: although visitors may arrive and walk together in groups, each person must have their ticket scanned individually. Consequently, you will see the scan timeout repeated for each scanned customer.
We pass the walk duration and standard deviation to the scanning_customer() function since those values will vary depending on whether the visitors walked directly to the scanners or if they stopped at the sellers first.
Visualizing the Data using Tkinter (Native Python UI)
In order to visualize the data, we added a few global lists and dictionaries to track key metrics. For example, the arrivals dictionary tracks the number of arrivals by minute and the seller_waits and scan_waits dictionaries map the minute of the simulation to a list of waits times for those exiting the queues in those minutes. There is also an event_log list that we will use in the HTML5 Canvas animation in the next section. As key events take place (e.g., a visitor exiting a queue), the functions under the ANALYTICAL_GLOBALS heading in simpy-example.py file are called to keep these dictionaries and lists up to date.
We used an ancillary SimPy event to send a tick event to the UI in order to update a clock, update the current wait averages and redraw the Matplotlib charts. The complete code can be found in the GitHub repository (https://github.com/dattivo/gate-simulation/blob/master/simpy%20example.py); however, the following snippet provides a skeleton view of how these updates are dispatched from SimPy.
The visualization of the users moving to and from seller and scanner queues is represented using standard Tkinter logic. We created the QueueGraphics class to abstract the common parts of the seller and scanner queues. Methods from this class are coded into the SimPy event functions described in the previous section to update the canvas (e.g., sellers.add_to_line(1) where 1 is the seller number, and sellers.remove_from_line(1)). As future work, we could use an event handler at key points in the process so the SimPy simulation logic is not tightly coupled to the UI logic specific to this analysis.
Animating the Data Using HTML5 Canvas
As an alternate visualization, we wanted to export the events from the SimPy simulation and pull them into a simple HTML5 web application to visualize the scenario on a 2D canvas. We accomplished this by appending to an event_log list as SimPy events take place. In particular, the bus arrival, walk to seller, wait in seller line, buy tickets, walk to scanner, wait in scanner line, and scan tickets events are each logged as individual dictionaries that are then exported to JSON at the end of the simulation. You can see some sample outputs of this here: https://github.com/dattivo/gate-simulation/tree/master/output
We developed a quick proof-of-concept to show how these events can be translated into a 2D animation which you can experiment with at https://htmlpreview.github.io/?https://github.com/dattivo/gate-simulation/blob/master/visualize.html. You can see the source code for the animation logic in https://github.com/dattivo/gate-simulation/blob/master/visualize.ts.
This visualization benefits from being animated, however, for practical purposes the Python-based Tkinter interface was quicker to assemble, and the Matplotlib graphs (which are arguably the most important part of this simulation) were also smoother and more familiar to set up in Python. That being said, there is value is seeing the behaviour animated, particularly when looking to communicate results to non-technical stakeholders.
Analyzing the Seller/Scanner Queue Configuration Alternatives
Although this example has been put together to demonstrate how a SimPy simulation can be created and visualized, we can still show a few examples to show how the average wait times depend on the configuration of the queues.
Let’s begin with the case demonstrated in the animations above: six sellers and four scanners with one seller and scanner per line (6/4). After 60 minutes, we see the average seller wait was 1.8 minutes and the average scanner wait was 0.1 minutes. From the chart below, we see that the seller time peaks at almost a 6-minute wait.
We can see that the sellers are consistently backed up (although 3.3 minutes may not be too unreasonable); so, let’s see what happens if we add an extra four sellers bumping the total up to 10.
As expected, the average seller wait is reduced to 0.7 minutes and the maximum wait is reduced to be just over three minutes.
Now, let’s say that by reducing the price of online tickets, we’re able to boost the number of people arriving with a ticket by 35%. Initially, we assumed that 40% of all visitors need to buy a ticket, 40% have pre-purchased online, and 20% are staff and vendors entering with credentials. Therefore, with 35% more people arriving with tickets, we reduce the number of people needing to purchase down to 26%. Let’s simulate this with our initial 6/4 configuration.
In this scenario, the average seller wait is reduced to 1.0 minutes with a maximum wait of just over 4-minutes. In this circumstance, increasing online sales by 35% had a similar effect to adding more seller queues to the average wait; if waiting time is the metric that we were most interested in reducing, then at that point we could consider which of these two options would have a stronger business case.
Conclusions and Future Work
The breadth of mathematical and analytical tools available for Python is formidable, and SimPy rounds out these capabilities to include discrete event simulations as well. Compared to commercially packaged tools such as SIMUL8, the Python approach does leave more to programming. Assembling the simulation logic and building a UI and measurement support from scratch may be clumsy for quick analyses; however, it does provide a lot of flexibility and should be relatively straightforward for anyone already familiar with Python. As demonstrated above, the DES logic provided by SimPy results in clean, easy-to-read code.
As mentioned, the Tkinter visualization is the easier of the two demonstrated methods to work with, in particular with Matplotlib support included. The HTML5 canvas approach has been handy for putting together a sharable and interactive visualization; however, its development was non-trivial.
One improvement that is important to consider when comparing queue configurations is the seller/scanner utilization. Reducing the time in the queues is only one component of the analysis as the percentage of the time that the sellers and scanners are sitting idle should also be considered. Additionally, it would also be interesting to add a probability that accounts for someone choosing not to enter if they see a queue that is too long.
Another area that we are interested in exploring is including real-world data into the analysis in order to make the simulations more realistic. For example, in one of our projects we developed both point-of-sale and hand-held scanning systems to be used in a scenario similar to this [11, 12]; we could use data generated in those systems to arrive at realistic sale and scan duration distributions. This is one area that SimPy has a distinct advantage over packaged products: where repeatable industry-specific DES models can be developed, SimPy allows those models to be incorporated into an existing product without needing to introduce third-party packages to complete after-the-fact analyses.
May 12, 2020 Update: We’ve also posted a 3D simulation of the scenario described above. Click the link to be able to see the different configurations in Virtual Reality: https://dattivo.com/3d-visualization-of-a-simulated-real-life-event-in-virtual-reality/
References
[2] https://www.mathworks.com/solutions/discrete-event-simulation.html
[3] https://en.wikipedia.org/wiki/Discrete-event_simulation
[4] https://www.simul8.com/videos/
[5] https://www.mathworks.com/videos/series/understanding-discrete-event-simulation.html
[7] https://simpy.readthedocs.io/en/latest/
[9] https://docs.python.org/3/library/tkinter.html
[10] https://wiki.python.org/moin/Generators
[11] https://www.dattivo.com/custom-point-of-sale-system-pos/
Kevin P. Brown
Kevin is a Software Engineer and Partner at Dattivo Software Inc. in London, Ontario. With a formal background in software engineering, he designs, develops and implements software solutions. He can be reached at kbrown@dattivo.com.
Follow Me: