Theme Park Route Optimization: Time-Dependent MILP Solver
An exact Gurobi MILP that plans a whole park day at once: which rides to do, in what order, and at what time, with every queue priced by the 30-minute slot you actually arrive in. The routing engine behind Mapblazer.
Problem Statement
Given a guest's must-do and nice-to-have rides, a start time and a time budget, decide which attractions to visit, in what order, and at what time. That is a Time-Dependent Orienteering Problem with mandatory nodes, and each of its three departures from the textbook Travelling Salesman Problem matters. You cannot do every ride, so the subset is part of the answer rather than given. The cost of visiting a node is its queue, which is not a constant but a function of when you arrive. And some rides are non-negotiable while others are merely worth points. The consequence is a circular dependency: the order determines the arrival times, the arrival times determine the queues, and the queues determine which order is best. Greedy rules such as "always take the shortest queue next" fail on exactly this, because the cheapest ride now can be the one that should have been left until the afternoon. The design question was therefore not which heuristic to use, but whether the whole day could be stated as one linear model and solved to optimality, with the time-dependence and the operational realities of breaks, opening hours and repeat rides all inside the model rather than patched on afterwards.
Results & Impact
22 min avg
Queue Time Saved
Vs. the legacy LLM planner, per itinerary, up to a full hour on a 12-hour day
83.3% faster
Response Time
10 s solver budget vs. 60 s legacy LLM average
$0.75 saved
Cost per Query
Token costs eliminated entirely
130 min
Day Shortened
Makespan objective vs. queue-time only, same 7 rides
0.4%
Gap to a 60s Search
Measured on 12- and 16-ride days
Exact
Optimality
Proven optimal to ~10 rides, best-found beyond
A Solved Day
| # | Arrive | Ride | Queue | Ride time |
|---|---|---|---|---|
| 1 | 09:07 AM | Tiana's Bayou Adventure | 13 min | 11 min |
| 2 | 09:33 AM | Matterhorn Bobsleds | 23 min | 2 min |
| 3 | 10:00 AM | Pirates of the Carbbean | 18 min | 16 min |
| 4 | 10:35 AM | Big Thunder Mountain Railroad | 27 min | 4 min |
| 5 | 11:09 AM | Space Mountainmust-do | 40 min | 3 min |
| 6 | 11:53 AM | Star Wars: Rise of the Resistancemust-do | 49 min | 18 min |
| 7 | 02:00 PM | Indiana Jones Adventuremust-do | 45 min | 4 min |
Cheap queues first
The four optional rides are cleared before 11 AM while their queues are still short, and the three must-dos are paid for later, once the morning is spent.
Idling on purpose
Indiana Jones lands at 2:00 PM, after the break, because the solver would rather sit through it than pay the morning queue. The day still ends at 2:48 PM rather than sprawling to closing time, since the objective charges for every minute.
Approach & Methodology
Naming the Problem Before Modelling It
The day is a single loop that leaves the park entrance and returns to it, so the depot is the entrance and the rides are nodes on a complete digraph. What separates this from a tour is that in- and out-degree are tied to a selection variable rather than fixed at one, which is the formal difference between orienteering and TSP: an unvisited ride simply carries no arcs and costs nothing, so choosing the subset and choosing the order happen in the same solve rather than in two passes that can disagree.
An Objective That Charges for the Whole Day
The model maximises priority-weighted rides minus a small charge on the arrival time back at the entrance, which is the makespan of the day. That single term covers queueing, walking, riding and idling at once. An earlier version penalised queue time alone, which left walking and idling free, and the optimiser exploited it exactly as written: it used the entire time budget and finished at closing time on every instance. Charging the makespan brought the same seven-ride Disneyland day in 130 minutes earlier with less walking, and it also gets the time-dependence right for free, because idling to reach a cheaper slot lengthens the makespan while the smaller queue shortens it. The solver therefore waits only when the queue it skips is bigger than the wait it costs, which is the correct trade and one a queue-only penalty cannot express.
Making Sure a Ride Is Never Traded for an Early Finish
Two terms in one objective need a defensible exchange rate, not a tuned constant. An extra ride can lengthen the day by at most the whole budget, so any per-minute charge below the smallest ride priority divided by the budget guarantees the ride reward wins. The default takes half of that bound for margin, which on a 480-minute day means a full-length day costs half of one optional ride and a twentieth of a mandatory one. The same weights are reused to score the reported routes, so the ranking the user sees agrees with what was actually optimised.
Time-Dependent Queues, Kept Linear
The visit is cut into 30-minute slots matching the forecast grid. Two big-M inequalities force the slot indicator to the slot the arrival actually falls in, one equation reads that slot's forecast out of the wait matrix, and the resulting wait feeds the departure time, which feeds the next arrival. Linearity survives because the forecast is a constant table: the product is a number times a binary, never a variable times a variable. That is the whole mechanism by which choosing when to ride changes the cost of everything downstream while the model stays a MILP.
Breaks, Opening Hours and Second Rides
A lunch break is a disjunction, finish before it or start after it, linearised with a binary that selects which of the two inequalities binds while a second big-M term excuses rides that were never visited. Operating hours are the same pattern without the choice. A ride worth doing twice becomes a virtual twin node with its own arrival time, a lower priority, and a constraint tying it to the original, which is what lets a pure routing formulation schedule the same attraction twice without any special-case logic in the search.
Connectivity Without the Exponential Family
Degree constraints are local, so they admit a valid depot tour plus free-floating cycles among the ride nodes. The classical repair adds a cut for every subset, 2^|R| of them, about a trillion at forty rides, which cannot be written down. Instead the cuts are discovered rather than enumerated: the model is solved without any of them, and every time the solver reaches an integer-feasible candidate a callback reads the selected arcs, walks the successor map to find the components, and for each cycle that does not contain the depot adds exactly that subset's cut and rejects the candidate. Because flow conservation gives every visited node exactly one outgoing arc, the components are simple paths and cycles and the walk is a single linear pass. Nothing about exactness is given up: a candidate that survives with no violated cut is provably a single tour.
Knowing When to Stop Searching
Finding a good route is fast; proving it optimal is not, because the root relaxation is already tight and the remaining work is closing one or two percent against a default tolerance that demands no rearrangement of the day saves even a fraction of a minute. Past roughly ten rides that proof does not finish. The incumbent, however, plateaus early, so the time limit was set from measurement rather than taste: on both a 12-ride and a 16-ride day, ten seconds lands within 0.4% of a sixty-second search. The status is reported honestly as a time limit rather than as optimality, and the finding that tightening the big-M constants per constraint made no measurable difference was written down rather than quietly abandoned.
Joining to the Forecast Without Lying About Gaps
Queue costs come from the companion Prophet forecasting service, a 7-day horizon at 30-minute resolution across 109 attractions. The two systems key rides differently, so names are compared on letters and digits alone after trademark symbols are stripped, which is also why a misspelling that exists in both systems is left alone rather than corrected: it is the working join key. Rides the forecast does not cover are surfaced as a field on the response, because the fallback is to plan them as zero wait, and a plan that silently treats an unknown queue as no queue is worse than one that says it does not know.
Architecture
── INPUTS ──────────────────────────────────────────────────────────
┌───────────────────────────────┐ ┌───────────────────────────────┐
│ Wait-Time Forecast API │ │ data/parks.json │
│ Prophet fleet . 7-day │ │ 5 parks . 116 rides │
│ horizon . 30-minute slots │ │ durations . operating hours │
│ predictions.py │ │ data/walk_times.json │
│ pages PostgREST, joins on │ │ ride-to-ride walk minutes │
│ letters-and-digits names │ │ per park │
└───────────────┬───────────────┘ └───────────────┬───────────────┘
│ W[ride, slot] │ c[i,j] . d[i]
└─────────────────┬────────────────┘
↓
── MODEL - solver.py ─────────────────────────────────────────────
┌──────────────────────────────────────────────────────────────────┐
│ nodes depot 0 . one node per selected ride . a twin per repeat │
│ vars x[i,j] arc . y[i] visit . z[i,s] slot . a[i] e[i] w[i] │
│ │
│ max sum p[i]*y[i] - gamma * a[0] │
│ reward every ride reached, charge the whole loop's time │
└─────────────────────────────────┬────────────────────────────────┘
↓
┌──────────────────────────────────────────────────────────────────┐
│ constraints │
│ degree tied to selection: in/out degree is y[i], not 1 │
│ time carried along the route by a big-M switch on x[i,j] │
│ the arrival slot pins z[i,s], which prices w[i] = W[ride(i),s] │
│ breaks as a linearised finish-before or start-after choice │
│ per-ride opening and closing hours │
└─────────────────────────────────┬────────────────────────────────┘
↓
── SEARCH - Gurobi ───────────────────────────────────────────────
┌──────────────────────────────────────────────────────────────────┐
│ branch and bound . TimeLimit 10s . solution pool for alternates │
└─────────────────────────────────┬────────────────────────────────┘
│ every integer-feasible candidate
↓
┌──────────────────────────────────────────────────────────────────┐
│ MIPSOL callback _eliminate_subtours │
│ read the arcs, walk successor[], find components O(|N|) │
│ a cycle with no depot -> cbLazy exactly that subset's cut │
│ reject the candidate; the cut stays in the model │
└─────────────────────────────────┬────────────────────────────────┘
│ repeat until no cycle remains
↓
── OUTPUT ──────────────────────────────────────────────────────────
┌──────────────────────────────────────────────────────────────────┐
│ replay the fixed plan minute by minute, idling included │
│ ranked itineraries + metadata: status . wait source . gaps │
└────────────────┬────────────────────────────────┬────────────────┘
↓ ↓
cli.py markdown day api.py POST /solve