A primary focus of the Math and the Mouse May Experience is the mathematics of decision-making. Students learn how to mathematically model decision-making processes, and they learn about the ways people find optimal solutions to those models. In three weeks, we can only scratch the surface of these models and methods, but we have future classes in the Mathematics Department for the students to explore these concepts in more depth. Over the past week we have asked the students to model two decision problems. The first was the Mickey Bar Problem in which our students decided where to move mobile concession stands around the Magic Kingdom throughout the day to achieve the most crowd exposure. All of the student groups did a great job of solving this problem and presenting their work to the class.
The second decision problem is something we call the Traveling Tourist Problem, which is a version of the better-known Traveling Salesman Problem (TSP). In this problem a salesperson has some number of sites to visit during a day and wants to know the fastest route to visit all of the necessary locations and return home. This is an easy problem to state but an extremely difficult problem to solve in practice. Companies like UPS, FedEx, Amazon, and pretty much all other logistics companies try to solve this problem on a daily basis when routing their trucks to pick up and deliver packages. The problem also shows up in a variety of other fields from crew scheduling in the airline industry to pattern cutting in the upholstery industry. Touring Plans is a company that solves this problem for Disney patrons. When planning a vacation to Walt Disney World, vacationers can visit touringplans.com, enter the attractions they want to see during the day (including breaks and meals), and Touring Plans will provide them with a tour for their visit.
The Magic Kingdom Traveling Tourist Problem is a staple of our course, and it exemplifies the type of hands-on, engaged learning that May Experience courses are known for. The problem asks our students to find the ordering of following 12 attractions/experiences that would minimize the total time it takes to complete the attractions when things like wait time, ride time, and walk time are taken into consideration.
- Space Mountain
- Buzz Lightyear's Space Ranger Spin
- Seven Dwarfs Mine Train
- Dumbo the Flying Elephant
- Under the Sea – Journey of the Little Mermaid
- Peter Pan’s Flight
- “it’s a small world”
- The Haunted Mansion
- Big Thunder Mountain Railroad
- Tiana’s Bayou Adventure
- Pirates of the Caribbean
- Jungle Cruise
Sunday night, before the Monday competition, we divided the students into four teams of size three and four. We gave each group a park map, a list of ride durations, walking times between each pair of attractions, and projected wait times, all supplied by Touring Plans. Each group was tasked to work together to design a tour of the 12 experiences and write down their thought process in creating the tour. Then, on Monday, the four student groups and the group of professors raced to see which group could finish the attractions first. Further, if a group deviated from their original plan during the Monday race, they were to describe their thought process in choosing to deviate. As an added benefit, on Tuesday of this week, we met with Len Testa, founder and president of Touring Plans, who talked about how his company solves this problem for vacationers.
What makes this problem hard to solve is the combinatorial explosion of possible solutions. In arranging/ordering the 12 experiences for their day, there are 12! = 479,001,600 possible orderings of these attractions. So, the students have no hope of verifying how close their solutions are to being optimal, but that’s okay. We want them to discover that the same thought processes that they come up with to produce and augment their solutions are similar to the thought processes that mathematicians have used for decades to produce good, but maybe not optimal, solutions to this problem. (We should point out that the TTP is actually harder to solve than the historic TSP problem because the time that one waits at an attraction depends on the time one visits the attraction since many attraction wait times vary throughout the day.)
These are some of the thought processes that students used in making their plans:
- Minimize walking distance.
- Minimize time waiting in lines.
- Take advantage of rides whose wait time is below the average wait time for that ride. This was the strategy of the first-place team.
- Finish the highly popular rides (Seven Dwarfs, Space Mountain, Jungle Cruise, Peter Pan) first then ride the less popular rides.
- Tackle rides that are in a geographically similar portion of the park together before moving to another geographic area.
- Be opportunistic in changing their original plan by moving big rides up in their order if they see a wait time at that ride below a certain threshold.
The first two strategies employ an algorithmic approach to solving the problem known as the Nearest Neighbor Algorithm. This approach attempts to create a tour by picking a starting ride and then going to the next ride based on some metric, such as the ride within the shortest walking distance or the ride that has the minimum wait time at that point in time. The third approach, choosing a ride whose deviation from average is most advantageous, is the subject of a paper, “A Comparison of Algorithms for Finding an Efficient Theme Park Tour” appearing in the Journal of Applied Mathematics, that the professors wrote with Len Testa and two previous Math and the Mouse students in 2018. So, it was really cool for us that our students recreated our published idea! It turns out that the winning team, comprised of Cassie, The Ahn, Harrison, and Della, used this strategy in forming their initial tour.
 |
