Please use this identifier to cite or link to this item: http://hdl.handle.net/10077/11529
Title: BILEVEL LINEAR PROGRAMMING MODELS AND ALGORITHMS FOR FREIGHT TRANSPORTATION
Authors: CASTELLI, LORENZO
Issue Date: 22-Feb-2002
Publisher: Università degli studi di Trieste
Abstract: 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. In particolare si prendono in considerazione due soggetti, che operano scelte in sequenza gerarchica, uno dei quali agisce per minimizzare i costi totali del trasporto e l'altro cerca invece di massimizzare il proprio profitto che dipende dal volume di traffico lungo gli archi sotto il suo controllo. Si propone una formulazione di programmazione lineare bilivello, per risolvere un gioco infinito statico non cooperativo con insiemi di vincoli accoppiati. Sono descritte le condizioni di esistenza e alcune proprietà dei punti di equilibrio di N ash, dalle quali discende un algoritmo di ricerca di un ottimo locale. Viene infine discussa un'applicazione del modello al caso del trasporto merci dalla Turchia all'Europa. Alcuni futuri sviluppi sono possibili. Essi portano alla progressiva eliminazione delle assunzioni semplificative che sono state adottate allo stato attuale nella formulazione del modello. In particolare si tratta della configurazione della rete, della struttura e delle proprietà dell'algoritmo (oggi trova solamente un ottimo locale). Inoltre si intende procedere con il perfezionamento del caso di studio.
Freight transportation is generally a very complex domain where several players, each with its own set of objectives, act and operate at various decisional levels. There are different players in the field. The shippers who decide how much of each commodity to move from every origin to every destination and the means by which the goods will be moved. The carriers who respond to this transportation demands and route freight over the actual transportation network under their contro!. Finally, the government defined as the set of international, national and local authorities involved in any way with freight transportation via regulation and the provision of transportation infrastructure. In this work, we consider the case where only one shipper determines the demand for transportation over a network. However, he cannot decide fiow levels on arcs in a fully independent way due to the presence of a second agent controlling some links of the network and optimizing her own objective function. This situation is modelled as a game between two players P and Q acting o n the same network G. Player P fixes the fiows o n the arcs of G in such a way t ha t their divergence at some given nodes (sources and sinks) is equal to prescribed values. Such divergences may represent demand and availability levels for some commodity. On the other hand, player Q decides the values of the maximum capacities of some arcs of the network. Both players are interested in the fact that the connectivity between the sources and the sinks in the network is respected, i.e., they both want that the goods can reach their destination. However, they have different objectives. Player P aims at minimizing the transportation costs, whereas player Q aims at maximizing her profit (or, in generai, her utility) that is proportional to the fiow passing through the arcs under her control. Note that, in generai, the profit of player Q is not assumed to be equal to the cost of player P for the same are. Such game between players P and Q is modelled as a minimum cost flow problem for player P, where the are costs are given and the player Q decides the are capacities. The modelling of the games under investigation are mainly based upon three different research lines. First, the players understand the freight transportation system as a system where the actors involved do not act simultaneously and they explicitly take into account the sequential nature of the interactions among them. Second, they play a (hierarchical) game over a flow network which causes severe limitations and constraints to their action sets. Finally, the games exhibit linear characteristics and can be solved using bilevel linear programming. All these issues have already been discussed in the scientific literature, even though in different separate contexts. The merging of three mentioned approaches in only one single framework is a major contribution of our modelling perspective. Furthermore, bilevel programming is rich of theoretical results and numerica! algorithms, but is scare in actual applications. From this point of view, the present work might be considered as an interesting addition to the field. Bilevel noncooperative games in which one player ( called the leader) declares his strategy first an d enforces i t o n the other players ( called the followers) w ho react (rationally) to the leader's decision are referred to as Stackelberg games. Since the payoff functions and all the constraints in our Stackelberg games may be expressed in a linear form, these games will be formalized as bilevellinear programming problems (BLPPs). In generai, bilevel programming problems are difficult to sol ve because of their inherent non-convexity and non-differentiability. To face their NP-hard nature, we identify some properties of the game solutions which allow us to define a heuristic algorithm restricting its (local) search on the set of the Nash equilibrium points. The optimal solution of any BLPP lies on a vertex of the leader's inducible region. Relying on this result, we develop an algorithm which allows to move from a starting point of the shipper's inducible region to another point in the shipper's inducible region always providing a better solution for him. When no further better points may be attained, the algorithm stops. Unfortunately, only a local optimum is identified. The rationale behind the algorithm stems from the consideration that the optimal solution for our BLPP is also a Nash equilibrium point. In particular, the algorithm moves from a Nash equilibrium point to another better Nash equilibrium point of the BLPP under study. This framework may describe, as an example, the situation where restrictions are imposed by some alpine country on the number of trucks allowed to cross it by road each year. A different context involving the presence of a second agent o n the shipper's network occurred when the International Transporters' Association (UND) of Turkey had to face when the war in the Balkans started. This situation motivates our investigation on hierarchical noncooperative network games. The road freight traffi.c from Turkey to Centrai and Western Europe and viceversa suffered major disruptions because of the war in Balkans during the nineties. UND is the shipper controlling the quasi-totality of this traffi.c thus assuming the role of player P. H e had to cope with an "adverse entity" able to modify the available capacity on some specific links his vehicles had to pass through. The region involved in the confiict may be represented as a connected subnetwork disconnecting the origin and the destinations of the road transportation network since alternative road routes are not easily affordable. Other possibilities, like the seaborne links now operating, did not exist at that time. Hence the whole freight traffi.c was performed using a single mode of transport. The models developed in this work allow the shipper to perform a worst-case analysis at the strategie level for this situation assuming that player Q wishes to maximize the costs he has to afford when going through the region under her control. In fact, it is meaningless to talk about the utility or the profit the war may seek t o maximize. However, i t becomes a sensible modelling when the utility of player Q is strictly related to the costs afforded by player P on this portion of the network. lf player Q is maximizing her utility which corresponds to player P's costs, automatically she plays to maximize player P's costs. Hence the model represents a worst-case analysis for player P. A simple graph composed of 99 nodes and 181 arcs is presented. Player P controls a sub network composed of 100 arcs. The others 81 links representing the connections within the Balkans and Eastern Europe form a connected sub network. Only the main road links ha ve been considered ( motorways or highways). The capacities are calculated taking into account the total number of transit permits available for each country. This figure is annually fixed in bilatera! Joint Committee Meetings. Player P's costs are the average generalized costs derived as a function of lengths and transfer times in the physicallinks. Player Q does not have profits or losses for the fiows passing through the P zone and it is also assumed that the profits she earns for each unit of fiow going through the arcs under her control are equal to the costs afforded by the shipper when traversing these arcs. All the relevant data required to calculate these figures are collected in the UND Annual Sector Report 1997-98 (1999). The heuristic algorithm has been tested on this network and its results have been compared with the outcome obtained by using an exact enumeration procedure. Since it turns out that the percentage error of the heuristic algorithm is equal to 0,3%, we may claim that its performances are certainly highly satisfactory, at least in this specific example. Different extensions of the models and the algorithm developed may be easily envisaged both from the theoretical and the application side. These advances would provide either faster local or global search algorithms either more complete models representing in deeper detail the actual system and the interactions among the actors involved. Hence a decision support system for the shipper's decision making process at the strategie level can be built and effectively used by freight transportation practitioners.
Description: 2000/2001
URI: http://thesis2.sba.units.it/store/handle/item/12244
http://hdl.handle.net/10077/11529
Appears in Collections:PREGRESSO

Files in This Item:
File Description SizeFormat 
20146.pdf1.27 MBAdobe PDFView/Open
Show full item record


CORE Recommender

Page view(s)

205
checked on Feb 18, 2018

Download(s)

240
checked on Feb 18, 2018

Google ScholarTM

Check


This item is licensed under a Creative Commons License Creative Commons