Ottimizzazione del ride-sharing elettrico autonomo, 31× più veloce della baseline Branch-and-Price pubblicata e con gap fino a 11× più stretti

Codifica dei nodi-evento. Ogni nodo v del grafo degli eventi è una Q-upla che registra nella posizione 1 l'ultimo evento di prelievo/rilascio e nelle posizioni 2..Q gli altri passeggeri presenti nel veicolo (in ordine crescente). Gli zeri riempiono i posti vuoti; un −1 finale indica gli stati presso una stazione di ricarica. Per costruzione la Q-upla non può contenere un passeggero già sceso, quindi la capacità del veicolo (al massimo Q passeggeri) e l'abbinamento prelievo-prima-del-rilascio sono codificati strutturalmente in V, non come vincoli.

Costo multiobiettivo e conservazione del flusso. L'obiettivo bilancia il costo di instradamento dei veicoli (∝ tempo di percorrenza) con il tempo di viaggio in eccesso R_i degli utenti, con pesi w_1, w_2 scelti dall'operatore. La conservazione del flusso stabilisce che in ogni nodo-evento diverso dal deposito a ogni arco entrante corrisponda un arco uscente. Insieme al vincolo esplicito «ogni utente servito esattamente una volta» (Σ_{δ^in(v), v ∈ V_i} x_a = 1), si ottiene un problema di flusso a costo minimo sul grafo degli eventi.

Vincoli temporali. L'istante di inizio servizio T_w dell'evento successivo deve essere almeno pari all'istante di inizio dell'evento precedente più il tempo di servizio e il tempo di percorrenza, con un big-M (l'orizzonte H) che disattiva il vincolo quando l'arco non è utilizzato. Il limite sul tempo di viaggio garantisce l'equità verso gli utenti: per ogni utente i, il tempo tra prelievo e rilascio non può superare il tempo di viaggio massimo p_i (così il sistema non può tenere qualcuno a bordo indefinitamente solo per ottimizzare i percorsi).

Dinamica dello stato di carica della batteria. Tra eventi che non sono di ricarica, lo SoC nel nodo successivo B_w è pari a B_v meno la scarica β_{(v,w)} = µ · t_{(v,w)} lungo l'arco. Nei nodi delle stazioni di ricarica (V_z) la batteria viene ricaricata di α · E_v, dove α è la velocità di ricarica ed E_v la durata della ricarica. Le versioni simmetriche con ≥ di entrambi i vincoli (omesse) fissano l'uguaglianza quando l'arco è utilizzato. Il vincolo di fine giornata B_v ≥ γG obbliga i veicoli a rientrare al deposito con almeno una frazione γ della capacità (il parametro principale del benchmark: γ = 0,7 è il caso difficile).

Tempo di viaggio in eccesso. R_i è la misura di equità verso l'utente: è la differenza tra il tempo effettivamente trascorso a bordo (T_rilascio − T_prelievo − tempo di servizio) e il tempo minimo t_{(i, n+i)} di un viaggio diretto. La minimizzazione della somma totale Σ R_i è il secondo obiettivo: senza di essa, l'ottimizzatore terrebbe volentieri qualcuno a bordo per ore pur di consolidare i viaggi.

Perché la formulazione basata su eventi vince. Il modello basato sugli archi (Bongiovanni 2019, Su 2023) ha una variabile per ogni terna (veicolo, luogo, luogo), ma la maggior parte di queste terne non è ammissibile (stato di capacità errato, violazione delle finestre temporali, violazione dell'abbinamento) e il solver deve scoprirlo durante il branch-and-bound. Il grafo degli eventi elimina gli stati non ammissibili già in fase di costruzione: i controlli di compatibilità tra finestre temporali e tempi di percorrenza scartano nodi che un modello basato sugli archi manterrebbe. Per le istanze type-a con Q = 6 si ottengono ~150-1'500 nodi e ~1'500-16'000 archi, una dimensione gestibile dal branch-and-cut di Gurobi.

Disuguaglianza valida per i percorsi non ammissibili. Per ogni utente i e ogni percorso di due archi P = (a, b) nel grafo degli eventi in cui i è a bordo, se il tempo di viaggio complessivo supera p_i, al massimo |P| − 1 = 1 degli archi può essere attivo. Aggiungere queste disuguaglianze fin dall'inizio (invece di aspettare che il branch-and-bound le scopra tramite tagli) rafforza sensibilmente il rilassamento LP sulle istanze type-r e type-u.