| The first-place team (L to R): Della, Cassie, The Anh, and Harrison |
Incidentally, after the race we entered the list of attractions into the Touring Plans Optimizer to see what they suggested was the optimal route to take on Monday. It came back with
- Jungle Cruise
- Pirates of the Caribbean
- Tiana’s Bayou Adventure
- Big Thunder Mountain Railroad
- Under the Sea - Journey of the Little Mermaid
- Seven Dwarfs Mine Train
- The Haunted Mansion
- "it’s a small world"
- Peter Pan’s Flight
- Space Mountain
- Buzz Lightyear’s Space Ranger Spin
- Dumbo the Flying Elephant
This plan projected the finish time to be around 3:30pm. Our group’s first place team finished at that time exactly (with a slightly modified tour). Amazingly, each team, except the professors, actually started at Jungle Cruise. In fact, one team’s plan was the same as the above plan from Touring Plans in the first three attractions to visit, and they came up with this without access to www.touringplans.com.
In the graph below we outline the path that the first-place team took. The dots are color-coded by time of day. The lighter dots are earlier in the day, and the darker dots are later in the day. The team completed the tour in the following order:
- Jungle Cruise
- Big Thunder Mountain Railroad
- Tiana’s Bayou Adventure
- Seven Dwarfs Mine Train
- Peter Pan's Flight
- The Haunted Mansion
- Under the Sea - Journey of the Little Mermaid
- Dumbo the Flying Elephant
- Space Mountain
- Buzz Lightyear's Space Ranger Spin
- "it’s a small world"
- Pirates of the Caribbean
Their tour is only a couple of small permutations away from the Touring Plans tour, showing that with the proper data, analysis, and sparks of inspiration, our students can do hard things!
 |
| Winning team's tour |
Since the strategy of the winning team was to try and visit a ride when it offered a bargain compared to the average wait time, the following chart shows the wait time comparison between teams for each ride. The horizontal line for each ride is the average wait time that our teams waited for that ride throughout the day. The star represents how long the winning team waited for each ride. For the winning team, they waited less than average for eight of the twelve rides, slightly above average for two rides, and more above average for two rides. This shows that everyone is going to have to wait for some ride during the day, but minimizing the number of times that happens is important if you don’t want to spend your entire day waiting in line. Unfortunately for them, their longest wait was for Dumbo, a ride that they probably wouldn’t have even ridden if we hadn’t made them. In contrast, the second-place team only had six rides where they had a below average wait time. That group was on the lower end of walking distances of all groups which allowed them to “catch up.”
 |
| Wait times for each team by attraction. Horizontal lines indicate average wait time of the five groups for each attraction and the stars indicate the first-place team's wait times. |
For the fourth-place finishers, the professors, we will try again next time to win our first TTP, but it is rewarding for us to see our students discover mathematics for themselves in a fun way. What the students discovered in all of this will be important for them to remember as they carry on in school and in their future careers. First, sometimes data is unreliable, such as the posted wait time on the attraction, and you have to be able to adapt to variation (such as encountering an unforeseen wait or an attraction because it was running at half capacity). Making decisions under uncertainty is difficult but is something that every manager has to do, and the students are learning that the deterministic problems that they see in textbooks only partially reflect what happens in the real world. Lastly, working collaboratively in teams, they produced their own algorithms to solve this problem, but at the same time, they reproduced some of the great ideas that great mathematicians have had before them. We hope they recognize the significance of that and that they build confidence in their own abilities!
No comments:
Post a Comment