ETD

Digital archive of theses discussed at the University of Pisa

 

Thesis etd-02052013-150026


Thesis type
Tesi di laurea specialistica
Author
BERTOLINI, ALESSANDRO
URN
etd-02052013-150026
Thesis title
"Algoritmi per l'ottimizzazione simultanea di orari e turni nel trasporto pubblico urbano"
Department
INFORMATICA
Course of study
INFORMATICA
Supervisors
relatore Prof. Frangioni, Antonio
controrelatore Prof. Pagli, Linda
Keywords
  • trasporto pubblico urbano
  • ottimizzazione
  • ricerca operativa
  • tecniche lagrangiane
  • timetabling
  • scheduling veicoli
Graduation session start date
22/02/2013
Availability
Full
Summary
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