Actualmente, aunque existen procedimientos específicos para resolver de forma óptima algunos problemas concretos de optimización combinatoria, la mayoría se deben solucionar con técnicas generales de exploración del espacio de soluciones, y más concretamente mediante procedimientos de exploración enumerativos en árboles y grafos de búsqueda.Se analizan los procedimientos de este tipo expuestos en la literatura, tanto en el área de la investigación operativa como en el de la inteligencia artificial, se realiza un estudio crítico que muestra las controvertidas y confusas relaciones que existen entre estas estrategias de resolución, para proponer, en último término, la necesidad de una formalización general que englobe a todas ellas.Concretamente, los objetivos y aportaciones de esta tesis son los siguientes:- Recopilación, análisis y crítica de diferentes procedimientos, estrategias de resolución y formulaciones generales de dichas técnicas expuestas en la literatura.- Propuesta y formalización de branch and win: un metalgoritmo de exploración de grafos que engloba a los diversos procedimientos de búsqueda (branch and bound, programación dinámica, A*, etc.), y que, además, incorpora la posibilidad de utilizar las nuevas herramientas que se están desarrollando en el campo de la inteligencia artificial (técnicas de consistencia y de propagación local de restricciones).- Diseño y proposición de nuevos procedimientos híbridos a partir de branch and win, resultado de la combinación de los ya existentes y de la incorporación de diversas ideas de carácter general.Las hipótesis de trabajo adoptadas presentan las siguientes implicaciones. Por un lado no se resuelven problemas combinatorios con datos aleatorios, ni aquéllos que deben resolverse dentro de un entorno dinámico. Y, por otro, tampoco se formalizan los procedimientos bidireccionales ni los basados en representaciones AND/OR (cabe destacar, sin embargo, que en este caso no se restringe de ninguna manera los problemas combinatorios que es posible resolver).La originalidad de la tesis reside en el diseño de branch and win, cuyas características principales son: es general, integrador, realista (incorpora aspectos importantes en la resolución de problemas industriales), utiliza terminología clara, dinámico (en función de la evolución de la arborescencia y/o del entorno) y derivador de otros procedimientos.Se ha realizado una implementación informática del metalgoritmo propuesto para dos conocidos problemas de optimización combinatoria (flow shop y cubrimiento), que ha permitido validar la generalidad de branch and win, así como obtener una serie de recomendaciones sobre la conveniencia de probar la adecuación de un conjunto de estrategias: invertir tiempo en la búsqueda de una solución inicial de calidad, utilizar funciones de evaluación y selección dinámicas, utilizar "en cascada" diversos procedimientos del mismo tipo, uso de procedimientos de reducción y de resolución heurísticos en los vértices intermedios de la arborescencia, incorporación de procedimientos de exploración de entornos al obtener una nueva solución factible, etc.En cuanto a las posibles extensiones y derivaciones de esta tesis, existe un gran campo de investigación abierto en la dirección de probar, para diferentes problemas de optimización combinatoria, nuevos procedimientos híbridos, que se pueden obtener al combinar y utilizar de diversas maneras los elementos que forman branch and win. Esta investigación se concretaría en ensayar el impacto de los diferentes elementos que forman el metalgoritmo propuesto, con el objetivo de encontrar reglas generales para la resolución efectiva de diferentes problemas de optimización combinatoria o de familias de problemas de características similares.
| Identifer | oai:union.ndltd.org:TDX_UPC/oai:www.tdx.cat:10803/6781 |
| Date | 23 October 1999 |
| Creators | Pastor, Rafael |
| Contributors | Corominas Subias, Albert, Universitat Politècnica de Catalunya. Departament d'Organització d'Empreses |
| Publisher | Universitat Politècnica de Catalunya |
| Source Sets | Universitat Politècnica de Catalunya |
| Language | Spanish |
| Detected Language | Spanish |
| Type | info:eu-repo/semantics/doctoralThesis, info:eu-repo/semantics/publishedVersion |
| Format | application/pdf |
| Source | TDX (Tesis Doctorals en Xarxa) |
| Rights | info:eu-repo/semantics/openAccess, ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs. |
Page generated in 0.0014 seconds