Un modelo ACO para una versión no estacionaria del problema del ascensor único

Abstract

La técnica Optimización de Colonias de Hormigas (ACO) puede ser aplicada a problemas de optimización combinatorios duros en ambientes estacionarios y no estacionarios. En dicha metaheurística, las hormigas artificiales de una colonia cooperan para encontrar soluciones de alta calidad en un tiempo razonable. Un ejemplo interesante de un problema de optimización combinatorio no estacionario para ser abordado a través de una técnica ACO, es el Problema de los Ascesores Múltiples (MEP) el cual consiste en encontrar la secuencia de movimientos que debe realizar cada ascensor de un edificio de manera tal de minimizar el tiempo medio de espera de los pasajeros. La llegada de un nuevo pasajero a la cola de un ascensor, la rotura de un ascensor, etc., son los eventos que provocan cambios de estado en este problema, haciéndolo dinámico. Una subclase del problema de ascensores múltiples es el denominado Problema del Ascensor Único (SEP) en su versión no estacionaria. En dicho problema se considera la existencia de un ´único ascensor en un edificio en donde no se tienen en cuenta las ocurrencias de eventos. En este trabajo se presenta un modelo ACO para SEP y en base a éste modelo, se propone el diseño de un Sistema de Colonias de Hormigas (ACS).

The Ant Colony Optimization (ACO) metaheuristic is a bio-inspired approach for hard combinatorial optimization problems for stationary and non-stationary environments. In the ACO metaheuristic, a colony of artificial ants cooperate for finding high quality solutions in a reasonable time. An interesting example of a non-stationary combinatorial optimization problem is the Multiple Elevators Problem (MEP) which consists in finding a sequence of movements for each elevator to perform in a building so that to minimize, for instance, the waiting average time of the passengers. Events like the arrival of one new passenger to the elevator queue or the fault of one elevator produce dynamically the changes of state in this problem. A subclass of MEP is the non-stationary version of the so called Single Elevator Problem (SEP). In this work, we propose the design of an ACO model for the SEP that can be implemented as an Ant Colony System (ACS).