← Selected work/Travel Tech/2025

Unki · Personalized urban itinerary platform

A Live Itinerary Engine That Picks the Best 3-Day Tour Out of 200M+ Google Places in Under 90 Seconds

Time-Dependent Team Orienteering with Time Windows, solved end-to-end on Geneva, Paris, London and Lausanne — engine, ingestion pipeline, and reference UI all shipped to production

Travel apps and LLM-based planners suggest cool places. None of them actually plans your day, opening hours, walking times, fatigue, the fact that one museum closes at 4pm and the other is 30 minutes away. That's an optimization problem, not a chatbot's job.

We led the design of Unki's itinerary engine: a Time-Dependent Team Orienteering Problem with Time Windows, solved with a custom Gurobi-backed pipeline that fuses presolve, LP relaxation, branch-and-cut, and a portfolio of warm-start heuristics. Plug in a city, get a beautifully-ordered tour back.

<90 s

3-day city trip optimized end-to-end, every benchmark city

1163% → 9%

optimality gap closed inside that ~90-second window

200M+

Google Places searchable through the live interface

Live

engine, ingestion pipeline, and reference UI all shipped to Unki

The challenge

Tourism planning is fragmented and slow. Travelers stitch together hotels, restaurants, and activities across half a dozen platforms. LLMs hallucinate. Generic planners ignore opening hours, transfer times, and the simple physics of being human.

Unki needed an itinerary engine sharp enough to power an interactive consumer app: model the real constraints, return high-quality itineraries fast enough to feel instantaneous, and scale to thousands of POIs with minute-by-minute travel-time data pulled from live APIs.

Our approach

We mapped Unki's product into the Orienteering-Problem family, specifically the Team Orienteering Problem with Time Windows and time-dependent travel times, and built the corresponding mixed-integer formulation, with desirability scoring per POI as the objective.

We engineered a multi-stage solve pipeline: presolve and constraint reduction, an LP relaxation step that gives strong initial bounds, branch-and-bound / branch-and-cut backed by Gurobi, and an insertion-style heuristic to deliver high-quality solutions even before the exact solver converges.

On the data side we built a robust ingestion layer pulling POI metadata, opening hours, ratings, and a full P×P travel-time matrix from the Google Distance Matrix API, including integrity checks to handle missing or malformed entries gracefully.

The outcome

Deliverable: the optimization backend, the Google Places ingestion pipeline, and a reference UI, all live and powering Unki's traveler-facing app. A 3-day trip on 70–84 candidate POIs solves to within 10% of the certified optimum in 63 s (Geneva), 84 s (Paris), 69 s (London), and 94 s (Lausanne). The optimizer closes an initial gap of over 1100% to under 10% inside that window.

Every real-world traveler constraint is enforced: opening hours, restaurant cardinality (at least one per day, at most two — lunch and dinner), a single hotel anchoring the trip, walking times pulled live from the Google Distance Matrix API, the physics of needing to come back to sleep. Travelers rate POIs on a 0–10 desirability scale and watch the itinerary land on the map in seconds.

Technical deep dive

The model behind the result.

The model

Each day of a trip is an orienteering tour on a temporal graph: the traveler walks a sequence of POIs, harvests a desirability score at each one, and has to start and end the day at the same hotel within a fixed time budget. Real opening hours, real travel times, real restaurant logic. Decisions split across the entire trip: which hotel anchors it, which POIs are visited and on which day, in what order, and at which precise minute.

P = H ⊔ R ⊔ A, d \in D, x_{ij d}, u_{i d}, y_{h} \in {0, 1}, t_{i d}, ω_{i d} \in Z_{\geq 0} .

P partitions into hotels H, restaurants R, and activities A, indexed across day set D. x marks an ordered transition i → j on day d; u marks a visit; y picks the single hotel that anchors the trip; t and ω are arrival and waiting times in minutes from midnight.

max d \in D \sum i \in P ∖ H \sum d_{i} \cdot u_{i d} .

Objective: maximize total desirability collected over the trip, each visited POI contributes its score d_i once, summed across the days.

h \in H \sum y_{h} = 1, j \in P ∖ H \sum x_{hj d} = y_{h}, j \in P ∖ H \sum x_{j h d} = y_{h} \forall h \in H, d \in D .

One hotel anchors the entire trip. Every day starts and ends at it: the only outgoing transition from a hotel on day d (and the only incoming one) exists exactly when that hotel is the chosen one.

