Travel Itinerary Planner: Constraint Search Where the User Is the Optimiser

A trip planner that returns a route is easy. A trip planner that returns a five-day plan is hard in a specific way: the hard part is not the ordering, it is the constraints, and the hardest constraint is that the correct answer depends on a preference nobody can express in a scoring function.

The scale

  a 5-day trip in one city
    40 candidate activities per day available
    8 hours usable per day
    3,200 candidate activities in the trip space

  constraints, hard
    - opening hours
    - reservation requirements and slots
    - travel time between consecutive activities
    - geographic feasibility (30 min to cross town)
    - daily time budget
    - a museum closed on Tuesdays
    - a flight that lands at 16:00 on day 1

  constraints, soft
    - "don't want two museums in one day"
    - "prefer food early, not late"
    - "one relaxed evening"
    - "nothing before 09:00 on day 3"

  and the thing that is not a constraint at all
    - what this person actually enjoys

The last line is the crux. Everything above is computable. Whether a person wants a third museum in a day is not, and any system that pretends otherwise produces plans that are technically valid and emotionally wrong.

The model

  STATE
    - day index
    - current location
    - time of day
    - set of placed activities
    - remaining budget, energy, spend
    - open reservations to consume

  ACTION
    - place activity A at (day d, time t)
    - travel from current location to A
    - or SKIP: leave idle time (a rest block)

  TRANSITION
    - t' = t + travel(loc, A) + service(A)
    - loc' = A.loc
    - feasibility: t' within A's window,
                   daily budget respected,
                   reservations available

  OBJECTIVE (a default, to be overridden)
    maximise  Σ value(A)
    - w1 * total_travel_time
    - w2 * total_walking
    - w3 * schedule_fragmentation
    - w4 * number_of_long_days
    + w5 * buffer_for_uncertainty

A note on the SKIP action, because its absence is a common and consequential bug. Search that must place an activity in every available slot will produce a day packed to the brim, because filling every gap weakly increases total value. Real itineraries need the ability to say “two hours free” — and if the model cannot express that, the resulting plan has no rest and the user discards it.

Why the objective is a conversation

  user A: "I want to see as much as possible"
    -> w1 low, w3 low, w4 low
    -> dense plan, 3 museums, 7 activities/day

  user B: "I don't want to rush"
    -> w1 high, w3 high, w4 high
    -> 3 activities/day, generous buffers

  same trip, same city, same constraints
  -> different plans

  and the honest answer
    -> both are valid
    -> the system should offer 2-3
       distinct plans with the trade-off
       stated, not one plan plus a
       settings screen

The design conclusion is that the system should generate a small set of distinct plans, not one optimised plan. Three candidates labelled “packed”, “balanced”, and “relaxed” is more useful than one plan with a slider, because a slider makes the user do the optimiser’s job and a set of finished plans makes the trade-off visible. Distinctness matters: three plans that differ only slightly are worse than one plan plus two genuinely different shapes.

Search, with the right heuristic

  state = (day, location, time, energy, spend)
  branching factor: 40 activities x 5 days
  depth: 20+ placements

  BFS: intractable
  DFS: finds the first feasible thing
  pure A*: bad heuristic here because the
          cost function is what you're
          trying to figure out

  what works
    1. order candidates by a
       day-plan heuristic
       (not by value alone: opening
        windows, distance, popularity,
        "does it fit now")
    2. BEAM SEARCH
       keep the best K partial plans
       at each day boundary
       K = 50-500
    3. local repair on the survivors
       - swap an activity that does not fit
       - shift an activity to another day
       - shorten a day
    4. de-duplicate by "shape"
       (which activities, which order)
       so the final 3 plans are
       genuinely different

Beam search at day boundaries rather than at every action is the important structural choice. The state space explodes within a day and the interesting decisions are which activities go on which day, so searching at the granularity of “what does day 3 look like” is both far cheaper and better aligned with the actual decision.

The heuristic ordering does more work than the search machinery. A good day-level heuristic clusters activities geographically (so a day is not four cross-town trips), respects opening hours (don’t place something that closes before you can get there), and considers variety (don’t let a day be five museums — that requires knowing category, which is a legitimate constraint to expose to the search).

