Mini Motorways

Mini Motorways

71 ratings
Queuing Theory Guide
By Sardaukar4
An analysis of Mini Motorways through the lens of Queuing Theory.
4
2
5
2
2
   
Award
Favorite
Favorited
Unfavorite
Introduction
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 . . . (Little's Law) 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))) . . . (Erlang-C Formula)
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 customers
Game-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.60
Additionally, 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!
17 Comments
Antilop14 8 Apr @ 2:40am 
lambda
Sardaukar4  [author] 11 Dec, 2023 @ 11:35am 
Happy to hear that!
Peanits & Worms 1 Dec, 2023 @ 8:54pm 
Excellent post. I actually go to GMU and I am a student in the Systems Engineering and Operations Research department. I just took a class on Stochastic Models, and much of what you say here directly applies. Well done.
Penguin8510 16 Oct, 2023 @ 5:09pm 
TL;DR stats
Sardaukar4  [author] 6 Apr, 2023 @ 10:44am 
Hey! My background is Industrial Engineering and Operations Research. I did some quick reading and it seems queuing theory has many applications, and I had not been aware of its use in allocating computation resources. Very cool.
rocketeer 5 Apr, 2023 @ 3:31pm 
I have a bachelor’s degree in computer science and thusly I’ve found your article to be extremely fascinating. I’m personally more familiar with queuing strategies as related to operating systems (scheduling methods, and page replacement theory), and was curious to know your background to better understand the interest in this write up. Needless to say, I also started playing this game on my phone and I intend to replicate this experiment and see what interesting information about the game’s implementation I can glean for myself.
Sardaukar4  [author] 3 Jan, 2023 @ 11:11am 
Base speed so that I could keep track of all the different events being measured - demand pins, sampling a car trip, etc.
N1n3 2 Jan, 2023 @ 10:37pm 
Quick question, was the testing done on the base speed or the accelerated speed.
Duncan Flex 15 Nov, 2022 @ 9:25am 
Other Games' Guides: How to Jump (Not even worth reading)
Prodigy Mini Motorways Fan's Guide: An analysis of Mini Motorways through the lens of Queuing Theory
G-ray 3 Nov, 2022 @ 6:26pm 
Hold left click and point.