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

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.