Mini Motorways Queuing Theory Guide

Introduction

(Little's Law)

(Erlang-C Formula)

Queuing theory is a field of mathematics that gives us the ability to analyze the capacity and transit times of customers within queuing systems. A city designed in Mini Motorways can be conceptualized as a collection of single queues where customers (demand pins) originate from destinations and servers (cars) originate from houses.

Kendall's notation - A/S/c/K/N/D - is used to represent the characteristics of an individual queue:

Symbol Description A inter-arrival time distribution S service time distribution c number of servers K system capacity N calling population D queue discipline

For our analysis, we intend to analyze a single queue across one session of Mini Motorways. Thus, we assume the queue can be characterized as having Markovian (exponentially distributed) inter-arrival times, Markovian service times, c servers, infinite system capacity, infinite calling population, and a First-In First-Out service discipline.

More concisely, this is represented as M/M/c/inf/inf/FIFO. I will remark on system capacity (K) later, but, in general, it is common to drop the latter three terms and simply represent this queue as M/M/c. This representation will be the basis for our analysis.

Given our M/M/c queue, there exist some fundamental quantities of interest we seek to derive:

Metric Description rho traffic intensity L long-run average # of customers in the system Lq long-run average # of customers in queue W long-run average system time per customer (sojourn time) Wq long-run average queue time per customer Pi steady-state probability of i customers in system

Importantly, traffic intensity must remain less than one for any queue to be stable. This metric is the ratio of inter-arrival rate to service rate. Expressed by the following equation:

rho = lambda / mu where, lambda = inter-arrival rate per unit time mu = service rate per unit time But a slight adjustment needs to be made since our M/M/c queue has multiple servers. We are truly concerned with the quantity:

rho = lambda / (c * mu)Both rates are derived from the Markovian distributions assumed earlier. Equations for the other quantities of interest are as follows:

L = lambda * W . . . Lq = lambda * Wq W = Wq + (1 / mu) and . . . Pi = P0 * ((lambda / mu) ^ i) / i! FOR i <= c Pi = P0 * (((lambda / (c * mu)) ^ i) * (c ^ c) / c! FOR i > c Observing that the sum of all steady-state Pi values from zero to infinity should aggregate to 1, we can derive the value of P0:

P0 = [SUM (((lambda / mu) ^ i) / i!) FROM i = 0 TO c-1 + ((lambda / mu) ^ c) / (c! * (1 - lambda / (c * mu)))] ^ -1 Furthermore, we observe that the sum of all steady-state Pi values from c to infinity is the probability that an arriving customer has to wait in the queue - yielding the following equation:

Pq = P0 * ((lambda / mu) ^ c) / (c! * (1 - lambda / (c * mu))) . . . Finally, in tandem with our prior equations, we have a means to derive the quantities of interest for our M/M/c queue:

Lq = Pq * (lambda / (c * mu)) / (1 - lambda / (c * mu)) Wq = Lq / lambda W = Wq + (1 / mu) L = lambda * W

Assumptions

Mathematical and game-specific assumptions are necessary to accurately measure the quantities of Lq, Wq, W, and L. Notably, assumptions that are specific to Mini Motorways will directly influence the design of our experiment.

Mathematical assumptions

Inter-arrival times are independent random variables, and exponentially distributed ~ Exp(lambda)

Service times are independent random variables, and exponentially distributed ~ Exp(mu)

Inter-arrival distribution and service distribution exhibit the memory-less property

The number of customers in the system can be modeled as a birth-death process (continuous time Markov chain)

The birth-death process is irreducible and positive recurrent

No balking or reneging behavior by customersGame-specific assumptions

Customers are represented by demand pins originating at destinations

Servers are represented by cars originating at houses

The number of servers is represented by the number of cars solely serving a given destination

Service time is represented by the total time it takes for a car to travel to a destination and return

The system under observation must be closed, such that cars can only serve a single destination

The number of parking spaces at a destination has negligible effect on service time

Experiment Design

Data collection takes place within distinct epochs. Each epoch represents a unique iteration of the queue layout as the Mini Motorways city evolves. The algorithm is as follows:

START Epoch Measure number of demand pins that are generated Measure number of cars servicing destination Sample and measure the round-trip service time of one car RESET Epoch IF Number of servers changes OR Transit path of servers changes, i.e. update to road layout OR Transit assets - highway, stoplight, or roundabout - introduced to service path OR Demand pin generation significantly increases, i.e. update to circle destination STOP Experiment IF Mini Motorways session ends OR No longer feasible for cars under observation to service one destination All that is needed is a pen, paper, and stopwatch to begin.

Analysis

Epoch One: 0:00 - 3:55

The session begins with a simple system under observation that is composed of one yellow square destination and two yellow houses providing service.

Measurements:

Demand Servers Service time (sec) Duration (min) 14 4 26 3.92

Stability:

lambda mu rho rho < 1 3.571 2.308 0.387 Yes

Quantities:

Metric Value P0 0.210 ~ 21% Pq 0.082 ~ 8.2% L 1.600 avg. # of customers in system Lq 0.052 avg. # of customers in queue W 0.448 avg. minutes in system Wq 0.014 avg. minutes in queue

Epoch Two: 3:56 - 12:20

The session matured to epoch two when a blue destination and blue houses appeared that required intersection with the system under observation. A roundabout was deployed to facilitate transit.

Measurements:

Demand Servers Service time (sec) Duration (min) 29 4 30 8.41

Stability:

lambda mu rho rho < 1 3.449 2.000 0.431 Yes

Quantities:

Metric Value P0 0.175 ~ 17.5% Pq 0.113 ~ 11.3% L 1.810 avg. # customers in system Lq 0.086 avg. # customers in queue W 0.525 avg. minutes in system Wq 0.025 avg. minutes in queue

Epoch Three: 12:21 - 19:37

The session matured to epoch three when another blue destination and associated blue houses appeared that required connection to the system under observation. A highway was utilized to facilitate transit across this distance.

Measurements:

Demand Servers Service time (sec) Duration (min) 35 4 30 7.28

Stability:

lambda mu rho rho < 1 4.808 2.000 0.601 Yes

Quantities:

Metric Value P0 0.083 ~ 8.3% Pq 0.288 ~ 28.8% L 2.838 avg. # customers in system Lq 0.434 avg. # customers in queue W 0.590 avg. minutes in system Wq 0.090 avg. minutes in queue

Epoch Four: 19:38 - 23:26

The session matured to the final stage, epoch four, when the original yellow destination updated to a circle destination (significant increase of demand pins) and required more yellow houses to be connected to the system. A highway was utilized to connect this distant group of houses.

Measurements:

Demand Servers Service time (sec) Duration (min) 43 10 35* 3.85 *Slight variation in procedure. This is the weighted average of one trip sampled from each group of houses - since both groups are relatively separate locations.

Stability:

lambda mu rho rho < 1 11.169 1.714 0.652 Yes

Quantities:

Metric Value P0 0.001 ~ 0.10% Pq 0.156 ~ 15.6% L 6.806 avg. # customers in system Lq 0.291 avg. # customers in queue W 0.609 avg. minutes in system Wq 0.026 avg. minutes in queue

Final Layout: 23:26

The Mini Motorways session ended when a destination - unrelated to the system under observation - reached capacity. At roughly the same time, a yellow destination appeared at the double-destination on the left-hand side of the map. This would lead to servers having access to more than one destination which is a condition to stop the experiment.

Closing Remarks

That was a lot of math, huh. What can we conclude from our analysis?

Arrival rate steadily increases over time even if the destination form (square, circle) remains static

An update from square destination to circle destination yields a significant increase in arrival rate

Four cars appear to be an adequate amount for servicing a square destination, when relatively close in location

Ten cars appear to be an adequate amount for servicing a circle destination, when relatively close in location or expedient in access (it may be worthwhile to investigate how eight cars performs)

The probability that the system is empty (P0) rapidly becomes negligible as traffic intensity (rho) exceeds 0.60Additionally, I stated I would remark on system capacity (K) earlier in this guide. Every Mini Motorways session essentially ends when an individual destination reaches system capacity. There exists some limit to the number of customers that can be in-queue or in-service before the system fails. This would also be represented by a rho > 1 value - i.e. unstable traffic intensity. I do not know the value of system capacity (K) for square or circle destinations, but it would be interesting to explore since M/M/c/K is another class of models that produce system insights.

If you enjoyed this application of queuing theory, I found that Missouri S&T, George Mason University, and University of Washington have some excellent open-source documentation on the subject.

Thank you for reading!

Source: https://steamcommunity.com/sharedfiles/filedetails/?id=2808098164

Queuing Theory Guide

Introduction

Assumptions

Experiment Design

Analysis

Closing Remarks

More Mini Motorways guilds