técnicas avanzadas de optimización en sistemas de ...también se deriva un esquema de acotamiento...

CIENCIA UANL / VOL. XII, No. 4, OCTUBRE - DICIEMBRE 2009438

ROGER Z. RÍOS MERCADO *, CONRADO BORRAZ SÁNCHEZ *

El gas natural, como uno de loscombustibles fósiles más limpios,ha llegado a ser uno de los recur-sos naturales más importantes al-rededor del mundo. La confiabi-lidad y eficiencia con que puedeser transportado ha causado que

sus sistemas de transmisión se hayan incrementa-do de manera exponencial desde hace ya variasdécadas. Actualmente, estos inmensos sistemas detransmisión, los cuales yacen bajo el subsuelo, vir-tualmente no vistos, se encuentran entre los mé-todos más seguros de transporte de energía (gas)para satisfacer a miles de millones de clientes me-diante entregas de grandes volúmenes de gas parasu uso doméstico e industrial. En paralelo, un ele-vado costo asociado con esta transportación (mi-llones de dólares anuales) debe ser cuidadosamen-te observado.

En este trabajo nos enfocamos en el problemade minimización del costo de combustible(PMCC) incurrido por estaciones compresorasinstaladas en sistemas de transmisión de tuberías

de gas natural. El problema puede ser descritocomo sigue: necesitamos mover típicamente enor-mes cantidades de gas desde diversas posibles fuen-tes hacia diferentes centros de distribución a tra-vés de varios dispositivos incluyendo tuberías,reguladores, válvulas y compresores. Durante esteproceso de transmisión, la energía y presión vandisminuyendo debido a la fricción entre el gas ylas paredes internas de las tuberías, así como a latransferencia de calor entre el gas y el medio am-biente. Por lo tanto, encender las estacionescompresoras instaladas en la red se torna crucialpara incrementar la presión periódicamente ymantener así el gas fluyendo a través del sistema.En consecuencia, altos costos asociados de consu-mo de combustible son incurridos por estas esta-ciones compresoras, además de que se estima quetípicamente entre 3 y 5% del gas transportado estambién consumido por dichos compresores. Porotro lado, aún una mejora marginal de 1-2% so-bre el costo total en la operación del gas tiene unimpacto positivo muy significativo desde un pun-to de vista económico, ya que hablamos de unahorro de millones de dólares por año que conlle-

TécnicTécnicTécnicTécnicTécnicas aas aas aas aas avvvvvanzadas de optimización en sistanzadas de optimización en sistanzadas de optimización en sistanzadas de optimización en sistanzadas de optimización en sistemasemasemasemasemasde trde trde trde trde transpanspanspanspansporororororttttte de gas nae de gas nae de gas nae de gas nae de gas naturturturturturalalalalal

El presente artículo está basado en la investigación ″Técni-cas avanzadas de optimización en sistemas de transporte degas natural″, galardonada con el Premio de InvestigaciónUANL 2009 en la categoría de Ingienería y Tecnología, otor-gado en sesión solemne del Consejo Universitario, en sep-tiembre de 2009.

* División de Posgrado en Ingeniería de Sistemas, FIME-UANL.

CIENCIA UANL / VOL. XII, No. 4, OCTUBRE - DICIEMBRE 2009 439

varía a establecer una relación más afable entre lasociedad en general y el sector industrial. De ahíque el problema de determinar un plan de trans-porte sobre una red existente que satisfaga la de-manda especificada mientras se cumplen con to-das las restricciones provee, desde una perspectivapráctica, es la principal motivación del trabajo queahora presentamos.

El problema es representado por una red, don-de sus arcos representan los ductos o estacionescompresoras, y sus nodos son los puntos físicosde interconexión. Se consideran dos tipos de va-riables continuas de decisión: el flujo másico através de cada arco de la red, y los niveles de pre-sión en cada nodo. Así, desde la perspectiva de laoptimización, el PMCC es modelado como unproblema de programación no lineal (NLP, porsus siglas en inglés, Non-Linear Programming), don-de tanto la función de costo y el conjunto de res-tricciones son típicamente no lineales y no con-vexos. Dado que es bien conocido que los proble-mas NLP no convexos son clasificados como pro-blemas NP-duros,1 esto motiva aún más al estudioe implementación de la aproximación heurísticaque en este artículo se propone.***

El estado del arte revela dos tipos fundamenta-les de de redes: no cíclicas y cíclicas. Las primerashan recibido la mayor atención durante los últi-mos 40 años, llegando a ser inclusive un proble-ma trivial donde diversas metodologías de solu-ción, la mayoría basadas en técnicas de programa-ción dinámica2 (DP por sus siglas en inglés, Dynamic

Programming) han sido aplicadas con éxito. En con-traste, los sistemas cíclicos presentan un proble-ma mucho más difícil de resolver. En este senti-do, trabajos en esta área son prácticamenteinexistentes, y aquellos implementados con baseen técnicas de aproximación de búsqueda delgradiente y DP han tenido poco o limitado éxito.De hecho, la principal limitación de las técnicasde gradiente es su estatus de optimalidad local,mientras que la desventaja de la DP es que su apli-cación se limita a estructuras no cíclicas o proble-mas la solución final obtenida es “óptima” con

