← Ausgewählte Projekte/Travel Tech/2025

Unki · Personalisierte Stadt-Itinerar-Plattform

Eine Live-Itinerar-Engine, die unter 90 Sekunden den besten 3-Tages-Trip aus 200 Mio.+ Google Places auswählt

Time-Dependent Team Orienteering with Time Windows, Ende-zu-Ende gelöst für Genf, Paris, London und Lausanne — Engine, Ingestion-Pipeline und Referenz-UI alle in Produktion

Reise-Apps und LLM-basierte Planer schlagen coole Orte vor. Keiner von ihnen plant tatsächlich Ihren Tag, Öffnungszeiten, Fusswege, Erschöpfung, die Tatsache, dass ein Museum um 16:00 schliesst und das andere 30 Minuten entfernt ist. Das ist ein Optimierungsproblem, nicht die Aufgabe eines Chatbots.

Wir haben das Design der Itinerar-Engine von Unki geleitet: ein zeitabhängiges Team Orienteering Problem with Time Windows, gelöst mit einer massgeschneiderten Gurobi-basierten Pipeline aus Presolve, LP-Relaxierung, Branch-and-Cut und einem Portfolio von Warmstart-Heuristiken. Stadt einsetzen, wunderschön sortierte Tour zurückbekommen.

<90 s

3-Tages-Stadtreise Ende-zu-Ende optimiert, jede Benchmark-Stadt

1163 % → 9 %

Optimalitätslücke innerhalb dieses ~90-Sekunden-Fensters geschlossen

200 Mio.+

Google Places durchsuchbar über das Live-Interface

Live

Engine, Ingestion-Pipeline und Referenz-UI alle bei Unki ausgeliefert

Die Herausforderung

Tourismusplanung ist fragmentiert und langsam. Reisende kombinieren Hotels, Restaurants und Aktivitäten über ein halbes Dutzend Plattformen. LLMs halluzinieren. Generische Planer ignorieren Öffnungszeiten, Transferzeiten und die einfache Physik des Mensch-Seins.

Unki brauchte eine Itinerar-Engine scharf genug für eine interaktive Consumer-App: reale Nebenbedingungen modellieren, hochwertige Itinerare schnell genug zurückgeben, um sich sofort anzufühlen, und auf Tausende POIs skalieren, mit minutengenauen Reisezeitdaten aus Live-APIs.

Unser Vorgehen

Wir haben das Produkt von Unki in die Orienteering-Problem-Familie eingeordnet, konkret das Team Orienteering Problem with Time Windows mit zeitabhängigen Reisezeiten, und die entsprechende gemischt-ganzzahlige Formulierung gebaut, mit Begehrlichkeits-Score pro POI als Zielfunktion.

Wir haben eine mehrstufige Löse-Pipeline entwickelt: Presolve und Constraint-Reduktion, einen LP-Relaxierungsschritt für starke Anfangsschranken, Branch-and-Bound / Branch-and-Cut über Gurobi und eine Insertion-Heuristik, die selbst vor Konvergenz des exakten Solvers hochwertige Lösungen liefert.

Auf der Datenseite haben wir eine robuste Ingestion-Schicht gebaut, die POI-Metadaten, Öffnungszeiten, Bewertungen und eine vollständige P×P-Reisezeit-Matrix aus der Google-Distance-Matrix-API zieht, inklusive Integritätsprüfungen, die fehlende oder fehlerhafte Einträge sauber behandeln.

Das Ergebnis

Deliverable: das Optimierungs-Backend, die Google-Places-Ingestion-Pipeline und ein Referenz-UI, alles live und treibt die Reisenden-App von Unki an. Eine 3-Tages-Reise auf 70–84 POI-Kandidaten löst auf 10 % vom zertifizierten Optimum in 63 s (Genf), 84 s (Paris), 69 s (London) und 94 s (Lausanne). Der Optimierer schliesst eine Anfangslücke von über 1100 % innerhalb dieses Fensters auf unter 10 %.

Jede reale Reisende-Nebenbedingung wird durchgesetzt: Öffnungszeiten, Restaurant-Kardinalität (mindestens eines pro Tag, höchstens zwei — Mittag und Abend), ein einziges Hotel, das die Reise verankert, Fusswege live über die Google-Distance-Matrix-API gezogen, die Physik, abends zurück zum Schlafen zu kommen. Reisende bewerten POIs auf einer 0–10-Begehrlichkeits-Skala und sehen das Itinerar in Sekunden auf der Karte landen.

Technischer Deep Dive

Das Modell hinter dem Ergebnis.

Das Modell

Jeder Tag einer Reise ist eine Orienteering-Tour auf einem temporalen Graphen: Der Reisende läuft eine Sequenz von POIs ab, erntet an jedem einen Begehrlichkeits-Score und muss den Tag innerhalb eines festen Zeitbudgets am gleichen Hotel beginnen und beenden. Reale Öffnungszeiten, reale Reisezeiten, reale Restaurant-Logik. Entscheidungen verteilen sich über die ganze Reise: welches Hotel sie verankert, welche POIs an welchem Tag besucht werden, in welcher Reihenfolge, zu welcher genauen 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 zerfällt in Hotels H, Restaurants R und Aktivitäten A, indiziert über die Tagesmenge D. x markiert einen geordneten Übergang i → j an Tag d; u markiert einen Besuch; y wählt das einzige Hotel, das die Reise verankert; t und ω sind Ankunfts- und Wartezeit in Minuten ab Mitternacht.

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