Travel time is the hidden constraint

  a real trip, 2 days
    09:00 Louvre (opens 09:00)
    10:30 Musée d'Orsay (12 min away)
    12:00 lunch
    13:00 Eiffel Tower
    15:00 Seine cruise
    17:00 Montmartre

  looks fine on paper

  with real travel times
    09:00-11:15 Louvre (peak queue: 2h15)
    11:27-12:00 transit
    12:00-13:00 lunch
    13:20-14:05 Eiffel Tower (queue)
    14:20-15:00 transit
    15:00-16:20 Seine cruise
    16:50-17:40 transit
    17:40-19:00 Montmartre

  total: 6 activities, 1h15 of transit, 8h day
  and it was planned as a 5-activity day

Two things this exposes. Service time is a distribution, not a number — the Louvre at peak is 2h15 and off-peak is 45 minutes, and a planner that uses the mean produces plans that fail at exactly the moment they are most needed. Distance-based estimates systematically undercount because real transit includes waiting, walking to stops, and the specific misery of a connection.

The mitigation that pays for itself: use time-of-day-aware service estimates, and treat the resulting uncertainty as a soft cost. A plan with a tight connection and a 2h15 tail on one activity is riskier than a plan with 45 extra minutes of total transit and no long tail, and if the system can only optimise for the mean, at least let it prefer plans with fewer single points of failure.

Reservations and the booking layer

  reservation-backed activities
    - Eiffel Tower: timed entry, slots
    - Louvre: timed entry
    - popular restaurants: booking required
    - shows: fixed start times

  what the planner must know
    - which activities have hard slots
    - slot availability (live, from the provider)
    - booking lead time (some are 3 months out)
    - cancellation deadlines and fees

  the two-way coupling
    1. the plan proposes a slot
    2. the booking system confirms or fails
    3. a failure is a CONSTRAINT VIOLATION
       -> the plan must be recomputed
       from the current state
    4. and the user must be told what
       changed and why

This is the part that separates a planner from an itinerary generator, and it is where the state-recompute design earns its place. A plan that holds a reserved slot is a plan with a hard commitment. When that booking fails at 21:00 the night before, the correct behaviour is a partial replan from the current state — not a regeneration from scratch that discards the user’s other choices, and not a silent plan that now contains an unbookable activity.

Two specific design consequences. Store the plan as activity placements plus their reservation status, so a recompute can distinguish “we chose this” from “we committed to this”. And surface the recompute: a plan that silently changed overnight is a plan the user does not trust.

Day boundaries and the fatigue model

  naive model
    day 1: 09:00 - 22:00, 6 activities
    day 2: 07:00 - 23:00, 7 activities

  what the data says
    - activity quality degrades after
      ~6 hours of continuous activity
    - a late night activity makes the
      next morning's early start worse
      than a shorter day would
    - a "free" afternoon after a heavy
      morning has outsized value

  model the coupling
    state includes a "fatigue" level
    fatigue rises with consecutive hours
    and with late-night activities
    fatigue decays with idle blocks
    and lowers the effective value of
    the next activity

The coupling between consecutive days is the part that a day-by-day optimiser cannot see. A plan that is independently optimal for each day is often jointly bad, because day 2’s 07:00 start is a direct consequence of day 1’s 22:00 finish. Carrying a fatigue or energy value in the state and letting the search trade a slightly worse day against a much better adjacent day is a small model change with a large effect on the plan’s real-world quality.

Recomputing from a partial state

  the plan is a DAG of commitments
    - placed activities with slots
    - travel legs
    - day boundaries

  events that trigger recompute
    - a booking failed
    - a flight delayed by 3h
    - weather closed the outdoor option
    - the user changed a hotel (everything
      that depended on the location)
    - a place the user wanted is fully booked

  recompute, not regenerate
    1. keep all placements that are still
       valid AND still preferred
    2. keep the user's manual locks hard
    3. free only the affected region
       (usually one day, often one block)
    4. re-run the beam search scoped to
       that region
    5. show a diff: what moved, why

The scoping is what keeps recompute fast. A hotel change invalidates distances, which can affect every day, but in practice the search re-converges if you free one day at a time and keep the others fixed, iterating if needed. The alternative — regenerate everything — throws away the user’s accumulated adjustments, which is the fastest way to make someone stop using a planner.

