TSP y Orthogonal Arrays: Una posible conexión

Abstract

El propósito de este trabajo es estudiar, programar y analizar métodos para la creación de los orthogonal arrays (matrices ortogonales), así como exponer una posible relación existente entre los métodos de obtención de dichos elementos con aquellos destinados a la resolución del Travelling Salesman Problem (Problema del Viajante de Comercio). No obstante, se indagará en muchas de las propiedades que guardan dichos elementos, comprendiendo su naturaleza, la importancia que tienen en diversos ámbitos de trabajo y el origen de los mismos. Asimismo, se expondrán distintos algoritmos que buscarán poder hallar orthogonal arrays de forma eficiente y novedosa, donde se estudiará la capacidad de efectividad de cada uno de ellos y las limitaciones que presentan. Este trabajo tiene dos vertientes claramente diferencias; en una primera instancia, se caracteriza por ser un apoyo teórico de ambos temas mencionados anteriormente (OA y TSP), exponiendo nociones necesarias y fundamentales para poder comprender lo que resta de documento; por otro lado, se incluye la parte práctica, donde se formularán métodos de resolución de los orthogonal arrays, justificando los diversos procedimientos, extrayendo conclusiones de cada uno de ellos y generando comparaciones con el fin de determinar en qué situaciones es óptimo optar por uno o por otro. Todos los resultados han sido programados y obtenidos mediante el lenguaje de programación Phyton, suponiendo un apoyo indiscutible para la justificación de las conclusiones expuestas en las últimas páginas de este documento.

The purpose of this work is to study, program, and analyze methods for the creation of orthogonal arrays, as well as to explore a possible relationship between the methods for obtaining these elements and those aimed at solving the Travelling Salesman Problem (TSP). Nevertheless many of the properties of these elements will be investigated, including understanding their nature, their importance in various fields of work, and their origin. Additionally, various algorithms will be presented that aim to find orthogonal arrays efficiently and innovatively, with an examination of the effectiveness and limitations of each algorithm. This work has two clearly differentiated aspects. Initially, it serves as a theoretical support for both topics mentioned above (OA and TSP), presenting necessary and fundamental notions to understand the rest of the document. Subsequently, it includes the practical part, formulating methods for solving orthogonal arrays, justifying the various procedures, drawing conclusions from each, and making comparisons to determine in which situations it is optimal to choose one method over another. All results have been programmed and obtained using the Python programming language, providing undeniable support for the justification of the conclusions presented in the final pages of this document.