In mathematics there are problems that are easy to state but deceptively difficult to solve. The Knapsack Problem is one such problem. The problem supposes there are items that can be packed into a knapsack to take on journey. Each item fills a certain amount of space in the knapsack and also supplies the traveler with a certain amount of utility (or happiness). The goal is to pack as much utility into the knapsack without exceeding the space constraints. Each student and professor participating in Math and the Mouse had to solve such a problem before our trip began. Having loaded each of our students' knapsacks into the van, we can attest that some students were more successful at solving this problem than others.
To further explore this idea in the context of theme parks, we created an integer knapsack activity where the goal was to pack our knapsack (a morning in Hollywood Studios) with the most utility (pre-assigned values to each attraction based off a combination of average wait time, ride length, and proximity to other attractions). For instance, Toy Story Mania had a utility of 110 because of its extreme wait times, Tower of Terror had a value of 80, Rock 'n' Roller Coaster 70, etc. The problem we gave the students is slightly different than the packing problem they faced before coming to Disney in that the groups were allowed to 'pack' a ride multiple times. All groups used anticipated wait time, average walk time, and ride length data supplied by touringplans.com to prepare a strategy the day before our time in Hollywood Studios. Each group was tasked with creating a strategy to pack their knapsack using data that they would put to the test the following morning by executing their strategy in person.
One important lesson that the groups learned quite quickly was that the knapsack problem is much different when thinking things through on paper than when generating a solution in real time with real-world data and conditions. For instance, our data started at 9am (the park's posted opening time), but we were allowed to enter the park early at 8:50am and were on our first rides before 9am. Our group (the professors) were on Tower of Terror when the ride broke down, throwing an unexpected twist into our packing strategy. There were upsides to these unexpected events though -- we were on rides earlier than expected and we got to see a backstage area of Tower of Terror when they evacuated our ride vehicle (we did get to ride an elevator to end our ride, it just was a bit more reliable than the service elevators that are part of the usual attraction). Actual ride and wait times vary due to efficiency in loading and unloading passengers, unexpected crowds, and difficulty in predicting people's decision-making.
The Integer Knapsack Problem is part of a group of problems that are known to be Nondeterministic Polynomial. These are problems where a solution might be easy to find, but there is no known way, other than to generate all possible solutions, to check whether a solution generated is optimal. Given that the number of possible solutions for these types of problems can be quite large, it might take days (weeks, months,..) to enumerate all possible solutions. So, most researchers focus on trying to generate what are known as heuristic solutions to the problem. These are approaches to generate good, near-optimal solutions to a problem. One of the well-known heuristics for this problem is known as the 'bang-for-the-buck' algorithm. Here, for each item that can be included in the knapsack, a calculation is performed. This calculation divides the utility of the item by it's 'space,' or cost to include, to get a utility per cost metric. Items are then put in decreasing order of this metric. The items with highest metric are included in as many quantities as the knapsack has room. Then, as room remains, remaining items are added in order until no item can be added in the remaining knapsack room.
What is always fun for a professor to see is that students will often use their intuition to generate algorithms that work really well in practice. We think all of our groups employed this bang-for-the-buck heuristic in some fashion without us ever mentioning it to them ahead of time. For instance, Alex, Jamie, and Molly used the following metric to pick rides in order: the ratio of utility to the summation of waiting time and ride time throughout the time period. Lindsay, Mary Lib, and McKenna calculated the utility divided by the average wait time plus the ride length for each time slot. The student group who finished ahead of all other students groups (Alyssa, Courtney, and Zach) used the following, more complicated algorithm to decide on the next ride to visit:
1. Start at Rocking Roller Coaster (RRC) or Tower of Terror (TT)
2. Choose Tower of Terror if the wait time is less than RRC wait time minus 10 minutes
3. When it is quicker to ride Toy Story Midway Mania than riding any combination of TT or RRC twice based on wait times go to Toy Story
4. If time remaining is less than an hour and more than 40 minutes and Toy Story will not fit, go to the Great Movie Ride.
5. If time remaining is less than 40, ride Star Tours.
6. If Star Tours will not fit, find a ride that works disregarding utility.
Courtney, Zack, and Alyssa on Rock 'n' Roller Coaster
The above algorithm garnered the winning student group a total utility of 440 points, 50 points ahead of each of the other student groups. The professors, however, employed the best algorithm of all and won the day with 520 points. Our strategy was to calculate the same bang-for-the-buck calculation that the other groups employed, but instead of using the expected wait times, we used an initial 5-minute wait for each ride, except Toy Story Mania where we used a 30-minute wait time estimate. When this is employed, Dr. Hutson's favorite ride, Tower of Terror, gives the most bang-for-the-buck compared to other rides, followed closely by Rock 'n' Roller Coaster. The professors also knew that the pre-show for Tower of Terror and Rock 'n' Roller Coaster was roughly the same duration of time for both of these rides but Tower of Terror could service more people at once since it has four elevators whereas Rock 'n' Roller Coaster only has three trains on the track at once. So our approach was to ride Tower of Terror until the split time between entering its queue and then re-entering its queue was 20 minutes. The 20-minute cutoff was chosen for a couple of reasons. First, Tower of Terror sits a good distance away from most other rides, at least a couple minutes walk at Dr. Bouzarth's speed. Further, given the build up in expected wait times for the other rides, we felt certain that no other ride could give the same bang-for-the-buck as Tower of Terror until the 20-minute split time was breached. Under that strategy, we ended up riding Tower of Terror six straight times (even surviving a 15-minute break down) to generate 480 points. After that, the wait time had built up over 20-minutes, so we headed for the next best bang-for-the-buck option, Star Tours, which happens to be Dr. Harris' favorite Hollywood Studios ride. Unfortunately, we only had time to ride this once, but it brought our total to 520 points, a comfortable victory! A close inspection of the articles of clothing that Drs. Hutson and Harris adorned for the competition might have given some clue as to the professors' (winning) strategy.
We look forward to an increased student effort for our next competition on Monday, the Traveling Tourist Problem at the Magic Kingdom. The trash talking has already begun. Stay tuned for more posts on those results. Overall though, we are very pleased at the time the students have devoted to learning about mathematical optimization modeling and solution algorithms -- they have been working very hard!
No comments:
Post a Comment