Failure stories worth testing

Change the hotel to the other side of the city

Recompute must handle it without discarding the user’s manual choices, and the diff must explain the changes.

Make a reserved slot fail 12 hours before the activity

Confirm the plan recomputes, tells the user, and preserves the rest of the trip. This is the canonical reservation-coupling test.

Set service time distributions with a long tail (mean 45min, p90 2h15)

Compare the plan’s real failure rate against a plan built with fixed service times. This shows whether uncertainty is in the model.

Remove the SKIP action from the search

Every day becomes packed. Confirm the user-facing complaint and that plan quality drops even though “value” went up.

Set the beam width to 5

Compare distinctness of the three final plans. They will be near-identical variants. Beam width controls diversity more than it controls quality.

Change the day boundary rule so day 1 ends at 22:00 and day 2 starts at 07:00

Confirm the fatigue coupling prevents this. This is the test for whether the state carries energy.

Use mean travel time instead of time-of-day travel time

Measure plan failure at peak hours. Mean travel time is fine at 10am and wrong at 18:00.

Remove opening-hours constraints

The search will place activities that are closed. This is the test that the constraint layer is real.

Force a plan with three museums in one day

Confirm the category-variety heuristic resists it, and confirm the user is offered an alternative rather than the packed plan silently.

Change user preference from packed to relaxed at the end of the session

The plan should regenerate with the new weights, not require starting over.

Add 10 new candidate activities mid-session

Recompute should incorporate them without moving already-placed items more than necessary.

Make the activity set sparse (a small town, 6 things to do)

Confirm the planner returns a short, honest plan rather than padding with weak suggestions.

Test with a user who has booked nothing and is in a city with reservations required

The planner should say which activities need booking and by when, not produce a plan that cannot be executed.

A production-ready architecture

   user inputs
     - destination, dates, party, pace
     - hard constraints (must-do list)
     - soft preferences
        |
        v
  +----------------------------------------------------------+
  |  CONSTRAINT LAYER                                       |
  |  - opening hours + time-of-day service estimates        |
  |  - reservation requirements and lead times              |
  |  - travel time matrix (cached, per city)                |
  |  - geographic feasibility (is it even possible)         |
  +----------------------------+-----------------------------+
                               |
                               v
  +----------------------------------------------------------+
  |  CANDIDATE ACTIVITY SET                                  |
  |  - scored by fit with stated preferences                |
  |  - filtered by feasibility in the trip window            |
  |  - with uncertainty attached (service time tail)        |
  +----------------------------+-----------------------------+
                               |
                               v
  +----------------------------------------------------------+
  |  BEAM SEARCH over day plans                             |
  |  - state: day, loc, time, fatigue, spend, locks         |
  |  - actions: place activity / travel / SKIP              |
  |  - heuristic: geo-clustering, window fit, variety       |
  |  - dedupe by plan shape, keep distinct                   |
  +----------------------------+-----------------------------+
                               |
                               v
  +----------------------------------------------------------+
  |  3 DISTINCT PLANS with explicit trade-offs               |
  |  packed / balanced / relaxed                            |
  |  each with: total travel, activity count, risk notes,   |
  |  reservations needed and deadlines                      |
  +----------------------------+-----------------------------+
                               |
                               v
  +----------------------------------------------------------+
  |  BOOKING LAYER                                           |
  |  - propose slots, confirm with providers                |
  |  - track reservation status per placement                |
  |  - on failure: scoped recompute + user-facing diff       |
  +----------------------------+-----------------------------+
                               |
                               v
  user edits -> partial recompute, locks respected

  watch: constraint violation rate, plan failure rate,
        recompute blast radius, distinctness of plans

Delivery checklist:

