Solución exacta del problema diseño de redes multiproducto con arcos no dirigidos y capacidad finita

Abstract

A los vértices y arcos de una gráfica frecuentemente se les asocia información cuantitativa, por ejemplo a los vértices lo correspondiente a ofertas y demandas; distancias, longitudes, capacidad y costos en el caso de los arcos. Relativo a estas redes, hay problemas discretos de optimización que aparecen en estadística, ingeniería eléctrica, investigación de operaciones, telecomunicaciones, combinatoria, computación, entre otras disciplinas. El problema en el que se centrará este trabajo, es el diseño de redes multiproducto, con capacidad fija y arcos no dirigidos (Multicommodity Capacitated Network Design Problem, MCND), el cual se aplica principalmente en las áreas de transporte, ruteo, comunicación y computación, donde varios artículos – bienes, datos, paquetes, personas – se necesitan transportar de un origen a un destino particular, a través de los arcos de una red con capacidades limitadas. En este problema, se puede considerar dos tipos de costos asociados a cada arco: uno variable, de transportación, que está relacionado con el volumen de cada artículo que fluye a través del arco; y uno fijo, de construcción o utilización, costo que es pagado si se utiliza el arco o se añade la capacidad. Siendo el objetivo principal la minimización del costo total por diseñar y operar la gráfica de flujo. Una solución óptima del problema, puede ser encontrada por la numeración completa o implícita de todos los caminos posibles, sin embargo consume demasiado tiempo aún para problemas de tamaño moderado, ya que se ha demostrado que este problema pertenece a la clase Np-completo [42]. Además al construir una solución, la compensación entre los dos tipos de costos, así como la interacción entre la capacidad finita de los arcos y los costos fijos, añade dificultad a la resolución eficiente de los problemas [12]. Métodos eficientes de solución son los metaheurísticos y la computación paralela, en particular el procedimiento de Búsqueda Tabú ([25-27]), o GRASP y Búsqueda Dispersa [3] que se utilizan para identificar buenas soluciones factibles para problemas de gran tamaño. El objetivo y contribución principal de la investigación es la generación de un algoritmo computacional que resuelva este tipo de problemas de manera exacta, basado en un esquema de ramificación y acotamiento (Branch-and-Bound en inglés), combinándolo con la técnica de Generación de Columnas, es decir ramificación y precio (Branch-andPrice en inglés); utilizando el algoritmo de camino más corto, de Floyd y Warshall, para la elección de la columna cuya entrada a la base genere el mayor beneficio a la solución. Para ilustrar el procedimiento propuesto se presenta un ejemplo del diseño de una red pequeña, además se compara dos estrategias de ramificación ya que esto afecta la eficiencia de los algoritmos en un ambiente Branch-and-Price. Debido a que se presentan los mayores retos computacionales en problemas de gran escala, al final del trabajo se compara el método propuesto contra uno de resolución basado en un heurístico.