Metodi di Programmazione Dinamica per il Traveling Salesman Problem con vincoli di precedenza

Fontana, Eleonora (2019) Metodi di Programmazione Dinamica per il Traveling Salesman Problem con vincoli di precedenza. [Laurea magistrale], Università di Bologna, Corso di Studio in Matematica [LM-DM270]
Documenti full-text disponibili:
[img] Documento PDF (Thesis)
Disponibile con Licenza: Salvo eventuali più ampie autorizzazioni dell'autore, la tesi può essere liberamente consultata e può essere effettuato il salvataggio e la stampa di una copia per fini strettamente personali di studio, di ricerca e di insegnamento, con espresso divieto di qualunque utilizzo direttamente o indirettamente commerciale. Ogni altro diritto sul materiale è riservato

Download (895kB)

Abstract

Il Traveling Salesman Problem (TSP) è un problema di ottimizzazione combinatoria che si può formulare nel seguente modo. Siano date n città e i costi per spostarsi da una città all'altra. Il salesman partendo da una delle città, deve compiere un tour in cui visita una ed una sola volta ciascuna città ritornando alla città di partenza. L'obiettivo è minimizzare il costo del tour. Aggiungendo al TSP i cosiddetti vincoli di precedenza, si parla di Traveling Salesman Problem with Precedence Constrains (TSPP), noto in letteratura anche come Sequential Ordering Problem (SOP). Questi vincoli impongono che determinate città possano essere visitate solamente dopo averne visitate delle altre, specificate nei dati del problema. In questa tesi vengono presentati nuovi metodi di risoluzione del TSPP basati sulla Programmazione Dinamica (DP) e sul rilassamento dello spazio degli stati. Tali metodi consentono di calcolare nuovi lower bound in pochi secondi di tempo calcolo. I risultati di calcolo ottenuti su un insieme di problemi test mostrano l’efficienza dei nuovi metodi proposti. Infatti i lower bound proposti dominano o risultano competitivi con i migliori metodi proposti in letteratura, i quali richiedono tempi di calcolo di diversi ordini di grandezza superiori a quelli richiesti dai metodi proposti.

Abstract
Tipologia del documento
Tesi di laurea (Laurea magistrale)
Autore della tesi
Fontana, Eleonora
Relatore della tesi
Scuola
Corso di studio
Indirizzo
Curriculum A: Generale e applicativo
Ordinamento Cds
DM270
Parole chiave
programmazione a numeri interi programmazione dinamica rilassamento dello spazio degli stati metodi esatti / euristici
Data di discussione della Tesi
29 Marzo 2019
URI

Altri metadati

Statistica sui download

Gestione del documento: Visualizza il documento

^