The story of one queue

One Sunday I happened to stand in line at polling station No. 8134 in Almaty. I stood there for 4 hours, and some even more. And somehow, quite by accident, I remembered that at the institute I studied in the specialty “queuing systems and networks,” and here we have just such a network that you can try to calculate. And at the same time answer the following questions with calculations:

• Could it really go through the PEC? 1830 people indicated in the final protocol?

• Could fewer people pass through the PEC; what is the lower limit?

• Could more people pass through the PEC, what is the upper limit?

• Could 7,500 people go through the PEC (this is the number of ballots indicated in the official data)?

Initial data

I will divide it into three groups – facts, survey results, observations and assumptions.

Data

• The PEC issued 1,830 voter ballots out of 7,500 it had.

• The PEC had 2 voting booths, and 4 employees who registered voters and issued ballots

• At the entrance to the PEC there was one frame and one employee with a hand-held metal detector

• According to evidence, the bulk of people came between 10.00 and 14.00 – that’s when a large queue formed

• The maximum queue length was on the order of several hundred, if not thousands

Survey results

I conducted a short survey among those who came that day. Unfortunately, not much data was collected for my site (8134), 12 records, not all of which were suitable for analysis. Plus, I asked questions that were not entirely correct due to my inexperience. But you can glean something from the survey:

• Security inspection time is from 15 to 60 seconds. Average – 27.5 seconds.

• One voter went through inspection at a time, the rest waited

  • One interviewee answered that besides him, 3 people went through the inspection, but most likely he meant standing in line for inspection, because there was only one employee with a hand-held metal detector

• Inside the PEC, in 60% of cases there was no need to wait at all; in other cases, the wait did not last long. We can assume that there were no queues inside.

• The time spent in line among those who arrived after 11.00 was from 4 to 6 hours.

• Those who arrived before 10.00 – if they stood, it was less than an hour

Observations and assumptions

• Each PEC employee wrote down the voter's data in a journal with a pen and issued a ballot. I'm guessing it took anywhere from 30 to 120 seconds, with all the “Hello”, “Goodbye” and other delays.

• Each voter spent from 5 to 60 seconds in the voting booth

• Security not only inspected, but also controlled the number of voters at the polling station, asking them to wait

Image of our queuing network

The network turns out to be a very simple, open-loop type. A total of 3 nodes connected in series:

• Security – one “service device”

• PEC employees – four “service devices”

• Voting booths – two “service devices”

For the calculations, I will take my own diploma – the ITMOdel application (it seems that it is even used in ITMO, but I don’t know for sure) – and enter my assumptions there. As the intensity of the source of applications, I will take the required number of ballots (1830) and divide it by the working hours of the precinct election commission (13 hours, from 8 am to 21 pm) – we will get 0,0391025641025641 people per second.

For all nodes, let's take the average processing time – 27.5s for security, 75.5s for employees, and 32.5s for booths.

Hm. If we take these numbers, it turns out that the security could not cope with the job, and 1830 ballots could not be processed.

But let's not draw conclusions, because… Some of our data is approximate. Let's try to clarify them.

Simulation and search for suitable parameters

I sketched out a small simulator in Python that creates requests, runs them through processing nodes, collects statistics, and does more beautiful process animation:

First, let's fill it with the same data as in the calculation model above. The results look like this:

model_uik(
   guard_processing_time=27.5,
   registrator_processing_time=75.5,
   box_processing_time=32.5,
   requests_total=1830,
   print_log=True
)

[xx] Max Guard Queue Length: 128
[OK] Max UIK queue Length: 0
[OK] Max Guard Queue Waiting Time: 0.92h
[xx] 11:45 Queue Waiting Time: 0.28h
[xx] 12:30 Queue Waiting Time: 0.33h
[OK] Processed: 1698
    Came: 1830
    Guard Load: 100.00%
    Registrators Load: 68.59%
    Boxes Load: 58.98%

You can ignore the queue lengths, but the load percentages are generally similar. The most important thing here is that the security node cannot cope with the load for a given average service duration.

If you try to take smaller values ​​(let’s assume that the security guards worked faster on average), then something already emerges – with an average value of 25.5s, the model begins to have time to process applications.

[xx] Max Guard Queue Length: 0
[OK] Max UIK queue Length: 1
[OK] Max Guard Queue Waiting Time: 0.00h
[xx] 11:45 Queue Waiting Time: 0.00h
[xx] 12:30 Queue Waiting Time: 0.00h
[OK] Processed: 1826
    Came: 1830
    Guard Load: 99.69%
    Registrators Load: 73.72%
    Boxes Load: 63.43%

But this is more like guessing from the tea leaves, and we want to get data that matches what we know about the queue.

Thus, the following requirements for the model were set:

• The maximum queue for security should be more than 500. In general, it was closer to a thousand, but let’s take the lower limit as 500

• The maximum queue inside the PEC should be less than 4.

• Applications queuing around 11.45 must wait 4 hours (or so)

• Applications queued around 12:30 should wait 6 hours (or so)

• The maximum waiting time in queue should not exceed 8 hours

You can see that the model above, although it ensures the processing of the required number of applications in 13 hours, does not give the picture that was in reality. Perhaps this is due to the fact that people came unevenly. I have identified 3 time periods:

• From 8 to 10 – presumably low intensity

• From 10 to 14 – presumably high intensity. I'll call it “big queue”

• From 14 to 21 – presumably low intensity

I think the gradient descent method would be a good fit here, if we can create a good distance function from the requirements above. But, to be honest, I was too lazy to do this, so I just randomly generated 500 thousand model parameters, ran the simulation, and selected those that suited the conditions.

