Algoritmos de Ruteo en Superficies de Embaldosados Rectilíneos

Fidel González Gutiérrez

Buscar

dc.rights.license	http://creativecommons.org/licenses/by-nc-nd/4.0	es_ES
dc.contributor	Arturo González Gutiérrez	es_ES
dc.creator	Fidel González Gutiérrez	es_ES
dc.date	2023-01-31
dc.date.accessioned	2023-05-19T19:24:40Z
dc.date.available	2023-05-19T19:24:40Z
dc.date.issued	2023-01-31
dc.identifier.uri	https://ri-ng.uaq.mx/handle/123456789/8245
dc.description	Se estudia el problema de ruteo en superficies de embaldosados rectilíneos. Formalmente el problema consiste en, dado un rectángulo R dividido en rectángulos de tamaño 1 x 2 (dominós), encontrar un conjunto de aristas sobre la periferia de R y dominós, interconectadas y libres de ciclos (árbol o corredor) que conecten todos los dominós desde un punto de acceso sobre la periferia de R, y cuya longitud total sea la mínima. Así planteado, es un subproblema del problema del Corredor de Longitud Mínima (MLC), el cual es NP-completo, y en consecuencia no existe algoritmo eficiente que produzca soluciones óptimas. Por lo que el objetivo es diseñar algoritmos de ruteo en superficies de embaldosados rectilíneos utilizando una metodología basada en la técnica de diseño greedy que produzcan un corredor de longitud total mínima. Para ello, se diseñan familias de instancias de embaldosados para el análisis experimental de los algoritmos de ruteo. Se presentan varias técnicas para la enumeración de embaldosados en general, a la vez que se utiliza una metodología de acuerdo a la técnica de backtracking para la generación de familias de embaldosados con dóminos no isomorfos y libres de corte de tamaño 6 x 5, 6 x 7, 6 x 8, 6 x 9, 6 x 10 y 7 x 8. Sobre dichas familias, se lleva a cabo el análisis experimental de cuatro heurísticas, midiendo su rendimiento y la solución, bajo los criterios de conectar primero: dominós más cercanos, dominós más alejados, vértices compartidos (mejorado), vértices internos (usando reducción). Las heurísticas se implementan en ©Mathematica versión 11.3.0.0 en una computadora MacBook Pro con un CPU de 2.6 GHz Intel Core i7 con 6 núcleos y 16 GB de memoria RAM. Como resultado del análisis experimental se establece que existen cotas inferior y superior para la longitud total del corredor, entre las cuales se encuentra la solución óptima. Asimismo, se establece que la heurística basada en el criterio de conectar todos los vértices internos, de acuerdo a los algoritmos de Kruskal y Prim, y enseguida llevar a cabo un proceso de poda para eliminar conexiones redundantes de dominós, produce los corredores de menor longitud total dentro de las cotas inferior y superior en el menor tiempo de ejecución. Los resultados se encuentran publicados en las revistas indexadas Revista de la Ingeniería Industrial y Visum Mundi	es_ES
dc.format	Adobe PDF	es_ES
dc.language.iso	spa	es_ES
dc.publisher	Informática	es_ES
dc.relation.requires	Si	es_ES
dc.rights	Acceso Abierto	es_ES
dc.subject	Ingeniería y Tecnología	es_ES
dc.subject	Ciencias Tecnológicas	es_ES
dc.subject	Ciencia de los Ordenadores	es_ES
dc.title	Algoritmos de Ruteo en Superficies de Embaldosados Rectilíneos	es_ES
dc.type	Tesis de doctorado	es_ES
dc.creator.tid	curp	es_ES
dc.contributor.tid	curp	es_ES
dc.creator.identificador	GOGF670818HMNNTD09	es_ES
dc.contributor.identificador	GOGA690910HNLNTR09	es_ES
dc.contributor.role	Director	es_ES
dc.degree.name	Doctorado en Ciencias de la Computación	es_ES
dc.degree.department	Facultad de Informática	es_ES
dc.degree.level	Doctorado	es_ES