Vai ai contenuti. | Spostati sulla navigazione | Spostati sulla ricerca | Vai al menu | Contatti | Accessibilità

logo del sistema bibliotecario dell'ateneo di padova

Marchezzolo, Paolo (2013) An Integer Linear Programming Heuristic for the Travelling Salesman Problem. [Magistrali biennali]

Full text disponibile come:

[img]
Preview
PDF
4Mb

Abstract

The work develops a new heuristic for the Travelling Salesman Problem, that aims at improving an existing solution for a given TSP instance. We look for improvements in the neighborhood of the solution on input, solving iteratively an ILP relaxation of the TSP model modified to minimize a distance function with the input, and a 1-tree subproblem that heuristically tries to enforce the relaxated constraint. The algorithm was coded in C and successfully tested over several instances.

Item Type:Magistrali biennali
Uncontrolled Keywords:TSP, Heuristic, ILP, CPLEX
Subjects:Area 01 - Scienze matematiche e informatiche > MAT/09 Ricerca operativa
Codice ID:42724
Relatore:Fischetti, Matteo
Data della tesi:21 March 2013
Biblioteca:Polo di Ingegneria > Biblioteca Interdipartimentale di Ingegneria dell'Informazione e Ingegneria Elettrica
Tipo di fruizione per il documento:on-line per i full-text
Tesi sperimentale (Si) o compilativa (No)?:Yes

Solo per lo Staff dell Archivio: Modifica questo record