Los Problemas Combinatoriales han sido un problema recurrente para el hombre El objetivo de la optimalidad global versus el costo que esto supone es un tema no resuelto por los investigadores. En este sentido problemas como tsp




Скачать 33.78 Kb.
НазваниеLos Problemas Combinatoriales han sido un problema recurrente para el hombre El objetivo de la optimalidad global versus el costo que esto supone es un tema no resuelto por los investigadores. En este sentido problemas como tsp
Дата конвертации19.04.2013
Размер33.78 Kb.
ТипДокументы
Propuesta de Arquitectura para la Resolución de

Problemas Combinatoriales en un Entorno Ubicuo


Guillermo Cabrera G.

Jose Miguel Rubio L.

Pontificia Universidad Católica de Valparaíso

Pontificia Universidad Católica de Valparaíso

Av. Brasil 2241

Av. Brasil 2241

Valparaíso

Valparaíso

CHILE

CHILE

guillermo.cabrera@ucv.cl

jose.rubio.l@ucv.cl


Abstract – Los Problemas Combinatoriales han sido un problema recurrente para el hombre El objetivo de la optimalidad global versus el costo que esto supone es un tema no resuelto por los investigadores. En este sentido problemas como TSP (travel salesman problem) o el VRP (vehicle routing problem) corresponden a problemas combinatoriales que resultan cotidianos para un grupo de personas que desearía tener la solución a este tipo de problemas lo más cerca posible. Es así como la idea de que dichos problemas, netamente operacionales, sea resuelto de manera heurística por los dispositivos de uso normal del vendedor o del conductor del vehiculo repartidor toma sentido. En este artículo se propone una arquitectura que de soporte a la resolución de problemas combinatoriales complejos en dispositivos móviles a través de heurísticas o metaheurísticas embebidas en los propios dispositivos y que trabajen a partir de un conjunto de datos proporcionados por un servidor central.


  1. introduction


La necesidad del hombre actual por tener acceso a la información en cualquier momento o en cualquier lugar, ha provocado un desarrollo explosivo de una serie de tecnologías que dan el soporte para poder alcanzar ese objetivo. PDA’s (Personal Digital Assistants) y teléfonos móviles con acceso a Internet son sólo una muestra de ello. Esta posibilidad de acceso en “todos lados” es llamado en [12] computación ubicua o ubicomp. Sin embargo, hoy ya no sólo es necesario estar conectado, sino que dicha conexión debe permitirnos algo más que navegar en la red: debe permitir la solución de los problemas con los que se debe enfrentar el hombre día a día en su entrono. Algunos de esos problemas de tipo operacional, es decir, del día a día, corresponden a problemas combinatoriales complejos, como por ejemplo el TSP o el VRP.

La posibilidad de integrar la resolución de problemas combinatoriales, a través de heurísticas y metaheurísticas, con el desarrollo de aplicaciones en un entrono ubicuo, asoma como una alternativa real de resolución de problemas operativos de distintos negocios. La idea de que el vendedor, a través de una aplicación en su celular pueda saber cuales son los clientes que debe visitar y, principalmente, la ruta que deberá seguir de manera de incurrir en el mínimo de gastos de movilización, aparece como posible gracias al desarrollo de la computación ubicua.

Cabe destacar que la arquitectura propuesta en este artículo considera la resolución del problema directamente en el dispositivo móvil, haciendo que la dependencia de un servidor central se limite sólo al envío de los datos de entrada necesarios para la correcta ejecución del algoritmo.


  1. descripción del problema


Tal como se mencionó anteriormente, los problemas a considerar en esta propuesta son el TSP y el VRP. The traveling salesman problem (TSP) is a paradigmatic NP-hard combinatorial optimization problem which has attracted an enormous amount of research effort [1, 2], while the VRP is a very complicated combinatorial optimization problem that has been worked on since the late fifties, because of its central meaning in distribution management. Problem specific methods a well as meta-heuristics like Tabu Search [5], simulated annealing [6], genetic algorithms [7] and neural networks [8] have been proposed to solve it The VRP and the TSP are closely related. As soon as the customers of the VRP are assigned to vehicles, the VRP is reduced to several TSPs [10].

The TSP is a very important problem also in the context of Ant Colony Optimization because it is the problem to which the original AS was first applied [3, 4], and it has later often been used as a benchmark to test new ideas and algorithmic variants. En este paper se busca presentar una arquitectura que soporte la implementación de una aplicación en un entorno ubicuo, que resuelva ambos problemas recién mencionados (TSP y VRP). A continuación se presentará brevemente la formulación del TSP. No se entrará en detalle pues se considera un problema bien conocido y estudiado en la literatura.


  1. Arquitectura Propuesta


En esta sección se presenta la arquitectura de resolución propuesta para ambos problemas. En rigor, se presenta una generalización para la resolución de problemas de optimización combinatorial, la cual será aplicada posteriormente a los dos problemas especificados en la sección anterior.