respecto a un conjunto de flujos factibles previa-mente establecido.

Desde hace ya varios años la búsqueda tabú3

(TS, por sus siglas en inglés, Tabu Search) ha esta-blecido su posición como una metaheurística efec-tiva que se ha tomado como base para el diseño eimplementación de algoritmos que resuelven pro-blemas de optimización combinatorios en diferen-tes áreas de investigación. De ahí que, aun cuandolidiamos con un problema de optimización con-tinuo, la no convexidad que la función objetivo yel dominio factible de operación presentan a TS,sobre un espacio apropiado de factibilidad discre-to, una muy atractiva y prometedora estrategia desolución debido a su versatilidad para sobrellevarla optimalidad local.

En este trabajo proponemos una metodologíanovel para lidiar con el problema de cómo operarde manera óptima las estaciones compresoras enlos sistemas de tuberías de gas natural, enfocandonuestro esfuerzo a resolver topologías de red conestructuras cíclicas. La técnica propuesta combi-na una técnica de programación dinámica nosecuencial4 (NDP por sus siglas en inglés, Non-

sequential Dynamic Programming) dentro de un es-quema de búsqueda tabú.

Evidencia empírica sobre una extensa base dedatos de instancias cíclicas con diferentes configu-raciones de flujo muestra la eficiencia de la aproxi-mación propuesta. Una comparación con el mé-todo del Gradiente Reducido Generalizado (GRG) bajoun esquema multiarranque, demuestra la superio-ridad de nuestro procedimiento. Asimismo, nues-tra metodología propone una mejora significativaen el estado del arte de los procedimientos exis-tentes. Además, con el fin de desafiar la calidad delas soluciones entregadas por nuestro algoritmo,también se deriva un esquema de acotamientoinferior demostrando que el margen de optimali-dad encontrada por nuestra técnica es menos de16%, donde la mayoría de las instancias resueltasestuvieron a no más de 10% del óptimo global,lo cual representa un gran avance del actual esta-do del arte en esta área de investigación. De ahí

ROGER Z. RÍOS MERCADO, CONRADO BORRAZ SÁNCHEZ


TÉCNICAS AVANZADAS DE OPTIMIZACIÓN EN SISTEMAS DE TRANSPORTE DE GAS NATURAL

que la contribución científica del presente traba-jo esté en proveer la mejor técnica conocida a lafecha para resolver el PMCC sobre topologías cí-clicas.

Descripción del problema

En esencia, los sistemas de gasoductos pueden serclasificados en sistemas en estado estable o siste-mas transientes. Aquí asumimos un sistema enestado estable e isotérmico (temperatura constan-te) para proveer soluciones a sistemas que han es-tado operando por una cantidad de tiempo relati-vamente grande –lo que en la práctica es una si-tuación bastante común–. Con respecto a los mo-delos transientes, debido a su alta intratabilidaddesde la perspectiva de la optimización, su análi-sis puede llevarse a cabo básicamente mediante mo-delos descriptivos. De ahí que la optimización so-bre estos sistemas permanezca aún en estos díascomo uno de los grandes desafíos en esta área.

Asumimos también un modelo determinista,esto es, cada parámetro es conocido con certeza.En términos de las estaciones compresoras, consi-deramos unidades compresoras centrífugas por serlas más utilizadas en la industria del gas natural.Ahora bien, con respecto al modelo de red, noso-tros asumimos que la red está balanceada y es diri-gida, es decir, no hay pérdida de gas en lo absolu-to y cada arco en la red tiene una dirección previa-mente especificada.

Definición del modelo matemático

El modelo matemático se plantea como un mo-delo no convexo (NLP). Sea G = (V, A) un grafodirigido que representa una red de transmisión degas, donde V representa el conjunto de nodos y Ael conjunto de arcos dirigidos. Desde la perspecti-va real, cada nodo en V representa un punto deunión entre ductos o entre un ducto y una esta-ción compresora, en donde existe forma de mediry/o controlar la presión del gas. Además, existentres tipos de nodos distintos: nodo proveedor

(donde se inyecta gas al sistema), nodo demanda(donde se extrae gas del sistema) y nodo de paso.Estos tres conjuntos de nodos se representan porV

s, V

d y V

p, respectivamente, donde V = V

s ∪ V

d

∪ Vp. De igual manera, el conjunto de arcos A

puede dividirse en un conjunto de arcos que re-presentan físicamente a los ductos (A

p) y uno que

representa a las estaciones compresoras (Ac), don-

de A = Ap ∪ A

c. Esto es, si (i, j)∈A

c entonces i, j ∈

V son los nodos de red que representa los puntosde entrada y salida, respectivamente, de alguna es-tación compresora (i, j). Una interpretación aná-loga es hecha para los arcos ductos (i, j)∈A

p.

La capacidad y la resistencia de un ducto (i,j)∈A

p se denotan por U

ij y R

ij, respectivamente.

PiL y P

iU son los límites de presión inferior y supe-

rior en el nodo i∈V. Bi es la tasa de flujo neto en

