Nuovo Metodo per l'Ottimizzazione della Programmazione dei Veicoli

Le compagnie di trasporto pubblico devono assegnare in modo efficiente i veicoli ai viaggi per portare i passeggeri da un posto all'altro. Qui entra in gioco la programmazione dei veicoli. L'obiettivo è combinare diversi orari di viaggio nel modo migliore possibile, assicurandosi che i veicoli siano disponibili nei momenti e nei luoghi giusti.

Quando i veicoli possono partire da diversi depositi, ci troviamo a dover affrontare la sfida di ridurre i costi assicurandosi che tutti i viaggi siano coperti. Questo problema specifico è conosciuto come il Problema di Programmazione dei Veicoli Multi-Deposito (MDVSP). Consentire piccole modifiche negli orari di partenza dei viaggi, chiamate "trip shifting", può aiutare a migliorare la programmazione. Permettendo questi piccoli cambiamenti, possiamo creare migliori combinazioni di viaggi, risparmiando così sui costi.

Tuttavia, se proviamo a considerare ogni possibile aggiustamento per gli orari di partenza, il problema diventa estremamente complesso e difficile da gestire per i metodi attuali. Per questo motivo, i ricercatori spesso utilizzano metodi più semplici, chiamati Metodi euristici, per risolvere problemi più grandi, che non garantiscono però la migliore soluzione.

In questo articolo, presentiamo un nuovo metodo chiamato Dynamic Discretization Discovery (DDD). Questo metodo può trovare la migliore soluzione per il Problema di Programmazione dei Veicoli Multi-Deposito con Trip Shifting (MDVSP-TS) senza dover elencare esplicitamente tutti i possibili aggiustamenti degli orari di partenza. Invece, risolve il problema passo dopo passo su una versione semplificata della rete fino a trovare un programma di veicoli praticabile.

#Panoramica della Programmazione dei Veicoli

Il processo di programmazione dei veicoli richiede alle compagnie di pianificare le rotte e gli orari dei loro veicoli in base a un orario stabilito. Ogni veicolo deve visitare luoghi specifici a orari programmati, assicurandosi che nessun viaggio resti scoperto. Quando sono coinvolti più depositi, la complessità aumenta poiché i veicoli devono tornare al deposito corretto dopo aver completato i loro percorsi.

Avere orari fissati aiuta a semplificare il problema di programmazione, ma può anche limitare il potenziale di migliorare l'orario complessivo. Consentire piccole modifiche agli orari di partenza dei viaggi offre opportunità per connettere viaggi che altrimenti sarebbero impossibili. Questa flessibilità di consentire che i viaggi inizino un po’ prima o dopo è conosciuta come "trip shifting", trasformando un problema più complesso nel Problema di Programmazione dei Veicoli Multi-Deposito con Trip Shifting (MDVSP-TS).

La sfida di considerare tutti i possibili aggiustamenti dei viaggi è che può portare a un numero travolgente di opzioni. Più aggiustamenti sono consentiti, maggiore diventa il problema, potenzialmente causando di superare la capacità dei metodi di risoluzione attuali. È per questo che si utilizzano spesso approcci euristici, anche se potrebbero non garantire le migliori soluzioni.

#Dynamic Discretization Discovery (DDD)

Dynamic Discretization Discovery (DDD) è un metodo avanzato sviluppato per aiutare a risolvere il MDVSP-TS. Non richiede una rappresentazione completa di ogni possibile spostamento di viaggio. Invece, lavora perfezionando iterativamente un modello di rete semplificato per trovare una soluzione continua ottimale.

L'algoritmo DDD inizia con una rappresentazione semplificata del problema, il che significa che non tutti i possibili spostamenti di viaggio sono mostrati. Questa rappresentazione è chiamata rete parzialmente espansa nel tempo. L'algoritmo risolve il problema su questa rete semplificata, fornendo un limite inferiore per la soluzione. Se la soluzione può essere aggiustata per adattarsi ai tempi di viaggio reali, allora è considerata ottimale. Altrimenti, la rete viene aggiornata, aggiungendo nuovi punti temporali e affinando il modello per risolvere nuovamente.

Uno dei principali vantaggi del DDD è che può scoprire migliori soluzioni più rapidamente perfezionando il problema iterativamente piuttosto che provare a risolvere tutto in una volta. Questo processo consente di esplorare programmi di veicoli efficienti senza bloccarsi in calcoli complessi.

#Implementazione del DDD nella Programmazione dei Veicoli

