Solución exacta del problema diseño de redes multiproducto con arcos no dirigidos y capacidad finita
Export citation
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.