OPTIMIZING FOR FUN

Taking the kids to Disney World? You bought the tickets, reserved the hotel, arrived there, and … wooow there are so many things to do at an amusement park. You do not have time for all of the rides, or do you? Does it matter whether you ride the Space Mountain first and then Splash Mountain, or should you start with the Pirates of the Caribbean and finish up with a visit at Space Mountain? It turns out that some of these places are busier at different times and days of the week. According to The Unofficial Guide to the Walt Disney World, selecting optimal tours is the key to getting the most out of your visit. On days of heavy attendance, groups who did not use The Guide ended up spending an average of three and a half hours more in line and experienced 37% fewer attractions than did those who used the touring plans suggested by the authors of The Guide.

The 2010 edition of The Guide is part of a series that has sold over four million copies and devotes an entire chapter (pages 75 through 107) explaining the significance of optimal tours and how they were derived. In page 76, the authors express their thanks to Nick Sahinidis and his graduate students “who have contributed a number of exceptionally helpful studies.” Did Nick take his graduate students to Disney World and come up with optimal tours? Not really. It turns out that the problem of optimal tours at Disney World is mathematically identical to certain production scheduling products. When production in a continuous chemical reactor is switched from one type of polymer to another, there is an inevitable transition time, during which the intermediate product satisfies neither the specs of the starting product nor those of the final product. The intermediate product must be recycled at a cost proportional to the transition time. In turn, this time depends on the starting and final products. Sequence-dependent transition times give rise to interesting optimization problems, as explained in Nick’s paper [1]. Back in the early 1990s, Nick and his first graduate student, Russ Vander Wiel, addressed a natural extension of this problem, the case when transition times depend on sequence as well as the time of the day that the transition takes place. This, time-dependent traveling salesman problem, became the subject matter of three papers [2, 3, 4] that, apparently, are acknowledged in The Guide. Who says research in optimization does not impact the life of everyday people?

2.          Vander Wiel, R. J. and N. V. Sahinidis, Heuristic bounds and test problem generation for the time-dependent traveling salesman problem, Transportation Science, 29(2), 167-183, 1995.

3.          Vander Wiel, R. J. and N. V. Sahinidis, An exact solution approach for the time-dependent traveling salesman problem, Naval Research Logistics, 43(6), 797-820, 1996.

4.          Vander Wiel, R. J. and N. V. Sahinidis, The assignment problem with external interactions, Networks, 30(3), 171-185, 1997.