1. Build the planner as constraint search, not route optimisation. The ordering is a small part of it.
2. Include SKIP as an action. A planner that cannot express free time produces plans that get discarded.
3. Search with beam search at day boundaries, not breadth-first over actions.
4. Attach a service-time distribution to every activity, and treat the tail as a soft cost.
5. Use time-of-day travel times, and cache the city matrix.
6. Expose the objective. Offer 2-3 finished plans with the trade-off labelled, not one plan plus a settings screen.
7. Carry fatigue or energy in the state so day-to-day coupling is visible to the search.
8. Model reservations as hard commitments with their own status, and recompute from the current state on failure.
9. Recompute scoped, not globally. Preserve the user’s manual locks and show a diff.
10. Make the search prefer geographic clusters per day. Cross-town hopping is the most common reason a valid plan is a bad plan.
11. Report which activities need reservations and their deadlines, so the plan is executable.
12. Test uncertainty honestly: run plans against actual opening-hour and queue data and measure the failure rate.
13. Keep the “unbookable but wanted” list visible, with a warning rather than a silent drop.
14. Version the constraint data. Opening hours change and stale data produces confidently wrong plans.

Common mistakes

Mistake	What actually happens	Better decision
Route optimisation for a multi-day trip	Ignores opening hours, reservations, fatigue	Constraint search
No SKIP action	Days packed, plans discarded	Free time as a first-class action
Mean service times	Plans fail at peak hours exactly when used	Distributions, tail as a soft cost
Mean travel times	Wrong at the times people travel	Time-of-day matrix
Breadth-first search	Does not terminate usefully	Beam search at day boundaries
Beam width too small	Three near-identical plans	Width for diversity, dedupe by shape
One optimised plan	Technically valid, emotionally wrong	2-3 labelled trade-offs
Ignore fatigue	Each day optimal, trip jointly bad	Energy in the state
Regenerate on any change	User’s choices thrown away	Scoped recompute, locks preserved
Reservations as soft preferences	Unbookable plans reach the user	Hard commitments with status
Silent recompute	User does not trust the plan	Diff with reasons
No geo-clustering heuristic	Four cross-town trips per day	Cluster by neighbourhood per day
Category variety ignored	Five museums in a day	Variety term in the heuristic
No booking deadlines shown	Plan cannot be executed	Surface lead times
Ignoring what is unbookable	User finds out at the gate	Show the waitlist/warning state

The complete story in one minute

A multi-day itinerary is a constraint satisfaction problem. Opening hours, reservation slots, travel feasibility, daily budgets, a flight landing at four in the afternoon — those are the constraints, and the route ordering is a small part of the difficulty. Search must be guided: breadth-first over five days and forty activities a day does not terminate, so use beam search at day boundaries rather than at every action, because the interesting decision is which activities land on which day. Include SKIP as an action, or every day comes out packed and gets discarded.

The objective is a conversation, not a function. “See as much as possible” and “I don’t want to rush” produce different valid plans for the same trip, and the system should hand over two or three finished plans with the trade-off labelled — packed, balanced, relaxed — rather than one plan plus a settings screen that makes the user do the optimiser’s job.

Travel time is the hidden constraint and service time is a distribution, not a number. The Louvre is forty-five minutes off-peak and two hours fifteen at peak, and a planner built on means fails exactly when it is most needed. Use time-of-day travel times, attach the tail as a soft cost, and prefer plans without a single point of failure over plans that are optimal on average. Carry fatigue in the state, because a day independently optimised for itself is often jointly bad: day two’s seven-in-the-morning start is a direct consequence of day one’s ten-at-night finish.

Reservations are what turn a planner into real software, because a confirmed slot is a hard commitment. Store placement and reservation status separately, recompute scoped when a booking fails, preserve manual locks, and show a diff — a plan that silently changed overnight is a plan nobody trusts. Version the constraint data, since stale opening hours produce confidently wrong plans.

constraint search with beam at day boundaries, SKIP as an action
service time as a distribution, travel time by time of day
fatigue carried across days; 2-3 labelled plans, not a slider
reservations as hard commitments; scoped recompute with a diff

The hard part was never finding the order of the stops. It was knowing that the right order is a function of what the person wants, and that the person is the only one who can say.

What this team still owns

Opening hours, reservation slots, transport schedules, and travel times are observations with sources and freshness, not timeless facts. Persist the plan’s assumptions and distinguish hard constraints from preferences so recomputation can explain what changed. User-pinned activities and paid reservations form a frozen set; a delayed flight should re-solve the affected horizon around them, surface infeasibility, and offer alternatives rather than silently deleting commitments.

Technical references

• IETF RFC 5545: iCalendar
• Google OR-Tools: constraint optimisation
• Google Maps Routes API: traffic-aware duration