el nodo i∈V, donde Bi > 0 si i∈ V

s, B

i < 0 si i∈

Vd, y B

i = 0 en cualquier otro caso. Definimos a

las variables de decisión como xij, el flujo másico a

través del arco (i, j)∈A, y pi, la presión en el nodo

i ∈V.Luego, entonces, el PMCC se formula como:

La expresión (1) representa la función objeti-vo, la cual mide el costo total del combustibleconsumido por las estaciones compresoras en elsistema. Definida por:

donde α y m son parámetros constantes conocidosque dependen de las propiedades físicas del gas.

Las ecuaciones (2) y (3) son dos restriccionestípicas en cualquier problema de flujo en redes:


balance de flujo nodal, con ∑i∈V

Bi = 0, y restric-

ción de capacidad, respectivamente. La ecuación(4) representa la dinámica del flujo de gas a travésde cada ducto de la red, es decir, nos muestra larelación que existe entre la disminución de pre-sión y el flujo de gas en estado estable (válida paragases de alta presión). Ésta se denomina ecuaciónde Osiadacz5 (para un análisis más detallado véaseS. Kim, R. Z. Ríos Mercado y E. A. Boyd)6.

Los límites de presión en cada nodo son da-dos por la restricción (5). La expresión (6) repre-senta el dominio de operación factible para cadaestación compresora del sistema (para una inspec-ción más detallada ver Wu, R.Z. Ríos Mercado,E. A. Boyd y L.R. Sco ).7

La figura 1 muestra en 2-D el dominio Dij cuan-

do la presión de entrada (o de succión) pi se fija.

La formulación exacta del modelo está totalmen-te disponible en: http://yalma.fime.uanl.mx/∼∼∼∼∼roger/ftp/.

Finalmente, la expresión (7) representa la con-dición de no negatividad de las variables de deci-sión.

Revisión de la bibliografía

