ETD system

Electronic theses and dissertations repository

 

Tesi etd-02052013-150026


Thesis type
Tesi di laurea specialistica
Author
BERTOLINI, ALESSANDRO
URN
etd-02052013-150026
Title
"Algoritmi per l'ottimizzazione simultanea di orari e turni nel trasporto pubblico urbano"
Struttura
INFORMATICA
Corso di studi
INFORMATICA
Commissione
relatore Prof. Frangioni, Antonio
controrelatore Prof. Pagli, Linda
Parole chiave
  • trasporto pubblico urbano
  • ottimizzazione
  • ricerca operativa
  • tecniche lagrangiane
  • timetabling
  • scheduling veicoli
Data inizio appello
22/02/2013;
Consultabilità
completa
Riassunto analitico
Argomento della Tesi è la realizzazione di un programma modulare e parametrizzato, scritto in C++, volto ad implementare un modello integrato che descrive scenari complessi di Trasporto Pubblico Urbano con lo scopo di trovare soluzioni che siano simultaneamente buoni orari dal punto di vista del soddisfacimento della clientela (problema del Timetabling) e ottimizzino l&#39;impiego dei veicoli in servizio (problema dello Scheduling dei veicoli), obiettivi chiaramente in contrasto fra loro.<br>Per cercare soluzioni sono stati utilizzati e integrati tra loro algoritmi della Ricerca Operativa quali il Simplesso Primale per la risoluzione di problemi di Flusso di Costo Minimo per il problema dello Scheduling dei veicoli, algoritmi di risoluzione di Cammini Minimi su grafi orientati aciclici, quindi sono state utilizzate tecniche di rilassamento Lagrangiano per rilassare i vincoli che legano tra loro i due sotto-problemi.<br>Il lavoro svolto non si è limitato all&#39;implementazione del modello e degli algoritmi suddetti, ma ha previsto uno studio sulle soluzioni trovate intento a scoprire le effettive potenzialità del modello al di fuori del contesto degli algoritmi implementati, quindi la realizzazione di un&#39;euristica ad hoc volta ad ottimizzare l&#39;efficienza del codice ed uno studio approfondito dei parametri del programma nel tentativo di migliorare tempi d&#39;esecuzione e qualità delle soluzioni.<br>
File