I ended up with 722 model options. Of these, 4 options described the model in such a way that the output was about those same 1830 people.

As expected, the security time was decisive here, and was about 25 seconds. Other treatment times varied more widely.

Let's take the very first line and look at the simulation results in more detail.

[OK] Max Guard Queue Length: 1533
[OK] Max UIK queue Length: 4
[OK] Max Guard Queue Waiting Time: 7.83h
[OK] 11:45 Queue Waiting Time: 4.29h
[OK] 12:30 Queue Waiting Time: 6.15h
[OK] Processed: 1842
    Came: 2871
    Guard Load: 91.84%
    Registrators Load: 86.31%
    Boxes Load: 78.80%

We got a maximum queue of 1.5 thousand people, suitable waiting times, and 1842 people were accepted, although 2871 came.

If we run the same model through calculations, we get the following picture:

Again, the load factors are the same. This is good for us because we can test different options without running the simulation. Although the simulation can give more beautiful pictures. Here, for example, is a graph of exit time versus entry time.

It’s not for nothing that it ends at around 13.00. Apparently, everyone who came later did not get into the PEC.

And here is the animation:

There are security guards at the bottom, registrars at the top, and voting booths on the right. The yellow rectangle shows the number of voters who came out.

So, in the data we had more options. For example, the last line is funny.

Almost 9,000 people came there, but the result was the same. Let's run it in simulation:

[OK] Max Guard Queue Length: 7113
[OK] Max UIK queue Length: 1
[OK] Max Guard Queue Waiting Time: 7.72h
[OK] 11:45 Queue Waiting Time: 4.47h
[OK] 12:30 Queue Waiting Time: 6.04h
[OK] Processed: 1890
    Came: 9007
    Guard Load: 100.00%
    Registrators Load: 78.31%
    Boxes Load: 44.92%

And let's look at the graph of queue length over time:

And on the entry/exit time chart:

In general, the result is clear. People who arrived after 14.00 in this model did not end up in the PEC at all, therefore, you can bring even a billion or even 0 of them into this period – the result will not change.

Finding the Lower Bound

It is clear that in a general sense the lower limit is 0. It is enough to simply set the inspection time to 14 hours, and that’s all.

But we are interested in the option in which all the conditions specified above are met. That is, what is the minimum number of voters that the PEC could accept by reproducing the same queue.

After searching through 500 thousand options, such an option was found with a minimum number of accepted voters.

3 minutes of security per person, not bad! As a result, we get a fairly large queue, the same standing times, and only 210 accepted voters. In general, it could have been worse!

[OK] Max Guard Queue Length: 809
[OK] Max UIK queue Length: 0
[OK] Max Guard Queue Waiting Time: 7.83h
[OK] 11:45 Queue Waiting Time: 4.17h
[OK] 12:30 Queue Waiting Time: 6.19h
[OK] Processed: 210
    Came: 1021
    Guard Load: 88.49%
    Registrators Load: 17.88%
    Boxes Load: 16.68%

Finding the upper bound

This option was found when searching:

Here we have ultra-high-speed security, which spends 9 seconds per person, and a registrar who manages to copy down the name, passport details and address in 12 seconds. With such fantastic introductions, the PEC could receive more than 5,000 voters, maintaining all the signs of the queue that we saw:

[OK] Max Guard Queue Length: 4111
[OK] Max UIK queue Length: 0
[OK] Max Guard Queue Waiting Time: 7.80h
[OK] 11:45 Queue Waiting Time: 4.30h
[OK] 12:30 Queue Waiting Time: 6.11h
[OK] Processed: 5471
    Came: 7325
    Guard Load: 100.00%
    Registrators Load: 35.29%
    Boxes Load: 88.22%

A queue of 4,000 people, I'm afraid, would not fit on the surrounding streets.

What would need to be done at the PEC to accommodate 7,500 people?

But let’s take the “realistic” parameters found and try to understand what had to be done so that the PEC could accept 7,500 voters – the number of ballots they had prepared?

Let's use calculations in ITMOdel. 7500 voters in 13 hours is approximately 0.1603 people per second.

As expected, the UIK would not be able to cope with such a load in its current configuration.

The “load” coefficient on the right kind of hints to us how many “service devices” there should be so that the system can process all requests.

In total, it should have been

• 4 security guards conducting searches (instead of 1)

• 15 voter registration staff (up from 4)

• 7 voting booths (not 2)

Why the PEC staff, counting on 7,500 voters, did not bother to provide such capacity is a mystery.

conclusions

Let's remember the questions asked at the beginning of the article:

• Could the indicated 1,830 people really go through the PEC?

• Could fewer people pass through the PEC; what is the lower limit?

• Could more people pass through the PEC, what is the upper limit?

• Could 7,500 people go through the PEC (this is the number of ballots indicated in the official data)?

  • Answer: no, it could not under existing conditions. It was necessary to quadruple the number of security guards, receptionists and booths.

Conclusion

You're probably wondering – why is this? What to do with this information now?

To be honest, I don't know. I feel like Adam Jensen in this picture:

At school I was taught that 2+2=4, and for 2+2=5 they give a two. At the institute I was taught to count queuing systems and networks and calculate queue lengths.

Neither here nor there they taught me what to do when you upgraded your mathematics and calculated everything, and your opponent upgraded their arrogance, strength and ability to tell me to my face that 2+2=87%.

This is powerlessness and despair, which I am trying to fill with amusing calculations, which, unfortunately, will not change anything..

Source data can be found here

Simulator – here

Data from PEC – here . You won't be able to watch from abroad without a VPN.