Una extensa bibliografía para resolver el PMCCha sido publicada durante las últimas décadas.Dentro de ésta se incluyen aplicaciones basadasen simulaciones numéricas (A. J. Osiadacz),5 pro-gramación dinámica2 (DP por sus siglas en inglés,Dynamic Programming) (ver S. Wu, R. Z. Ríos-Mer-cado, E.A. Boyd y L.R. Scott,7 J.T. Jefferson8 yP.J. Wong y R.E. Larson,9 técnicas de gradiente(ver H.J. Flores-Villarreal y R.Z. Ríos-Mercado),10

y otros. La mayoría de las contribuciones han es-tado prácticamente limitadas a redes de tuberíascon estructuras no cíclicas o pequeñas redes cícli-cas, obteniendo un considerable o modesto éxitosobre tales instancias.

Diversos trabajos, algunos relacionados con laprogramación dinámica no secuencial (ver R.G.Carter4 y C. Borraz Sánchez y R.Z. Ríos Merca-do)11 han sido desarrollados con la promesa demanejar topologías cíclicas. El trabajo más impor-tante sobre redes cíclicas conocido a la fecha sedebe a Carter,4 quien desarrolló un algoritmo deDP no secuencial, aunque con la desventaja deestar limitado a un conjunto de flujos másicosfactibles. Aun así, este trabajo constituye el mejormétodo conocido a la fecha para resolver este tipode problemas. Este trabajo nos conduce a la inte-resante cuestión de cómo modificar inteligente-mente los valores de las variables de flujo actualsobre la red para mejorar la función de objetivo,al encontrar una mejor configuración global delsistema. En nuestro trabajo, desarrollamos preci-samente estos conceptos e ideas y derivamos unatécnica híbrida de optimización que incorporaexitosamente un método avanzado de optimiza-ción metaheurística como la búsqueda tabú y unesquema de programación dinámica no secuencial.

Método de solución propuesto

La metodología propuesta (mostrada en la figura2), denominada como NDPTS, procede como si-gue:

Fig. 1. Dominio factible Dij de una estación compresora (i,j)

∈Ac con Pi fija.




Fig. 2. Pseudocódigo del procedimiento NDPTS.

En el paso 1 se ejecuta una fase de preproce-samiento que refina el dominio D

ij mediante téc-

nicas de acotamiento sobre las variables de deci-sión y aplica una técnica de reducción de red (mo-tivados por el trabajo de Ríos Mercado et al).2 Des-pués, en el paso 2, se encuentra un conjunto deflujos factibles iniciales (x) aplicando dos diferen-tes métodos: una técnica de asignación clásica yun algoritmo de grafo reducido. En el paso 3, unconjunto de presiones óptimas (p), para el flujoobtenido en el paso anterior, es encontrado me-diante la aplicación de un algoritmo DP nosecuencial (NDP). En este punto del algoritmo,nosotros ya tenemos la solución factible inicial (x,p) que usaremos para ejecutar el procedimientoiterativo de búsqueda local basado en búsquedatabú (TS).

Dentro de la búsqueda TS hay dos componen-tes principales para generar una trayectoria de pun-tos factibles: un componente de modificación delas variables de flujo y un componente de cálculode las variables de presión. En el primer compo-nente se hace un intento por encontrar un con-junto diferente de flujos factibles, y en el segun-do, su correspondiente conjunto de valores ópti-mos de presión es encontrado por el procedimien-to NDP. La búsqueda TS se ejecuta hasta que uncriterio de parada es alcanzado, en este caso, nues-tro criterio está dado por un número máximo deiteraciones.

A continuación describimos la fase de reduc-ción de red que se aplica en el paso 1 del algorit-mo. En lo que resta de la sección nosotros asumi-remos que hay un flujo factible inicial y proveere-

mos una descripción detallada de los componen-tes del procedimiento NDP (paso 3) y el esquemade búsqueda TS (paso 4), los cuales son el enfo-que central de este trabajo.

Técnica de reducción

En la fase de preprocesamiento se lleva a cabo unproceso esencial de reducción y simplificación dela red del sistema para aplicar el algoritmo NDPde una manera más directa y eficiente.

Una red compresora o reducida contiene ex-clusivamente arcos compresores, mientras que losdemás componentes de la red (arcos ducto ynodos) son agrupados en metanodos. Típicamen-te se define una red reducida G’ = (V’, A

c) de G,

donde Ac es el conjunto de arcos compresores de la

red original, y V’ es el conjunto de metanodos, elcual describimos más abajo. Esta técnica se basa enla demostración de unicidad de asignación de flujossobre un sistema de gasoductos en Ríos Mercado etal.12 donde se establece que si se conocen los flujosen los compresores y los flujos netos del fluido encada nodo, es posible determinar los flujos corres-pondientes en los ductos de una forma sencilla me-diante la resolución de un sistema de ecuacionesalgebraicas.

La transición de reducción se describe por tressimples pasos (figura 3): remover temporalmentetodos los arcos compresores de G, “comprimir”cada componente conexo en un metanodo SN

q,

=1, …, Q y, finalmente, regresar cada arco com-presor removido a su sitio. La idea central de latécnica se basa en el manejo de las estructuras paradisminuir el tamaño de la red sin alterar su estruc-tura matemática. La complejidad computacionalde este procedimiento es O(|A|). Los detallespueden ser encontrados en R.Z. Ríos Mercado, S.Wu, L.R. Scott y E.A. Boyd. 12

Programación dinámica no secuencial (NDP)

Se aplicó NDP sobre un conjunto de flujos facti-bles para obtener un conjunto de presiones ópti-


Fig. 3. Proceso de reducción de G a G'.

Fig. 4. Tres tipos de operaciones de composición simples para

reducir un sistema de gas.

mas. Primero discretizamos el rango continuo delos límites de presión [pL, pU]. Asumimos que haym puntos discretizados denotados por p

i

1,…,pi

m,i∈V’, y sea ' ( , )kl k lg g p p

ij ij i j= si (p

i, p

j)ÎD

ij (factible)

y ( , )i j

klg p pij = ∞ (costo muy grande) en cualquier

otro caso (infactible). NDP reduce la red de n

compresores en otra equivalente de n-1compresores, mediante la combinación de doscompresores en uno equivalente. El método ini-cia con un sistema de |Ac| compresores y proce-de iterativamente hasta obtener un sistema de uncompresor que contiene la información óptimadel sistema completo basado en el principio deoptimalidad de la DP. Estas combinaciones pue-den darse de tres formas (figura 4).

(a) Combinando dos compresores conectadosen serie: si v∈V’ tiene exactamente dos arcos inci-dentes (u,v) y (v, t) en G’, entonces (u,v) y (v,t) sonreemplazados por un nuevo arco (u, t), donde su

función de consumo de combustible óptima estádada por { }min : 1,..., .

kl ks sl

ut uv vtg g g s m= + =

(b) Combinando dos compresores conectadosen serie, pero con un arco tipo “colgantes” tipoárbol: en este caso v∈V’ tiene más de dos arcosincidentes. Se toma el arco (v,t) que está suelto o“colgando” y (u,v). En este caso el arco (v,t) esremovido, y para el arco (u,v) la función de consu-mo de combustible óptima kl

uvg es actualizada por

{ }min : 1,..., .kl ls

uv utg g s m+ = Actualizaciones similaresaplican a los vecinos que salen de v, y el principioaplica también si un solo vecino de t es externo.

(c) Combinando dos estaciones compresorasen paralelo: si los arcos

1,..., , 1,

sa a s∀ > en G’ co-

nectan los nodos u, v∈V’, entonces estos arcosson reemplazados por un solo arco (u, v). La co-rrespondiente función de costos óptimos se cal-cula como

Básicamente, NDP consiste en observar el sis-tema de red y centrar el análisis en dos compresoresconectados, reemplazándolos por un solo elemen-to “virtual” que representa la configuración de ope-ración óptima de ambos compresores. Es perti-




Fig. 5. Procedimiento NDPTS bajo un esquema de TS.

nente hacer mención que estos dos compresoresconectados para combinarse pueden ser seleccio-nados de cualquier forma en el sistema, por loque la filosofía de recursividad de la DP clásicaadquiere un matiz no secuencial. Este proceso decombinación continúa ejecutándose iterativamen-te, reduce el número de elementos a combinar, yune dos a la vez hasta que el sistema no puedereducirse más. Esto sucede cuando ha quedadoexactamente un único elemento virtual, el cualcaracteriza íntegramente el desempeño óptimo delsistema completo de red. Se concluye así que elcosto óptimo incurrido en la configuración de ope-ración sobre todas las estaciones compresoras dela red es el mínimo valor dado por la última tablade costos “virtual”. Después, el conjunto óptimode las variables de presión puede obtenerse porun proceso simple de sustitución hacia atrás. Lacomplejidad computacional de este algoritmoNDP es , donde es el número máxi-mo de elementos discretizados dados por el rangode presión.

Heurística de la búsqueda tabú (TS)

En esta sección proponemos y describimos un pro-cedimiento heurístico de TS (mostrado en la figu-ra 5) con la implementación de una estrategia dememoria corta para resolver el PMCC sobre redescíclicas.

Las dos características principales de TS –y quelo distinguen de otras estrategias de búsqueda–son: 1) el uso de estructuras de memoria para es-capar de óptimos locales al “moverse” de una so-lución a otra; 2) el uso de una lista tabú (Tabu

List) para evitar ciclarse en la búsqueda cuandooscila entre los estados ya visitados.

