← Projets sélectionnés/Travel Tech/2025

Unki · Plateforme d'itinéraire urbain personnalisé

Un moteur d'itinéraire en direct qui choisit la meilleure tournée de 3 jours parmi 200 M+ de Google Places en moins de 90 secondes

Time-Dependent Team Orienteering with Time Windows, résolu de bout en bout sur Genève, Paris, Londres et Lausanne — moteur, pipeline d'ingestion et UI de référence tous en production

Les applications de voyage et les planificateurs basés sur les LLM suggèrent des endroits sympas. Aucun d'entre eux ne planifie réellement votre journée, heures d'ouverture, temps de marche, fatigue, le fait qu'un musée ferme à 16 h et que l'autre est à 30 minutes. C'est un problème d'optimisation, pas le travail d'un chatbot.

Nous avons dirigé la conception du moteur d'itinéraire d'Unki : un Time-Dependent Team Orienteering Problem with Time Windows, résolu via un pipeline sur mesure basé sur Gurobi qui combine presolve, relaxation LP, branch-and-cut et un portefeuille d'heuristiques de warm-start. Branchez une ville, recevez une tour bien ordonnée.

<90 s

voyage de 3 jours optimisé de bout en bout, chaque ville de référence

1163 % → 9 %

écart d'optimalité comblé dans cette fenêtre d'environ 90 secondes

200 M+

Google Places interrogeables depuis l'interface en direct

Live

moteur, pipeline d'ingestion et UI de référence tous livrés à Unki

Le défi

La planification touristique est fragmentée et lente. Les voyageurs cousent ensemble hôtels, restaurants et activités sur une demi-douzaine de plateformes. Les LLM hallucinent. Les planificateurs génériques ignorent les heures d'ouverture, les temps de transfert et la simple physique d'être humain.

Unki avait besoin d'un moteur d'itinéraire suffisamment affûté pour propulser une application grand public interactive : modéliser les vraies contraintes, renvoyer des itinéraires de haute qualité assez vite pour paraître instantanés, et passer à l'échelle de milliers de POIs avec des données de temps de trajet minute par minute tirées d'API en direct.

Notre démarche

Nous avons mappé le produit d'Unki sur la famille des problèmes d'Orienteering, précisément le Team Orienteering Problem with Time Windows avec temps de trajet dépendant du temps, et construit la formulation mixte correspondante, avec un score de désirabilité par POI comme objectif.

Nous avons conçu un pipeline de résolution multi-étapes : presolve et réduction de contraintes, une étape de relaxation LP qui donne de fortes bornes initiales, branch-and-bound / branch-and-cut soutenu par Gurobi, et une heuristique d'insertion pour livrer des solutions de haute qualité avant même que le solveur exact ne converge.

Côté données, nous avons construit une couche d'ingestion robuste tirant les métadonnées POI, heures d'ouverture, notes et une matrice complète P×P de temps de trajet depuis l'API Google Distance Matrix, incluant des vérifications d'intégrité pour gérer proprement les entrées manquantes ou mal formées.

Le résultat

Livrable : le backend d'optimisation, le pipeline d'ingestion Google Places et une UI de référence, tous en direct et propulsant l'application grand public d'Unki. Un voyage de 3 jours sur 70–84 POIs candidats résout à moins de 10 % de l'optimum certifié en 63 s (Genève), 84 s (Paris), 69 s (Londres) et 94 s (Lausanne). L'optimiseur ramène un écart initial de plus de 1100 % à moins de 10 % dans cette fenêtre.

Toutes les contraintes voyageur réelles sont imposées : heures d'ouverture, cardinalité de restaurants (au moins un par jour, au plus deux — déjeuner et dîner), un seul hôtel ancrant le voyage, temps de marche tirés en direct de l'API Google Distance Matrix, la physique de devoir rentrer dormir. Les voyageurs notent les POIs sur une échelle de désirabilité 0–10 et voient l'itinéraire se poser sur la carte en quelques secondes.

Plongée technique

Le modèle derrière le résultat.

Le modèle

Chaque jour d'un voyage est une tour d'orienteering sur un graphe temporel : le voyageur parcourt une séquence de POIs, récolte un score de désirabilité à chacun, et doit commencer et terminer la journée au même hôtel dans un budget de temps fixé. Vrais horaires d'ouverture, vrais temps de trajet, vraie logique de restaurant. Les décisions s'étalent sur tout le voyage : quel hôtel l'ancre, quels POIs sont visités et quel jour, dans quel ordre, à quelle minute précise.

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 se partitionne en hôtels H, restaurants R et activités A, indexé sur l'ensemble des jours D. x marque une transition ordonnée i → j le jour d ; u marque une visite ; y choisit l'unique hôtel qui ancre le voyage ; t et ω sont les temps d'arrivée et d'attente en minutes depuis minuit.

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

