ETD

Archivio digitale delle tesi discusse presso l'Università di Pisa

Tesi etd-02052013-150026


Tipo di tesi
Tesi di laurea specialistica
Autore
BERTOLINI, ALESSANDRO
URN
etd-02052013-150026
Titolo
"Algoritmi per l'ottimizzazione simultanea di orari e turni nel trasporto pubblico urbano"
Dipartimento
INFORMATICA
Corso di studi
INFORMATICA
Relatori
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
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'impiego dei veicoli in servizio (problema dello Scheduling dei veicoli), obiettivi chiaramente in contrasto fra loro.
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.
Il lavoro svolto non si è limitato all'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'euristica ad hoc volta ad ottimizzare l'efficienza del codice ed uno studio approfondito dei parametri del programma nel tentativo di migliorare tempi d'esecuzione e qualità delle soluzioni.
File