Itinerari turistici personalizzati calcolati in pochi secondi

Nota sulla fonte. Pertinenza solo indiretta (pianificazione di visite urbane, non crociere); lavoro parzialmente finanziato da un operatore ferroviario.

La domanda

Come pianificare automaticamente itinerari turistici personalizzati, su uno o più giorni, che rispettino orari di apertura, orari del trasporto pubblico, tempi di visita variabili e preferenze individuali, in tempi compatibili con un servizio in tempo reale?

Il metodo

Formulazione matematica (programmazione lineare intera mista) di un problema di orienteering a squadre dipendente dal tempo con finestre temporali e benefici variabili, più algoritmi euristici (greedy e iterated local search) su un grafo pre-calcolato di percorsi a piedi e in trasporto pubblico. Test su 41 punti di interesse di Berlino e 25 richieste (tour da 2 a 10 ore, uno o due giorni).

Cosa emerge

41 luoghidi interesse di Berlino usati per i testPer i test gli autori hanno usato 41 luoghi di interesse di Berlino, scelti manualmente tra più categorie e con gli orari di apertura raccolti a mano.

6–20%di scarto dal massimo teorico dopo 10 oreAnche dopo 10 ore di calcolo per richiesta, il metodo esatto dimostra di aver trovato l'itinerario migliore possibile solo per il caso più semplice (un tour di due ore); per gli altri la distanza tra la migliore soluzione trovata e il massimo teorico resta fra il 6% e il 20%.

5–10 punti %di qualità in meno del metodo greedyIl metodo greedy più semplice dà una risposta in 2-4 millisecondi, ma i suoi itinerari valgono 5-10 punti percentuali in meno di quelli del metodo esatto, e in un caso 16 punti in meno.

≈ 1,5 stempo medio di calcolo della ricerca locale iterataLa ricerca locale iterata impiega in media circa 1,5 secondi: corregge bene le soluzioni iniziali di scarsa qualità, ma non migliora quasi mai quelle già buone.

Calcolare in anticipo tutti i collegamenti a piedi e con i mezzi pubblici tra questi luoghi richiede circa un quarto d'ora: abbastanza poco da poterlo rifare a ogni cambio di orario o di percorso.
Dividere la giornata in intervalli di 5 minuti è il compromesso migliore: passando a intervalli di 1 minuto il calcolo è circa cinque volte più lento e la qualità migliora solo di 0,5-1 punti percentuali.

Perché conta per porti e città

Lo studio non riguarda le crociere, ma affronta un problema simile a quello di una sosta a terra: costruire un itinerario personale in un tempo fisso, tenendo conto di orari di apertura e trasporto pubblico. Mostra che si possono ottenere proposte utilizzabili in pochi secondi, anche se i metodi rapidi possono restare sensibilmente sotto la soluzione migliore.

Limiti

Studio algoritmico senza utenti reali né dati di comportamento; benefici dei punti di interesse e preferenze sono parametri ipotizzati; un solo caso (Berlino, 41 punti di interesse) e nessun riferimento specifico al turismo crocieristico o a vincoli di rientro a bordo.

Riferimento completo e fonte

Gündling, F., Witzel, T. (2020). Time-Dependent Tourist Tour Planning with Adjustable Profits. 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020), OpenAccess Series in Informatics (OASIcs), Schloss Dagstuhl – Leibniz-Zentrum für Informatik.

Leggi lo studio originale ↗

Sintesi dell'Osservatorio ODYBOAT con parole nostre. Tabelle e figure restano degli autori.