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. 

What Are the Odds?

We have crossed the halfway point here at Disney World on day 11 of our MayX. Blogging today are Mary Lib and Zack! We started our day later than normal, giving us a chance to make up for the sleep that we missed out on for our Keys to the Kingdom tour yesterday. After class and lunch we spent our afternoon in Animal Kingdom and are currently writing this blog from Panera at dinner.

Morning Class Time

In our class time this morning, we discussed binomial experiments, probability distributions, and applied the idea of conditional probability to the game Liars Dice which we played yesterday. 

A binomial experiment uses a binomial random variable and allows you to calculate the likelihood of an outcome after performing n-trials in which each results in a success or failure and the probability is fixed and independent for each trial.  This technique can give the probability of a coin landing on heads 5 times if you flip it 7 times. The expected value is the weighted average of outcomes which could tell you how many times you would expect heads if you flip a coin a certain number of times.

Related to the binomial random variable is the geometric random variable. It gives the probability of the first success happening on trial k. This can be used in Disney to see when the first person will give up on a line that isn't moving.

In our games of Liars Dice last night, we could see our dice and had to make a guess on how many of any number there were based on what we had in our hands. Conditional probabilities use this kind of information to calculate the probability of A, given B. Knowing our dice, conditional probability would allow us to make a more accurate bet on the total number of dice displaying a certain number.

Animal Kingdom

In the park today we had FastPasses for Finding Nemo the Musical, Expedition Everest, and DINOSAUR! 

Many of our group took the time to ride Expedition Everest, Primeval Whirl, and watch the It's Tough to be a Bug show before our FastPasses. The It's Tough to be a Bug show was a lot more interactive than any of us remembered. We were sprayed with bug spray, poked in the back by bees, and had bugs crawling on the seats under us. This show is actually inside the Tree of Life, so the line to get to it brings you close to the animals carved into the tree.

While a little cheesy at parts, Finding Nemo the Musical was a cool adaptation of the movie. The actors are much more talented than either of us - singing, dancing, and puppeteering - all at the same time. Our favorite scene was with Squirt the turtle who was flying and flipping over the stage. Thanks to Crush and Squirt, Mary Lib will have "Go With the Flow" stuck in her head for the next few days. 

We finished up our park time on Kali River Rapids. The warning that "you will get wet and may get soaked" was quite the understatement. Based on our experience, the warning should have just said, "Plan to get soaked." However, it was a nice refresher in the heat.

Tonight

Tonight our groups are working on our second project of the trip. On Monday groups tested strategies for our traveling tourist problem. This project asks us to design new solutions to the problem by using genetic algorithms. A genetic algorithm creates new tours based on your current best solutions to the problem. Each group has to create their own operators for creating new tours based on altering one parent tour or a crossover tour from two parents. 

Written by: Mary Lib Saine and Zack Miller

If You're Not First, You're Last

Hey everyone! Today's blog is brought to you by Courtney and Zack! Today was day 6 of our time in Disney World, and what an adventure it was.

Today we tackled the "traveling salesman problem" in the Magic Kingdom. Arriving well before the gates were opened, we were able to be at the front of the line to enter the park at 8:50 and start the competition. However, Disney cast members were at the front of the crowd setting the pace for getting to rides at the back of the park.

For spending a full morning and afternoon in the park, we lucked out on the weather. The rain mostly held off for us and clouds gave us some shade. We spent our night relaxing a little and then working on our workforce scheduling projects. As we get deeper into the problem we are running into some of the details that we hadn't considered so far that are very important for programming our models into the computer.

Group photo after we all finished the traveling tourist problem
and ate our Dole Whip reward

Traveling Tourist Problem

Caroline, Alex, and Lindsay
playing with some toys

On Prince Charming's Carousel
with Molly, Courtney, and McKenna

The challenge in our traveling tourist problem was to find the most efficient path between 17 rides and two picture requirements in the Magic Kingdom and complete it all before 6pm. There were a number of attractions that every group had to visit, and some attractions that we were given a choice between. We were all given data last night that included the ride time for every attraction, the walking time between attractions, and the average wait times throughout the day which we used to make our plan for the day. For the attractions we had to choose between, many groups took into account the ride times and the average wait times and made their decisions based on which attractions would take the least amount of time.

Statue of Walt Disney with
Zack, Mary Lib, and Johanna

Jamie was thrilled to meet Ariel along
with Alyssa and Maria

One member of each group was carrying an iPad with them all day which recorded that group's path through the park. Most of our maps turned out looking like a child scribbled with a crayon over the Magic Kingdom. All of the crisscrossing across the park shows that many groups placed more emphasis on wait times than walking distances when choosing their next rides. 

Both of our groups found that we deviated from last night's plans due to ride closures and unexpectedly long lines at rides that we thought we could get through later in the day. Many of our plans were based on the average wait time data that we were given, but we found that the real 

world is much less predictable.

Goofy and our professors

Unfortunately for some, in our traveling tourist problem, each group had to complete the full circuit of attractions even after a winner checked in at the finish line. When the first group crossed the finish, there was a collective sigh from all the groups still racing. The final group crossed the finish line at 4:48, well before the 6:00 cutoff. The official results of our competition will be posted sometime in the next few days with more details on the strategy of each group. This was our second and final competition between student groups and the professor group (who didn't win this time). At the end of the competition, though, everyone 

was treated to a Dole Whip reward at Aloha Isle.

Written by: Courtney Gale and Zack Miller