Vehicle scheduling

L’algoritmo che è alla base del vehicle scheduling può essere a singolo deposito o a multi-deposito. Soffermiamoci sull’algoritmo a multi-deposito, cpt ha vari depositi e rappresenta la parte maggioritaria di CTT scrl.

Sia T={1,2,….n} un insieme di corse e si assuma che la corsa i E T inizi al tempo si e termina al tempo ei; le due corse i e j risultano compatibili se possono essere realizzate dallo stesso veicolo, vale a dire se e solo se

ei +tij≤sj , dove tij è il tempo impiegato per andare dalla località alla fine della corsa. Tra queste due può esistere una corsa senza trasporto di passeggeri (corsa a voto) nel deposito d E D si trovano kd veicoli che da tale deposito devono partire e ivi tornare. Un veicolo che lascia il deposito per raggiungere il punto di partenza di una corsa in uscita costituisce il pull-out mentre se è di rientro dalla corsa si ha il pull-in. Un turno ammissibile è composto da un pull-out, una serie di corse a vuoto e una corsa di pull-in. Le corse a vuoto, come quelle di allontanamento e rientro al deposito, sono costi aggiuntivi e vengono presi in considerazione nella funzione obiettivo. Infatti il costo totale di una schedula è la somma dei costi delle singole corse. Lo scopo di questo metodo multi-deposito è quello di determinare un insieme di schedule ammissibili in modo che:

ogni corsa i E T è coperta esattamente da una schedula;

possono essere determinate al più kd schedule per ogni deposito appartenente all’insieme;

i costi totali delle schedule sono minimizzati.

Si noti che ogni corsa a vuoto implica un tempo di attesa per l’inizio della corsa successiva.

Il SVDP metodo a singolo deposito, è utilizzato da Sequi. Infatti, esso è ideneo per aziende di trasporto di dimensioni medie e piccole e può essere

Progetto di analisi per la Riorganizzazione e Ottimizzazione della Rete di Trasporto Pubblico Locale nel Comprensorio del Cuoio

2013

risolto in tempo polinomiale, poiché può essere modellato come un problema di flusso di costo minimo.

Questo flusso è stato formulato da Rebiro e Soumis48: ad ogni deposito d E D è associato un grafo diretto Gd=(Nd,Ad), in cui Nd = T U {d} e Ad= C U ({d } x T) U (Tx { d }) denotano l’ insieme dei nodi e degli archi del grafo.

Le variabili decisionali xdij rappresentano il flusso dei veicoli che hanno origine dal deposito d E D sull’ arco (i,j).

L’algoritmo di programmazione lineare del multi-uso può essere così formulato:

minimize ∑ ∑ cij xdij d E D (i,j)E Ad subject to

∑ ∑ xdij = 1 per ogni j E T d E D (i,j)E Ad

∑ xdj ≤ kd per ogni d E D j E T

∑ xdij - ∑ xdij = 0 per ogni j E T U {d} (i,j)E Ad (i,j)E Ad (i,j)E Ad Xdij E {0,1}, per ogni d E D

Il modello appena descritto ha come obiettivo quello di minimizzare i costi dei viaggi. Inoltre, può essere svolto con la programmazione in AMPL e anche come un problema NP49 con l’ uso della polinomiale. Esso può trovare soluzione anche utilizzando il Branch & Bound50, mentre con il rilassamento

48

Ribiero, Soumis: A Column Generation Aprroach to the Multiple Depot Vehicle

Scheduling Problem. Operation Research, 42 (1):41-52,1994.

49 _{I problemi di classe-NP sono problemi decisionali risolvibili da una macchina non}

deterministica in tempo polinomiale. Un problema decisionale è nella classe P se è risolubile da un algoritmo di complessità polinomiale. Un problema NP di classe decisionale e risolubile attraverso un algoritmo non deterministico.

50 _{Branch and Buond è una risoluzione tramite l’albero di enumerazione totale: ha per}

radice il problema P, facendo poi una partizione in due o più sottoinsiemi si ottengono I nodi di primo livello, che corrispondo ai sottoproblemi di P, il resto dell’albero viene generato allo stesso modo, fino ad arrivare alle foglie che corrispondono a sottoproblemi

