Resolución computacional de un problema de optimización combinatorio hibrido Computational resolution of a hybrid combinatorial optimiza-tion problem

Abstract

En este articulo definimos un problema de optimizacion combinatorio hibrido, y exploramos varias heuristicas computacionales de resolucion del mismo. El problema de optimizacion combinatorio hibrido consiste en los problemas de la mochila y el viajero de comercio. Este problema hibrido tiene aplicaciones muy importantes, en particular, aqui lo exploramos en el ambito de la robotica, para el caso en el que se requiere optimizar el comportamiento de los robots en la busqueda de multiples objetos en varios recorridos, segun sus capacidades. Se requiere minimizar el numero de recorridos y que cada recorrido sea lo mas corto posible, pasando por los sitios que contienen los objetos a recoger en ese recorrido. Ese problema es muy importante en los supermercados automatizados, en particular para la gestion de los almacenes cada vez que llega un pedido de los clientes. En este articulo planteamos el problema, asi como analizamos su resolucion usando varias meta-heuristicas, en especifico, el recocido simulado, los algoritmos geneticos, las redes neuronales aleatorias y los algo-ritmos tabu. Ademas, presentamos el ejemplo de aplicacion en robotica y algunos resultados. Palabras claves: Problemas de optimizacion combinatoria, algoritmos heuristicos, automatizacion de supermercado, ambientes inteligentes. Abstract In this article, we define a hybrid combinatorial optimization problem and explore various computational heuristic to solve it. The hybrid combinatorial optimization problem consists of the knapsack problem and the traveling salesman problem. This hybrid problem has very important applications, in particular, in this paper we explore the field of robotic, to optimize the behavior of robots in search of multiple objects on multiple tours, according to their abilities. In this case, it is required to minimize the number of routes, and each route must be as short as possible, through sites that contain objects to pick up on that tour. This problem is very important in automated supermarkets, particularly, to warehouse management when an order comes from customers. In this article we pose the problem, and analyze its resolution using various meta-heuristics, specifically, simulated annealing, genetic algorithms, artificial neural networks and the taboo random algorithms. In addition, we present an example of application in robotic, and some results. Keywords: Combinatorial optimization problems, heuristic algorithms, supermarket automation, intelligent environments.