{"id":20940,"date":"2018-03-09T09:10:30","date_gmt":"2018-03-09T09:10:30","guid":{"rendered":"https:\/\/www.deberes.net\/tesis\/sin-categoria\/introduccion-de-penalizaciones-de-giro-en-los-problemas-de-rutas-por-arcos-sobre-grafos-mixtos\/"},"modified":"2018-03-09T09:10:30","modified_gmt":"2018-03-09T09:10:30","slug":"introduccion-de-penalizaciones-de-giro-en-los-problemas-de-rutas-por-arcos-sobre-grafos-mixtos","status":"publish","type":"post","link":"https:\/\/www.deberes.net\/tesis\/politecnica-de-valencia\/introduccion-de-penalizaciones-de-giro-en-los-problemas-de-rutas-por-arcos-sobre-grafos-mixtos\/","title":{"rendered":"Introducci\u00f3n de penalizaciones de giro en los problemas de rutas por arcos sobre grafos mixtos"},"content":{"rendered":"<h2>Tesis doctoral de <strong> Eulalia Mart\u00ednez Molada <\/strong><\/h2>\n<p>El principal objetivo de este proyecto es introducir la existencia de giros prohibidos y penalizados en el conocido como problema del cartero rural mixto, obteniendo as\u00ed el que hemos llamado problema del cartero rural mixto con giros penalizados (pcrm-gp), que pensamos modeliza de una forma m\u00e1s ajustada determinados problemas reales de rutas de veh\u00edculos de recogida o reparto dentro de una gran ciudad, y que b\u00e1sicamente consiste en:  \u00absea g un grafo mixto fuertemente conexo con costes no negativos asociados a sus enlaces y penalizaciones no negativas asociadas a sus giros, entendiendo que una penalizaci\u00f3n infinita implica que el giro es prohibido. Dado un subconjunto no vac\u00edo de enlaces requeridos de g, se trata de encontrar un tour que pase por cada enlace requerido al menos una vez, que no realice giros prohibidos, y que tenga coste total m\u00ednimo, entendiendo por coste del tour  la suma de los costes de los enlaces que atraviesa y de las penalizaciones de los giros que realiza\u00bb.  destacar en el estudio te\u00f3rico de este problema, su transformaci\u00f3n en tiempo polinomial al conocido problema del agente viajero asim\u00e9trico (pav asim\u00e9trico), lo que nos permite en una primera etapa, saber resolverlo tanto \u00f3ptima como heur\u00edsticamente.  a continuaci\u00f3n presentamos un algoritmo heur\u00edstico para el pcrm-gp que se aplica directamente sobre el grafo original, mostrando los resultados computacionales que obtenemos tanto con este heur\u00edstico como un algoritmo exacto y otro heur\u00edstico para el pav asim\u00e9trico. Concluimos que nuestro heur\u00edstico tiene un buen comportamiento, que lo hace muy competitivo sobre todo cuando el n\u00famero de aristas requeridas es grande.  por otra parte, con otra experiencia computacional y dado el algoritmo exacto para el pav asim\u00e9trico mencionado anteriormente, mostramos que la transformaci\u00f3n dada parece ser muy eficaz para la b\u00fasqueda de un doble recorrido fuerte en un grafo no dirigido (un tour que pasa por<\/p>\n<p>&nbsp;<\/p>\n<h3>Datos acad\u00e9micos de la tesis doctoral \u00ab<strong>Introducci\u00f3n de penalizaciones de giro en los problemas de rutas por arcos sobre grafos mixtos<\/strong>\u00ab<\/h3>\n<ul>\n<li><strong>T\u00edtulo de la tesis:<\/strong>\u00a0 Introducci\u00f3n de penalizaciones de giro en los problemas de rutas por arcos sobre grafos mixtos <\/li>\n<li><strong>Autor:<\/strong>\u00a0 Eulalia Mart\u00ednez Molada <\/li>\n<li><strong>Universidad:<\/strong>\u00a0 Polit\u00e9cnica de Valencia<\/li>\n<li><strong>Fecha de lectura de la tesis:<\/strong>\u00a0 19\/12\/2002<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h3>Direcci\u00f3n y tribunal<\/h3>\n<ul>\n<li><strong>Director de la tesis<\/strong>\n<ul>\n<li>David Soler Fern\u00e1ndez<\/li>\n<\/ul>\n<\/li>\n<li><strong>Tribunal<\/strong>\n<ul>\n<li>Presidente del tribunal: Antonio Herv\u00e1s Jorge <\/li>\n<li>Antonio Caselles moncho (vocal)<\/li>\n<li>francesc Ar\u00e1ndiga llaudes (vocal)<\/li>\n<li>M\u00aa lourdes Pe\u00f1alver herrero (vocal)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Tesis doctoral de Eulalia Mart\u00ednez Molada El principal objetivo de este proyecto es introducir la existencia de giros prohibidos y [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"footnotes":""},"categories":[16820],"tags":[63469,27581,27579,63468,43390,63470],"class_list":["post-20940","post","type-post","status-publish","format-standard","hentry","category-politecnica-de-valencia","tag-antonio-caselles-moncho","tag-antonio-hervas-jorge","tag-david-soler-fernandez","tag-eulalia-Martinez-molada","tag-francesc-arandiga-llaudes","tag-ma-lourdes-penalver-herrero"],"_links":{"self":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/20940","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/comments?post=20940"}],"version-history":[{"count":0,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/20940\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/media?parent=20940"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/categories?post=20940"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/tags?post=20940"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}