In this project, I used my Queue to simulate shoppers picking check-out lines. A queue is a First In First Out sequence where we add a thing only at the tail and remove a thing only at the head. It has three key methods—offer, poll, and peek. For the project, I used a node-based doubly linked list to implement a queue.
With the simulations, I compared the performance of three different strategies for selecting a line which are random, pick2, and picky.
The results are overall as expected and relatable to our daily life.
The Customer class is an abstract class from which I derive three classes that implement their own chooseLine methods.
The CheckoutAgent class incorporates a queue of customers. The draw method draws the CheckoutAgent as a rectangle, but I later modified it so that the simulation becomes visually attractive and informative. I also added a getNumItemsInQueue method that returns the total number of items in a queue for one of my extensions. In the updateState method, I used if else statements and a for each loop.
The Landscape Class uses ArrayList and LinkedList. In the draw method, I used a for each loop to loop through the CheckoutAgent ArrayList, calling each CheckoutAgent's draw method.
The RandomCustomer extends the Customer class and implements the random line-choosing strategy. Its chooseLine method returns an integer randomly chosen from the range 0 (inclusive) to the length of the list (exclusive). I used the Random package to generate a random integer.
The PickyCustomer class extends the Customer class and implements the strategy in which the customer chooses to join the shortest queue. In the chooseLine method, I initialized a large integer named
The Pick2Customer class extends the Customer class and implements the strategy in which the customer randomly chooses two lines, then joins the shorter of those two. In the chooseLine method, I first generate two random integers in the range of [0, 5). To ensure that there are two different lines chosen, I use a while loop to renew one of the integers if the two integers are the same. Then I use an if else statement to compare the two different integers and return the index accordingly.
I made three new classes--RandomCustomerSimulation, PickyCustomerSimulation, and Pick2CustomerSimulation. And I added an updateCheckouts method in the Landscape class that loops through all of the CheckoutAgents, calling updateState.
Evaluate the strategies
Initially, each Customer has 1 to 10 items. The lines grow over time, which means that 1 to 10 items is too many. So I adjust the maximum number of items to find a situation where the queues don't grow over time.
In all the simulations, I add one Customer every one time step.
The lines grow too long with [1, 10] items per Customer:
Short lines with [1, 7] items per Customer:
I added a method
printFinishedCustomerStatistics() to the Landscape to compute and print the average and standard deviation of the time-to-leave for all of the Customers in the finished customer list.
I ran each simulation with 1000 customers and print out the statistics once every 100 time steps.
The results of the three strategies are as below:
Picky Customers spend the longest time in average because they need to scan all of the checkout stations.
Pick2 Customers spend the shortest time in average because they only compare two lines and choose the shorter one.
Random Customers spend the shortest time on choosing to join a line, but the line they choose may be very long. So the time they spend is not the shortest overall.
In terms of standard deviation, the time spent varies little among each Picky Customer.
Pick2 is the most stable strategy.
Random is unpredictable and thus unstable, so its standard deviation is the largest.
1) Re-implement your Queue using an array-based method instead of a Node-based method and show the functionality is identical.
The result of testing is shown below:
2) Allow each agent to choose one of the three strategies randomly. Then calculate the statistics for each strategy in the mixed situation. Which strategy does the best?
In the Landscape class, I added another three LinkedList fields which are randomCusLL, pick2CusLL, and pickyCusLL.
I made a new ChooseRandomStrategySimulation class in which I allowed each Customer to choose a random strategy. In the for loop, I randomly generate 0, 1, or 2, and each of them is related to a condition of the if else statements. For example, if the integer generated is 0, I add a new RandomCustomer and increment a variable numRandomCust that represents the number of RandomCustomers. Since the integers are randomly generated, each Customer's strategy is also randomly chosen.
In order to calculate the statistics, initializing three variables(numRandomCust, numPick2Cust, and numPickyCust) aside, I created a new printFinishedCategorizedCustomerStatistics method in the Landscape class that calculates the average and standard deviation of the time-to-leave for all of the 3 types of Customers in their respective finished customer list.
I added 1000 customers in total to the five checkouts and I kept the maximum number of items (which is 9) the same for each customer.
In one simulation, the numbers of each kind of customers are printed in the terminal, as shown below:
I used three variables in the if else statements to count the numbers.
I printed out the stats every 100 time steps.
I also plotted four charts:
The three strategies take approximately the same amount of time to be checked out, specifically, random < pick2 < picky. Theoretically, pick2 should be the most temporally efficient strategy. But in this case, the maximum number of items(9) is relatively large, which could affect the results to some extent.
Additionally, Picky is the most reliable strategy due to its small standard deviation.
3) Make the simulation visually interesting or more informative.
4) Analyze different aspects of the performance. For example, keep track of the average line length.
In my RandomCustomerSimulation, Pick2CustomerSimulation, PickyCustomerSimulation classes, I calculated the average line length every 100 time steps using a for each loop.
The average line length refers to the average number of customers in a line.
I fixed the maximum number of items to be 8 for all three strategies.
To have a clearer idea of the average line length, I display the output statistics in a dialog box.
In the LandscapeDisplay class, I created an output method using the showMessageDialog() method of JOptionPane.
5) Analyze different aspects of the performance. For example, see if the amount of time a Customer spends in line is related to the number of items he has.
In order to analyze the relationship between the amount of time and the number of items, I created a chooseNumItems() method using JOptionPane in LandscapeDisplay and assigned the result of calling chooseNumItems() to a variable maxNumItems in my ChooseRandomStrategySimulation class.
From the statistics, we can observe that the fewer items each customers has, the less it takes a customer to be checked out.
6) Try other strategies for checking out, such as choosing a line based on how many items are in the line (rather than how many customers). Be sure to choose an initial time-step value that reflects the amount of time it would take to make the line choice. The item-counting example should take significantly more time steps than the one that chooses the shortest line.
Firstly, I added a getNumItemsInQueue method in CheckoutAgent class that loops through each Customer in a CheckoutAgent's queue to get the sum of items in the queue and returns the total number of items.
I also created CountItemsCustomer and CountItemsCustomerSimulation classes.
The CountItemsCustomer class extends Customer, and the constructor takes in the total number of items as the time steps.
Based on the PickyCustomer's chooseLine method, I modified the chooseLine method for CountItemsCustomer. I initialized a variable fewest and assigned to it a large integer. In a for loop, I used an if statement to compare the total number of items in each checkout line with fewest and update the value of fewest if necessary. Finally, I return the index of the CheckoutAgent with the fewest items in its line.
In the CountItemsCustomerSimulation class, before I create a new CountItemsCustomer in the for loop, I initialized a variable totalNumItems and then used a for each loop to call each CheckoutAgent's
Another small extension I did in my CountItemsCustomerSimulation class is using Scanner to allow user to determine the maximum number of items each Customer has.
The average time is around or above 20. Since the customers count the number of items, they spend significantly more time in a line.
7) Gaussian distribution
Inspired by Professor Maxwell, in my Pick2CustomerSimulation class, instead of choosing the max number of items from 1 to 8 uniformly, I chose 6, 4, and 2 recurrently, simulating a Gaussian distribution.
The variation of average time is little.
In order to see the pattern more clearly, I changed the modulo operator to 3 + (j / 10) % 6 so that it generates 7, 5, 3.
Now we can see the interesting pattern:
At the end of the project, I became more familiar with data structures such as doubly-linked lists, arrays, array lists, and queues. I also learned a lot of GUI functions like showMessageDialog and showInputDialog. Additionally, I tried to improve the visualization using functionalities of Graphics. Besides, I learned how to design a new strategy and facilitate the process of user controlling variables and receiving information. I also spent a lot of time collecting and analyzing data. Overall, the project was super fun.
Professor Maxwell and his lecture notes
Professor Layton and his lecture notes