El método TS parte del supuesto de que pue-de construirse un entorno para identificar solu-ciones adyacentes (llamadas típicamente “solucio-nes vecinas”) que puedan ser alcanzadas desde lasolución actual. Existen muchas maneras de defi-nir el entorno reducido de una solución. La mássencilla es etiquetar como tabú las soluciones pre-

viamente visitadas en un pasado cercano, conoci-da como memoria a corto plazo (short-term memory),la cual se basa en guardar en una lista tabú lassoluciones visitadas recientemente (recency).


El vecindario V(x) de una solución x se definecomo el conjunto de soluciones alcanzables des-de x mediante una ligera modificación de ∆

x

uni-dades en cada uno de sus componentes. Esto esdado por:

(8)

donde Nsize es el tamaño predefinido del vecinda-rio de x y ∆

x

cuenta para el tamaño de la malla aser construida.

Fig. 6. Componentes básicos de una solución factible del

NDPTS sobre una topología cíclica.

El espacio de búsqueda empleado por TS secaracteriza únicamente por las variables de flujox

ij, ya que, una vez fijadas, las variables de presión

pueden encontrarse por el algoritmo NDP demanera óptima. Nótese que, para una solucióndada, no almacenamos la solución completa, sinosólo el flujo a ser modificado en uno de los arcosdel ciclo. Así, en esencia, un estado dado se repre-senta por un vector x’=(x

a1,…,x

am), donde a

w

es unode los arcos del ciclo w seleccionado. El conjuntode arcos se selecciona de manera arbitraria, y elproceso de conversión de un flujo x a x’ (o vicever-sa) se logra mediante una simple actualización so-bre los arcos restantes del ciclo en cuestión. Deesta manera, la caracterización de x y x’ puede serusada arbitrariamente. De ahí que la mejor solu-ción x’∈V(x), la cual no es tabú, es seleccionada ysu subconjunto asociado se actualiza acordemente.

La lista tabú (TL) almacena los atributos re-cientemente usados, en nuestro caso, los valores

de x sobre el único arco atributo del ciclo selec-cionado. De esta forma, el tamaño de la lista tabú(tabu tenure) controla el número de iteraciones enlas que un atributo en particular permanece en lalista antes de poder volver a ser considerado. Fi-nalmente, la búsqueda TS termina al satisfacer elcriterio de parada establecido, el cual típicamentese basa en un número máximo (Iter_max) deiteraciones.

Experimentación, resultadosy discusión

El propósito del diseño y configuración de nues-tra base de datos de instancias del problema tieneun objetivo doble. Primero, es necesario para eldesarrollo eficiente de nuestra fase experimentaly, segundo, proveer un punto de referencia paralos diversos algoritmos encontrados en la biblio-grafía. En consecuencia, la construcción y elabo-ración de esta base de datos constituye una con-tribución importante de este trabajo.

Desde la perspectiva de la optimización en re-des, se han clasificado tres tipos de topologías dered: a) lineal o gun-barrel (figura 7), b) tipo árbol(figura 8) y c) cíclicas (figura 9).

En las figuras 7-9, un nodo rayado (mostradocon una flecha entrante a él) representa un nodosuministro, un nodo negro (mostrado con unaflecha saliente a él) es un nodo demanda, y unnodo blanco es simplemente un nodo de paso.Un arco dirigido con un trapezoide, uniendo dosnodos cualesquiera corresponde a una estacióncompresora, de otro modo es un ducto (tubería).

En la base de datos de prueba, un nombre net-x-mCn representa una instancia del tipo x∈{a, b,c}, con m nodos y n arcos compresores. Además,se añade un sufijo –Cy, donde y∈{1...9} identificauno de los nueve diferentes tipos de compresorescentrífugos utilizados en la industria. Esta base dedatos está disponible en: http://yalma.fime.uanl.mx/roger/ftp/, o directamente delos autores bajo petición. Cada una de las instan-cias está dada como un archivo de GAMS. GAMS




