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 

Day 9: Thy Kingdom Come

Hey there readers, it's Molly and Lindsay walking you through Day 9 of Math and the Mouse. Today we presented our first project, had class, met with some members of Team Disney, and got to finish the day in Magic Kingdom!

Mickey calls this pose "the wizard"

Presentations and Class:
For the past week we have been working on a hypothetical workforce scheduling problem for Pecos Bill Cafe. As mentioned in earlier blog posts each group was given an objective that they had to minimize and a certain set of constraints. For example, my group (Molly, Caroline, Zach and Alex) had to minimize the number of shifts of different length while also meeting or exceeding the required workload for each fifteen minute time period. On the other hand my group (Lindsay, Mary Lib, Jamie and Alyssa) was similar to Molly's group but our objective was to minimize the number of over-scheduled shifts. Today we had to present our projects to the rest of the class. It was very interesting to see that while we had similar problems to solve, we each had our own way of modeling the problem. Dr. Bouzarth even mentioned that having different perspectives is useful while doing research because it allows for more creativity when trying to reach a solution and when each method returns a similar solution, there can be more confidence in the likelihood of a correct solution.

Group 1 (Maria, Johanna, McKenna, Courtney) presenting their project

Today Dr. Hutson taught us a new way to solve the Operations Research problems we have been working on this trip.  In these types of problems, we are trying to come up with the “optimal solution,” or best possible solution, to a problem.  One example is the Traveling Salesman Problem, where we picked an order to ride attractions in the Magic Kingdom so that we could ride all the rides as quickly as possible.  In this problem, the tour that got us through the rides in the shortest possible time is the optimal solution.  Unfortunately, in many problems, including the Traveling Salesman Problem, finding the optimal solution takes a really long time (months or years), even for a fast computer.  Since most people probably don’t want to wait for ten years before making plans for which Disney attractions they will be riding the next day, it is important to be able to generate solutions quickly.  One way to do this is to find a really good solution to a problem instead of finding the very best solution.  This might mean a tour through the Magic Kingdom that takes 10 minutes longer than the best possible tour.

One way to find a really good (but not optimal) solution to problems like the Traveling Salesman Problem is called the genetic algorithm, which Dr. Hutson taught us this morning. This approach tries to mimic biological reproduction that we see in nature.  The first step is to randomly generate lots of possible solutions (not necessarily good solutions) to the problem.  For example, we could generate lots of completely random paths through Magic Kingdom.  Then two of these solutions can be mixed together to make a “child” solution.  Good child solutions are kept so that they can be paired to make even more child solutions.  Eventually, a very good child solution will be produced.  After learning some theory, we got to play around with a program that a previous Math and the Mouse student wrote that uses a genetic algorithm to solve the Traveling Salesman Problem in Disney World.  It was pretty crazy to see a solution to a problem that we had worked on for hours generated in just a few seconds.

Team Disney: 

After our morning class, we had the unique opportunity to meet with some Disney professionals.  After getting cleaned up and dressing in something a bit nicer than workout shorts and t-shirts, we drove out to their Team Disney office building, where we were able to get a group picture with the Seven Dwarves.

Even the office building was up to the Disney standards we’ve come to expect. Though we weren’t allowed to take any pictures (sorry guys, Disney secrecy!), we can tell you that the whole building was decked out in Disney fashion, down to rugs with Mickey Mouse ear designs. We could tell that our hosts had been kind enough to make a special exception for us, because everyone was looking at this large group of college students as though we were talking teacups. Our afternoon was broken up into four different talks. One was about workforce management, which we are all pretty familiar with after our Pecos Bill scheduling project. Another session focused on using simulation to model theme park rides and attractions to work out the kinks before the rides are actually built. Our third talk was about how Disney creates memorable experiences for their guests. I, Lindsay, experienced this special Disney treatment at dinner, when I asked for a refill of my drink. Even though the restaurant doesn’t normally give refills, I was given a new drink with a Mickey straw, because I “didn’t know and walked all the way up there.” The last presentation was about machine learning – a bit of history, and then the different types of machine learning that can be done. After saying goodbye to our hosts, we hung out in the lobby for a while to avoid the rain, and then set off for Magic Kingdom.

Evening:

Jamie with Princess Belle

Dr. Harris ready to perform his role

Immediately following our meetings at Team Disney we made our way over to parks for an evening in the Magic Kingdom. When we arrived we were all a little hungry, so we decided what better way to celebrate our completion of our workforce scheduling project than a group dinner at Pecos Bill Cafe. Like their sign said the food really was the best grub in the west, at least in the western section of Magic Kingdom.

With our appetites satisfied we were ready to conquer our favorite rides. A visit to the Magic Kingdom is not complete without riding Space Mountain, Splash Mountain and Big Thunder Mountain Railroad and so we made sure to hit all of those at least once or even three times. After meeting Mickey in Town Square Theater, we all broke off to ride different rides. We still had fast passes for two rides but decided to ride them separately. Our first fast pass was for Enchanted Tales with Belle, reenactment of when Belle and the Beast first fell in love. Although the ride is meant for younger kids, it was still fun for us because both Dr. Harris and Jamie were chosen to play the guards.  It was hilarious watching them march around the room to the tune of "Be Our Guest". Our final Fast Pass was for Big Thunder Mountain Railroad and we were able to time it so that we got on the ride as soon as the fireworks show was starting and Thunder Mountain has one of the most amazing views of the castle from the ride. Since it is one of our favorite rides and even more fun to do in the dark, we took advantage of the 10 minute wait time and rode the ride two more times! By then it was getting late and so we headed back to the hotel for some rest before our 8am Keys to the Kingdom Tour the next morning!