En primer lugar, se presentan los componentes principales de la arquitectura propuesta:

  1. Servidor Central. El servidor central contiene los datos de los lugares que debe visitar cada uno de los vendedores del sistema y las distancias entre ellos. Además contiene el WS (web service) que responde a los requerimientos del dispositivo móvil

  2. Dispositivo Móvil: Se considera un dispositivo móvil que cuente con una JVM (Java Virtual Machina) con el fin de ejecutar una aplicación J2ME que implementa la heurística de resolución y un servicio de datos GPRS para la transmisión de datos.

  3. Transmisión de la información: La comunicación entre el servidor y el dispositivo móvil se logra a través del GPRS (General Packet Radio Service), el cual es un servicio móvil orientado a paquetes y de un servidor HTTP el cual es el encargado de almacenar y enviar los datos de entrada ante una solicitud de servicio por parte del dispositivo móvil.

  4. Heurística de Resolución: La heurística de resolución será ACO (Ants Colony Optimization). Esta heurística para la resolución de problemas combinatoriales complejos esta inspirada en the pheromone trail laying and following behavior of real ants which use pheromones as a communication medium. In analogy to the biological example, ACO is based on the indirect communication of a colony of simple agents, called (artificial) ants, mediated by (artificial) pheromone trails. The pheromone trails in ACO serve as a distributed, numerical information which the ants use to probabilistically construct solutions to the problem being solved and which the ants [11]. Las primera pruebas a las cuales fueron sometidos los algoritmos ACO corresponden justamente a los problemas que se quieren abordar en este artículo (TSP y VRP)[11][10], por lo que un detalle de la forma de operar de la heurística puede ser encontrada en la literatura.


Una vez definidos los componentes principales de la arquitectura propuesta, la figura 1 muestra la organización de dichos componentes y cómo interactúan entre si.




Fig. 1. Arquitectura Propuesta para la Resolución de Problemas Combinatoriales en un Entrono de Computación Ubicua



  1. Medicion de Resultados


En esta sección se presentan algunos de los indicadores relevantes para la medición de futuros experimentos basados en la arquitectura propuesta en este artículo.

    1. Tiempo de Respuesta del Servidor: Corresponderá al tiempo que transcurre entre el envío del requerimiento desde el dispositivo móvil

    2. Tiempo de Ejecución de la Heurística: Corresponde al tiempo que transcurre desde que el mensaje enviado por el WS desde el servidor central llega al dispositivo móvil hasta cuando la heurística entrega por pantalla al usuario la ruta obtenida a partir de la heurística.

    3. Uso de energía: En general se busca un bajo consumo de energía en el desarrollo de procesadores[13] y por lo mismo las aplicaciones que se ejecutan sobre ellos deben ser altamente eficientes en su implementación con el fin de no ejecutar mas acciones que las realmente necesarias para el correcto funcionamiento de la aplicación. Por lo anterior, otro indicador relevante en la medición de resultados será el nivel de consumo de la aplicación, ya que un alto consumo podría hacer que la arquitectura propuesta fuera impracticable.




  1. Conclusiones


Los esfuerzos por desarrollar los conceptos derivados de la computación ubicua hacen pensar en la resolución de problemas en entornos altamente interconectados. Lo anterior supone una arquitectura que dé soporte a las aplicaciones que resolverán problemas definidos, en el caso de este paper, problemas combinatoriales complejos, lo cual puede resultar altamente beneficioso para aquellos individuos cuyo trabajo tiene a este tipo de problemas como actividades de tipo operacional. En este artículo se presenta una arquitectura que de soporte a la implementación de algoritmos conocidos para la resolución de problemas combinatoriales complejos en un entorno de computación ubicua. A modo de trabajo futuro, se espera implementar un prototipo basado en esta arquitectura, que sea capaz de resolver problemas específicos (benchmark), de manera de poder comparar su rendimiento en base a los indicadores definidos previamente y a otros que puedan surgir a lo largo de su desarrollo y experimentación.


  1. REFERENCES




  1. D. S. Johnson and L. A. McGeoch. “The travelling salesman problem: A case study in local optimization”, in E. H. L. Aarts and J. K. Lenstra, editors, Local Search in Combinatorial Optimization, pages 215–310. John Wiley & Sons, Chichester, 1997

  2. E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys. The Travelling Salesman Problem. John Wiley & Sons, Chichester, UK, 1985.

  3. M. Dorigo, V. Maniezzo, and A. Colorni. “The Ant System: An autocatalytic optimizing process”, Technical Report 91-016 Revised, Dipartimento di Elettronica, Politecnico di Milano, Italy, 1991.

  4. M. Dorigo. Optimization, Learning and Natural Algorithms, PhD thesis, Dipartimento di Elettronica, Politecnico di Milano, Italy, 1992. pp.

  5. E. Taillard. “Paralel Iterative Search Methods for Vehicle Routing Problems”, Networks 23, 1993, 661.

  6. I. Osman, “Metastrategy simulated annealing and tabu search algorithm for the Vehicle Routing Problem”, Annals of Operations Research, 1993, 421



  7. H. Ghaziri, “Supervision in the Self-Organizing Feature Map: Application for the Vehicle Routing Problem”, Meta-Heuristics: Theory & Applications, ed. I. Osman and J. Kelly (Kluwer, Boston, 1996).

  8. M. Dorigo, V. Maniezzo, and A. Colorni. “The Ant System: Optimization by a colony of cooperating agents”, IEEE Transactions on Systems, Man, and Cybernetics – Part B, 26(1):29–41, 1996.

  9. Marco Dorigo and Thomas Stützle, “The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances”, Handbook of Metaheuristics, International Series in Operations Research and Management Science, Vol 57, 2003.

  10. B. Bullnheimer, R.F. Hartl, and C. Strauss. “An Improved Ant System Algorithm for the Vehicle Routing Problem”. Annals of Operations Research, 1997.

  11. Mark Weiser, "Hot Topics: Ubiquitous Computing" IEEE Computer, October 1993.

  12. Mark Weiser, "Some Computer Science Problems in Ubiquitous Computing," Communications of the ACM, July 1993.