Fig. 7. Topología no cíclica: estructura lineal.

Fig. 8. Topología no cíclica: estructura lineal.

Fig. 9. Instancias de la base de datos de prueba que muestran

una estructura cíclica.

es un paquete de modelación algebraica, amplia-mente conocido y usado a nivel mundial, coninterfaz a varios métodos de optimización.

Los procedimientos, codificados en C++, hansido ejecutados en una estación de trabajo SunUltra 10, sobre una plataforma Solaris v.7, pro-piedad del Laboratorio de Cómputo de Alto Des-empeño de la División de Posgrado en Ingenieríade Sistemas de la UANL. Todos los datos relacio-nados con las estaciones compresoras fueron pro-

porcionados por una firma consultora de la in-dustria del gas natural.

Con respecto a los tamaños de la lista tabú ydel vecindario V(x), se realizaron diversos experi-mentos preliminares con valores de {5, 8, 10} y{20, 30, 40}, respectivamente. De ahí, en los ex-perimentos que aquí presentamos sobre una am-plia gama de instancias con diferentes configura-ciones cíclicas nosotros usamos los siguientes va-lores: Iter_max = 100, tamaño de discretización ∆

x

= 5 en V(x), tamaño de discretización ∆p = 20 para

las variables de presión, tamaño de lista tabú Ttenure

= 8, y tamaño Nsize

=20 del vecindario V(x).En primera instancia se realizó una compara-

ción entre nuestro método y el GRG, el cual em-plea una búsqueda local por gradiente. A estemétodo GRG le incluimos una estrategiamultiarranque para hacerlo aún mejor. Posterior-mente presentamos una comparación entre nues-tro método y el mejor algoritmo conocido exis-tente para resolver este tipo de problemas: el NDP.Como fase final de la experimentación, desafian-do aún más las soluciones obtenidas por elNDPTS, proveemos evidencia sobre la calidad delas soluciones reportadas mediante una compara-ción con una cota inferior desarrollada en este tra-bajo.

La tabla I muestra los resultados del análisiscomparativo entre el GRG y NDPTS aplicados ex-clusivamente sobre instancias con estructuras cí-clicas. Para este análisis se usó la implementacióndel GRG en Flores Villarreal y R.Z. Ríos-Merca-do,10 añadiendo una estrategia multiarranque. Estoes, dado que el GRG es básicamente un métodode búsqueda local, la idea fue aplicarlo con múlti-ples puntos iniciales, basándonos en un criteriode parada definido por la cantidad de tiempo queel NDPTS usó para encontrar su mejor soluciónpara las instancias de prueba en cuestión. En estatabla, la primera columna muestra las instanciasde prueba. La segunda columna muestra el núme-ro total de iteraciones empleadas por el GRG conmúltiples puntos iniciales, mientras que los me-jores valores de las funciones objetivos (en millo-


Tabla I. Comparación entre GRG y NDPTS.

nes), cuando una solución óptima pudo ser en-contrada por el GRG y el NDPTS, son mostradosen la cuarta y quinta columnas, respectivamente.La tercera columna muestra el tiempo de ejecu-ción (en segundos) de ambos métodos. La últimacolumna corresponde al mejoramiento relativo(RI) de nuestro procedimiento propuesto NDPTSsobre el GRG dado por

donde

Zg

denota el mejor valor de la funciónobjetivo encontrado por el método Z∈{GRG,NDPTS}.

En la tabla I puede observarse primero que elNDPTS obtuvo soluciones para todas las instan-cias de prueba, mientras que el GRG falló en cua-tro de éstas, esto es, para cuatro de las instanciasmás difíciles el GRG no pudo encontrar ningunasolución factible. Los resultados indican queNDPTS sobresalió también en términos de la ca-lidad de la solución al GRG. Por ejemplo, al ob-servar el RI obtenido, puede verse fácilmente queen las instancias donde ambos procedimientos en-contraron una solución óptima, el NDPTS obtu-vo soluciones significativamente de mejor calidadque las obtenidas por el GRG. En términos delesfuerzo computacional, ambos procedimientosemplearon la misma cantidad de tiempo en unrango de 270-400 segundos.

Tabla II Comparación entre NDP y NDPTS.

Ahora bien, la tabla II presenta los resultadosde la comparación de nuestro método NDPTScontra el NDP sobre las mismas instancias cíclicasque en el experimento anterior. La primera co-lumna de la tabla muestra las instancias de prue-ba, y las siguientes dos presentan los mejores ob-jetivos (en millones) encontrados por el NDP y elNDPTS, respectivamente. Así, el mejoramientorelativo (RI) de nuestro procedimiento propuestoNDPTS sobre el NDP es presentado en la últimacolumna.

