The Itinerary Is a Constraint Problem

Here is a day we were once asked to look at. Day two of a five-day family trip based in Santa Fe, two parents and children aged six and ten, printed in a handsome proposal:

• 8:00 Leave the hotel
• 9:00 Cliff-dwelling site, self-guided (2 hours)
• 11:30 Lunch at a village café
• 1:00 PM Hot springs soak (90 minutes)
• 3:00 PM Visit with a local potter at her studio
• 5:30 PM Back at the hotel

It reads beautifully. Nothing in it is outlandish. And it could not have happened as written, because the trip fell on a Tuesday.

This article takes that day apart, writes it down the way an operations researcher would, and puts it back together. The goal isn’t to turn tour designers into mathematicians. It’s to show that “the itinerary didn’t work” almost always means “the itinerary broke a constraint nobody wrote down.”

The teardown: five failures, five constraint types

Run the day against reality and here’s what happens. The drive to the cliff site takes 80 minutes door to door, not the 70 the map promised, so the family arrives at 9:20. They leave at 11:20 and reach the village at noon. The café is closed on Tuesdays, so lunch is gas-station sandwiches. At the hot springs, soaks start only on even hours, so they wait 75 minutes for the 2:00 PM slot. By the time they’re back in the village at 4:00, the potter’s last appointment, which had to start by 1:00, is long gone. A six-year-old has spent nearly four hours in the car.

Each failure maps to a distinct type of constraint:

What happened	What it really was	Constraint type
Arrived 20 minutes late at the first stop	Map time is not door-to-door time	Travel-time matrix, realistic and time-of-day aware
Café closed	Opening hours vary by weekday	Time window, indexed by day of week
75 minutes waiting at the springs	Entry only at fixed slot starts	Discrete start times (slot capacity)
Missed the potter	Appointments must start between 10:00 and 1:00	Time window plus a booking requirement
A melted-down six-year-old by 3 PM	230 minutes of driving, no downtime	Pacing, a soft constraint

The proposal had been sold on 200 minutes of driving, the sum of the map estimates. The real figure was 230. That 15% gap is typical of what you find when you rebuild legs from parking, walking and loading time rather than from a map line.

Writing it down properly

A constraint model has four parts. Naming them is most of the value.

Decision variables are the choices: which candidate stops to include, in what order, and at what time each one starts.

Hard constraints are the rules a plan cannot break:

• Each stop starts inside its time window for that weekday and season.
• The next stop can’t start until this one ends and the door-to-door travel time has passed.
• Slot-based stops start only at permitted times (here, 12:00, 2:00 or 4:00).
• Stops that need appointments are booked within their lead time.
• The day ends by a fixed return time, here 5:30 PM.

Soft constraints are preferences, each with a penalty weight. For this family:

Soft constraint	Penalty
Driving beyond 150 minutes in a day	1 point per 10 extra minutes
Lunch starting outside 11:30–1:00	2 points per 15 minutes outside
No 60-minute downtime block before dinner	3 points
Soak before the dusty walk rather than after	2 points

The objective is the total value of the stops included, minus penalties. For this family’s stated priorities, the cliff site is worth 10 points, the hot springs 8, the potter 6, a sit-down lunch 3 and a picnic 2.

If this sounds familiar, it’s because it’s a known problem class. When every stop must be visited, it’s a traveling salesman problem with time windows. When you choose which stops to include under a time budget, it’s an orienteering problem. Across several days it becomes a team orienteering problem with time windows, with each day playing the role of one “team member.” Decades of operations research apply directly.

Re-solving the day

With the model written down, here is the door-to-door travel matrix in minutes (map estimate, then realistic):

• Hotel to cliff site: 70 / 80
• Cliff site to village: 35 / 40
• Cliff site to hot springs: 50 / 55
• Village to hot springs: 25 / 30
• Hot springs to hotel: 55 / 60

Plan B: keep all four, reorder

Leave at 8:00 and arrive at the cliff site at 9:20. Visit until 11:05, since the value curve for a six-year-old flattens after about 90 minutes. Reach the village at 11:45 and see the potter from 11:45 to 12:45, inside her window. Pick up a picnic from the village grocery, eat until 1:20, then drive to the springs, arriving at 1:50 for the 2:00 slot. Soak until 3:30 and be back at the hotel at 4:30, with ninety minutes of downtime before dinner.

It’s feasible. Driving is 210 minutes, which earns 6 penalty points. Value is 26. Net score: 20.

Plan C: move the potter to Thursday

