The Genetics of Touring

Each student has written three blog posts at this point, so it's now the professors' turn to take over! Yesterday, we started the day with an optional trip to Hollywood Studios to allow students to collect project data. Unfortunately, the park had Extra Magic Hours that morning, so WDW resort guests could enter the park an hour before we could, which made for long lines early in the day. After some time to work on projects back in the hotel in the afternoon, we headed to Animal Kingdom to enjoy another evening in the park. 

The Genetics of Touring

Last week, the students participated in a race to see which team could accomplish a list of 19 tasks in the Magic Kingdom most efficiently.  The tasks ranged from riding an attraction to getting a picture taken with a character.  Differing from the Traveling Tourist Problem at Epcot two years ago, we allowed teams some flexibility in the attractions that they visited.  Here is a list of possible events:

The winning group's tour of the Magic Kingdom.

Required                                

Space Mountain       

Buzz Lightyear’s Spin            

Seven Dwarfs Mine Train 

Dumbo   

Haunted Mansion 

Peter Pan’s Flight           

Under the Sea - Voyage of the Little Mermaid

Splash Mountain              

Big Thunder Mountain Railroad

Pirates of the Caribbean           

Jungle Cruise         

Group Photo with a costumed character  

Group Photo with Walt Disney 

Fantasyland (Pick 3)
It’s a Small World
Winnie the Pooh

The winning group, Zack, Mary Lib, and Johanna.

Mad Tea Party
Hall of Presidents
Enchanted Tales with Belle
Barnstormer
Prince Charming’s Royal Carousel
Mickey’s Philharmagic

Tomorrowland (Pick 2)
Astro Orbitors
Stitch’s Great Escape
Monster’s Inc. Laugh Floor
Carousel of Progress
Tomorrowland Speedway

Adventureland (Pick 1)
Magic Carpets of Aladdin
Country Bear Jamboree
Enchanted Tiki Room

The students were assigned into groups of three and were given data on the expected wait, walk, and ride times in the Magic Kingdom that day (supplied by tourningplans.com).  They had an afternoon to design a tour of the chosen 19 attractions and were allowed time in the park to perform reconnaissance.  The following day we raced, and (drumroll, please) the winning team was Johanna, Mary Lib, and Zack who finished the tour in just under 6 hours.  Their tour is shown above.

Johanna, Mary Lib, and Zack flying with Dumbo.

After the race, the students learned to model the problem using networks and also learned that the problem they were trying to solve is a variation of the Traveling Salesman Problem.  This problem of trying to find an efficient tour of a given list of locations is one that is researched by logistics companies like FedEx and UPS.  A variety of algorithms exist to try to produce optimal, or near-optimal, solutions to these types of problems.  One such method is to use what are known as genetic algorithms.  These algorithms mimic natural selection in that a variety of solutions are produced (called a population) and their tour length (called their fitness) are calculated.  A solution for this problem is just a sequence of attractions in the order that they are visited (called a tour).  Solutions are then subjected to one of two types of operations to produce new, child solutions.  The first type of operation is called a mutator.  These operators take a member of the population and augment it in some way, such as switching the order in which you visit two (or more) attractions.  The second type of operation is called a crossover operator.  These operators take two members of the population and produce a child that resembles both parents.  For instance, a crossover operator might take two members of the population and find the attractions that are sequenced in a common position in both parents and include those attractions in those positions in the child.  The remaining attractions are then randomly placed in the remaining sequence positions in the child.  Every time a child is produced its fitness is calculated and if it is better fit than the least-fit solution in the population, that child replaces the least-fit solution in the population.  These operations reoccur for a fixed number of iterations (usually quite large) and the most-fit solution from the population is chosen as the “optimal” solution. 

The winning group at the finish line and
home of Dole Whip, Aloha Isle.

The second project for the students in the course involved inventing mutators and crossovers for a genetic algorithm to find the optimal solution of an abbreviated Traveling Tourist Problem involving only ten rides.  In fact, the example mutation and crossover operators described above are ones that students came up with.  Here are examples of other inventive operators that the students generated.

Crossover Example

1. Define Parent 1 as the parent with the single highest wait time.
2. Find the sequenced attractions that match in P1 and P2.  Include these attractions in these sequenced slots in the child.  Then take P1’s highest non-matching wait time and swap it with other attractions until it is in the location in P2’s sequence of the highest non-matching wait time.
3. Continue to find a nonmatching ride whose wait time is the highest and switch it with the lowest remaining wait time of the other parent. 

Mutator Example (Frame Shift)

Move an attraction from sequence spot j to sequence spot k and then shift all of the attractions in between sequence spots j and k one slot to the right or left depending on j’s relative position to k.

