Skip to end of metadata
Go to start of metadata
Overview

The purpose of this lab was to use the abstract data type queue to analyze the flow of supermarket checkout lines. It uses the same simulation/landscape classes as before, so it wasn't too difficult to implement. As a related project, I simulated the lanes at a border security checkpoint, as on the US-Canada border.

Solution

The checkout simulation has three objects: Customers, CheckOut counters, and a Spawner.

The Spawner is responsible for producing more Customers to replace those who have been checked out. Since it has to add agents to the landscape, it cannot be an agent (when an agent acts, an iterator is working on the list of agents so the list may not be modified), so I made it a Resource. I wanted to make a generic Spawner that could spawn any type of agent, but got stuck when I realized that you can't construct using the generic reference type. Instead, my Spawner just makes Customers at a rate specified in its constructor. They are added to the Landscape in a random position within the Spawner, but you never see them there since agents update after resources, so the Customer gets into line before the Landscape is redrawn.

Customers are agents that get into line, keep fastidious track of the time that they've waited, and leave the Landscape when all their items have been scanned. The class has a static variable and setter method for the decision type -- random, best of two randomly selected, and best of all(choosing randomly from the shortest). The variable dictates how the chooseCounter private method works, which is called from primaryUpdate when the Customer is not in a CheckOut line (which it can tell since it keeps a track of a variable that tells it which line it is in). It has a method that allows other classes to make it decrement its number of items to scan. This number is how it can tell if it should get off the Landscape. Before it returns true in secondaryUpdate, though, it tells its CheckOut to move to remove it from the line.

CheckOut counters are agents that have Lines (queues) of Customers. Each turn, they simply check a certain number of items from the first customer in line (the rate is given in their constructor). They have methods to poll and offer called addToQueue and moveToNext that not only use poll/offer, but also set the positions of the agents in the queue. It is the responsibility of the Customer to call moveToNext; a Checkout will give the Customer a negative number of items if it does not. Whenever a Customer is removed, its wait time is recorded in an ArrayList<Integer> so that the Checkout can do statistical analysis of it later(it probably only wants the average, but just in case it wants the standard deviation of its customers' times, it needs to know all the times, not just the sum). When it draws itself, it also writes its average wait time underneath it.

I have referenced a Line, which is my implementation of a queue. It is generic, so CheckOut uses a Line<Customer>. It is a linked implementation, but not circular, so it keeps track of a head and tail reference. Like the java Queue, peek, offer, and poll return false/null when the action is impossible; and element, add, and remove throw exceptions. It also has a getPosition method that performs a sequential search for an element, but I never use it in my simulations. Line also provides an iterator that returns its elements in order, but I don't use that except in getPosition. It is nifty in there, though, since I wrote -- for(T element:this) -- which I've never done before.

This is a sample run where Customers randomly choose two Checkouts to choose between.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Results

My QueueSim and Spawner make Customers with an average of about 5 items, with a pretty small variation (I use 5 + (int)(rand.nextGaussian()-.5) to make two new Customers each turn, and 5+(int)rand.nextGaussian() to make the additional Customer if it is made that turn). Experimenting using the bestOfTwo method, I found that generating 2.523 kept the number of Customers fairly constant (the decimal is the chance of an additional customer being spawned each time). I ran two trials of 20000 iterations with twelve CheckOut counters each for every selection method. The checkouts reported their average wait times, and I analyzed these 12 numbers. My results are in the following table:

simType

averageWait

StDeviation

bestOfAll1

32.9

.70

bestOfAll2

14.6

.69

chooseFromTwo1

28.58

.08

chooseFromTwo2

24.17

.24

randomChoice1

137.98

70.84

randomChoice2

146.58

64.61

I had expected the bestOfAll to have a low standard deviation, but it didn't because the line lengths fluxuated -- all the lines were always almost the same length, but sometimes that was one or two, and sometimes it was 10. Since randomness played a role in the number of agents spawned and their number of items, the first trial had longer lines than the second trial. This is an accurate portrayal of how supermarket lines are shorter some days than others.

It is surprising that choosing the best of two has such a low standard deviation, compared to choosing the absolute best line. I think that maybe the lines are less likely to fluxuate with the randomness since not all the lines are kept the same; one line can get a little longer without all of them being affected.

In a randomChoice simulation, the number of customers waiting in line rises quickly because often there is a register empty. This makes the spawning rate faster than the checking rate, so certain lines get much longer. The disparity creates a large standard deviation.

Extension

As an extension, I made a BorderSecuritySim in which queues of cars are connected in a tree-like structure. I did not create a tree class, but in initialize I create Lanes in a similar fasion to how you create a tree: I first make the leaf-like final lanes, then create the other lanes referencing the others. Therefore, Lane is like a node whose data type is a queue. Lanes have a fixed length, and they keep track of how much space is filled up (they ask for the cars' lengths, so I could make buses and the lanes would fill accordingly). Initial lanes (differentiated from "intermediate" or "final" lanes by a String parameter) add new cars when they are not full. Initial and intermediate lanes check if any of the lanes to which they point have room for the next car, and if they do, they pass their first car to the end of that Lane. Final lanes are like CheckOuts; they decrement the car's process time. Unlike QueueSim, BorderSecuritySim has the final lanes check if the car is done, and it then calls its method to remove the car from the queue and move up the others. Of course, it is still up to the car to remove itself from the simulation, but that is simply done with a boolean expression in secondaryUpdate.

I wanted to determine if there is a good arrangement of lanes that minimizes wait time at the border. When I am careful to include the same number of cars in the simulation, though, I found that it makes no difference where splits occur -- the wait time is only dependent on the number of cars and the number of security checkpoints. I had thought that maybe a later split would be helpful since some cars have a longer process time than others, and a later split would let fewer cars be stuck behind a really well searched car, but my results did not give much evidence to support my hypothesis, especially over extended periods of time.
The final average waits for each set of 4 checkpointe in this simulation are listed in the following table. It performed 20,000 iterations; the gif shows every 400.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

102

103.75

104

102.5

104

102.5

102.5

103.75


Conclusion

This assignment provided lots of practice dealing with the Queue data structure. I am now comfortable with them, and my tree-like lanes have even helped introduce me to the concept of trees.

Labels