j \in P \sum x_{ij d} = u_{i d}, j \in P \sum x_{j i d} = u_{i d} \forall i \in P ∖ H, d \in D, d \in D \sum u_{i d} \leq 1 \forall i \in P ∖ H .

Visit-degree constraint: each non-hotel POI has in-degree and out-degree equal to its visit indicator u_id, and is visited on at most one day across the whole trip.

t_{j d} \geq t_{i d} + τ_{i} + ρ_{ij} + ω_{i d} \forall i \in P, j \in P ∖ H, i \neq = j, d \in D .

Time continuity: arrival at j is at least departure from i (arrival + dwell τ_i + optional wait ω) plus travel time ρ_ij. Linearized with a big-M when x_ijd = 0.

O_{i} \leq t_{i d}, t_{i d} + τ_{i} + ω_{i d} \leq C_{i}, t_{h d} y_{h} = S_{d}, t_{i d} + τ_{i} + ρ_{ih} + ω_{i d} \leq E_{d} .

Time windows. Each visit lands inside the POI's opening interval [O_i, C_i]; each day starts at S_d at the hotel and the return must complete by E_d.

1 \leq i \in R \sum u_{i d} \leq 2 \forall d \in D .

Restaurant cardinality: at least one restaurant per day (you have to eat), at most two (lunch and dinner).

What looks like a routing problem is actually three coupled decisions: which hotel anchors the trip, which POIs fit each day's time budget, and the minute-level schedule that makes opening hours work out. The full MILP is hard at scale, so we wrap it in a multi-stage solve: aggressive presolve and bound tightening, an LP relaxation that supplies a strong upper bound, an insertion-style heuristic that builds a feasible warm-start tour in seconds, and Gurobi's branch-and-cut closing the remaining gap.

Benchmark

End-to-end pipeline timings on the four benchmark cities (3-day trip, single hotel anchor, validated POI sets after API ingestion).

Stage	Geneva (74 POIs)	Paris (84)	London (80)	Lausanne (73)
Data structuring	< 0.1 s	< 0.1 s	< 0.1 s	< 0.1 s
PlaceID fetching (Google Places)	52.5 s	49.2 s	47.3 s	51.4 s
Place details fetching	19.4 s	18.7 s	19.5 s	17.1 s
Travel-time matrix (P × P calls)	17 m 12 s	18 m 28 s	18 m 35 s	17 m 47 s
Data normalization	< 0.1 s	< 0.1 s	< 0.1 s	< 0.1 s
Optimization (Gurobi MILP, 10% gap)	63 s	84 s	69 s	94 s

The travel-time matrix dominates wall-clock because it's a P² Distance Matrix API workload, straightforwardly cacheable, and the obvious next engineering move (precompute as POIs are added, not at solve time). The MILP itself converges to within 10% of the optimum in roughly a minute on every city; the heuristic insertion pass produces a feasible warm-start in seconds. The 10% gap stop is a deliberate trade-off: the marginal itinerary improvement from closing the last few percent isn't worth the extra wait for an interactive consumer app.

From the record

Figure 1 from the report: the end-to-end pipeline. The user selects POIs and rates them; we hit the Google Places API for metadata and the Distance Matrix API for a P × P travel-time matrix; we structure everything into hotel / activity / restaurant subsets; Gurobi solves the TDOPTW; the routed itinerary lands back on the map.

Figure 4 from the report: spatial distribution of the validated POI set in each benchmark city after API ingestion. Red markers are activities, blue are hotels, green are restaurants, this is the geometry the optimizer routes through.

Figure 5 from the report: the live interface with 73 Geneva POIs ingested. Travelers tag each pin with a 0–10 desirability score; the solver consumes that, opening hours, and the precomputed travel-time matrix to plan a feasible multi-day trip.

Figure 7 from the report: heuristic objective value across iterations on a 3-day Geneva trip. The insertion heuristic finds a feasible tour at iteration 1; Gurobi's branch-and-cut closes the gap from above 1000% down to under 10% in 26 iterations, the steep jump around iteration 8 is the LP relaxation kicking in and unlocking a structurally different tour.

Techniques

Orienteering / TOP / TOPTW / TDOP
Branch-and-cut
LP relaxations and presolve
Insertion heuristics

Stack

Python
Gurobi
Google Distance Matrix API
FastAPI

A problem like this?

We'd like to hear about it.

contact@optimally.ch