Zielfunktion: maximierte Summe der Begehrlichkeits-Scores über die Reise, jeder besuchte POI trägt seinen Score d_i einmal bei, summiert über die Tage.

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 .

Ein Hotel verankert die ganze Reise. Jeder Tag beginnt und endet dort: Der einzige ausgehende Übergang von einem Hotel an Tag d (und der einzige eingehende) existiert genau dann, wenn dieses Hotel das gewählte ist.

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 .

Besuchsgrad-Constraint: Jeder Nicht-Hotel-POI hat Eingangsgrad und Ausgangsgrad gleich seinem Besuchsindikator u_id und wird über die ganze Reise an höchstens einem Tag besucht.

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 .

Zeitkontinuität: Die Ankunft bei j ist mindestens die Abreise bei i (Ankunft + Verweildauer τ_i + optionales Warten ω) plus Reisezeit ρ_ij. Linearisiert mit Big-M, wenn 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} .

Zeitfenster. Jeder Besuch liegt innerhalb des Öffnungsintervalls [O_i, C_i] des POIs; jeder Tag beginnt um S_d am Hotel, und die Rückkehr muss bis E_d abgeschlossen sein.

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

Restaurant-Kardinalität: mindestens ein Restaurant pro Tag (man muss essen), höchstens zwei (Mittag und Abend).

Was wie ein Routenproblem aussieht, sind drei gekoppelte Entscheidungen: welches Hotel die Reise verankert, welche POIs in das Zeitbudget des Tages passen, und der minutengenaue Plan, der die Öffnungszeiten aufgehen lässt. Das volle MILP ist im Massstab schwer, also wickeln wir es in eine mehrstufige Löseschleife: aggressive Presolve und Bound-Tightening, eine LP-Relaxierung, die eine starke obere Schranke liefert, eine Insertion-Heuristik, die in Sekunden eine zulässige Warmstart-Tour baut, und Gurobis Branch-and-Cut, das die verbleibende Lücke schliesst.

Benchmark

End-to-End-Pipeline-Zeiten auf den vier Benchmark-Städten (Drei-Tages-Reise, ein verankertes Hotel, validierte POI-Sets nach API-Ingestion).

Stufe	Genf (74 POIs)	Paris (84)	London (80)	Lausanne (73)
Datenstrukturierung	< 0,1 s	< 0,1 s	< 0,1 s	< 0,1 s
PlaceID-Abfrage (Google Places)	52,5 s	49,2 s	47,3 s	51,4 s
Details-Abfrage	19,4 s	18,7 s	19,5 s	17,1 s
Reisezeit-Matrix (P × P Calls)	17 m 12 s	18 m 28 s	18 m 35 s	17 m 47 s
Datennormalisierung	< 0,1 s	< 0,1 s	< 0,1 s	< 0,1 s
Optimierung (Gurobi MILP, 10 % Lücke)	63 s	84 s	69 s	94 s

Die Reisezeit-Matrix dominiert die Wall-Clock-Zeit, weil sie eine P²-Distance-Matrix-API-Last ist, gut cachebar, und der naheliegende nächste Engineering-Schritt (vorberechnen, sobald POIs hinzugefügt werden, nicht zur Lösezeit). Das MILP selbst konvergiert auf jeder Stadt in rund einer Minute auf 10 % vom Optimum; die Insertion-Heuristik produziert in Sekunden einen zulässigen Warmstart. Der 10-%-Lücken-Stopp ist ein bewusster Zielkonflikt: Die marginale Itinerar-Verbesserung durch Schliessen der letzten Prozente ist das zusätzliche Warten in einer interaktiven Consumer-App nicht wert.

Aus den Unterlagen

Abbildung 1 aus dem Bericht: die End-to-End-Pipeline. Der Nutzer wählt POIs und bewertet sie; wir greifen auf die Google Places API für Metadaten und die Distance Matrix API für eine P × P-Reisezeit-Matrix zu; wir strukturieren alles in Hotel- / Aktivitäts- / Restaurant-Teilmengen; Gurobi löst das TDOPTW; das geroutete Itinerar landet zurück auf der Karte.

Abbildung 4 aus dem Bericht: räumliche Verteilung der validierten POI-Sets in jeder Benchmark-Stadt nach API-Ingestion. Rote Marker sind Aktivitäten, blaue Hotels, grüne Restaurants, das ist die Geometrie, durch die der Optimierer routet.

Abbildung 5 aus dem Bericht: das Live-Interface mit 73 in Genf importierten POIs. Reisende markieren jeden Pin mit einem 0–10-Begehrlichkeits-Score; der Solver konsumiert das, die Öffnungszeiten und die vorberechnete Reisezeit-Matrix, um eine zulässige Mehrtages-Reise zu planen.

Abbildung 7 aus dem Bericht: heuristischer Zielfunktionswert über die Iterationen einer Drei-Tages-Genf-Reise. Die Insertion-Heuristik findet bei Iteration 1 eine zulässige Tour; Gurobis Branch-and-Cut schliesst die Lücke von über 1000 % auf unter 10 % in 26 Iterationen, der steile Sprung um Iteration 8 ist die LP-Relaxierung, die eine strukturell andere Tour freischaltet.

Techniken

Orienteering / TOP / TOPTW / TDOP
Branch-and-Cut
LP-Relaxierungen und Presolve
Insertion-Heuristiken

Stack

Python
Gurobi
Google Distance Matrix API
FastAPI

Ein Problem wie dieses?

Wir würden gerne davon hören.

contact@optimally.ch