Written By:

Molly

Lindsay

Day 4: Lions, Tigers and Yetis, Oh My!

Jambo, readers, Molly and Alyssa here giving you the highlights of our day exploring Disney's Animal Kingdom. Jambo means "hello" in Swahili, which we learned from our tour guide during the Kilimanjaro Safari.

Our mandatory group photo in front of the Tree of Life

Our Morning:
We arrived at the park as soon as it opened in order to have as much time at the park before our math portion of the day started. Since our first fast pass was not until 11:00, we were given free time to roam the park. For our first ride we took advantage of the short wait time at Expedition Everest, the popular attraction where riders encounter the infamous Yeti as they venture through Mount Everest. From there we went our separate ways to explore the parts of the park that we were most excited about.

Molly:
After riding Expedition Everest, my group decided to journey through the Maharajah Jungle Trek, a wildlife trail in the Asian Section of Animal Kingdom. On the trail we came across many animals native to Asia such as a komodo dragon, a tiger, some water buffalo and various Asian birds. We were very surprised to see that the tiger, water buffalo and deer are all kept in the same enclosure, thinking that there was no way that was safe for the other animals. However we were assured that the tiger is kept very well-fed and usually just keeps to herself in the shade. On our way over to Dinoland, USA we got distracted by some monkeys right outside the Maharajah Trek. We stayed and watched them for a while, fascinated by the way they moved around, swinging from one rope to another. Once we reached Dinoland we decided to ride Primeval Whirl and Dinosaur, which are two very popular, but both very different rides. On Primeval Whirl we were screaming with excitement, while on Dinosaur we were screaming with fear.

Alyssa: 
Some of us had so much fun at Mount Everest we decided to partake in the adventure again. Since we were now experienced expeditioners, we knew this time to look behind us during the two instances where the ride stops to see the track spin and redirect our course.Viewing this Disney “secret” was perhaps even more exciting than the Yeti sightings Disney wants you look at. After round two of Everest, we decided we needed our spines realigned so we ventured to Primeval Whirl and received a healthy dose of whiplash. It turns out that great math minds think alike, because we all reunited at Dinosaur. Together we enjoyed the exciting, albeit a bit terrifying end to our Animal Kingdom free time. After the ride Dr. Hutson was sure to point out the ridiculousness of a dinosaur being kind enough to help us with our time traveling mission by holding up the log that let us escape a deadly meteorite shower. This, however, did not phase us because we concluded that any dinosaur wanted by Disney must be of the friendly, life saving variety.

Reunited (and it felt so good): 
To ease our fears from riding Dinosaur, we boarded the Kilimanjaro Safari for a relaxing ride through the Harambe Wildlife Reserve, which is dedicated to the protection of many different African animals. On the ride our tour guide pointed out to us a wide variety of animals, ranging from hyenas and flamingos to rhinos and giraffes. The crowd favorite was the giraffe who almost stuck his head in the jeep. We had so much fun trying to spot animals as we rode along and by the end of the ride we had filled the storage on our phones with countless images of every animal.

This giraffe came right up to the side of our vehicle

A crash (group) of rhinos

Following the end of the safari, we made our way to the Festival of the Lion King, a show filled with singing, dancing and tumbling monkeys celebrating King Simba. The energy was so high that we couldn't keep ourselves from singing along to our favorite songs, such as "Circle of Life", "I Just Can't Wait to be King", "Hakuna Matata" and "Can You Feel the Love Tonight".

The finale of Festival of the Lion King 

We ended our day at the park in the exact same way we started, a final ride on Expedition Everest. This marked fourth time for some of us who rode it twice after lunch in the single rider line. With some guidance from Dr. Hutson we were all able to find the Yeti and our reaction was priceless.

Post Animal Kingdom Fun 

To celebrate the completion of visiting all four parks we all went to 7-Eleven to cheer our accomplishment with Slurpees. After that it was back to business, all of the attractions and adventure left us itching to do some math. In the previous days we learned how to model operation problems, but today we finally got to learn the most important part--how to solve them. First, we were introduced to a software called Mosel which basically does all of the hard calculating work for us. The user inputs the objective function, variable declarations, and constraints and the Mosel returns the optimal solution almost instantaneously! 

To introduce how to think about solving this type of  problem, Caroline graciously volunteered to step outside the “classroom” and be blindfolded. We then placed a Clif Bar on the floor, and when she re-entered the room she was allowed ask yes/no questions to direct herself to the prize. From this activity we learned that there are three types of questions you can ask when solving a snack finding problem, “Can I move?, Should I move?, How far can I move?”. It turns out that trying to find a snack while blindfolded is pretty similar to finding an optimal solution, because those are the exact same questions you ask when searching a graph for the right intersection of our constraints. 

For the rest of the night, we were given time to work on our group project. In this problem we are trying to create a work schedule for a Disney restaurant, where each group has to wrestle a different set of constraints. It may to be hard to believe now, but this time next week each group will have a solution to what now seems like a Mount Everest of a problem.

Written by:

Molly

Alyssa