Optimización del problema del viajante: métodos de Branch and Bound y Lin Kernighan

Abstract

El problema del Viajante (TSP) es formulado como un problema de programación lineal entera que trata de encontrar un ciclo hamiltoniano que minimice los costes de las aristas utilizadas sobre un grafo completo ponderado G = (V,A). Al tratarse de un problema NP-completo tiene diversas técnicas de resolución tanto exactas como heurísticas. Se planteará el método exacto de Branch and Bound con la regla de ramificación Little y el método heurístico de mejora iterativa k−opt Lin Kernighan, además de exponer peque˜nos problemas ilustrativos de ejemplo para ver el procedimiento de los métodos. Finalmente se implementarán en Matlab los algoritmos mencionados para la resolución de dos problemas reales comparando las soluciones y tiempos de ejecución.

The Traveling Salesman Problem (TSP) is formulated as an integer linear programming problem what tries to find a Hamiltonian cycle that minimises the costs of the edges used on a weighted graph G = (V,A). As it is an NP-complete problem, it has several exact and heuristic solution techniques. The Branch and Bound exact method with the Little branching rule and the Lin Kernighan heuristic iterative improvement method will be presented, as well as small illustrative example problems to show the procedure of the methods. Finally, the aforementioned algorithms will be implemented in Matlab to solve two real problems, comparing the solutions and execution times.