Desarrollo de la Solución del Problema del Viajante de Comercio con un método de construcción de tour con dyadic tiling

Abstract

[ES] El tfg consiste en: 1. Estudiar la literatura relacionada con el tema. El estudio de la literatura debería centrarse en enfoques a la solución del Problema del Viajante de Comercio, tilings y bisección. 2. Implementar la idea básica de la solución del Problema del Viajante de Comercio con dyadic tilings en Matlab. 3. Mejorar el código en al menos un aspecto comparado con el código original (e.g. bisección eficiente para agrupar los puntos en el tiling. 4. Resolver una cantidad inmensa de casos aleatorios del Problema del Viajante de Comercio para obtener estadísticas. 5. Evaluar la solución estadística, comprobar si existe una correlación entre la calidad de la solución y las propiedades del tiling. 6. Resumir el trabajo en el formato de documento requerido de la tesis de grado.

[EN] Study the literature of the topic. The literature survey should focus on TSP solution approaches, tilings and bisectioning. 2. Implement the basic idea of the TSP solution with dyadic tilings in Matlab environment. 3. Improve the code in at least one aspect compared to the original code (e.g. efficient bisectioning to group the points in the tiling). 4. Solve a huge amount of random TSP instances to obtain statistics. 5. Evaluate the solution statistics, test whether there is a correlation between solution quality and the properties of the tiling. 6. Summarize your work in the required document format of the BSc Thesis.