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.
An Integer Linear Programming Heuristic for the Travelling Salesman Problem
Marchezzolo, Paolo
2013/2014
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.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
Tesi_Marchezzolo.pdf
accesso aperto
Dimensione
4.1 MB
Formato
Adobe PDF
|
4.1 MB | Adobe PDF | Visualizza/Apri |
The text of this website © Università degli studi di Padova. Full Text are published under a non-exclusive license. Metadata are under a CC0 License
Utilizza questo identificativo per citare o creare un link a questo documento:
https://hdl.handle.net/20.500.12608/16072