Progetto di analisi per la Riorganizzazione e Ottimizzazione della Rete di Trasporto Pubblico Locale nel Comprensorio del Cuoio

2013

si ottiene una soluzione ottimale per 600 corse e 3 depositi. Il rilassamento lagrangiano51 consente di separare i vincoli di flusso dai vincoli disgiuntivi legati al Set Partitioning.52 La soluzione duale è utilizzata per ridurre drasticamente l’insieme delle variabili. 53

Un altro metodo è quello proposto da Lobel54, definito come il metodo della generazione delle colonne: ad ogni iterazione, si risolve il probelma, utilizzando l’algoritmo del simplesso duale e si generano colonne basate sia sul rilassamento lagrangiano che sul criterio standard dei costi ridotti. Ad ogni iterazione vengono utilizzati due rilassamenti lagrangiani, il primo da luogo a m² problemi di flusso a costo minimo, risolvibili nella formulazione:

∑ ∑ xdij = 1 per ogni j E T d E D (i,j)E Ad

La soluzione ottima, che si ottiene dal rilassamento è a componenti intere. Il branch & buond può essere applicato come combinazione di tre metodi: generazione di colonne55, alcune vairabili e piani di taglio. Ad ogni nodo dell’albero di branching è configurata una prima soluzione ottenuta come flusso di costo minimo, applicando poi i piani di taglio sono individuate alcune disuguaglianze valide.

∑ xdij - ∑ xdij = 0 per ogni j E T U {d} (i,j)E Ad (i,j)E Ad (i,j)E Ad

aventi la regione ammissibile vuota o costituita da un solo elemento. Bound sta per rilassamento e branch per partizione. L’albero si può esaminare in ampiezza, profondità o qualità.

51 _{Il rilassamento lagrangiano è una tecnica risolutiva della programmazione lineare che}

consente di vedere il problema in modo più facile infatti consiste nell’eliminazione dei vincoli più complessi e nella loro introduzione nella funzione obiettivo. La regione ammissibile è cx+y(b-Ax)≥cx.

52 _{Dato un insieme Idi m oggetti e un insieme J di m oggetti, si definisce partizione:}

l’insieme J’ se J’è incluso in J e l’insieme dei Pj sottoinsiemi di J è uguale a I. ogni problema di set partioning può essere trasformato nel suo equivalente di set covering.

53 _{Ribiero, Soumis: A Column Generation Aprroach to the Multiple Depot Vehicle}

Scheduling Problem. Operation Research, 42 (1):41-52,1994.

54 _{Lobel: Vehicle Scheduling in Public Transit and Lagrangean Pricing, Operations}

Research, 44(12):1637-1649,1998.

55 _{Il metodo di generazione delle colonne è spesso usato per problemi che presentano un}

numero elevato di variabili e si basa su insieme di schemi di taglio. Il numero degli schemi può essere particolarmente copioso, tanto da richiedere un tempo lungo per la generazione della matrice.

Progetto di analisi per la Riorganizzazione e Ottimizzazione della Rete di Trasporto Pubblico Locale nel Comprensorio del Cuoio

2013

Indica che tanti veicoli eseguono un’attività e una volta terminata l’attività iesima procedono ad un’altra attività.

Il modello del vehicle scheduling è utilizzato per fornire supporto alle decisioni in campo logistico, è una tecnica molto utilizzata per coordinare la programmazione degli autobus in modo da minimizzare i costi, soprattutto per gli spostamenti a vuoto.

Obiettivo:

minimizzare i costi operativi

Leve decisionali:

assegnazione dei viaggi ai veicoli

Vincoli:

un veicolo può eseguire un viaggio se raggiunge la localizzazione di inizio in un tempo utile.

Ogni attività deve essere eseguita

Dati:

start e end time start e end location

costi di un viaggio e di trasferimento a vuoto

Il costo generico cij di un arco per spostarsi da i a j è composto dal costo del

traferimento a vuoto, dal rapporto profitti/costi operativi del viaggio (che è proprio il punto da cui si è partiti per la nostra analisi di efficienza) e i costi fissi legati all’uso del veicolo.