Tesi di Dottorato

Nell'ambito del presente lavoro di tesi e stato a rontato un problema di rilevante interesse applicativo relativo alla valutazione e generazione di o erte (Bid Generation Problem) nell'ambito di aste combinatorie per sistemi di trasporto di tipo full-truckload (a pieno carico). L'organizzatore (auctioneer) di un'asta combinatoria, vuole acquistare tramite asta dei servizi (contratti) di trasporto, cio e rotte (lane) su cui trasportare dei carichi (load). I vari trasportatori (carrier) devono quindi fare delle o erte (bid) sulle rotte di trasporto che vogliono vendere all'asta, non in maniera individuale (come nelle aste singole), ma raggrup- pate in pacchetti (bundle) di rotte. Il Bid Generation Problem (BGP) in un'asta combinatoria e il prob- lema a rontato dal carrier per poter costruire tali o erte (bundle di rotte) da sottomettere all'asta sotto forma di bid (cio e l'insieme di load con il relativo prezzo proposto). Le aste combinatorie sono di solito scelte per procurare i servizi di trasporto per via delle sinergie che usualmente esistono tra le varie rotte messe all'asta e quelle componenti la rete di trasporto attuale di un carrier. La necessit a di valutare un numero esponenziale di bundle (pari al numero di tutti i sottoinsiemi che si possano formare con le rotte messe all'asta) conferisce al problema decisionale una natura NP- completa, come evidenziato ad esempio in [33]. La scarsit a dei riferimenti bibliogra ci, se pur motivata dall'oggettiva di colt a di soluzione sopra descritta, non ha giusti cazioni per o dal punto di vista applicativo. In tale ambito si colloca la presente tesi di Dottorato avente come obi- ettivo lo sviluppo di un advisor che assista i carrier nelle loro decisioni di bidding, integrandosi nella piani cazione dinamica delle operazioni di trasporto. In particolare, nel lavoro di tesi e stato proposto un modello di ottimizzazione misto intero per il BGP in grado di determinare non solo il bundle di load sottomesso all'asta e il relativo prezzo, ma anche il relativo routing della otta del carrier, e etuato nell'orizzonte tempo- rale per servire sia il bundle di rotte sottomesso che la rete di trasporto attuale. I principali contributi innovativi del modello proposto derivano da: 1) l'inclusione nel modello di un vincolo di tipo probabilistico (chance constraint), che mira a guidare la scelta del bundle con maggiore chance di vincita alla ne dell'asta, cio e la cui probabilit a di superare il clearing price (rappresentato tramite una variabile aleatoria) sia superiore ad un certo livello di probabilit a. Rispetto al modello di Savelsbergh et al. ([54]), si considera la probabilit a che il bundle sia vincente nei vincoli invece che nella funzione obiettivo, e la distribuzione normale del clearing price (pi u realistica) invece di quella uniforme. Inoltre, in [54], si trattava di pi u aste singole indipendenti, svolte in parallelo, qui invece abbiamo un'asta combinatoria a busta chiusa, primo prezzo, single-round. 2) il considerare il prezzo del bundle come variabile di decisione, come solo in [54] accadeva , negli altri articoli si considera o qualche formula di calcolo ([42], [52], [53]) oppure noti, ssati uguali alla somma dei prezzi richiesti dall'auctioneer (ask price) per le singole rotte componenti il bundle ([6],[24]). 3) l'inclusione dell'aspetto temporale del problema reale ( nora solo Chang aveva considerato in [6] la rete estesa spazio-tempo per il BGP). 4) il determinare anche il routing dei camion relativo a tutto l'orizzonte temporale ([24] era il primo articolo che, nel modello proposto per il BGP, includeva anche il VRP, ma senza per o considerare la variabile tempo). 5) l'inclusione delle nestre temporali (time-windows) relative alla consegna di ogni carico messo all'asta e dei carichi della rete attuale di trasporto (precedentemente contrattati) dal carrier. 6) lo studio e la quanti cazione delle sinergie tra le rotte messe all'asta e quelle dell'attuale rete di trasporto del carrier (in due modi, e diver- samente di come fatto in [2], [6], [54], [58]) e l'inclusione di tali sinergie nella distribuzione della variabile aleatoria considerata (il clearing price del bundle). Per i motivi sopra descritti, il modello proposto risulta pi u completo e pi u complesso rispetto a tutti i modelli nora esistenti per il BGP nelle aste combinatorie nei trasporti a pieno carico. Il presente lavoro e organizzato in 5 capitoli, esclusa l'introduzione e le conclusioni. Nel seguito viene riportata una breve descrizione del contenuto di ogni capitolo. La tesi inizia con una introduzione al presente lavoro. Nel capitolo 1 vengono introdotte le aste combinatorie, partendo dalla loro de nizione e descrizione(fasi dell'asta), alla loro classi cazione rispetto vari criteri, agli svantaggi e vantaggi rispetto alle aste normali, evidenziati nella letteratura esistente. Nel capitolo 2 sono descritte, partendo dalla letteratura, le aste com- binatorie utilizzate per procurare servizi (contratti) di trasporto nel caso full-truckload e forniti esempi di aste. Inoltre, vengono descritti i prob- lemi presenti in un asta combinatoria: il problema di generazione e val- utazione delle o erte (Bid Generation Problem, BGP) ed il problema di determinazione del vincitore (Winner Determination Problem, WDP), ed evidenziata la loro di colt a di soluzione (problemi NP-hard). Il capitolo 3 e dedicato al BGP, oggetto di studio di questa tesi. Dopo aver presentato lo stato dell'arte relativo al BGP, viene riportato un modello originale proposto per il BGP, evidenziando le novit a di tale modello e le complicazioni rispetto ai modelli esistenti nella letteratura. Vengono illustrate le di colt a di risoluzione di tale modello (dovute al numero esponenziale dei bundle, quindi dei vincoli e delle variabili, ecc...). Con l'obiettivo di superare a priori il problema della dimensione, quindi per diminuire la cardinalit a dell'insieme dei bundle possibili, sono state sviluppate delle procedure di preprocessamento dell'insieme delle rotte messe all'asta, tenendo conto sia dalla posizione dei camion che dalle nestre temporali di consegna dei carichi. Inoltre, sono state studiate e quanti cate le sinergie tra le rotte messe all'asta e quelle dell'attuale rete di trasporto del carrier (in due modi, e diversamente di come fatto in [2], [6], [54], [58]) ed incluse nella distribuzione della variabile aleatoria con- siderata (il clearing price del bundle). Vengono presentati i chance con- straints ed e ettuata una discussione relativamente alla distribuzione ed all'indipendenza delle variabili aleatorie rappresentando i clearing price dei load componenti il bundle. Diverse versioni di tale modello sono state prodotte a partire dalla formulazione iniziale, includendo la sinergia nella funzione obiettivo e/o nei vincoli, considerando nestre temporali di prelievo dei carichi, con- siderando vincoli di copertura delle rotte (come in [51], [53]), riformu- lando il modello tale che la rete spazio-tempo sia esplicita. Nel capitolo 4 viene proposto un approccio risolutivo di tipo euristico in quanto l'elevata dimensione (esponenziale) del problema ha permesso la soluzione esatta soltanto no ad una certa cardinalit a del insieme di rotte messe all'asta. Per dimensioni superiori sono state costruite delle euristiche che permettono una risoluzione sequenziale del problema. Una prima categoria di euristiche, partendo dal bundle di load di cardinalit a massima, cio e uguale all'insieme dei load messi all'asta, val- uta il pro tto decrementale (bene cio marginale) di ogni bundle ottenuto togliendo un load del bundle corrente alla volta, sceglie il load in cor- rispondenza di cui si e ricavato il migliore pro tto decrementale, ag- giorna il bundle corrente (eliminandone il load selezionato) e cos i via. Il procedimento e ripetuto no a quando il bundle corrente non risulta vuoto. Una variante di questa euristica e ottenuta partendo dal bundle di cardinalit a minima (vuoto, per esempio) e valutando il pro tto incre- mentale (all'aggiunta di un load al bundle corrente). La complessit a sar a soltanto dell'ordine di n2 (con n la cardinalit a dell'insieme di load messe all'asta). Una seconda categoria di euristiche considera come insieme dei bun- dle iniziali un certo insieme di bundle scelti secondo vari criteri (ran- dom, quelli con maggiore sinergia e/o compressa in qualche intervallo, di cardinalit a compressa in qualche intervallo, etc...). Risolve il problema per ogni bundle di tale insieme e seleziona tra essi il bundle di massimo valore della funzione obiettivo. Il capitolo 5 e relativo alla fase sperimentale condotta al ne della val- utazione della correttezza (validazione) del modello e delle prestazioni dei metodi risolutivi proposti in termini di e cienza ed e cacia. Come am- bienti di sviluppo (implementazione e soluzione) del modello sono stati usati GAMS, Microsoft Visual C++, ILOG CPLEX ed ILOG CON- CERT. Dal momento che per le aste combinatorie non sono in generale disponibili pubblicamente i dati reali (come spesso viene segnalato in letteratura, per esempio in [2]), si e costruito anche un generatore di problemi test, implementato in C. A causa del numero esponenziale di vincoli e variabili (relativi ai bundle di load messi all'asta), il modello proposto e stato risolto in maniera esatta soltanto no ad una certa di- mensione (20 rotte messe all'asta). Per dimensioni superiori sono state utilizzate le euristiche proposte per una risoluzione sequenziale del prob- lema. Vengono e ettuati dei confronti tra le varie euristiche proposte implementate, fornendo il gap con la soluzione ottima ed i relativi tempi computazionali. I risultati preliminari ottenuti sono molto incoraggianti e mostrano l'e cacia e l'e cienza delle strategie risolutive sviluppate e l'utilit a del modello proposto in termini di strumento in grado di supportare i carrier nelle decisioni integrate di routing della otta e di bidding pro ttevoli. La tesi chiude con la parte relativa alle conclusioni del lavoro ed alla ricerca futura. Il lavoro di tesi rappresenta un valido studio ed una scrupolosa anal- isi delle problematiche riguardanti il BGP in un asta combinatoria nei trasporti di tipo full truckload. Il maggior contributo scienti co e stato quello di aver presentato e de nito un modello matematico per la valu- tazione e la generazione di o erte (integrando anche il routing della otta dei carrier) e delle procedure euristiche in grado di risolverlo su istanze pi u complesse. 9

The simulation of sewage systems and wastewater treatment plants is a strategic aspect for assessing the effect of new dwellings on the existing water facilities. This constitutes a quite common problem, since usually new edification areas are planned without looking at the effect that new scenarios will cause on the existent infrastructures. In this Thesis integration of water pollution and land use change models is presented and applied to a case study. The water pollution is meant as the complex relationship between proposed housing development and wastewater pollution incident control. The aim of these models is about the impact of new edification areas on the existent watercourse. This Thesis introduces an integrated framework made by a land use change model, a sewage system simulator and a wastewater treatment plant simulator. This is a complex system since each element is characterized by different dynamics. The land use change model simulates the expansion of an urban area according to planners’ guidelines; the sewage system simulator investigates the response of the drainage system to the expansion as well as its flexibility. The wastewater treatment plant is simulated in order to assess the impact of the new inflowing discharges on the existing plant. This Thesis describes the motivation, the rational and implementation details of a modeling framework namely Stochastic System Dynamics Integrative Model (SSDIM), which is an effort to bridge the gap of integrated models for decision making in urban planning. By combining automatic decision support tools with an integrated framework that brings together land use change and wastewater network infrastructure, it enables the analysis of the effect of alternative long-term urbanisation plans on the quality of the surrounding environment, measured through water indicator. The functionality of the SSDIM was demonstrated through a semi-hypothetical case study, in which three planning scenarios were evaluated for a new housing area against the quality of the wastewater drained by a sewer system and eventually treated by a wastewater treatment plant. On the one hand, the study highlighted the flexibility in representing planning scenarios and settingup the sewer networks in the framework and demonstrated that the framework, as a conceptual and quantitative tool, can easily accommodate for the complexity involved in a real-world case study. On the other hand, the results emphasised that the framework was able to capture the evolving ABSTRACT 10 impact of urban planning over a long term period, which play an important role in understanding the existing system and environmental capacities, and thus SSDIM provides a valuable decision support aid in the urban planning process. In the first part of this Thesis, the setting and motivation for the framework proposed and an extensive review of the studies available from literature are discussed as well as the legal background related to the problem at stake The second part of the Thesis presents the elements of the models implemented: in particular, both the conceptual representation and the implementation details are discussed in depth. Finally in the last part of the Thesis, an application of the developed framework to a real world environmental problem and the results of the application of the framework to a case study is described. The case study represents a sewage network of a town located in south west of Scotland and its wastewater treatment plant, where some urban development scenarios are assumed

Tesi di Dottorato

Browse

Filters

Settings

Sort By

Results per page

Search Results