Maximizing Fun in a Theme Park:
The M7TP
by Michael Cardiff,
Gwyneth Hughes,
and Robert Bosch
Introduction
This page is a companion to the article "Maximizing Fun in a Theme Park:
The M7TP".
In our opinion, this paper serves two purposes: (1) it provides an accessible
introduction to how integer programming can be used to solve Traveling
Salesperson Problems (in particular, the approach devised by Dantzig, Fulkerson,
and Johnson in 1954), and (2) it demonstrates how integer programming can
be used to solve a related problem, that of constructing a "fun maximizing"
itinerary for a theme park. By the way, M7TP stands for
"Maximizing Mirth and Merriment on Mickey Mouse's Magical Mystery Tour Problem."
Files
If you would like to read our paper:
- m7tp.ps : A copy of the paper, in postscript format.
If you would like to download the C program and data files we used to create the
".lp" files for CPLEX:
- Instructions : The instructions on how to
use the files below.
- m7tp.c : The C program that takes as input the files
mkdist.dat, mkrides.dat, and sec.dat
and produces as output a CPLEX ".lp" file that describes an integer programming
formulation of the problem.
- mkdist.dat : The data file that contains the
distances between all rides.
- mkrides.dat : The data file that contains the
times and fun values for each ride.
- sec.dat : The data file that contains information
on (added) subtour elimination constraints.
Finally, if you'd like to work
through the example problem found in the appendix of our paper
and you'd rather not type in the data and constraints by hand:
- small-m7tp.xls : An Excel file for a small
instance (involving just two of the six "lands" that comprise the Magic Kingdom)
of the M7TP.
To do this example problem, you will need a copy of Microsoft Excel, with the
"Solver" feature installed. For more information on how to do this, please see
www.microsoft.com.
If you have comments, please e-mail
bobb@cs.oberlin.edu
Link to
Bob Bosch's
page.