If you buy something using links in our stories, we may earn a commission. Learn more.
Last month GeekMom Dak reviewed Touring Plans, a website and app that helps you plan your Disney vacation and knock hours off queuing times at the theme parks. Touring Plans' features included crowd calendars, wait times and customisable plans that allow you to select the attractions you are interested in seeing each day before the site gives you a detailed, unique itinerary. But where does the data for such a system come from and how do you go about creating a website that can instantly produce such a detailed plan for the millions of permutations each park offers on a single day? I spoke with Len Testa, the founder of Touring Plans and co-author of The Unofficial Guide to Walt Disney World, about the mathematical side of planning your dream Disney trip.
You have a master’s degree in computer science and did your thesis on heuristics for time-dependent travelling salesman problems - can you explain what that is for non-mathematicians?
Probably the most straightforward example of the time-dependent travelling salesman problem is the kind of scheduling that a company like FedEx or UPS has to do for one of its drivers. The company’s goal is for the driver to deliver packages to customers in different locations while minimizing the overall cost, including labor and fuel. At any point in the day, the FedEx driver has to take into account not only the distance between his current location and the next customer, but how much traffic will delay him when he’s on the road to that next customer. For example, the driver may decide to take a 4-mile detour on a rural road to get to the next customer, rather than drive a 1-mile stretch of I-95 at 5 p.m. on a Friday. The I-95 segment may be shorter, but the rural road is faster because it has less traffic. The trade-off there is slightly higher fuel cost for much lower labor costs.
How did you come to work with Bob Sehlinger on The Unofficial Guide to Walt Disney World? Why did you choose to use your qualifications on a Disney related project?
After I finished my undergrad degree (also in computer science), I visited Walt Disney World the summer before I started graduate school. One day during that trip I waited in line almost two hours for the Great Movie Ride. Sometime during that wait I thought that there should be an app for minimizing your waits in line at theme parks.
I went back to my thesis advisors and discussed the problem. They proposed a literature search, which showed it was a suitably difficult problem. Once they gave their approval, I contacted Bob to see whether he’d share his data from the book.
It turned out that he was using a different approach than I was envisioning, so we didn’t get to share data. But Bob was exceptionally generous with his time, explaining how his modelling worked and what to look out for when creating a schedule for theme parks. We stayed in touch through my graduation, and I started joining Bob’s team for in-park research in 2000. Because I was spending so much time in the parks for touring plan research, I started updating other sections of the book when it needed to be done. I became co-author of the Guide in 2007.
You and Bob also own the Touring Plans website and smartphone apps. Can you tell us a bit about them and how they differ from other Disney park sites?
Two things make the Unofficial Guide book, the Touring Plans website and the Lines app different: First, our research is consumer-oriented. That means that we’ll tell you in plain language whether an attraction isn’t worth your time, or a restaurant isn’t worth your money. Second, we’re a data-driven organization. Our staff consists of scientists applying their knowledge to travel problems, which is unique in the travel publishing industry. This allows us to tackle things like touring plans, which are complex scheduling problems. It turns out that there are quite a few vacation questions that can be answered through science, math and operations research. Finding the least-expensive combination of Disney admission tickets, for example, is a bin-packing problem.
The other thing that makes our app different is that we’ll estimate how long you’ll actually wait in line at a given ride at a given time of day. Every other app just tells you Disney’s posted time, or (worse) tries to estimate Disney’s posted wait time because they don’t have people in the parks feeding them data. Any theme park veteran will tell you that the wait time posted outside an attraction isn’t how long you’ll really wait. Sometimes the posted waits are set artificially high on purpose, as a form of crowd control, to get people to get in line somewhere else. Sometimes the waits are set high at the end of the day to dissuade people from getting in line, so management can close the park on schedule and keep their labor costs low. And sometimes the posted waits are too low, because the kid staffing the sign got caught up doing something else.
On your staff you have two other computer scientists and three statisticians. How did you approach them with the concept of Touring Plans?
Just like me, they approached us by writing in to the Guide. We explain our scientific approach in the book, and that’s a powerful draw for some very smart people. There’s something about letting people apply their knowledge to Disney theme parks that is just irresistible. Lots of people will volunteer to work for free. All of our staff has come to us through the site and the book; we’ve never had to look externally.
How do you think your candidate hiring differs from other simulation software/Disney hiring?
A lot of it is the same for any organization, including Disney. We’re looking for bright, self-directed, team-oriented people. Because we’re both writers and scientists, we probably put more emphasis than other companies on the combination of fact-based decision making and strong oral and written communication.
I spent a long time doing architecture in American Express’ technologies group prior to joining the Guide. AmEx Technologies is an excellent place for computer scientists to learn how to run a company; their leadership team is level headed and fact-based. They make their tech teams responsible for rationalizing tech investment to the business group giving the funding. You learn how to verify that your idea makes business sense and how to communicate the investment to an audience whose skills are outside of technology.
The Touring Plans website has been self-funded and profitable since Day One because of that training. I couldn’t have had better preparation.
In what year did Bob create the original software to create the touring plan itineraries?
Around 1986, two years after the first edition of the book. It took that long to develop the model, in between writing and researching other books.
Bob’s original modelling software used OR and queuing theory to solve the problem. Can you explain what those are and how they apply?
Operations Research (OR) is a collection of techniques for making efficient decisions, usually in the context of running a business. OR problems tend to have real-world parallels and real-world constraints. Problems such as deciding on the most profitable set of products to manufacture with a limited amount of raw material might be an OR problem. Scheduling is a classic OR problem, because it involves making lots of decisions about what to do when.
Queuing theory is the study of waiting in lines. I believe it originally started with trying to model telephone exchanges, where people needed to know the minimum amount of capacity to build to handle a certain number of phone calls at a certain service level. You see queuing theory at work in banks and fast food restaurants, where the establishment has a certain number of tellers or cashiers working so that some number of customers gets served within a certain amount of time on average; that’s important because the longer a customer waits in line, the less happy they’ll be.
It’s the same idea for theme parks where you’re trying to balance the customer’s satisfaction with their wait in line versus the cost of running the ride. Sure, you can always run Space Mountain at full capacity, even during the slowest times of the year. That will increase the wear and tear on the infrastructure, take a lot of labor and cost a lot of money, for perhaps small gains in customer satisfaction. A better way to do it is to estimate how many people will want to ride Space Mountain in a given day, and estimate the times of day they’ll arrive at the ride. If you know how many people fit into a ride vehicle and how long it takes the vehicle to make a complete circuit of the track, you can figure out how many employees you need and how many ride vehicles to have running so that nobody waits more than, say, 20 minutes. You can also test customer satisfaction when they wait 10, 15, 25 and 30 minutes, and figure out where the happy medium is between guest satisfaction and your cost to run the ride.
What improvements did you make to the original algorithm created by Bob?
The fundamental difference between the first app and the current app is that the first app approached the problem as if we were theme park managers trying to route people through the attractions. So we had to make assumptions about things like how many boats were operating on It’s a Small World every day, how many trains were running on Big Thunder Mountain, how many employees were staffing the Mad Tea Party, and so on; plus how many people were visiting the parks, the relative popularity of the attractions and so on. It was a lot of the details that you need to know if you’re running a theme park.
The current app’s approach is to approach the problem from the guest’s point of view. The average theme park guest doesn’t know anything about the internals of running a theme park. The only real piece of information they have is the wait time posted outside each ride in the park. It turns out that that’s really all you need. If you think about it, the wait time at each ride is really the expression of all that other stuff: how many ride vehicles are in operation, how many people are staffing the ride, its popularity, and so on.
How much has computing technique changed for solving traveling salesman problems since Bob began?
There have been changes in both the infrastructure we use and the way we approach the problem. Bob’s original model ran in Excel, probably on a single-core Mac, on problems he hand-coded for the next edition of the book. It was a linear programming problem, for you OR people out there. Today we deploy on virtual machines within the Amazon Cloud, automatically scaling up and down to optimize touring plans in real time for users who are in the theme parks. And the algorithm is a hybrid of several different techniques, built around an evolutionary algorithm framework.
Can you explain in layman terms what the algorithm/logic is for solving this complex problem?
Sure. An algorithm is like a recipe: you start with some raw ingredients, whether it’s data or eggs, sugar and flour. You follow a specific set of steps in a specific order to combine and process the ingredients. The end result is a finished product, either a solution to a problem, a cake or whatever.
Our basic framework is an evolutionary algorithm, which models biological evolution. We start by creating a “gene pool” consisting of a few randomly-generated touring plans with the attractions the user has chosen. We “score” these touring plans to see how long they’d take to complete, if the user were to follow them in the park. Then we choose one or two of the touring plans to “mate,” which means we combine them together in a certain way to produce a new touring plan. We score that new touring plan, and if it’s better than the worst touring plan in the gene pool, the worst one dies and the new one takes its place in the population. Just like in real evolution, mutations (such as swapping the position of two rides in a plan) are introduced occasionally to keep the population diverse and evolving. The hard part was developing those mating functions.
Having an EA framework was not my idea. I was fortunate to have Gerry Dozier and Al Esterline on my thesis committee. Gerry now heads the Computer Science department at North Carolina A&T State University. He can explain more about EAs over lunch than I could learn in a week of reading texts; he’s got a gift for teaching. Esterline’s just the smartest person I’ve ever met; any programming language issue, any sort of problem, he knows the right way to solve it. I’ve never seen that kind of encyclopaedic knowledge anywhere else.
Have you had any feedback from Disney themselves regarding Touring Plans and the models and statistics you have developed?
We’ve never heard from Disney in any official capacity about any of the models or the apps. Unofficially, we’ve heard that restaurant wait staff will use our crowd predictions to figure out where to work extra shifts to make more tips. Once while we were testing our mobile app, we saw a Cast member in Disney’s Hollywood Studios using our app to adjust the wait time sign at an attraction. He figured our estimate was more accurate than Disney’s. (As it turned out, we were.) So I think that somewhere, within Disney, someone knows who we are.
The smartphone apps can recalculate your planned park itinerary based on ride data direct from the parks including current wait times on rides, how do you access the data you use?
The wait times are crowd sourced from within the parks, and we have paid staff which collect times as well. Those are fed into our statistical models in real time. The models will generate updated crowd forecasts for every attraction in the park for the rest of the day, based on what’s happening in the parks right now.
Have you faced problems with how long it took to compute so many itineraries for the thousands of users who might be using the app at the same time? How does the time taken to compute a touring plan for a user compare with the time taken when the site was first launched?
The original version of the optimizer, as we call the engine that creates touring plans, was written in Visual C++, single-threaded, and ran on a Windows PC. It took a couple of minutes to produce a touring plan that was within a couple percent of optimal, most of the time. Now we’re on Amazon’s auto-scaling cloud and the app is running on multi-core virtual machines. By working on the algorithm for over a decade, we’ve got the running time down to 10 to 30 seconds to produce an optimal solution. It’s still in C++ and single-threaded. Single-threading keeps the code simple. We figured it was cheaper and less error-prone to use the Amazon infrastructure for parallelism, so that’s how we architected.
How much have you had to change your algorithm over the years to allow for new features at the parks i.e. the introduction of FASTPASS, the recent enforcements of FASTPASS time windows or the new restaurant reservation timelines?
Not much. The app is, at its core, a general-purpose scheduling engine. It doesn’t have special rules built in for FASTPASS or for time windows or anything like that, since processing the special rules is time-consuming and difficult to program. It also doesn’t apply to other theme parks, such as Universal, which has its own slightly different reservation system. We’re not going to build a different app for every theme park.
All of the constraints, such as FASTPASS ride reservations, are encoded into the input data so that the engine just has to process the data. For example, one way to have people make use of FASTPASS is by writing rules that tell the engine to look for a FASTPASS reservation at Space Mountain, then check whether the reservation is valid for the time the user actually arrives, then compare the wait time using FASTPASS to the wait time if they user just got in the regular line. That’s a lot of code, takes a lot of CPU cycles and is brittle. Why not just feed the engine a set of wait times that show dramatically lower waits when you want the user to FASTPASS the ride, and let the engine figure out that it’s the most efficient approach?
How is Touring Plans collecting the “initial conditions” to run the model, e.g. to predict that Toy Story Mania is a popular attraction where does the trending data to that effect come from? Are you able to purchase the data from Disney or do you collect input from subscribers or by some other method?
We have data from every park, every day, going back many years. Our models are able to pick up on those trends over time, including seasonal trends. We’re able to tell, for example, that water-based rides such as Splash Mountain are not good indicators of crowds, because the air temperature influences people’s decision to ride. New Year’s Eve may be the Magic Kingdom’s most crowded day of the year, but waits at Splash will be low if it’s cold, regardless of how many people are in the park.
How often do you renew ... or refresh ... the data to keep it up to date. Daily? Weekly? How often does feedback from subscribers get incorporated?
The current day’s predictions are updated every five minutes. The forecasts for the next 365 days after today are updated nightly.
Do you report on trends in this data? For example the month of September, historically a very quiet month for WDW, is becoming less quiet over the years as we have helped to spread the word that September is the time to go.
We get calls from the investment community looking to know whether attendance is up or down at the parks. Usually, though, the fluctuations in attendance are 1, 2, maybe 3 percent one way or the other. We’re not yet at that level of resolution, so it’s hard for us to be that accurate. We’re trying.
One of the trickiest (and costliest) parts of a Disney vacation is figuring out which tickets your family needs. You’ve described figuring out the cheapest tickets as a “bin packing problem;” what is one of those and how does it apply to theme park tickets? What sources do you use to find the cheapest tickets besides official Disney retailers?
A quick Google search of “define bin-packing” will probably yield a better explanation than what I’m about to give, but here goes: think of bin-packing as the problem of trying to fit all of your groceries into as few shopping bags as possible. Every item has a specific size and shape, and the choice you make about which items go in which bags will ultimately determine how many bags you use.
Disney has dozens of different ticket options, depending on what you want to see and for how many days. For example, it’s got a ticket that gets you in to exactly one theme park for exactly one day, and it’s got a ticket that gets you in to exactly one water park for exactly one day. Other ticket that gets you in to one theme park and one water park for exactly one day each; two theme parks and two water parks for two days each, and so on. The question becomes, if you want to visit theme parks for N days and water parks for M days, what’s the cheapest combination of tickets to buy so that you get at least N and M days of admission?
It turns out that the easiest way to solve the problem for any user-provided values of N and M was to code it as a recursive bin-packing problem, so that’s what we did. It’s called the Least-Expensive Ticket Calculator and it’s available from the Touring Plans home page. We estimate that the average family can save $40 on its theme park admission by using it, and it’s absolutely free to use.
You can buy your admission from Disney, of course, but there are wholesalers who provide discounts on certain kinds of tickets and who’ll ship them to you at little to no cost. We include these wholesalers tickets as options in our ticket calculator, and we include only those wholesalers with whom we’ve established an ongoing relationship. We’ve bought our own tickets from these people, we talk to them periodically about pricing trends, we’ve visited their store – they’ve gone through a vetting process. We know they’ll stand by their product.
The amount of time required to go on a ride is easy enough to calculate but how do you create a model for more time variable activities such as character greets or meals and how are those models calculated when new characters are introduced? Such as Princess Tiana or Rapunzel/Flynn Rider from Tangled?
Waits for meals are pretty straightforward. Most people usually allow enough time, 30 to 45 minutes or whatever, so that a few extra minutes waiting in line doesn’t affect their schedule. Waits for character greetings are harder to model because they’re not like either a continuously running attraction or a show. Many character greetings happen only a few times a day, such as 12, 3 and 6 PM, and last only 30 minutes. If you get in line at 10 minutes before noon, there might be so many people already in line ahead of you that you have a 30-minute wait. And unlike a show, the wait will get longer after the character greeting has started. If you try to get in line 15 minutes after the starts, you may be told that you’re too late, because it’s going to take the rest of the character greeting’s time to get to everyone already in line.
How do you calculate a Touring Plan including a new character or experience/attraction on release day when no data exists for it?
A combination of educated guessing and legwork. Before the attraction opens we try to estimate its popularity based on how similar attractions have opened. For a headliner attraction such as Radiator Springs Racers in Disney California Adventure, we may look at how long the initial lines were for Indiana Jones at Disneyland when it first opened, to see how long people are willing to wait before they balk.
We also try to estimate the attraction’s hourly capacity. Disney’s usually really good about sharing that with us, although sometimes we’re able to piece it together ourselves. The plans for The Little Mermaid attraction at Disney California Adventure were on display to the general public inside the park, and had the ride’s speed, number of ride vehicles and passengers per vehicle printed on them. I think we calculated the hourly capacity on our iPhones’ calculators while standing in front of the plans.
What was the trickiest problem to solve during the creation of Touring Plans?
The concept of “free time,” where you may have 15 or 20 minutes with nothing to do before your next attraction, was a little hard to code and definitely hard to communicate to users. An example of free time is when you tell the engine you’re going to be in the Magic Kingdom for 13 hours, perhaps staying to see the nighttime fireworks, and the engine thinks it’ll only take 8 hours to see all the rides and shows you’ve selected.
If you’re busy for 8 hours in a 13-hour day, you’re going to have 5 hours of free time. The engine has to put those 5 hours of free time somewhere in the schedule. And it chooses where to place the free time so that the overall amount of time you spend waiting in line is minimized. In practice, what happens often is that the engine will put the free time in early afternoon, say between 1 pm and 4 pm, since that’s when the parks are most crowded and lines are longest. And it’ll put you on rides and in shows during the morning and evening, when lines are lowest.
Some folks will write us to say that the engine must be malfunctioning, because it has this huge chunk of free time scheduled in the middle of their day. Most folks think that the free time should come in the evening but whenever we’ve looked at the plan, it’s always optimal for the free time to come in the mid-afternoon. So we’ll encourage people to move steps around in their plan and use the ‘Evaluate’ button (which doesn’t re-arrange their steps) to see how much longer their version takes, and it’s usually a significant difference.
Touring Plans provides data for both Walt Disney World and Disneyland. What are the big differences between the two resorts from your mathematical standpoint?
They’re fairly similar, because it’s easier for Disney to run the parks if they’re similar. Disneyland does have one big difference: a show called Billy Hill and the Hillbillies, which is held inside a restaurant. It’s the only show-in-a-restaurant in either park. If you want to both see the show and eat lunch, the most efficient thing to do is see the lunchtime show. And Disneyland is the only place (for now) where that’s possible.
What kind of computing power do you use for this? Multi-processors? PC? Mac? Linux?
It’s all Linux-based Amazon Elastic Cloud virtual machines, and other Amazon Web services. We set up the image and Amazon keeps it running. It’s one less thing for us to have to think about. Jeff Bezos is a smart dude.
Do you plan to expand Touring Plans to cover other Disney parks worldwide? How about the Universal parks?
We’ll add Universal Orlando by early 2013. We may do Disneyland Paris depending on the demand and whether we can get enough data. I got the chance to visit Thorpe Park, Chessington, Blackpool and Alton Towers when I was in the U.K. doing research for our Britain’s Best Days Out book. I’d love to see how the app works at Thorpe. Those folks seem tech-friendly.
Do you have anything else you’d like to add?
I got my start in professional programming doing C on an AT&T 3B2 running UNIX System V, and through a friend at Bell Labs I was able to get copies of some of the original Kernighan and Ritchie documentation on how it all worked. I loved that machine, and I still love UNIX.
When I did my Masters thesis I found that Kernighan had, with Shen Lin, also made this major contribution to combinatorial optimization. In fact, our optimization engine uses a proprietary variation of the Lin-Kernighan heuristic to create touring plans. I’d tell you how it works, but I’m saving it for my Ph.D. thesis.
Anyway, a few years ago I sent Mr. Kernighan a copy of The Unofficial Guide, thanked him for everything he’d done, and said that I’d made a pretty comfortable living primarily off the stuff he’d invented. He sent back a nice note. I was thrilled.
