- Docente: Paolo Toth
- Crediti formativi: 6
- SSD: MAT/09
- Lingua di insegnamento: Italiano
- Moduli: Paolo Toth (Modulo 1) Silvano Martello (Modulo 2)
- Modalità didattica: Convenzionale - Lezioni in presenza (Modulo 1) Convenzionale - Lezioni in presenza (Modulo 2)
- Campus: Bologna
- Corso: Laurea Specialistica in Ingegneria informatica (cod. 0234)
Conoscenze e abilità da conseguire
Conoscenza delle tecniche per la definizione di algoritmi euristici in grado di determinare, in tempi di calcolo limitati, soluzioni utilizzabili in pratica per problemi reali di ottimizzazione delle risorse.
Capacità di: definire algoritmi euristici efficaci per la soluzione di problemi reali di ottimizzazione delle risorse.
Contenuti
Il modulo si propone di illustrare le tecniche più efficienti per la soluzione dei problemi decisionali complessi che si presentano nella ottimizzazione delle risorse, sia in ambito industriale che nei servizi. Particolare attenzione viene dedicata agli aspetti algoritmici e di implementazione. Vengono considerate alcune applicazioni reali delle tecniche proposte.
Il modulo sviluppa i seguenti argomenti: 1. Algoritmi euristici per problemi complessi di ottimizzazione: Algoritmi costruttivi ad una o più fasi. Algoritmi basati su tecniche di ottimizzazione. Algoritmi basati sul rilassamento Lagrangiano. Procedure di ricerca locale. 2. Algoritmi metaeuristici: 'simulated annealing', 'tabu search', algoritmi genetici, algoritmi ibridi. 3. Algoritmi per i problemi del circuito hamiltoniano a costo minimo (Travelling Salesman Problem), dell'istradamento di veicoli (Vehicle Routing Problem), della "copertura" a costo minimo (Set Covering) e della "colorazione" dei vertici di un grafo (Vertex Coloring Problem). 4. Analisi sperimentale delle prestazione degli algoritmi descritti. 5. Applicazioni: Problemi di instardamento ed i caricamento. Problemi di distribuzione di prodotti da un deposito ad un insieme di clienti. Problemi di trasporto di persone con ridotta capacità motoria. Problemi di determinazione dei turni del personale in aziende di trasporto pubblico.
Propedeuticità consigliate: corsi di base di Informatica e di Ricerca Operativa.
Testi/Bibliografia
Testi di consultazione:
S. Martello, P. Toth, Knapsack Problems: Algortihms and Computer
Implementations, J. Wiley, 1990.
R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows: Theory,
Algorithms, and Applications, Prentice Hall, 1993.
E.Aarts, J.K. Lenstra (a cura di), Local Search in Combinatorial
Optimization, J.Wiley, 1997.
G. Gutin, A. Punnen (a cura di), The Traveling Salesman Problem and
Its Variations, Kluwer, 2002.
P.Toth, D. Vigo (a cura di), The Vehicle Routing Problem, SIAM
Monographs on Discrete Mathematics and Applications, 2002.
C. Barnhart, G. Laporte (a cura di), Transportation, Handbooks in
Operations Research and Management Science, North Holland,
2007.
Metodi didattici
Il corso è tenuto in Inglese utilizzando un approccio di tipo "e-learning".
Modalità di verifica e valutazione dell'apprendimento
Prova scritta finale relativa alla definizione di algoritmi euristici.
Due esercizi facoltativi verranno proposti sulla AlmaChannel Platform. Il primo durante il corso, il secondo alla fine del corso. Tali esercizi possono sostituire la prova scritta finale.
Nella valutazione degli studenti si terrà conto della loro partecipazione attiva alle attività di "forum".
Strumenti a supporto della didattica
Il materiale didattico, relativo a tutte le lezioni del corso, sarà disponibile sulla AlmaChannel Platform.
L'accesso è riservato agli studenti che si iscrivono al corso.
Orario di ricevimento
Consulta il sito web di Paolo Toth
Consulta il sito web di Silvano Martello