Applications of Biased Randomization and Simheuristic Algorithms to Arc Routing and Facility Location Problems

dc.contributor
Universitat Oberta de Catalunya. Internet Interdisciplinary Institut (IN3)
dc.contributor.author
González-Martin, Sergio
dc.date.accessioned
2015-09-04T11:51:38Z
dc.date.available
2015-09-04T11:51:38Z
dc.date.issued
2015-03-13
dc.identifier.uri
http://hdl.handle.net/10803/306605
dc.description.abstract
La majoria de metaheuristiques tenen una component aleatori, que normalment està basada en aleatorització uniforme -i.e., l'ús de la distribució de probabilitat uniforme per fer seleccions aleatòries. Per altra banda, el marc Multi-start biased Randomization of classical Heuristics with Adaptive local search proposa l'ús de aleatorització esbiaixada (no uniforme) per al disseny de algoritmes metaheuristics alternatius -i.e., l'ús de distribucions de probabilitat esbiaixades com la geomètrica o la triangular. En algunes situacions, aquesta aleatorització no uniforme ha obtingut una convergència més ràpida a la solució quasi òptima. El marc MIRHA també inclou un pas de cerca local per a millorar les solucions generades durant el procés iteratiu. A més, permet afegir passos de cerca adaptats al problema, com cache (memòria) o splitting (dividir i conquerir), que permeten la generació de solucions competitives (quasi òptimes). Els algoritmes dissenyats amb el marc MIRHA permeten obtenir solucions d'alta qualitat a problemes realistes en temps de computació raonables. A més, tendeixen a utilitzar un nombre reduït de paràmetres, el que els fa simples d'implementar i configurar en la majoria d'aplicacions pràctiques. El marc s'ha aplicat exitosament a diversos problemes d'enrutament i planificació. Un dels principals objectius d'aquesta tesi és desenvolupar nous algoritmes , basats en el marc mencionat, per solucionar problemes d'optimització combinatòria que poden ser d'interès a la industria de les telecomunicacions.
cat
dc.description.abstract
La mayoría de metaheurísticas tienen un componente aleatorio, que normalmente está basada en aleatorización uniforme -ie, el uso de la distribución de probabilidad uniforme para hacer selecciones aleatorias. Por otra parte, el marco Multi-start Biased Randomization of classical heurística with Adaptive local search propone el uso de aleatorización sesgada (no uniforme) para el diseño de algoritmos metaheurísticos alternativos -ie, el uso de distribuciones de probabilidad sesgadas como la geométrica o triangular. En algunas situaciones, esta aleatorización no uniforme ha obtenido una convergencia más rápida en la solución casi óptima. El marco MIRHA también incluye un paso de búsqueda local para mejorar las soluciones generadas durante el proceso iterativo. Además, permite añadir pasos de búsqueda adaptados al problema, como caché (memoria) o splitting (dividir y conquistar), que permiten la generación de soluciones competitivas (casi óptimas). Los algoritmos diseñados con el marco MIRHA permiten obtener soluciones de alta calidad a problemas realistas en tiempo de computación razonables. Además, tienden a utilizar un número reducido de parámetros, lo que los hace simples de implementar y configurar en la mayoría de aplicaciones prácticas. El marco se ha aplicado exitosamente a varios problemas de enrutamiento y planificación. Uno de los principales objetivos de esta tesis es desarrollar nuevos algoritmos, basados ¿¿en el marco mencionado, para solucionar problemas de optimización combinatoria que pueden ser de interés en la industria de las telecomunicaciones.
spa
dc.description.abstract
Most metaheuristics contain a randomness component, which is usually based on uniform randomization -i.e., the use of the Uniform probability distribution to make random choices. However, the Multi-start biased Randomization of classical Heuristics with Adaptive local search framework proposes the use of biased (non-uniform) randomization for the design of alternative metaheuristics -i.e., the use of skewed probability distributions such as the Geometric or Triangular ones. In some scenarios, this non-biased randomization has shown to provide faster convergence to near-optimal solutions. The MIRHA framework also includes a local search step for improving the incumbent solutions generated during the multi-start process. It also allows the addition of tailored local search components, like cache (memory) or splitting (divide-and-conquer) techniques, that allow the generation of competitive (near-optimal) solutions. The algorithms designed using the MIRHA framework allows to obtain "high-quality" solutions to realistic problems in reasonable computing times. Moreover, they tend to use a reduced number of parameters, which makes them simple to implement and configure in most practical applications. This framework has successfully been applied in many routing and scheduling problems. One of the main goals of this thesis is to develop new algorithms, based in the aforementioned framework, for solving some combinatorial optimization problems that can be of interest in the telecommunication industry.
eng
dc.format.extent
133 p.
dc.format.mimetype
application/pdf
dc.language.iso
eng
dc.publisher
Universitat Oberta de Catalunya
dc.rights.license
L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-nd/3.0/es/
dc.source
TDX (Tesis Doctorals en Xarxa)
dc.subject
heurístiques aleatòries i esbiaixades
dc.subject
optimització
dc.subject
aplicacions reals
dc.subject
metaheurístiques
dc.subject
simulació
dc.subject
Heurísticas Aleatorias y Sesgada
dc.subject
Optimización
dc.subject
Aplicaciones Reales
dc.subject
Metaheurísticas
dc.subject
Simulación
dc.subject
Biased Randomized Heuristics
dc.subject
Optimization
dc.subject
Real applications
dc.subject
Metaheuristics
dc.subject.other
Ciència de la Computació i Inteligència Artificial
dc.title
Applications of Biased Randomization and Simheuristic Algorithms to Arc Routing and Facility Location Problems
dc.type
info:eu-repo/semantics/doctoralThesis
dc.type
info:eu-repo/semantics/publishedVersion
dc.subject.udc
004
cat
dc.subject.udc
519.1
cat
dc.contributor.authoremail
sgonzalezmarti@uoc.edu
dc.contributor.authoremailshow
true
dc.contributor.director
Juan Pérez, Ángel Alejandro
dc.contributor.director
Riera Terrén, Daniel
dc.contributor.authorsendemail
true
dc.embargo.terms
cap
dc.rights.accessLevel
info:eu-repo/semantics/openAccess
dc.identifier.dl
B 27249-2014


Documents

PhD Thesis Sergio Gonzalez Martin - Applications of Biased Randomization and Simheuristic Algorithms to Arc Routing and Facility Location Problems.pdf

2.751Mb PDF

This item appears in the following Collection(s)