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

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.

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.

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.