Leave at 8:15 and spend the full two hours at the cliff site, from 9:35 to 11:35. Drive straight to the springs and have a sit-down lunch from 12:30 to 1:30 at a roadside diner nearby that opens daily. Take a short river walk, soak from 2:00 to 3:30, and be back by 4:30.

Day four’s route already passes through the village, so the potter fits there with a ten-minute detour and no new penalty.

	Plan A (as sold)	Plan B (reorder)	Plan C (move potter)
Hard-constraint violations	2, plus a 75-minute wait	0	0
Driving on Tuesday	230 min (sold as 200)	210 min	195 min
Buffer before the 2:00 PM slot	none planned	10 min	30 min
Value points	n/a	26	21 today, 6 on Thursday
Penalty points	n/a	6.0	4.5
Net score	infeasible	20.0	22.5

Plan C wins, and not just on points. Look at the buffer row.

Slack is a constraint, not leftover time

The drive from the hotel to the cliff site has a median of 80 minutes door to door. Add roadwork, a slow truck on the two-lane stretch and a full gravel lot, and the 80th percentile is about 90 minutes and the 95th about 105. Now replay each plan with a bad morning.

Under Plan B, a 10-minute delay pushes everything later, and the family reaches the springs at exactly 2:00. A 25-minute delay gets them there at 2:15. They miss the slot, wait until 4:00, and the day collapses. Under Plan C, a 25-minute delay simply trims the cliff visit or lunch. The 2:00 slot is never at risk.

Three rules follow:

1. Put slack in front of hard constraints. Ten minutes before a slot-based entry is worth more than thirty minutes spread across a flexible afternoon.
2. Size it from the spread, not the median. Plan legs that feed a hard window at the 80th percentile, and the rest at the median.
3. Score robustness explicitly. A useful penalty is the probability that any hard window is missed under realistic travel-time variation. Plans that look identical on paper often differ by a factor of three here.

Why greedy planning and fluent text both fail

Most itineraries are built greedily. You pick the anchor stop, then the nearest interesting thing, then lunch near that, and so on. Greedy construction can’t see that the potter belongs before lunch, or that she belongs on Thursday. It commits early and patches late.

A language model makes a different mistake. It is excellent at the parts of trip planning that are about language, such as understanding “we’d like one slow morning” or explaining why a day is shaped the way it is. It is unreliable at arithmetic over facts it doesn’t have, like a Tuesday closure or a slot rule. A fluent paragraph is not a feasibility check.

The architecture that works splits the labor three ways. The model captures intent and drafts candidates. A solver enforces hard constraints and ranks options on soft ones. An advisor makes the taste call. This is how we built Nova’s Route Engine, and it’s why its options arrive in an advisor’s proposal workflow as drafts with their trade-offs shown, not as finished answers.

On the computing side, at the scale of a single day with five to twelve candidate stops, constraint programming or mixed-integer methods solve to optimality in well under a second. For a ten-day trip with eighty candidates, local search methods such as large neighborhood search reach near-optimal plans in seconds. Compute is not the bottleneck. Data is.

The data you need before any algorithm

A solver is only as truthful as its inputs. Before you optimize anything, make sure you have:

• Time windows by weekday and season, including closures, last-entry times and appointment windows.
• Realistic dwell times by traveler type. A family with a six-year-old and a pair of birders spend very different amounts of time at the same site.
• Door-to-door travel times by time of day, with a median and an 80th percentile, including parking and walking.
• Slot and booking rules: fixed start times, capacity, lead times, deposits.
• Accessibility facts as data, such as step counts, surfaces and gradients, so they can become hard constraints for travelers who need them. Our accessible travel work treats these exactly like opening hours.
• A closure calendar that someone owns and updates.

Gathering and reconciling these from supplier sheets, reservation systems and field notes is usually the largest single piece of work in a routing project. It’s the core of our travel data engineering service, and for most tour operators and DMCs it pays off even before any optimization runs, because the same data stops a lot of mistakes from being sold in the first place.

An audit you can run this week

Pull ten itineraries you sold last season. For each day:

1. Rebuild every leg door to door, including parking and walking. Note the gap from the map estimate.
2. Check each stop’s window for that weekday, not its general hours.
3. Mark every slot-based or appointment-only stop.
4. Total the driving minutes and compare them with what the proposal implied.
5. Find the buffer in front of each hard constraint, and replay the day with the first drive running 25 minutes late.

If more than one day in five breaks a hard constraint, you don’t have a content problem. You have a model problem. That’s good news, because model problems can be solved.