Buscar


Mostrar el registro sencillo del ítem

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


Ficheros en el ítem

Thumbnail
Nombre: RI007397.pdf
Tamaño: 15.24Mb
Formato: PDF
Ver/

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem