Un pianificatore di attività su scala urbana che riproduce il Microcensimento svizzero su uno stack open source

Un framework MILP a tempo continuo sviluppato con le FFS all'EPFL, calibrato su 10'110 programmi giornalieri reali del microcensimento ed eseguito end-to-end su una popolazione sintetica di Losanna di 46'970 programmi giornalieri — senza un solo correttivo basato su regole

46'970

programmi giornalieri della popolazione sintetica di Losanna simulati end-to-end

10'110

programmi giornalieri reali del Microcensimento svizzero usati per calibrare il framework

Open source

gira su SCIP / OR-Tools — zero costi di licenza per solver commerciali

STRC 2021

sottoposto a peer review, co-firmato FFS × EPFL, finanziato da Innosuisse

La previsione della domanda di trasporto dipende dalla capacità di simulare ciò che le persone fanno davvero durante la giornata: quando lavorano, quando fanno acquisti, quando pranzano, e non solo quante auto circolano sulle strade. La maggior parte dei modelli operativi aggira la dimensione temporale con euristiche basate su regole, e perde ogni realismo non appena si verifica un evento dirompente.

Insieme alle FFS e all'EPFL abbiamo costruito un vero modello di ottimizzazione per la dimensione temporale. Un modello di programmazione intera mista decide congiuntamente l'intera giornata di ogni persona, calibrato su dati reali del Microcensimento svizzero. Il risultato è una simulazione su scala urbana i cui profili di attività corrispondono alle osservazioni empiriche, senza alcun correttivo euristico.

Il problema

I modelli di trasporto tradizionali basati sulle attività simulano le decisioni in sequenza (cosa fare, poi quando, poi dove, poi come) e restano così ciechi ai compromessi. Due attività in competizione per la stessa ora? Quarantamila persone che vogliono spostarsi e fare acquisti nello stesso momento? I modelli sequenziali tirano a indovinare; non ottimizzano.

Le FFS avevano bisogno di un framework abbastanza realistico da alimentare l'assegnazione del traffico in MATSim, abbastanza veloce da simulare programmi giornalieri completi per un'intera città e abbastanza flessibile da assorbire grandi cambiamenti di comportamento, come la diffusione del telelavoro.

Cosa abbiamo costruito

Abbiamo trasformato la dimensione temporale in un vero problema di ottimizzazione: orari di inizio, durate e sequenza delle attività di ogni persona sono decisi congiuntamente da un programma lineare intero misto, con parametri di utilità stimati dai dati. Le scelte non temporali (dove, cosa, come) restano nei modelli di scelta discreta già in uso alle FFS e alimentano l'ottimizzatore come input fissi.

Lo abbiamo messo in esercizio sul solver open source SCIP tramite OR-Tools, così la pipeline operativa non richiede alcuna licenza commerciale, e lo abbiamo validato rispetto al Microcensimento svizzero sulla sottopopolazione dei lavoratori a tempo pieno di Losanna.

Il risultato

Deliverable: un framework di pianificazione basata sulle attività, calibrato e validato, che risolve i conflitti temporali nei programmi giornalieri tramite un MILP che massimizza l'utilità, costruito sullo stack open source SCIP / OR-Tools (zero costi di licenza per solver commerciali). Pubblicato a STRC 2021 in co-firma con le FFS e l'EPFL, nell'ambito della collaborazione FFS × EPFL sulla modellazione della domanda di trasporto finanziata da Innosuisse (progetto 2155006680).

Su una popolazione sintetica di Losanna di 46'970 programmi giornalieri, i profili di attività simulati riproducono tutti i tratti empirici del Microcensimento svizzero (picco lavorativo del mattino, calo di mezzogiorno, finestra serale del tempo libero, struttura a più tour) senza un solo correttivo basato su regole. Il framework calibra 64 parametri comportamentali su 10'110 programmi giornalieri reali del microcensimento e raggiunge ρ̄² = 0,165.

Approfondimento tecnico

Il modello dietro il risultato.

Il modello

Ogni individuo i ha un insieme fisso di attività A_i da svolgere entro un budget di 24 ore ξ. Il MILP sceglie l'orario di inizio x_a, la durata τ_a, il tempo di viaggio tt_a verso l'attività successiva e un indicatore binario di sequenza z_{ab} (= 1 se a è immediatamente seguita da b). La funzione obiettivo è l'utilità totale del programma giornaliero: una somma di penalità per gli scostamenti dagli orari di inizio e dalle durate desiderati, più una disutilità legata al tempo di viaggio.

U_{i} = a \in A_{i} \sum U_{timing} (x_{a}) + a \in S_{i} \sum U_{duration} (τ_{a}) + O \in {P_{i}, H_{i}} \sum U_{duration} (a \in O \sum τ_{a}) + a \in A_{i} ∖ {dusk} \sum β^{travel} t t_{a} .

Utilità del programma giornaliero. Le attività secondarie sono penalizzate singolarmente; le attività primarie e quelle a casa condividono un budget di durata sull'arco della giornata.