Como podemos observar en la tabla II, elNDPTS reporta mejoras realmente muy significa-tivas en cuestión de la calidad que el NDP. Porejemplo, recordando que aún un mejoramientorelativo (RI) de 1% de la solución implicaría mi-llones de dólares ahorrados, puede verse fácilmen-te la contribución significativa del NDPTS al des-cubrir que sólo en una de las once topologías deprueba el RI fue menor a 1%. De esta manera,podemos ahora remarcar la superioridad delNDPTS sobre el NDP al encontrar mejoras entodas las instancias excepto una. Además, en seisde once casos el RI obtenido por nuestro métodofue mayor a 10%, percibiéndose inclusive hastamás de un 27% sobre una de las topologías másgrandes: net-c-19c7-C4. Estos resultados son en ver-dad de un altísimo impacto desde el punto devista económico.

Ahora bien, derivar cotas inferiores para un pro-blema como éste es una tarea que puede inclusive




Fig.10. Convergencia NDPTS en la instancia net-c-6c2-C5.

llegar a ser tan complicado como resolver el pro-blema original. Sin embargo, llevando a cabo unanálisis y estudio riguroso de la estructura y pro-piedades del modelo, podemos notar dos propie-dades muy importantes que pueden ser explota-das con el fin de poder aproximar esta cota infe-rior y medir así, de una manera más eficiente, lacalidad de nuestras soluciones. Primero, median-te una relajación del modelo matemático delPMCC, enfocándonos en la ecuación (4), el pro-blema llega a ser separable en cada estacióncompresora. Esto es, el problema relajado consisteen la optimización de cada arco compresor de mane-ra individual. No obstante, dado que el modelo per-manece como un problema no convexo, nosotros,como segunda fase, explotamos el hecho de que encada compresor el objetivo es una función dada porsólo por tres variables, así que construimos una mallatridimensional sobre estas tres variables como base yejecutamos una evaluación exhaustiva para encon-trar el óptimo global del problema relajado (parauna discretización especificada).

La tabla III muestra los resultados de la evalua-ción de la calidad de las soluciones NDPTS con-tra las cotas inferiores (LB). La primera columnamuestra las instancias de prueba, la segunda y ter-cera columnas muestran la cota inferior y el mejorvalor encontrado por la heurística, respectivamen-te, y la última columna muestra la distancia relati-va (GAP) al óptimo global obtenida por el NDPTS.Como podemos observar en la tabla, todas lasinstancias probadas tienen una distancia óptimarelativa de menos de 7%, donde para siete de ellaspudo observarse estar a menos de 10% del ópti-mo global, y aún mejor, tres de estas once instan-cias estuvieron a menos de 1% del óptimo. Estodemuestra la capacidad y efectividad de nuestraaproximación propuesta.

El cálculo de esta cota es también una contri-bución científica notable, ya que es la primera vezque se reporta en más de 40 años de investigaciónen este campo.

Finalmente, la convergencia del algoritmoNDPTS sobre la instancia de prueba net-c-6c2-C5

Tabla III. Calidad de la solución NDPTS por cotas inferiores.

se muestra en la figura 10. En ella puede observar-se cómo en algunas iteraciones, la solución puedellegar a deteriorarse para después mejorar hacia unasolución más fuerte, ilustrando que quedarse es-tancado en un óptimo local es sobrellevado demanera efectiva por el mecanismo TS. Típicamen-te se observó que para todas las instancias la solu-ción no mejora más allá de las primeras 50-60iteraciones.

Conclusiones y recomendaciones

En este trabajo hemos propuesto una heurísti-ca híbrida basada en NDP y TS para un problemamuy importante y a la vez difícil surgido de la in-dustria de gas natural. El procedimiento NDPTSpropuesto, basado en una estrategia que integratécnicas avanzadas como DP no secuencial y TScon un mecanismo de memoria corta, demostróser muy eficiente en el trabajo experimental, cuan-


do al aplicarse sobre un gran número de instan-cias con datos reales tomados de la industria fuecapaz de obtener soluciones de mayor calidad queaquéllas entregadas por los métodos anteriores(GRG multiarranque y NDP). Además, la maneraen la que el método opera claramente producemejores soluciones que aquéllas encontradas porel método NDP de Carter, el cual era hasta elmomento, el referente a nivel mundial en la reso-lución de problemas de este tipo. Por ende, lamayor contribución científica del trabajo es elproveer un método de resolución que obtienensoluciones de mucha mejor calidad que el mejormétodo reportado previamente. Como se mos-tró, las mejoras obtenidas por nuestro métodofueron dramáticas, alcanzando en algunos casoshasta más de 27% de mejora. Otra aportación cien-tífica del trabajo fue el desarrollo y evaluación deun esquema de acotamiento inferior para evaluarla calidad de las soluciones reportadas por losmétodos de optimización. Éste es el primer es-quema de acotamiento desarrollado en más de 40años de investigación en este campo, lo cual lohace bastante notable. La evaluación numérica dela cota permitió verificar la alta calidad de las so-luciones reportadas por el NDTPS. Finalmente,una tercera contribución fue la elaboración de unacolección de conjuntos de datos que constituyeun punto de referencia en trabajos posteriores parael resto de la comunidad científica que labora enesta área. Como resultado global, esta investiga-ción se ha convertido ya en un avance significativoal estado del arte en este campo de la ciencia.

