IX Jornadas de Informática e Investigación Operativa

8 al 12 de noviembre de 2004
Montevideo, Uruguay

Instituto de Computación, Facultad de Ingeniería, PEDECIBA Informática, Universidad de la República
navegacion

  • PÁGINA PRINCIPAL

  • LLAMADO

  • RECEPCIÓN DE RESUMENES

  • PROGRAMA

  • MODERADORES

  • SESIONES


  • LINKS
    • FACULTAD DE INGENIERÍA

    • INSTITUTO DE COMPUTACIÓN

    • EDICIÓN ANTERIOR

      COMITE ORGANIZADOR:
      • Daniel Calegari
      • Diego Garat
      • Antonio Mauttone
      • Franco Robledo
Título: Diseño de una red de acceso de una WAN

Marco de Trabajo: DOCTORADO

Área de desarrollo: Investigación Operativa

Autor: Franco Robledo

Contacto: frobledo@fing.edu.uy

Día: JUEVES

Hora: 15:00:00

Palabras Claves: RNN, GRASP, topología de acceso,
Resumen:

Al modelar una red de acceso de una WAN (Wide Area Networ) podemos identificar tres tipos de sitios. Sitios terminales (los clientes), sitios de concentración y sitios conmutadores de la red dorsal. El mayor costo de inversión asociado al diseño topólogico de este tipo de redes, es el costo del dragado para el tendido de las lineas. Modelando las conexiones factibles entres sitios como un grafo simple no dirigido ponderado con los costos de tendido de lineas, el problema del diseño topológico de la Red de Acceso consiste en encontrar el subrafo de costo mínimo donde todos los nodos terminales tengan salida hacia la red dorsal, con la restricción que éstos deberan tener grado 1 en la solución. Nosotros proponemos una algoritmo híbrido basado en la metodología GRASP combinada con una red neural randómica (RNN) la cuál es usada en la fase de búsqueda local para la determinación de nodos de concentración como potenciales mejoradores de la solución actual. El algoritmo demostró ser muy performante al ser testeado sobre una gran variedad de instancias con diferentes características topológicas, obteniendo siempre soluciones óptimas o sub-óptimas con gaps inferiores al 5% respecto de cotas inferiores.


Ultima modificacion 5 de Octubre 2004 16:30