Добавить в свой блог или на сайт

Похожие:

Los Problemas Combinatoriales han sido un problema recurrente para el hombre El objetivo de la optimalidad global versus el costo que esto supone es un tema no resuelto por los investigadores. En este sentido problemas como tsp iconObjetivo general consultar los diferentes tic para la investigación y desarrollo de los temas venideros. Objetivo especifico

Los Problemas Combinatoriales han sido un problema recurrente para el hombre El objetivo de la optimalidad global versus el costo que esto supone es un tema no resuelto por los investigadores. En este sentido problemas como tsp iconPara adentrarnos en los problemas de la Ética, partamos de nuestra experiencia. Es un hecho que nos señala nuestra propia experiencia que, en determinadas

Los Problemas Combinatoriales han sido un problema recurrente para el hombre El objetivo de la optimalidad global versus el costo que esto supone es un tema no resuelto por los investigadores. En este sentido problemas como tsp iconHaga un clic en las secciones debajo para guiar a diferentes áreas del documento Haga un clic en los enlaces. Usted será dirigido a un sitio o directorio web con la lista de materiales de este tema

Los Problemas Combinatoriales han sido un problema recurrente para el hombre El objetivo de la optimalidad global versus el costo que esto supone es un tema no resuelto por los investigadores. En este sentido problemas como tsp iconEl panorama mundial está enmarcado por una creciente preocupación por los efectos que pueda traer consigo la poca práctica de actividad física. Los gobernantes

Los Problemas Combinatoriales han sido un problema recurrente para el hombre El objetivo de la optimalidad global versus el costo que esto supone es un tema no resuelto por los investigadores. En este sentido problemas como tsp iconEl lenguaje y los sistemas de indicadores como estrategia tecnológica para la competitividad de PyMEs

Los Problemas Combinatoriales han sido un problema recurrente para el hombre El objetivo de la optimalidad global versus el costo que esto supone es un tema no resuelto por los investigadores. En este sentido problemas como tsp iconObjetivo general Lograr un conocimiento de los conceptos y procedimientos de la evaluación de impactos ambientales, con énfasis en la metodología de trabajo necesaria para la misma

Los Problemas Combinatoriales han sido un problema recurrente para el hombre El objetivo de la optimalidad global versus el costo que esto supone es un tema no resuelto por los investigadores. En este sentido problemas como tsp iconDebemos decir, lamentablemente, que las trade-unions aquí han olvidado su deber como vanguardia de la clase obrera. ( ). Junto a las asociaciones en los ramos

Los Problemas Combinatoriales han sido un problema recurrente para el hombre El objetivo de la optimalidad global versus el costo que esto supone es un tema no resuelto por los investigadores. En este sentido problemas como tsp iconEl Departamento Ejecutivo determinará mediante los estudios correspondientes la conveniencia de la venta del inmueble como única parcela, como parcelas subdivididas o como propiedad horizontal

Los Problemas Combinatoriales han sido un problema recurrente para el hombre El objetivo de la optimalidad global versus el costo que esto supone es un tema no resuelto por los investigadores. En este sentido problemas como tsp iconАникеева Н. Е. / N. Anikeeva
К вопросу о классификации иноязычных заимствований в испанском языке / Observaciones sobre el problema de la clasificación de los...

Los Problemas Combinatoriales han sido un problema recurrente para el hombre El objetivo de la optimalidad global versus el costo que esto supone es un tema no resuelto por los investigadores. En este sentido problemas como tsp iconLanl (Los Alamos National Laboratory), July 21, 1988. “Requestor Data Sheet #7132, ta-21-61, pcb survey ta-21,” Los Alamos National Laboratory, Los Alamos, New


Разместите кнопку на своём сайте:
lib.convdocs.org


База данных защищена авторским правом ©lib.convdocs.org 2012
обратиться к администрации
lib.convdocs.org
Главная страница