Objectif : maximiser la désirabilité totale collectée sur le voyage, chaque POI visité contribue son score d_i une fois, sommé sur les jours.

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 .

Un seul hôtel ancre tout le voyage. Chaque jour commence et finit là : la seule transition sortante d'un hôtel le jour d (et la seule entrante) existe exactement quand cet hôtel est celui choisi.

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 .

Contrainte de degré de visite : chaque POI non hôtel a un degré entrant et sortant égal à son indicateur de visite u_id, et est visité au plus un jour sur tout le voyage.

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 .

Continuité temporelle : l'arrivée à j est au moins le départ de i (arrivée + temps sur place τ_i + attente optionnelle ω) plus le temps de trajet ρ_ij. Linéarisée avec un big-M quand 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} .

Fenêtres de temps. Chaque visite tombe dans l'intervalle d'ouverture du POI [O_i, C_i] ; chaque jour commence à S_d à l'hôtel et le retour doit se terminer avant E_d.

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

Cardinalité des restaurants : au moins un restaurant par jour (il faut manger), au plus deux (déjeuner et dîner).

Ce qui ressemble à un problème de routage est en réalité trois décisions couplées : quel hôtel ancre le voyage, quels POIs entrent dans le budget temps de chaque jour, et le planning à la minute qui fait fonctionner les heures d'ouverture. Le MILP complet est dur à l'échelle, donc nous l'enveloppons dans une boucle de résolution multi-étapes : presolve agressif et bound-tightening, une relaxation LP qui fournit une forte borne supérieure, une heuristique d'insertion qui construit une tour faisable en quelques secondes en warm-start, et le branch-and-cut de Gurobi qui ferme l'écart restant.

Benchmark

Temps end-to-end du pipeline sur les quatre villes de référence (voyage de 3 jours, hôtel unique, ensembles POI validés après ingestion API).

Étape	Genève (74 POIs)	Paris (84)	Londres (80)	Lausanne (73)
Structuration des données	< 0,1 s	< 0,1 s	< 0,1 s	< 0,1 s
Récupération PlaceID (Google Places)	52,5 s	49,2 s	47,3 s	51,4 s
Récupération des détails	19,4 s	18,7 s	19,5 s	17,1 s
Matrice de temps de trajet (P × P)	17 m 12 s	18 m 28 s	18 m 35 s	17 m 47 s
Normalisation des données	< 0,1 s	< 0,1 s	< 0,1 s	< 0,1 s
Optimisation (Gurobi MILP, écart 10 %)	63 s	84 s	69 s	94 s

La matrice de temps de trajet domine le temps de l'horloge car c'est une charge API Distance Matrix en P², facilement cachable, et le prochain pas d'ingénierie évident (précalculer à mesure que les POIs sont ajoutés, pas au moment de la résolution). Le MILP lui-même converge à 10 % de l'optimum en environ une minute sur chaque ville ; la passe d'insertion heuristique produit un warm-start faisable en quelques secondes. L'arrêt à 10 % d'écart est un compromis délibéré : l'amélioration marginale de l'itinéraire en fermant les derniers pourcents ne vaut pas l'attente supplémentaire pour une application grand public interactive.

Tiré du dossier

Figure 1 du rapport : le pipeline end-to-end. L'utilisateur sélectionne et note des POIs ; nous appelons l'API Google Places pour les métadonnées et l'API Distance Matrix pour une matrice P × P de temps de trajet ; nous structurons tout en sous-ensembles hôtels / activités / restaurants ; Gurobi résout le TDOPTW ; l'itinéraire routé revient sur la carte.

Figure 4 du rapport : distribution spatiale du jeu de POIs validés dans chaque ville de référence après ingestion API. Marqueurs rouges : activités, bleus : hôtels, verts : restaurants, c'est la géométrie sur laquelle l'optimiseur route.

Figure 5 du rapport : l'interface en direct avec 73 POIs ingérés à Genève. Les voyageurs tagguent chaque pin avec un score de désirabilité 0–10 ; le solveur consomme cela, les heures d'ouverture et la matrice de temps de trajet précalculée pour planifier un voyage multi-jours faisable.

Figure 7 du rapport : valeur objectif heuristique au fil des itérations sur un voyage de 3 jours à Genève. L'heuristique d'insertion trouve une tour faisable à l'itération 1 ; le branch-and-cut de Gurobi ferme l'écart de plus de 1000 % à moins de 10 % en 26 itérations, le saut brutal vers l'itération 8 est la relaxation LP qui débloque une tour structurellement différente.

Techniques

Orienteering / TOP / TOPTW / TDOP
Branch-and-cut
Relaxations LP et presolve
Heuristiques d'insertion

Stack

Python
Gurobi
API Google Distance Matrix
FastAPI

Un problème de ce type ?

Nous serions ravis d'en entendre parler.

contact@optimally.ch