Wednesday, September 16, 2015

A Basic Discrete Event Simulation

Let me paint a picture.  You run a service station (or gas station for our American friends), and you sell bread.  It's a 24 hour business with a uniform flow of customers throughout the week and you want to investigate the effectiveness of the ordering routines you use.  How do you do it?  The answer is Discrete Event Simulation.

I'm ashamed to say I've never heard of it, and once again came up with the idea independently  (Another case of "Wouldn't it be cool if ........  *Googles*  Oh, this already exists, is well developed, and people make a living from it").  I'm familiar with the simulations used in designing electronics, but had never experienced this type.  Basically a queue of events with timestamps is created, the next event is removed and processed and this is repeated until a certain time or all the events have been processed.

The reason I'm looking into this is because I have something I want to simulate and had originally planned to use the Simpy simulation package for python, but as I started working it became apparent that it was overkill for what I needed.  It's great for simulating resources that interact with each other, and although it looked like my problem needed this it really didn't.  The ordering process and customer process don't interact, even though it looks like they do.  I'm referring to the time that events occur.  Customers arrive indepenently of each other and of when deliveries happen.  They are linked by the stock levels in the store but this is handled by a stock on hand variable (My basic scenario above could probably be handled by Simpy, but I plan for it to get complicated).

After much procrastination I decided to write my own, but as it turns out someone has done the hard work for me.

User GaretJax  from http://codereview.stackexchange.com/questions/3670/discrete-event-simulation-with-variable-intervals already had a basic framework for this problem.  So I ran with it.  (Check github for  DiscreteEventSimulator.py)

The first thing to do is describe the processes at play.  The customer for example is described below.  They walk in and if bread is on the shelves, they buy a loaf and the stock on hand is decremented.  The time until the next customer is described by an exponential distribution to simulate a poisson process.  The final thing to do is schedule the next customer arrival.  The sales rate is 0.0004 loaves per second, or more intuitively, one loaf every 2500 seconds or around 40 minutes.

Python Code
Customer Process

The ordering process is very simple.  The bread delivery truck turns up and the staff member counts the stock the store currently has, and then works out how many loaves are needed to bring the stock levels back to 50 loaves.  But there is a small problem.  Loaves of bread only come in crates of 24.  So they need to round up to the nearest multiple of 24 and take that from the driver.  This is then added to the stock on hand.

Python Code
Order Process

All that's needed now is to start the simulation.  7 events are created for the bread deliveries, one for each day of the week at 1 am.  An initial customer is also scheduled.  Only one is needed as each customer generates the next customer event.  I've then set the simulation to run for a week.

Python Code
Simulation configuration

The results below starting from Monday are interesting.  We can see the random nature of the purchases, but the overall trends are visible.  We can see that on Monday, Tuesday, Wednesday, Thursday, Friday, and Sunday, only one crate a day was needed, but on Saturday two crates were needed.  It's also possible that they're holding too much stock as for the first 3 days of the week the stock barely falls below 40 loaves.  (Customers have been complaining about stale bread, maybe this is the reason.)

Stock Graph
Simulation Results
This is only a quick overview of the process with some very simplistic assumptions and modelling, but I've got a framework to use now and I have thoughts on how to make this more realistic (and complicated).  This problem has been kicking my arse all week,  I only managed to pull it all together in the last couple of hours.  Very happy at the moment


https://github.com/GrantTrebbin/DiscreteEventSimulator
Get the code!


No comments:

Post a Comment

Note: Only a member of this blog may post a comment.