After running their genetic algorithms on the subset of rides that they were given, the group consisting of Johana, Mary Lib, Alyssa, and Molly found a tour that could be traversed in 284 minutes.  The sequence of attractions in this tour was

1. Seven Dwarfs Mine Train
2. Peter Pan's Flight
3. Haunted Mansion
4. Jungle Cruise
5. Buzz Lightyear
6. Dumbo
7. Space Mountain
8. Splash Mountain
9. Pirates of the Caribbean
10. Big Thunder Mountain Railroad

After studying these genetic algorithms, our group met with Len Testa, President of Touring Plans and co-author of The Unofficial Guide to Walt Disney World, which has sold more than 4 million copies worldwide.  Testa’s company, Touring Plans, employs an analytic approach to travel, helping its subscribers not only find good park tours, but also finding affordable options for park tickets, finding the quietest hotel rooms, etc.  His company employs mathematicians, statisticians, and computer scientists to model and produce solutions to many problems related to travel.  Len spoke with our students about the evolutionary algorithms (such as genetic algorithms) that his company employ to produce tours for users in a quick amount of time.  The time that the students put into to developing an intuition about the problem and creating mutation and crossover operators paid off when they saw how Touring Plans employs these types of algorithms to produce solutions to real-world problems.  They came away with an appreciation for the mathematical sophistication that Touring Plans brings to their solution approaches.  For some students this was an experience that caused them to remark that they wished they had brought a resume to the talk to give to Testa.  For the professors, we give many thanks to Len Testa for inspiring a group of students to continue to develop their mathematical creativity and problem-solving skills to make a difference for others. 

Day 14: Don't Try This at Home

Aloha, everyone! Molly and Jamie here giving you the scoop on on our Day 14 of Math and the Mouse! We had an early morning in Epcot, did some data collection for our third project, ventured around Disney Springs, and ended the day with Disney's Spirit of Aloha Dinner Show at the Polynesian Resort.

Morning
We arrived at the park as soon as it opened for breakfast and a meeting with Len Testa, the co-author of The Unofficial Guide to Walt Disney World and president of touringplans.com, a website that creates personalized routes through different parks, including Disney and Universal. During his presentation he talked with us about many different resources that he and his team have come up with in order to create optimal touring plans. Since this is essentially a larger scale traveling salesman problem, like we learned about earlier in our trip, he uses evolutionary or genetic algorithms to provide optimal solutions. This part was very interesting to us because just yesterday we all presented our projects for which we had to use genetic algorithms of our own design to generate efficient routes that included ten rides in the Magic Kingdom. Touring Plans uses steps that are similar to those that we took in our own projects, however with more constraints and on a far greater scale. In addition, they are exploring other applications of various optimization methods, including the Disney Dining Plan and ticket purchases. Furthermore, he has recently extended his focus to the world of medicine by using his experience to guide doctors' prescriptions of medication to diabetes patients in an effort to minimize cost and maximize benefit to the patients.

Our group with Len Testa (second row, third from the right)

Data Collection

McKenna collected data on Alice and got a picture too!

Following our meeting with Len Testa, we split up into pairs for some data collection regarding character meet and greet lines. Each pair was assigned a character to collect data on for two 15 minute time periods. In those time periods we took note of how many families were in the line before we started our time, how many entered and exited, how long each family spent with the character, and how many autographs were given per group. At the end of our collection, we were all relieved that none of us were picked up by Disney Security since we were lingering around the character meeting spots collecting data. For our next project, this data will be used to analyze the efficiency of character meeting lines all over Disney.

Disney Springs!

After collecting data and lunch in World Showcase, we took our first trip to Disney Springs, formerly known as Downtown Disney. This area is similar to an outdoor mall filled with Disney merchandise along with well-known stores and some restaurants. Our favorite place in Disney Springs was the World of Disney, which is the largest merchandise store on Disney's property. If you are looking for something Disney, there is no better place to shop! Following an hour and a half of shopping, we all met back at Sprinkles Cupcakes for a sweet treat. We all enjoyed trying different ice creams, cupcakes, and shakes! As we were finishing our treats, it began to rain, so we decided to head back to the hotel for some free time before we had to leave for the Luau. 

Everyone with their Sprinkles Treats!

You won't like him when he's angry.

Spirit of Aloha Show!

For dinner we went to the Polynesian Resort for a Hawaiian Luau. There was a lively atmosphere with delicious food, live music, and traditional dances from around the Polynesian Islands; Molly was even called up to dance on stage. Our favorite part of the performance was the fire dance. Watching him throw his flaming stick up in the air and balancing them on his fight had us captivated on the edge of our seats. The whole experience was so fun and definitely worth seeing! 

The Fire Dance

Polynesian Dancers

Written By:

Jamie

Molly