NAGIOS: RODERIC FUNCIONANDO

Algunos problemas de rutas por arcos

Repositori DSpace/Manakin

IMPORTANT: Aquest repositori està en una versió antiga des del 3/12/2023. La nova instal.lació está en https://roderic.uv.es/

Algunos problemas de rutas por arcos

Mostra el registre parcial de l'element

dc.contributor.advisor Corberán Salvador, Ángel
dc.contributor.advisor Plana Andani, Isaac
dc.contributor.advisor Sanchis Llopis, José María
dc.contributor.author Ávila Valverde, Thais
dc.contributor.other Departament d'Estadística i Investigació Operativa es_ES
dc.date.accessioned 2014-02-10T10:09:31Z
dc.date.available 2014-02-11T07:10:03Z
dc.date.issued 2014
dc.date.submitted 06-02-2014 es_ES
dc.identifier.uri http://hdl.handle.net/10550/32824
dc.description.abstract En esta tesis se estudian tres problemas de rutas por arcos muy importantes tanto a nivel práctico como teórico. Se tratan del General de Rutas por Arcos en un grafo dirigido (Directed General Routing Problem, DGRP), su caso particular, el problema de la Grúa (Stacker Crane Problem, SCP) y el problema del Cartero Rural Generalizado en un grafo dirigido (Generalized Directed Rural Postman Problem, GDRPP). El primer problema estudiado es problema de la Grúa el cual se define en un grafo mixto G=(V,E,A), donde cada arista o arco, (i,j), tiene un coste asociado cij > 0, y tiene como objetivo hallar una ruta de coste mínimo que recorra al menos una vez cada arco del grafo. El problema General de Rutas por Arcos en un grafo dirigido se define en un grafo dirigido G=(V,A) con costes no negativos asociados a los arcos donde, dados un subconjunto de arcos requeridos A_R y un subconjunto de vértices requeridos V_R, se trata de encontrar una ruta de mínimo coste que recorra todos los arcos requeridos y visite todos los vértices requeridos. Por último, el problema del Cartero Rural Generalizado en un grafo dirigido se define en un grafo dirigido G=(V,A) con costes no negativos asociados a los arcos en el que, dados unos conjuntos de arcos H_1,...,H_n, el objetivo es encontrar una ruta de coste mínimo que recorra al menos un arco de cada conjunto H_i. El estudio y resolución de estos problemas ha sido abordado en esta tesis desde el punto de vista de la Combinatoria Poliédrica, uno de los enfoques más útiles para la resolución de muchos problemas NP-difíciles de optimización combinatoria. Se presenta dentro de ella, un heurístico, basado en una búsqueda local iterada, para la resolución aproximada del SCP, un algoritmo de ramificación y corte para el DGRP y otro para el GDRPP. Resolviendo instancias del DGRP y del SCP que varían entre 100 y 3000 arcos requeridos y 500 y 5000 vértices. Así como instancias del GDRPP, donde los tamaños van desde 1000 a 1500 arcos, de 500 a 800 vértices y de 500 a 15000 clientes. Los resultados obtenidos en esta tesis doctoral han mejorado, a veces de forma sustancial, los presentados por otros autores para estos o similares problemas. . es_ES
dc.format.extent 234 p. es_ES
dc.language.iso es es_ES
dc.subject optimización es_ES
dc.subject matemáticas es_ES
dc.title Algunos problemas de rutas por arcos es_ES
dc.type doctoral thesis es_ES
dc.subject.unesco UNESCO::MATEMÁTICAS::Investigación operativa es_ES
dc.embargo.terms 0 days es_ES

Visualització       (1.876Mb)

Aquest element apareix en la col·lecció o col·leccions següent(s)

Mostra el registre parcial de l'element

Cerca a RODERIC

Cerca avançada

Visualitza

Estadístiques