U_{timing} (x_{a}) = β_{a}^{early} max (0, x_{a}^{*} - x_{a}) + β_{a}^{late} max (0, x_{a} - x_{a}^{*}) .

Penalità d'orario lineare a tratti attorno all'orario di inizio desiderato x_a*. È asimmetrica: arrivare in anticipo può pesare più o meno che arrivare in ritardo.

U_{duration} (τ_{a}) = β_{a}^{short} max (0, τ_{a}^{*} - τ_{a}) + β_{a}^{long} max (0, τ_{a} - τ_{a}^{*}) .

Penalità speculare attorno alla durata desiderata τ_a*. Stimata per massima verosimiglianza sui dati del microcensimento.

(z_{ab} - 1) ξ \leq x_{a} + τ_{a} + z_{ab} t t_{a} - x_{b} \leq (1 - z_{ab}) ξ \forall a, b \in A_{i} .

Coerenza della sequenza con big-M. Quando z_{ab} = 1, la coppia di disuguaglianze si riduce all'uguaglianza x_b = x_a + τ_a + tt_a; altrimenti i limiti sono inattivi.

a, b \in A_{i} \sum (τ_{a} + z_{ab} t t_{a}) = ξ, b \neq = a \sum z_{ab} = 1, b \neq = a \sum z_{ba} = 1 \forall a \in A_{i} ∖ {dawn, dusk} .

Il budget di tempo copre esattamente la giornata di 24 ore. Ogni attività (eccetto gli estremi dawn/dusk) ha esattamente un predecessore e un successore.

I parametri di flessibilità β^early, β^late, β^short, β^long sono incogniti per ciascun tipo di attività. Li stimiamo per massima verosimiglianza: per ogni programma giornaliero osservato nel microcensimento costruiamo un insieme di scelta competitivo, valutiamo ogni alternativa con la funzione di utilità definita sopra e calibriamo i parametri che rendono più probabile il programma osservato secondo un modello di scelta logit. In fase di simulazione i parametri vengono poi inseriti nello stesso MILP.

Benchmark

Parametri di flessibilità stimati per una selezione di cluster di attività (significativi al livello del 5 %).

Attività / cluster	β^early	β^late	β^short	β^long
lavoro : inizio al mattino	−0,615	−0,436	-	-
lavoro : inizio al pomeriggio	−0,406	0	-	-
lavoro : budget di durata giornaliero	-	-	−0,022	0
tempo libero : pranzo (sotto-tour)	−1,610	−0,821	−7,550	−1,360
tempo libero : tour secondario serale	−0,076	0	−3,060	−0,692
acquisti : in un tour secondario	−0,239	−0,486	−5,910	−0,721
casa : dopo il lavoro	−0,073	−0,596	-	-
casa : budget di durata giornaliero	-	-	0	−0,354

I valori negativi sono penalità (perdita di utilità per ora di scostamento). Il pranzo è l'attività più rigida, sia per lo scostamento d'orario sia per il mancato rispetto della durata desiderata. Il lavoro del mattino ha un orario di inizio rigido; quello del pomeriggio è molto più flessibile. La penalità per il rientro tardivo a casa (β^late = −0,596) riflette la preferenza, ben documentata, di essere a casa entro l'inizio della serata. Campione di 10'110 programmi giornalieri ripuliti di lavoratori a tempo pieno, ρ̄² = 0,165, log-verosimiglianza migliorata da −57'295,58 a −47'847,37 con 64 parametri.

Dalla documentazione

Figura 1 del rapporto: i due flussi del framework. La riga superiore calibra i parametri di flessibilità a partire dai programmi giornalieri del microcensimento; la riga inferiore usa tali parametri per simulare i programmi giornalieri della popolazione sintetica.

Figura 4 del rapporto: profili di attività simulati (a sinistra) rispetto ai profili osservati nel microcensimento (a destra) per la sottopopolazione dei lavoratori a tempo pieno. Il picco lavorativo del mattino, il calo di mezzogiorno, l'aumento serale del tempo libero e la predominanza della permanenza a casa vengono riprodotti senza correttivi basati su regole.

Figura 5 del rapporto: heatmap 2D orario di inizio × durata per le attività di lavoro e di tempo libero, modello rispetto al microcensimento. Il pattern lavorativo bimodale (solo mattino oppure mattino e pomeriggio separati) e il picco del tempo libero in pausa pranzo alle 12:00 sono colti dalla sola ottimizzazione.

Tecniche

Pianificazione basata sulle attività a tempo continuo
Programmazione lineare intera mista con OR-Tools / SCIP
Stima di massima verosimiglianza dei parametri di utilità
Generazione dell'insieme di scelta (alternative probabili + casuali)
Accoppiamento dell'ottimizzazione MILP con modelli sequenziali di scelta discreta

Stack

Python
OR-Tools
SCIP
Biogeme
Ray (esecuzione parallela)
Integrazione con MATSim

Un problema simile?

Inviatecelo. In pochi giorni vedete una prima versione sui vostri dati.

Descrivete il vostro problema

Caso successivo~1 mio. €: Un carico che riempie ogni camion, senza mai violare un limite di peso