{"id":114510,"date":"2018-03-11T10:42:31","date_gmt":"2018-03-11T10:42:31","guid":{"rendered":"https:\/\/www.deberes.net\/tesis\/sin-categoria\/the-capacitated-minimum-spanning-tree-problem\/"},"modified":"2018-03-11T10:42:31","modified_gmt":"2018-03-11T10:42:31","slug":"the-capacitated-minimum-spanning-tree-problem","status":"publish","type":"post","link":"https:\/\/www.deberes.net\/tesis\/investigacion-operativa\/the-capacitated-minimum-spanning-tree-problem\/","title":{"rendered":"The capacitated minimum spanning tree problem"},"content":{"rendered":"<h2>Tesis doctoral de <strong> H\u00e9ctor Efra\u00edn Ruiz Y Ruiz <\/strong><\/h2>\n<p>En esta tesis nos enfocamos en el problema del \u00e1rbol de expansi\u00f3n capacitado de coste m\u00ednimo (cmst, por sus siglas en ingl\u00e9s), que es una extensi\u00f3n del problema del \u00e1rbol de expansi\u00f3n de coste m\u00ednimo  (mst, por sus siglas en ingl\u00e9s). El cmst considera  un v\u00e9rtice ra\u00edz que funciona como servidor central y que env\u00eda y recibe bienes (informaci\u00f3n, objetos, etc)  a un conjunto de v\u00e9rtices llamados terminales.  Los bienes solo pueden fluir entre el servidor y las terminales a trav\u00e9s de enlaces cuya capacidad es limitada. Dichas restricciones sobre los enlaces dan relevancia al problema, ya que existen muchas aplicaciones en que las restricciones de capacidad son de vital importancia.  Dentro de las \u00e1reas de aplicaci\u00f3n del cmst m\u00e1s importantes se encuentran las relacionadas con el dise\u00f1o de redes de telecomunicaci\u00f3n,  el dise\u00f1o de rutas de veh\u00edculos y problemas de localizaci\u00f3n. Dentro del dise\u00f1o de redes de telecomunicaci\u00f3n, el cmst est\u00e1 presente cuando se considera un servidor central, cuya capacidad de transmisi\u00f3n y env\u00edo est\u00e1 limitada por las caracter\u00edsticas de los puertos del servidor o de las l\u00edneas de transmisi\u00f3n. Dentro del dise\u00f1o de rutas de veh\u00edculos el cmst resulta relevante debido a la influencia que pueden tener los \u00e1rboles en el proceso de construcci\u00f3n de soluciones.  Por el  simple de a\u00f1adir las restricciones de capacidad, el problema pasa de  resolverse de manera exacta en tiempo polinomial usando un algoritmo voraz, a un problema que es muy dif\u00edcil de resolver de manera exacta.    en el primer cap\u00edtulo se describe y define el problema, se introduce notaci\u00f3n y se presenta una revisi\u00f3n bibliogr\u00e1fica  de la literatura existente. En dicha revisi\u00f3n bibliogr\u00e1fica se incluyen formulaciones, m\u00e9todos exactos y los m\u00e9todos heur\u00edsticos utilizados m\u00e1s importantes. En el siguiente cap\u00edtulo se muestran dos formulaciones binarias existentes, as\u00ed como las desigualdades v\u00e1lidas m\u00e1s usadas para resolver el cmst. Para cada una de las formulaciones propuestas, se describe un algoritmo de planos de corte.  dos nuevas formulaciones para el cmst se presentan en el tercer cap\u00edtulo. Dichas formulaciones est\u00e1s basadas en la identificaci\u00f3n de un tipo de v\u00e9rtices especiales llamados subra\u00edces. Los subra\u00edces son aquellos v\u00e9rtices que se encuentran directamente conectados al ra\u00edz. Un forma de caracterizar las soluciones del cmst es a trav\u00e9s de identificar los nodos subra\u00edces y los nodos dependientes a ellos.  Ambas formulaciones utilizan variables  para identificar los subraices y variables adicionales para identificar los arcos que forman parte del \u00e1rbol.  Adicionalmente, las variables en la segunda formulaci\u00f3n ayudan a identificar la profundidad con respecto al ra\u00edz a la que se encuentran dichos arcos. Para cada formulaci\u00f3n se presentan desigualdades v\u00e1lidas y se plantean procedimientos para resolver el problema de su separaci\u00f3n.   en el cuarto cap\u00edtulo se presenta un algoritmo gen\u00e9tico llamado brkga para resolver el cmst. El brkga est\u00e1 basado en el uso de poblaciones generadas  por secuencias de n\u00fameros aleatorios, que posteriormente evolucionan. Diferentes decodificadores, un m\u00e9todo de b\u00fasqueda local, espacios de b\u00fasqueda y estrategias de exploraci\u00f3n son presentados y analizados. El cap\u00edtulo termina presentando un algoritmo final que permite la obtenci\u00f3n de cotas superiores para el cmst.<\/p>\n<p>&nbsp;<\/p>\n<h3>Datos acad\u00e9micos de la tesis doctoral \u00ab<strong>The capacitated minimum spanning tree problem<\/strong>\u00ab<\/h3>\n<ul>\n<li><strong>T\u00edtulo de la tesis:<\/strong>\u00a0 The capacitated minimum spanning tree problem <\/li>\n<li><strong>Autor:<\/strong>\u00a0 H\u00e9ctor Efra\u00edn Ruiz Y Ruiz <\/li>\n<li><strong>Universidad:<\/strong>\u00a0 Polit\u00e9cnica de catalunya<\/li>\n<li><strong>Fecha de lectura de la tesis:<\/strong>\u00a0 15\/07\/2013<\/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>Elena Fern\u00e1ndez Ar\u00e9izaga<\/li>\n<\/ul>\n<\/li>\n<li><strong>Tribunal<\/strong>\n<ul>\n<li>Presidente del tribunal: jaume Barcel\u00f3 bugeda <\/li>\n<li>Francisco Saldanha-da-gama (vocal)<\/li>\n<li>  (vocal)<\/li>\n<li>  (vocal)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Tesis doctoral de H\u00e9ctor Efra\u00edn Ruiz Y Ruiz En esta tesis nos enfocamos en el problema del \u00e1rbol de expansi\u00f3n [&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":[37303,6264,15596,11392],"tags":[39503,140225,226955,15707],"class_list":["post-114510","post","type-post","status-publish","format-standard","hentry","category-heuristica","category-investigacion-operativa","category-politecnica-de-catalunya","category-programacion-entera","tag-elena-fernandez-areizaga","tag-francisco-saldanha-da-gama","tag-hector-efrain-ruiz-y-ruiz","tag-jaume-barcelo-bugeda"],"_links":{"self":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/114510","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=114510"}],"version-history":[{"count":0,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/114510\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/media?parent=114510"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/categories?post=114510"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/tags?post=114510"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}