Trying to improve buffet lines using simulations

<i>&gt; Writing the simulation in Python was probably a bad idea in retrospect: it turns out to be incredibly slow to run Dijkstra’s shortest path algorithm on a large grid.</i><p>Dijkstra&#x27;s algorithm is the completely wrong approach for this problem. First of all, the cost to enter any grid square is the same, so Dijkstra&#x27;s priority queue is needless overhead. When all edges have the same weight Dijkstra&#x27;s behaves identically to breadth-first search.<p>BFS is obviously a poor approach for a mostly open grid like you have here. It will explore <i>every single</i> open vertex whose distance is less than the distance to the goal. Imagine the person standing in the center of a circular room with the food at the edge. With DFS, the pathfinder will look at every single vertex in that room.<p>What you want is A-star, which is no harder to implement than Dijkstra&#x27;s. Even better would be something like jump-point search that handles open spaces better. But just A-star alone will yield a <i>massive</i> improvement for problems like this.

Alas, this post suffers from mathematician syndrome (&quot;first, assume cows are spherical...&quot;). Actual buffet queues can&#x27;t be modeled like this; because of the physical constraints, they should be modeled as particle flows and hence take into account that one person cannot occupy the same space as another, and the overhead of routing, blocking etc.<p>While I agree that the &#x27;default&#x27; buffet queue is inefficient, I don&#x27;t agree with the proposed methodology of finding an improvement.<p>(also, I missed a literature study - there is so so so much research on this already)

I recently visited the Schönbrunn Palace in Vienna. My ticket had an entry time printed on it. I arrived at the entrance a few minutes before that time.<p>There was a long line. I asked a few people to see their tickets. All of them had entry times after mine. When my time was on the display, I asked the person in the front of the queue to see his ticket. He still had a few minutes to go. So I pointed at the time on my ticket and entered before him. He felt cheated, but as we together wondered through the museum, he agreed with my logic.<p>My point is that online booking systems can make many lines obsolete.<p>This article though touches on a more difficult problem, namely congestion.

Back in college, I remember waiting in a buffet line and there were, what I gathered to be, two of the cafeteria managers in front of me.<p>They were chatting about the efficiency of buffet lines and one of them mentioned &quot;It&#x27;s well known that a buffet line with a server is 30% faster than a line with no server.&quot;<p>Made total sense at the time because in a self service line, people have to:<p>- stop<p>- pick up the utensil<p>- some people then take a while deciding which piece of food is the best<p>- grab the food<p>- put the utensil down and move on etc<p>With a food server, it goes so much quicker if only because the server isn&#x27;t waiting around to pick the best piece for you.

If your workplace ever has a big pizza lunch, take a few boxes and just walk somewhere else to open them. Turn an O(n) problem into O(1) with just a few people helping.

the buffet problem (long lines) is due to head of line blocking by actors who take very long time at a station.<p>the simplest solution is 1 entrance line and N parallel buffet rows.

I did a similar analysis with a nearly-identical model but without the assumption of a constant stream of people coming from the left. In my analysis, the best model depends heavily on the assumptions: <a href="http:&#x2F;&#x2F;blog.maxshinnpotential.com&#x2F;2019&#x2F;03&#x2F;02&#x2F;are-buffets-efficient.html" rel="nofollow">http:&#x2F;&#x2F;blog.maxshinnpotential.com&#x2F;2019&#x2F;03&#x2F;02&#x2F;are-buffets-eff...</a>

I think there are two additional drawbacks of the &quot;classical&quot; method that the simulation does not cover.<p>1. Ordering of the food does not matter in the classical method (you always have a bottleneck at the most popular option), whereas in practice some buffet options will be more popular than others, and spreading them out will help in the rogue and don&#x27;t go backwards models. 2. In the classical model you have to wait for each food, so you might as well take everything (or at least more options), in the other options there is a market-based mechanism to discourage people to get the more popular option (because they would have to spend more time queueing), that could help spread people more evenly across the buffet.

There are some obvious problems. While we can argue about whether Dijkstra is efficient, the real problem is it&#x27;s unnecessary. The queue can, and should, be fully defined, not dynamic. There is no reason to let each individual actor search for the best location to go. If we are looking for an optimal solution, then there is no need for individual decision making.<p>Consider: Imagine every parallel queue, but with a &quot;gap&quot; every 3 people to allow others to pass by. In real life, humans wouldn&#x27;t walk all the way around the queue, they&#x27;d find someone who would step momentarily aside to let them pass. Representing this by forcing the individual queues to not be fully solid would allow that behavior to be represented.<p>Anyway, this work doesn&#x27;t even get to some of the more interesting aspects of buffet design, like handling multiple tables, popular items, correlated items, etc.

I expect you can model this analytically as well to some extent.<p>IIRC queueing theory suggests that a single line feeding into two sides of multiple buffet tables would work reasonably well.<p>In practice this also seems to work well, although head of line blocking can occur on each table side.

The best large-scale buffet option I&#x27;ve seen is how they do it at AWS re:Invent (at least last time I was there a few years ago). They have a large number of identical buffet stations, with catering employees directing attendees on which line to join. As soon as one buffet line is full (maximum length is still pretty short), they start directing new arrivals to the next line, and so on. It&#x27;s not perfect, but it&#x27;s quite an impressive operation and I have never had a significant wait for food there (though sometimes it&#x27;s a bit of a walk because the dining hall is MASSIVE and you might end up getting sent to a buffet line at the far end).

I eat at buffets probably more than I should, and in my experience, the biggest slowdown are people that walk up to an item, stare at it for a minute, then decide to grab the utensil and serve themselves, put the utensil down, then stand there for another minute contemplating what they just did before getting the hell out of the way.<p>It&#x27;s especially bad on large cruise ships where the average age of the clientele is probably 90 years old.

PDQ is useful open source software to model queues.<p><a href="http:&#x2F;&#x2F;www.perfdynamics.com&#x2F;Tools&#x2F;PDQ.html" rel="nofollow">http:&#x2F;&#x2F;www.perfdynamics.com&#x2F;Tools&#x2F;PDQ.html</a>

The best buffet organizations I have seen are circular. I wonder how they compare to the double side accessible solution given in the article.

In the backwards method, did you account for people potentially colliding?

Of course there is the wonderful hygiene of the buffet, the sneezing, the coughing, the tasting off the serving spoon, dropping the serving spoon on the floor and putting it back into the food. Let&#x27;s not forget all the wasted food, and the encouraged gluttony.