BILEVEL LINEAR PROGRAMMING MODELS AND ALGORITHMS FOR FREIGHT TRANSPORTATION

Ogni sistema di trasporto delle merci si presenta generalmente molto articolato e complesso: in particolare l'esistenza di numerosi soggetti che, a diverso livello e con diversi obiettivi, sono tenuti ad operare decisioni rappresenta un elemento che influisce in maniera spesso importante sull'assetto del sistema stesso. Il lavoro prende in esame un sistema di trasporto merci con due attori, denominati P e Q, che attraverso le rispettive decisioni determinano l'assetto dei flussi sulla rete. Il soggetto P, in particolare, ਠincaricato di soddisfare una data domanda di trasporto (ad esempio espressa mediante una matrice 0/D data) e puಠdecidere come ripartire i flussi su una rete multi modale della quale percepisce i tratti fondamentali. Al momento della sua decisione, P conosce il costo generalizzato degli archi della rete e cerca di minimizzare il costo totale del trasporto. Inoltre il giocatore P deve rispettare le decisioni del giocatore Q. Il giocatore Q, che controlla una porzione della rete che connette le origini alle destinazioni di P, invece conosce il profitto unitario che deriva dal transito veicolare sui suoi archi e cerca di massimizzare il proprio profitto complessivo. Nel far questo puಠmodificare la capacità  degli archi della sua sotto rete, ma anch'egli deve comunque soddisfare la condizione di bilanciamento ai nodi e deve rispettare le decisioni di P. Quale primo elemento di originalità  del presente lavoro puಠessere considerato il tentativo di condensare in un unico approccio alcuni elementi presenti singolarmente in filoni diversi. Infatti, tra i modelli della letteratura che intendono rappresentare esplicitamente le dinamiche decisionali interattoriali si ricordano i modelli multiattoriali sequenziali, i giochi su rete e la programmazione lineare bilivello i quali formano il quadro di riferimento in cui la presente lavoro si inserisce. Il quadro attoriale appena delineato offre l'opportunità  di affrontare una serie di problemi diversi, nel campo dell'affidabilità  della rete, a seconda dell'ordine con il quale i due giocatori decidono. Infatti il caso in cui la decisione di P preceda quella di Q puಠessere significativo, per P, al fine di valutare la peggiore situazione che potrebbe presentarsi per effetto di Q una volta stabilito l'assetto dei flussi sulla propria rete. àˆ questo un tipico esempio della cosiddetta "worst case analysis. Viceversa, se gioca prima Q, P riesce a determinare il migliore assetto dei propri flussi nel rispetto di vincoli imposti da Q su una parte della rete interposta tra la sua origine e la destinazione. Si pensi ad esempio alla problematica dell'attraversamento di Paesi, quali Austria e Svizzera, che impongono severe limitazioni per i veicoli pesanti. Il problema descritto viene formulato come un gioco su rete nel quale i due giocatori, P e Q, non cooperano tra loro. Si ottiene cosଠuna formulazione di programmazione lineare bilivello (BLP) dove il giocatore che gioca per primo ਠil leader, mentre l'altro assume il ruolo di follower. Ricordando che i problemi BLP sono NPhard, ਠstato sviluppato ed implementato un algoritmo euristico di ricerca della soluzione ottima. Sfruttando perಠl'osservazione che, nel particolare caso in questione, la soluzione ottima del problema BLP ਠanche un punto di equilibrio di Nash, l'algoritmo restringe la sua ricerca nell'insieme dei punti di equilibrio di Nash. Da un punto di equilibrio di Nash si passa ad un altro corrispondente ad una soluzione "migliore per il leader fino a quando l'algoritmo non si ferma. Purtroppo perಠnon si ਠsempre in grado di determinare un ottimo globale, ma solamente un ottimo locale individuando cosà¬, nel caso sia P a giocare per primo, un limite superiore alla soluzione ottima. Lo studio di tale modello ਠstato motivato dalla volontà  di rappresentare, con riferimento al sistema del trasporto merci su gomma tra la Thrchia e l'Europa Occidentale, la situazione che si ਠvenuta a creare nella regione dei Balcani a causa dei recenti eventi bellici. Tra le due regioni, annualmente, si registra un traffico dell'ordine delle centinaia di migliaia di veicoli commerciali. Per ragioni di semplicità , si ਠfatto riferimento alla sola componente verso l'Europa, fermo restando che la direzione opposta potrebbe essere analizzata in maniera del tutto analoga. Nell'esempio affrontato, la domanda di trasporto delle merci, che viene misurata in numero di veicoli all'anno, e che si sposta con origini diverse nel Sud-Est asiatico e destinazioni pure diverse nell'Europa Occidentale, ਠstata concentrata in due sole polarità  (1 origine e l destinazione). Nel sistema appena descritto l'Associazione Industriali della nazione di origine (UND) svolge il ruolo di decisore centrale ed ਠstata assimilata al giocatore P di cui sopra. In breve, nota la domanda da trasportare, l'UND decide la distribuzione delle merci tra vari percorsi sulla rete che collega l'origine (Turchia) alla destinazione (Europa occidentale). Conosce pure il costo generalizzato degli archi di tale rete e opera le proprie decisioni con l'obiettivo di rendere minimo il costo del trasporto. L'evento bellico ha causato, come riflesso su detto sistema, una decisa modifica alla capacità  degli archi di una porzione della rete stradale iniziale, che garantiva la connessione tra origine e destinazione. Alcuni archi sono stati eliminati (la rispettiva capacità  posta pari a zero), altri hanno subito una netta riduzione della capacità , o un significativo aumento del costo generalizzato. La guerra quindi ha assunto un comportamento analogo a quello del giocatore Q. In questo caso perà², non ha significato parlare di un'utilità  che la guerra cerca di massimizzare secondo quanto esposto in precedenza, a meno che non si proceda ad assimilare l'utilità  del giocatore Q con i costi di P: se Q gioca per massimizzare la propria utilità  e quest'ultima corrisponde ai costi di P, automaticamente Q gioca per massimizzare i costi di P e il modello acquista proprio il significato di una analisi del caso peggiore per P. La rete considerata ਠstata semplificata in accordo con il livello di dettaglio delle informazioni di cui dispone P ed ਠformata da 99 nodi e 181 archi, di cui solamente 100 sotto il controllo di P. Gli altri 81 archi, concentrati nella regione dei Balcani, sono sotto il controllo di Q e costituiscono una sottorete connessa, che disconnette l'origine dalla destinazione. La capacità  degli archi ਠstata determinata in accordo con il numero dei permessi di transito annui che ogni Stato concede ai veicoli turchi. Tale numero viene annualmente definito, mediante contrattazione tra le parti, in accordi bilaterali. In questa fase non si ਠtenuto conto delle differenti tipologie di permessi. In accordo con alcune necessarie ipotesi semplificative, la rete stessa ਠaciclica. I valori del costo per veicolo percepito da parte di P per transitare sugli archi della sottorete propria od altrui rispettivamente, sono stati determinati come funzione del costo monetario, della lunghezza fisica dell'arco e del tempo di percorrenza, tenendo in considerazione le varie voci che concorrono alla formazione del costo unitario (per veicolo-chilometro) di produzione di un servizio di trasporto sull'arco preso in esame. Per quanto riguarda i termini che compaiono nella funzione obiettivo di Q, si suppone che la guerra non tragga beneficio alcuno dal transito dei flussi veicolari sulla rete di P, mentre il profitto di Q ਠstato posto pari al costo sostenuto da P cambiato di segno come descritto in precedenza. Ai fini di valutare le prestazioni dell'algoritmo, il medesimo problema, viste le sue contenute dimensioni, ਠstato risolto anche con un algoritmo esatto, cioਠin grado di determinare l'ottimo globale. Il risultato dell'algoritmo proposto si discosta di solo lo 0,3% dal risultato ottenuto con una procedura di branch and bound. L'esempio applicativo ha consentito di comprendere le potenzialità  dell'approccio proposto e nell'ottica di un suo utilizzo concreto ha fornito delle utili indicazioni su possibili sviluppi da intraprendere legati sia all'algoritmo, sia al modello sia al caso di studio. In conclusione, il lavoro presenta un modello per la definizione dell'assetto del sistema di trasporto delle merci, con la trattazione esplicita delle dinamiche decisionali interattoriali.