Hay aún muchas áreas que proponen impor-tantes desafíos desde la perspectiva de la optimiza-ción. Por ejemplo, el procedimiento propuestoes una búsqueda tabú básica con memoria corta,de ahí que pudiera ser interesante incorporar es-trategias más sofisticadas del TS, como intensifi-cación o diversificación. Además, uno de los desa-fíos más grandes en la industria del gas natural eslidiar con sistemas dependientes del tiempo, esdecir, con problemas mucho más complejos des-de la perspectiva de la modelación, tal como los

modelos transientes. Hemos visto algunos esfuer-zos preliminares en esta dirección, pero induda-blemente que este tema constituye el reto de ma-yor envergadura en el campo.

Agradecimientos

Este trabajo de investigación fue apoyado por elConsejo Nacional de Ciencia y Tecnología (Co-nacyt, proyecto J33187-A) y por la UniversidadAutónoma de Nuevo León, bajo su Programa deApoyo para la Investigación Científica y Tecnoló-gica (UANL-Paicyt, proyecto CA820-04).

Resumen

En este trabajo nos enfocamos al problema decalcular planes óptimos de transportación de gasnatural mediante compresores instalados en siste-mas cíclicos. Este problema no lineal (no convexo)considera dos tipos de variables continuas: flujomásico en cada arco y presión en cada nodo. Loscompresores consumen combustible dependien-do de la configuración del flujo y presión, así elproblema es asignar valores que minimicen el com-bustible total consumido. Aquí proponemos unatécnica híbrida que integra la programación diná-mica no secuencial dentro de una estrategia debúsqueda tabú con memoria corta. Evidenciaempírica demuestra el tremendo impacto del al-goritmo, superando contundentemente a los me-jores métodos conocidos a la fecha.

Palabras clave: Gas natural, Red cíclica, Compre-sor, Programación dinámica, Búsqueda tabú.

Abstract

In this work, we address the problem of comput-ing optimal transportation plans of natural gas bycompressors installed in cyclic networks. This non-linear (non-convex) problem considers two typesof continuous decision variables: mass flow ratethrough each arc, and gas pressure level at each



node. Since compressors consume fuel at ratesdepending on flow and pressure, the problem isto assign values that minimize the total fuel cost.We propose a hybrid technique integrating non-sequential dynamic programming within a short-

term memory tabu search strategy. Empirical evi-dence shows the tremendous impact of the pro-posed algorithm, outperforming significantly thebest solution methods known to date.

Keywords: Natural gas, Cyclic-network, Compres-sor, Dynamic programming, Tabu search.

Referencias

1. R. Horst, P.M. Pardalos y N.V. Thoai.Introduction to Global Optimization.Kluwer, Dordrecht, Holanda, 1995.

2 R. Bellman. Dynamic Programming. Prince-ton University Press, Princeton, EUA. 1957.

3 F. Glover y M. Laguna. Tabu Search. Kluwer,Boston, EUA, 1997.

4 R.G. Carter. Pipeline optimization: Dynamicprogramming after 30 years. En Proceedingsof the 30th PSIG annual meeting, Denver,EUA, 1998.

5 A.J. Osiadacz. Simulation and Analysis of GasNetworks. Gulf Publishing Company,Houston, EUA, 1987.

6 S. Kim, R.Z. Ríos-Mercado y E.A. Boyd. Aheuristic for minimum cost steady-state gastransmission networks. En Proceedings of the25th International Conference on Compu-ters & Industrial Engineering, New Orleans,EUA, 1999.

7 Wu, R.Z. Ríos-Mercado, E.A. Boyd y L.R.Scott. Model relaxations for the fuel costminimization of steady-state gas pipelinenetworks. Mathematical and ComputerModelling, 31(2-3):197-220, 2000.

8 J.T. Jefferson. Dynamic programming. Oil andGas Journal, pp. 102-107, 1961.

9 P.J. Wong y R.E. Larson. Optimization ofnatural-gas pipeline systems via dynamicprogramming. IEEE Transactions onAutomatic Control, AC-13(5):475-481, 1968.

10 H.J. Flores-Villarreal y R.Z. Ríos-Mercado.Computational experience with a GRGmethod for minimizing fuel consumption oncyclic natural gas networks. En N. E.Mastorakis, I. A. Stathopulos, C.Manikopoulos, G. E. Antoniou, V. M.Mladenov e I. F. Gonos (editores), Computa-tional Methods in Circuits and SystemsApplications, pp. 90-94, WSEAS Press, Ate-nas, Grecia, 2003.

11 C. Borraz-Sánchez y R.Z. Ríos-Mercado. A non-sequential dynamic programming approachfor natural gas network optimisation. WSEASTransactions on Systems, 3(4):1384-1389,2004.

12 R.Z. Ríos-Mercado, S. Wu, L.R. Scott y E.A.Boyd. A reduction technique for natural gastransmission network optimization problems.Annals of Operations Research, 117(1-4):217-234, 2002.

Recibido: 16 de agsoto de 2009

Aceptado: 10 de septiembre de 2009


técnicas avanzadas de optimización en sistemas de ...también se deriva un esquema de acotamiento...

Documents