Per applicare il DDD al MDVSP-TS, iniziamo creando una rete parzialmente espansa nel tempo. Questa rete include percorsi per sequenze di viaggi fattibili, garantendo che tutti i viaggi siano inclusi. La rete utilizza diversi tipi di connessioni, come gli archi dei viaggi, che rappresentano i viaggi programmati e i loro possibili aggiustamenti temporali, e gli archi di vuoto, che indicano i movimenti a vuoto tra i viaggi.

I viaggi in questa rete si basano sui tempi di viaggio e consentono aggiustamenti come indicato. L'obiettivo è trovare una soluzione in cui tutti i viaggi siano coperti riducendo al contempo i costi operativi.

L'algoritmo utilizza tre metodi principali per creare la rete parzialmente espansa nel tempo:

1. Il primo metodo assomiglia da vicino ai metodi DDD esistenti, assicurandosi che tutti gli archi siano accurati o più brevi di quanto dovrebbero essere.
2. Il secondo e il terzo metodo tengono conto della struttura specifica del MDVSP-TS, consentendo archi più lunghi senza aumentare il numero di punti temporali, risultando in soluzioni più robuste.

Inoltre, il DDD incorpora più strategie di affinamento per garantire che la soluzione sia praticabile. La prima strategia si concentra sulla suddivisione della soluzione in doveri, o sequenze di viaggi effettuati dai veicoli, e controlla la loro fattibilità. Se un dovere non può essere eseguito, l'algoritmo aggiunge punti temporali per garantire che il dovere non venga più incluso nelle iterazioni future.

#Test delle Prestazioni del DDD

Per valutare l'efficacia dell'algoritmo DDD, vengono condotti una serie di esperimenti computazionali. Questi esperimenti utilizzano istanze generate di viaggi-che vanno da 500 a 1000-e analizzano le prestazioni dell'algoritmo.

Le valutazioni chiave si concentrano sul tempo necessario per raggiungere una soluzione ottimale e sull'impatto di diversi schemi di costruzione degli archi di vuoto sulle prestazioni. I risultati dimostrano che il DDD con una costruzione di archi più efficiente può superare significativamente i metodi tradizionali, soprattutto man mano che il tempo massimo consentito per gli aggiustamenti aumenta.

Gli esperimenti indicano che il tempo medio di calcolo diminuisce significativamente con l'implementazione del DDD, specialmente nei casi in cui sono coinvolti un numero maggiore di viaggi. Utilizzando schemi di costruzione migliorati, l'algoritmo riesce a trovare soluzioni ottimali molto più rapidamente di quanto sarebbe se tutti i possibili aggiustamenti fossero rappresentati.

#Vantaggi del Trip Shifting

La ricerca esamina anche i vantaggi del trip shifting e come influisce sui costi. L'analisi mostra che consentire lievi aggiustamenti negli orari dei viaggi può portare a risparmi significativi. Con la possibilità di spostare i tempi dei viaggi, il numero complessivo di veicoli richiesti diminuisce, riducendo così le spese operative.

L'indagine sugli esiti dell'algoritmo illustra che questi risparmi crescono man mano che aumenta il numero di viaggi. Ad esempio, nei casi in cui viene aumentata la deviazione massima consentita, i costi possono essere ridotti di circa l'1% per un aggiustamento minimo o fino a circa il 5% con maggiore flessibilità.

Curiosamente, anche se i costi sono inferiori, le deviazioni medie dagli orari originali rimangono relativamente piccole. Questo suggerisce che il sistema può raggiungere efficienza senza causare interruzioni sostanziali agli orari stabiliti.

#Conclusione

In questo articolo, abbiamo discusso di un nuovo metodo chiamato Dynamic Discretization Discovery, progettato per risolvere il Problema di Programmazione dei Veicoli Multi-Deposito con Trip Shifting. Questo approccio di raffinamento iterativo consente soluzioni ottimali senza la necessità di mappare tutti i potenziali spostamenti di viaggio.

Lo studio computazionale supporta l'idea che il DDD superi significativamente i metodi di modellazione tradizionali e possa gestire efficacemente istanze di problemi più grandi. È importante notare che il DDD dimostra anche un alto grado di flessibilità consentendo modifiche agli orari senza creare impatti eccessivi sulle operazioni complessive.

Guardando al futuro, lo sviluppo del DDD apre nuove possibilità per la ricerca nel trasporto, particolarmente in aree come la pianificazione dei veicoli elettrici e l'integrazione delle sfide di programmazione di veicoli e equipaggi. Man mano che i sistemi di trasporto pubblico continuano ad evolversi, metodi come il DDD possono essere cruciali per soddisfare le esigenze di una programmazione dei veicoli efficiente e adattabile.