PONTIFICIA UNIVERSIDAD CATOLICA DE CHILE

ESCUELA DE INGENIERIA

PLANIFICACION DE REDES DE

DISTRIBUCION: APROXIMACION VIA

CLUSTERING, DIAGRAMAS DE

VORONOI Y BUSQUEDA TABU

ALEJANDRO ANDRES NAVARRO ESPINOSA

Tesis para optar al grado de

Magíster en Ciencias de la Ingeniería

Profesor Supervisor:

HUGH RUDNICK VAN DE WYNGARD

Santiago de Chile, diciembre, 2007

2007, Alejandro Andrés Navarro Espinosa

PONTIFICIA UNIVERSIDAD CATOLICA DE CHILE

ESCUELA DE INGENIERIA

PLANIFICACION DE REDES DE DISTRIBUCION: APROXIMACION VIA

CLUSTERING, DIAGRAMAS DE VORONOI Y BUSQUEDA TABU

ALEJANDRO ANDRES NAVARRO ESPINOSA

Tesis presentada a la Comisión integrada por los profesores:

HUGH RUDNICK

DAVID WATTS

RODRIGO PALMA

HECTOR JORQUERA

Para completar las exigencias del grado de

Magíster en Ciencias de la Ingeniería

Santiago de Chile, diciembre, 2007

ii

Al que resiste y lucha

iii

AGRADECIMIENTOS

Dar las gracias, ennoblece dicen algunos, mas yo quisiera señalar que las gracias son sólo la

consecuencia a posteriori de un acto muy superior en nobleza y entrega, que convierte al

agradecimiento únicamente en forma y resultado, toda vez que el contenido y causa de las

gracias, es que alguien quiso renunciar a su tiempo y a sus recursos, para entregárselos a

otro, desinteresadamente y sin presión alguna, son ellos y su voluntad, los que han hecho

posible este trabajo. Ejemplo de ello es Chilectra, que proporcionó datos referenciales sobre

su zona de concesión, lo cual constituyó un aporte importante e imprescindible en el

correcto desarrollo de este desafío.

En suma, las siguientes líneas teóricas y técnicas presentan algo más que un problema

complejo, algo más que una investigación, lo que hay es una construcción colectiva de

entrega y ayuda. Agradezco entonces, en estas líneas que habrán de perdurar tanto como la

infinitud de mis agradecimientos, a mi familia, por enseñarme a soñar, a mi colegio, el

Colegio San Viator, por mostrarme la posibilidad de los sueños, a la Fundación Juan Pablo

II, por hacer posible el sueño de muchos, a mis amigos y a la oficina 303, por compartir

nuestros sueños y a veces la ausencia de ellos, y finalmente a Hugh Rudnick, el profesor,

sin el cual despertar hubiese sido un hecho.

INDICE GENERAL

Pág.

DEDICATORIA .......................................................................................................... ii

AGRADECIMIENTOS .............................................................................................. iii

INDICE DE TABLAS ............................................................................................... vii

INDICE DE FIGURAS............................................................................................... ix

RESUMEN................................................................................................................. xii

ABSTRACT.............................................................................................................. xiii

1. INTRODUCCION.............................................................................................. 1

1.1 Planificación de Sistemas de Distribución de Energía Eléctrica ............... 1

1.2 Planteamiento del Problema....................................................................... 2

1.3 Objetivo...................................................................................................... 4

1.4 Estructura de la Tesis ................................................................................. 4

2. ESTADO DEL ARTE Y EVOLUCION ............................................................ 7

2.1 Programación Matemática ......................................................................... 7

2.1.1 Planificación de subestaciones ........................................................ 8

2.1.2 Planificación de redes ...................................................................... 9

2.1.3 Planificación conjunta de subestaciones y redes ........................... 10

2.2 Técnicas Meta-heurísticas........................................................................ 12

2.2.1 Planificación con sistemas expertos .............................................. 13

2.2.2 Planificación con intercambio de ramas ........................................ 13

2.2.3 Planificación con temple simulado (Simulated Annealing)........... 15

2.2.4 Planificación con búsqueda tabú (Tabu Search) ........................... 15

2.2.5 Planificación con colonias de hormigas (Ant Colony System)....... 16

2.2.6 Planificación con algoritmos evolutivos........................................ 17

3. METODOLOGIA DESARROLLADA ........................................................... 20

3.1 Antecedentes Generales ........................................................................... 20

3.2 Breve Explicación de la Metodología Desarrollada................................. 24

3.3 ¿Cómo abordar el problema? ................................................................... 24

4. PROCESO DE MICRO-OPTIMIZACION...................................................... 31

4.1 Descripción General................................................................................. 31

4.2 Análisis de Cluster ................................................................................... 32

4.3 Metodología de Micro-Optimización....................................................... 36

4.3.1 Etapa previa: determinación de la red vial .................................... 40

4.3.2 Ubicación y asignación de los transformadores ............................ 47

4.3.3 Trazado de red ............................................................................... 49

4.3.4 Selección óptima de conductores................................................... 56

4.3.5 Cálculo de pérdidas de energía ...................................................... 62

4.3.6 Iteraciones y resultados.................................................................. 67

5. PROCESO DE MACRO-OPTIMIZACION .................................................... 76

5.1 Macro-Optimización Vía Diagramas de Voronoi .................................... 76

5.1.1 Diagramas de Voronoi ................................................................... 77

5.1.2 Procedimiento de optimización vía Voronoi ................................. 79

5.2 Macro-Optimización Vía Búsqueda Tabú ............................................... 91

5.2.1 Triangulación de Delaunay............................................................ 92

5.2.2 Resolución mediante vecindarios .................................................. 96

5.2.3 Resolución mediante búsqueda tabú............................................ 101

5.3 Macro-Optimización: Unión Diagramas de Voronoi y Búsqueda Tabú 107

6. PLANIFICACION OPTIMA DEL GRAN SANTIAGO............................... 109

6.1 Aplicación del Proceso de Micro-Optimización .................................... 109

6.2 Aplicación del Proceso de Macro-Optimización ................................... 112

6.2.1 Metodología basada en diagrama de Voronoi ............................. 115

6.2.2 Metodología simplificada basada en diagrama de Voronoi......... 117

6.2.3 Metodología basada en vecindarios............................................. 119

6.2.4 Metodología basada en búsqueda tabú y único vecindario ......... 121

6.2.5 Metodología secuencial Voronoi-búsqueda tabú......................... 123

7. CONCLUSIONES Y TRABAJOS FUTUROS ............................................. 125

7.1 Conclusiones .......................................................................................... 125

7.2 Trabajos Futuros..................................................................................... 130

BIBLIOGRAFIA ..................................................................................................... 133

A N E X O S ............................................................................................................ 141

Anexo A: Complejidad Algorítmica ........................................................................ 142

Anexo B: Descripcion de Meta-heurísticas.............................................................. 145

B.1 Algoritmos Genéticos............................................................................. 147

B.2 Temple Simulado (Simulated Annealing) .............................................. 149

B.3 Colonias de Hormigas ............................................................................ 151

B.4 Búsqueda Tabú....................................................................................... 154

Anexo C: Analisis de Cluster................................................................................... 155

C.1 Métodos Jerárquicos............................................................................... 155

C.2 Métodos de Partición.............................................................................. 156

Anexo D: Costo de Conductores y Transformadores .............................................. 159

Anexo E: Aplicacion Proceso de Micro-Optimización............................................ 161

Anexo F: Costo Mínimo en la Optimzación de una Mini-Zona .............................. 168

Anexo G: Resultados de la Micro-Optimización ..................................................... 170

Anexo H: Resultados Aplicación Gran Santiago ..................................................... 171

vii

INDICE DE TABLAS

Pág.

Tabla 4.1: Evolución de la distorsión en el caso de ejemplo ..................................... 34

Tabla 4.2: Menor distorsión por número de lanzamientos......................................... 47

Tabla 4.3: Resultado selección óptima de conductores ............................................. 62

Tabla 4.4: Variación del costo total con la búsqueda................................................. 70

Tabla 4.5: Efecto del equilibrio de red....................................................................... 72

Tabla 4.6: Confiabilidad del algoritmo ...................................................................... 74

Tabla 5.1: Aplicación diagrama de Voronoi .............................................................. 87

Tabla 5.2: Aplicación diagrama de Voronoi al caso simplificado ............................. 90

Tabla 5.3: Ahorro v/s número de combinaciones con cota en 300 kVA ................... 99

Tabla 5.4: Ahorros por la recombinación de redes .................................................. 101

Tabla 6.1: Micro-optimización del gran Santiago.................................................... 111

Tabla 7.1: Metodologías de macro-optimización sobre Santiago............................ 127

Tabla D.1: Listado de transformadores, capacidades y precios ............................... 159

Tabla D.2: Listado de conductores de cobre desnudo.............................................. 159

Tabla D.3: Listado de conductores de aluminio desnudo ........................................ 160

Tabla D.4: Listado de conductores de aluminio preensamblado ............................. 160

Tabla E.1: Evolución de la función de costo total ................................................... 165

Tabla G.1: Simulaciones equilibrio de red............................................................... 170

viii

Tabla G.2: Evolución de la solución para distintos tamaños de mini-zonas............ 170

Tabla H.1: Micro-optimización del gran Santiago - parte I ..................................... 171

Tabla H.2: Micro-optimización del gran Santiago - parte II.................................... 171

ix

INDICE DE FIGURAS

Pág.

Figura 1.1: Estructura de la tesis .................................................................................. 6

Figura 3.1: Ejemplo 10 nodos .................................................................................... 26

Figura 3.2: Triangulación de Delaunay para el ejemplo de 10 nodos........................ 26

Figura 3.3: Ubicación de los consumos comuna de Macul........................................ 28

Figura 3.4: Diagrama simplificado del algoritmo propuesto ..................................... 30

Figura 4.1: División en mini-zonas............................................................................ 32

Figura 4.2: Ejemplo de aplicación de k-means .......................................................... 35

Figura 4.3: Proceso de micro-optimización para una mini-zona ............................... 37

Figura 4.4: Trazado vial para una mini-zona ............................................................. 41

Figura 4.5: Asignación de los consumos a una calle ................................................. 43

Figura 4.6: Componentes conexas de la red vial........................................................ 46

Figura 4.7: Árbol de mínima expansión..................................................................... 51

Figura 4.8: Trazado de la red de baja tensión ............................................................ 53

Figura 4.9: Equilibrio de red ...................................................................................... 55

Figura 4.10: Efecto de la inclusión del equilibrio en la optimización ....................... 72

Figura 4.11: Costo y tiempo total v/s tamaño de la mini-zona .................................. 75

Figura 5.1: Diagrama de Voronoi para 30 centros..................................................... 78

Figura 5.2: Diagrama de Voronoi para la comuna de Macul..................................... 81

x

Figura 5.3: Identificación zonas interiores diagrama de Voronoi.............................. 82

Figura 5.4: Identificación y cierre de polígonos con vértices exteriores ................... 83

Figura 5.5: Envolvente convexa de los centros generadores ..................................... 85

Figura 5.6: Diagrama de Voronoi para una solución de la micro-optimización........ 86

Figura 5.7: Diagrama de Voronoi generado por transformadores de 300 kVA......... 88

Figura 5.8: Desventaja de la división en mini-zonas ................................................. 91

Figura 5.9: Ejemplo de la triangulación de Delaunay................................................ 93

Figura 5.10: Aumento de la triangulación producto del aumento en la entrada ........ 95

Figura 5.11: Posibilidad de combinación de redes................................................... 104

Figura 5.12: Configuración de redes producto de la micro-optimización ............... 106

Figura 5.13: Configuración de redes producto de la macro-optimización............... 107

Figura 5.14: Configuración de redes luego de la macro-optimización secuencial .. 108

Figura 6.1: División en mini-zonas del gran Santiago............................................. 110

Figura 6.2: Redes del caso base: micro-optimización.............................................. 114

Figura 6.3: Diagrama de Voronoi aplicado a Santiago ............................................ 117

Figura 6.4: Creación de vecindarios para la recombinación de redes...................... 120

Figura 6.5: Triangulación de Delaunay para Santiago............................................. 122

Figura B.1: Comportamiento de las hormigas ......................................................... 152

Figura E.1: Ubicación de consumos en una mini-zona............................................ 161

Figura E.2: Trazado de calles y asignación de consumos........................................ 162

xi

Figura E.3: Ubicación y red inicial .......................................................................... 163

Figura E.4: Ubicación y red del primer mínimo encontrado ................................... 164

Figura E.5: Ubicación y red en la última iteración .................................................. 165

Figura E.6: Evolución de la función objetivo .......................................................... 166

Figura E.7: Equilibrio de la red óptima.................................................................... 166

Figura F.1: Ejemplos de la evolución del costo total ............................................... 169

xii

RESUMEN

La planificación de la distribución eléctrica considerando como input sólo la ubicación y

proyección de la demanda de los consumos, es clave en aquellos mercados en que la

distribución está regulada mediante el esquema de empresa modelo, donde las tarifas son

fijadas de acuerdo a una empresa ficticia óptima, que abastece la misma zona de concesión

de la empresa regulada.

En la presente tesis, se analiza lo referente a la optimización de la red de baja tensión

partiendo desde cero (Greenfield planning), así se propone un procedimiento del tipo

“Dividir y Conquistar”, en que la zona a planificar es dividida en mini-zonas, y a cada una

de ellas se les aplica un procedimiento de optimización, con uso intensivo de clustering,

cuyo acierto es considerar en forma acoplada la ubicación y capacidad de los

transformadores con la red asociada, optimizando también su topología y los conductores

que la componen.

Sin embargo tal división es arbitraria, para perfeccionarlo se realizaron dos familias de

metodologías, una que busca realizar una mejor partición, basada en los diagramas de

Voronoi, en que la ubicación de ciertos transformadores representan los puntos generadores

para los polígonos de Voronoi, logrando mini-zonas irregulares y optimizando cada una de

ellas, y la otra basada en la posibilidad que redes vecinas puedan ser unidas en una misma

red siempre y cuando tal unión genere ahorros, dada la gran cantidad de variables, dicha

construcción es realizada utilizando búsqueda tabú.

La metodología final es una combinación secuencial de ambas, realizando primero una

adecuada fragmentación, para luego optimizar cada mini-zona irregular y finalmente

analizar la posibilidad de unión entre ellas. Obteniendo una metodología que permite

resolver la planificación desde cero para una zona de gran tamaño, la que finalmente es

aplicada sobre la ciudad de Santiago, proceso que entrega como resultado 7.686

transformadores de distribución con una capacidad instalada de 2.625 MVA, con una red de

distribución de baja tensión de 8.935 km.

xiii

ABSTRACT

Electrical distribution planning, considering only the location and the projection of

consumption’s demands as inputs, is crucial in those markets in which the distribution is

regulated based on the “model firm” scheme, where prices are set by an optimal fictitious

company that supplies the same concession zone than the regulated company.

In this thesis, the low tension network optimization is analyzed starting from zero

(Greenfield planning), and a “divide and conquer” procedure is utilized. In this method, the

planning zone is divided into mini-zones and an optimization procedure is applied to each

one of them with intensive use of clustering. The relevant achievement is the coupled

solution of the transformer location and sizing, with the associated optimization of the

network topology and its conductors.

Nevertheless such division is arbitrary and two families of methodologies were developed

to improve it. The fist one tries to make a better partitioning process, based on Voronoi’s

diagrams, where the location of particular transformers represents the generating points for

the Voronoi’s polygons, obtaining irregular mini-zones and optimizing each one of them.

The second method takes advantage of the possibility that neighboring networks can be

combined in a single network, as long as such union generates savings. Given the large

number of variables of this structure, it is solved using “Tabu Search”.

The final methodology is a sequential combination of both, making in the first place an

adequate fragmentation, then optimizing each irregular mini-zone, and finally analyzing the

possibility of unions among them. A methodology is finally developed, able to resolve the

Greenfield planning for a large scale zone, finally applying it over the city of Santiago,

giving a solution with 7,686 distribution transformers with an installed capacity of 2,625

MVA, and a low tension distribution network of 8,935 km.

1

1. INTRODUCCION

1.1 Planificación de Sistemas de Distribución de Energía Eléctrica

En la cadena de suministro de energía eléctrica es posible distinguir tres grandes

segmentos, encargados cada uno de ellos de una labor clara y definida, el segmento de la

generación es el responsable de transformar la energía proveniente de diversas fuentes,

tales como combustibles, viento, biomasa, agua, fusión nuclear, en energía eléctrica, en

tanto el segmento de la transmisión es el encargado de transportar grandes bloques de

energía desde los centros de generación hacia los centros de consumo. Finalmente, el

segmento de la distribución es el encargado de repartir la energía entre los usuarios finales,

ya sean estos residenciales, comerciales o industriales, por tanto constituye el segmento

más cercano al cliente y por ende está bajo la evaluación constante de los consumidores,

quienes no pueden cambiarse de compañía distribuidora, producto que este segmento

constituye un monopolio natural.

El monopolio natural se produce cuando es más eficiente que exista sólo una empresa

operando en una determinada zona, que varias empresas operando en la misma, ello dado

que su función de costos es subaditiva para el rango de demanda que satisface (Berg y

Tschirhart, 1988), en términos simples, en el negocio de distribución, el costo de satisfacer

a un cliente cuando se suministra a muchos clientes a la vez, es más bajo que cuando se

satisface a un único cliente, fenómeno conocido como economías de densidad. La

existencia de tal monopolio, requiere una regulación por parte del estado, de manera que la

empresa regulada remunere adecuadamente su actividad, y así tenga los incentivos para

seguir operando, y los consumidores reciban un adecuado nivel de servicio.

En Chile, la regulación empleada es por “empresa modelo”, esto significa que la empresa

en cuestión es remunerada no de acuerdo a sus costos reales, sino que de acuerdo al costo

eficiente de una empresa ficticia que cubriría la misma zona de concesión, la cual debe

estar óptimamente diseñada tanto en su gestión como en su política de inversiones, de

manera de estar siempre adaptada a la demanda y cumplir las normativas vigentes de

calidad y seguridad de servicio. Para tal diseño, se considera que la construcción de la

2

empresa modelo se realiza desde cero, esto es, la empresa eficiente considera únicamente la

ubicación y demanda actual y proyectada de los consumos, de manera de no incluir en su

diseño, ninguna de las ineficiencias que podría tener la empresa que está siendo regulada.

Con este tipo de regulación, la empresa real sólo obtendrá rentabilidad si es capaz de

comportarse igual o mejor que la empresa modelo en sus gastos de inversión y operación,

lo que genera incentivos a gestionarse de manera racional y eficiente.

De lo anterior se desprende que la fijación tarifaria comprende dos aristas bien definidas,

por un lado está la optimización de la gestión, vale decir de aquellos costos relacionados

con la administración, facturación y atención al cliente, y por otro, se encuentra la

optimización de las inversiones, localización y tamaño de subestaciones y transformadores,

trazado de la red y tipo de conductores utilizados, es decir la planificación óptima de la red,

lo que constituye un aliciente importante para el desarrollo de la presente tesis.

Se debe señalar que en los sistemas de distribución es posible distinguir dos sistemas

relacionados, uno de media tensión, que es el encargado de comunicar las subestaciones

primarias con los transformadores de distribución y uno de baja tensión que comunica

dichos transformadores con los consumidores finales, siendo por tanto, este último el que

debe abastecer a un gran número de consumos. En el presente trabajo se aborda el problema

exclusivo de la planificación en baja tensión, el cual como se verá en el siguiente apartado,

por sí mismo representa un problema complicado y desafiante.

1.2 Planteamiento del Problema

En este trabajo se busca responder a la planificación óptima de las inversiones, no sólo por

su importancia regulatoria, sino también por la complejidad del problema, el cual, en

términos generales, consiste en abastecer un conjunto de nodos, identificados por su

demanda y por su ubicación espacial, para lo cual se debe determinar el trazado de la red y

el tipo de conductores a utilizar, la ubicación y tipo de transformadores, a fin de minimizar

los costos de inversión para un horizonte de tiempo determinado, cumpliendo las

restricciones de regulación de tensión y radialidad de la red. De lo cual se desprende el

carácter combinatorio del problema, con presencia de variables enteras, relacionadas con

las decisiones de inversión, como por ejemplo, número entero de transformadores,

3

instalación o no de un transformador en una posición determinada, entre otros, y variables

continuas relacionadas con los flujos eléctricos y regulación de tensión. Resumiendo, la

formulación global del problema sería la siguiente:

{ }min transformadores conductores pérdidasCInv CInv C+ +

Sujeto a

• Abastecer la totalidad de la demanda.

• Cumplir la regulación de tensión.

• Existencia de un conjunto discreto de conductores.

• Existencia de un conjunto discreto de transformadores.

• Realizar un trazado radial de la red.

• Respetar las zonas prohibidas de paso.

Se debe señalar que la planificación de la red de baja tensión, junto con ser un problema de

optimización combinatorial, representa un problema del tipo NP-completo1 (Garey y

Jonson, 1979), esto es que el orden de crecimiento del algoritmo para encontrar la solución

no está acotado por un polinomio de orden n, de hecho en la actualidad todos los algoritmos

conocidos para problemas NP-completos utilizan tiempo exponencial con respecto al

tamaño de la entrada. Con lo cual para resolverlo en un tiempo razonable, se requieren

realizar simplificaciones en las restricciones y/o planteamiento del problema, o buscar

métodos alternativos que permitan encontrar una buena solución (Gonen y Ramírez-

Rosado,1986, Khator y Leung, 1997). En particular, el problema aquí señalado, ha tratado

de ser resuelto mediante técnicas de programación matemática, con bastantes

simplificaciones que permiten su convergencia (Adams y Laugton, 1974, Ponnavaikko et.

al.,1987, Gonen y Foote, 1981, Youssef y Hackman, 1988, Ramírez-Rosado y Gonen,

1991, Paiva et. al. 2005) y en los últimos años mediante técnicas meta-heurísticas, tales

como intercambio de rama, algoritmos genéticos, algoritmos basados en el comportamiento

de las colonias de hormigas, entre otros (Hsu y Chen, 1990, Nara et al. 1992, Miranda et. al.

1 Para mayor información referirse al anexo A dedicado a la complejidad algorítmica.

4

1994, Goswami 1997, Míguez et. al 2002, Gómez et. al. 2004, Ramírez-Rosado y

Domínguez-Navarro, 2006). No obstante, en ellos no se realiza la optimización de gran

tamaño (más de 500.000 nodos), ni la optimización conjunta de la localización y capacidad

de transformadores con la red asociada, situaciones que en este trabajo serán consideradas.

1.3 Objetivo

Esta investigación busca contribuir al mejoramiento de los instrumentos de regulación con

miras a incentivar la eficiencia económica en el negocio de distribución de energía

eléctrica. A través de una metodología que:

a) Permita obtener la planificación desde cero para la red de distribución de baja

tensión.

b) Considere el análisis acoplado entre localización y capacidad del

transformador con su red de baja tensión asociada.

c) Sea aplicable a una red de gran tamaño.

1.4 Estructura de la Tesis

El trabajo es organizado de la siguiente manera, figura 1.1, en el primer capítulo se entrega

una visión de la importancia tanto regulatoria como técnica de la planificación de los

sistemas de distribución, además de presentar los antecedentes que describen al problema y

a su particular dificultad, mostrando que aspectos del mismo serán considerados en este

trabajo.

En el segundo capítulo se entrega una breve reseña sobre el estado del arte en la materia,

mostrando brevemente la bibliografía revisada y la evolución que ha tenido la forma de

abordar el problema, tanto en la incorporación de variables adicionales como en las nuevas

metodologías planteadas para su solución.

El tercer capítulo muestra los antecedentes de la metodología propuesta, planteando los

desafíos a resolver y los principales supuestos que se asumieron para realizarlos, además de

presentar en términos generales los elementos básicos de dicha metodología.

Posteriormente en el capítulo cuatro y cinco se presentan dos elementos claves del

procedimiento propuesto, que dicen relación con la optimización de zonas pequeñas y la

5

integración de ellas en zonas mayores respectivamente, explicando en detalle cada una de

las partes del algoritmo, y mostrando en cada etapa las decisiones que se tuvieron que

adoptar y los antecedentes en virtud de las cuales se tomaron. Se aplica, cada etapa a un

escenario real, constituido por los consumos de una comuna de la región metropolitana,

Macul, constituida por 20.215 consumos distribuidos en una superficie 12,9 de kilómetros

cuadrados.

En el capítulo seis se aplicarán las mejores prácticas obtenidas de la aplicación del modelo

a la comuna de Macul, en un problema de gran tamaño, dado por la totalidad de la región

Metropolitana, constituida por cerca de 1.300.000 consumos distribuidos en una superficie

de 2.118 kilómetros cuadrados.

Finalmente, en el capítulo siete se presentan las conclusiones del trabajo y los desafíos

futuros relacionados con la planificación de sistemas de distribución.

6

Figura 1.1: Estructura de la tesis

7

2. ESTADO DEL ARTE Y EVOLUCION

Este capítulo pretende entregar una visión del estado del arte en la planificación de los

sistemas de distribución, mostrando la evolución de los algoritmos empleados, con hincapié

en las restricciones consideradas y aplicabilidad en sistemas reales.

Es necesario reiterar la complejidad del problema a resolver (NP-completo) para el cual

resulta imposible encontrar una solución óptima, que no sea sino a través de la evaluación

completa de todos los posibles resultados, lo cual en un ejercicio de planificación es

imposible, dado el elevado número de variables y combinaciones a considerar, por ejemplo,

consideremos un problema con 100 variables binarias, esto es un espacio de búsqueda de

1002 , es decir 1,26 x 1030 combinaciones posibles. Suponiendo que en evaluar cada

combinación, optimistamente se toma 1 femto-segundo, se requeriría algo así como 40

millones de años en encontrar la solución, por tal razón, los algoritmos que se han

propuesto hasta la fecha, incluyendo el desarrollado en este trabajo, buscan encontrar una

buena solución, lo que no constituye una merma en la calidad, profundidad e importancia

de las investigaciones, sino que simplemente, constituyen una aproximación a la correcta

solución del problema. Es en este sentido, dada la imposibilidad de encontrar el óptimo,

que existen muchos trabajos que intentan dar respuesta al problema, los cuales se pueden

clasificar en dos grandes grupos, aquellos que buscan la solución mediante programación

matemática y aquellos que tratan de hacerlo por medio de vías meta-heurísticas.

2.1 Programación Matemática

La programación matemática también conocida como optimización matemática, busca

resolver problemas de maximización y/o minimización de funciones, sujetas a restricciones,

encontrando siempre la solución óptima, toda vez que ésta solución exista, mediante la

utilización de herramientas matemáticas, entre las que se pueden mencionar branch and

bound, programación dinámica, planos cortantes, etc. Tal como se señala en el comienzo

del trabajo, la complejidad del problema hace que este tipo de algoritmos no pueda resolver

el problema real y por tanto, tenga que abordar relajaciones del mismo, ya sea relajando la

función objetivo, por ejemplo separando el problema de la instalación de transformadores

8

con el problema de trazado y optimización de la red, o relajando las restricciones del

problema, tales como linealización de costos de red, simplificaciones en el flujo de

potencia, no consideración de las pérdidas, por mencionar algunas.

A continuación se presentará una clasificación de algunas de las investigaciones realizadas

en la materia, a fin de vislumbrar la evolución tanto en la metodología como los supuestos

empleados. La agrupación se realizará de acuerdo al tipo de problema que resuelven, ya sea

planificación de subestaciones y/o transformadores de distribución, planificación de redes y

finalmente planificación conjunta de redes y centros de transformación, en cada sección se

seguirá la evolución histórica de los mismos.

2.1.1 Planificación de subestaciones

Este apartado dice relación con la instalación de transformadores y subestaciones, así como

la ampliación de la capacidad de estas últimas. Los primeros algoritmos consideraban un

pequeño número de subestaciones y además requerían como entrada la ubicación de sus

posibles posiciones. Entre los primeros que abordan el problema de aumento de capacidad

de subestaciones está Masud (1974), quien además de determinar la ampliación, calcula el

momento en que se debe realizar, con un modelo compuesto de dos etapas, en la primera se

realiza la selección de la capacidad a aumentar, mediante programación entera y en la

segunda mediante programación lineal se determinan los consumos asociados a cada

subestación. Otros pioneros son Crawford y Holt (1975), quienes dado un conjunto de

ubicaciones para las subestaciones determinan sus respectivas capacidades y áreas de

servicio, mediante el uso del algoritmo de Dijkstra y del algoritmo de Ford y Fulkerson.

Posteriormente Thompson y Wall (1981) incluyen a las posiciones existentes, las posibles

posiciones de nuevas subestaciones como dato de entrada, incorporando una metodología

distinta a la programación lineal, mediante el uso de programación entera, utilizando el

algoritmo de “Branch and Bound”. Finalmente cabe destacar los trabajos de Willis et al

(1985) y Willis et al (1987), en que la función a minimizar esta dada por los costos de

inversión en las subestaciones más los costos de inversión y pérdidas de una red

simplificada, que no considera las restricciones de capacidad de los conductores, ni las

caídas de tensión y que supone que los costos de cada tramo de red son proporcionales al

9

flujo que circula por ellos y a la longitud de los mismos. El procedimiento de solución

emplea programación dinámica y “Branch and Bound”. En Willis et al (1987), se mejora

este algoritmo incorporando la consideración de la carga anual de los consumos y ubica las

subestaciones de manera que satisfaga la demanda con el mínimo de capacidad instalada.

En los años posteriores la atención de los investigadores se centra en la planificación

conjunta de subestaciones y redes, no obstante el problema de planificación de

subestaciones desacoplado de la red, nuevamente vuelve a ser abordado en Temraz y

Salama (2002), donde se determina el área de influencia y la función objetivo es

caracterizada por una función no lineal sin discontinuidades que se soluciona básicamente

siguiendo una metodología de descenso.

De lo anterior se desprende que en lo que respecta a las redes de distribución planificadas

con programación matemática, las investigaciones apuntan al segmento de MT, compuesto

por las subestaciones y alimentadores, sin considerar en el proceso la instalación de los

transformadores y su red BT, situación que recién es abordada en un primer intento por

Bujak (1988), realizando la elección de la ubicación de los transformadores de entre un

conjunto de posiciones candidatas, dato de entrada difícil de conseguir en la práctica,

usando para la resolución del problema como base la técnica de “Branch and Bound”

apoyada por métodos heurísticos auxiliares. Otro intento por resolver la ubicación de los

transformadores en forma independiente de la red se presenta en Moreno et al. (2006),

donde mediante un algoritmo de cluster modificado se asocian los consumos a un

determinado transformador, obteniéndose como resultado la ubicación y capacidad de los

transformadores de distribución, pero sin entregar información acerca de la factibilidad real

de la asociación, y sin conseguir, además, el trazado de la red de baja tensión.

2.1.2 Planificación de redes

Esta sección aborda la selección óptima de conductores y el trazado de la red en forma

independiente de la ubicación de las subestaciones y transformadores. La primera

investigación al respecto, fue realizada por Adams y Laughton (1974), en que dada una

ubicación y capacidad fija de las subestaciones, se escoge la ubicación y tipo de conductor

de las líneas, minimizando el costo de los conductores a través de programación entera –

10

mixta, considerando caídas de tensión y capacidad de conductores. Siguiendo los mismos

supuestos, Wall et al (1979), encuentra el trazado y capacidad de las líneas, usando el

algoritmo de transporte y aproximando la función de costo de los conductores a una función

lineal proporcional a su capacidad térmica. Posteriormente, en 1988, Tram y Wall,

trabajaron en la selección óptima de conductores, considerando la topología de la red como

dato de entrada, lo que implica tomar un alimentador compuesto de n tramos, y para cada

uno de ellos elegir el mejor conductor, considerando como restricción la caída de tensión y

la capacidad de transporte de los conductores. La función a minimizar corresponde a la

suma del costo de inversión más el costo de las pérdidas de todos los tramos del

alimentador, mediante un algoritmo iterativo de búsqueda local. Finalmente cabe

mencionar el trabajo de Mandal y Pahwda (2002) el cual realiza la selección óptima de

conductores basado en el menor valor presente, considerando tanto los costos de inversión

y pérdidas de cada conductor analizado, presentando dos metodologías para la elección de

la mejor alternativa, basadas en la capacidad térmica y económica de cada conductor.

2.1.3 Planificación conjunta de subestaciones y redes

Los trabajos de esta sección buscan resolver tanto la instalación de las subestaciones y/o

transformadores con la red asociada a ellos. Los primeros en abordar esta temática fueron

Hindi y Brameller (1977), a través de un modelo de transporte con restricción de capacidad

y un algoritmo de “Branch and Bound”, en el que se minimizan los costos fijos y variables

de las líneas y subestaciones, una vez que se tiene una solución factible se revisa el

cumplimiento de la restricción de radialidad, si no la satisface se hacen las modificaciones

para que sí lo sea. Resolviendo esta misma función objetivo, Gönen y Foote (1981) la

aproximan a una función lineal por tramos, y para la ubicación de las nuevas subestaciones

consideran como dato de entrada las ubicaciones posibles, su acierto está en considerar la

capacidad discreta de subestaciones y conductores, utilizando programación entera mixta,

dada la gran cantidad de variables necesarias sólo se puede aplicar a sistemas pequeños, de

hecho el modelo es probado sobre un ejemplo de tres posibles ubicaciones de subestaciones

que deben satisfacer en total a doce centros de carga (transformadores de distribución). En

un trabajo posterior Gönen (Gönen y Ramírez-Rosado, 1986), propone un modelo entero

11

mixto, que resuelve simultáneamente el problema de subestaciones y alimentadores, pero

esta vez, indicando el tiempo en que se debe realizar una determinada inversión, modelo

multi-etapa, y considerando las restricciones de regulación de tensión y topología radial de

la red. No obstante, nuevamente el modelo propuesto es sólo aplicable a redes de tamaño

reducido, en este caso el modelo es probado en una red con veinte consumos (centros de

consumo) y con cuatro posibles ubicaciones para subestaciones.

Cabe destacar que no todos los trabajos realizan la linealización de la función objetivo, así

Youssef et al. (1988) considera los costos no lineales, además, como simplificación utiliza

sólo variables continuas, de modo de resolverlo a través del método de Lagrange y así

abordar problemas de dimensiones mayores, siendo probado en un sistema con 3

subestaciones existentes, una subestación futura posible, 27 nodos de consumo y 56 nodos

de trasbordo, para un horizonte de 20 años. También en Ponnavaikko et al. (1987) se

considera la no linealidad de costos, nuevamente se considera continuidad de las variables

en el proceso de optimización, pero en este caso, dentro del proceso son aproximadas a

valores enteros, aplicado a un ejemplo con 10 nodos y 2 posibles ubicaciones para las

subestaciones.

El trabajo de Ramírez-Rosado y Gönen (1991) aborda la característica dinámica del

problema, es decir, no sólo obtiene las capacidades y ubicaciones de subestaciones (dado

un conjunto de ubicaciones posibles) y alimentadores, sino que indica el tiempo en que se

deben llevar a cabo las inversiones, realizando un modelo pseudo-dinámico que es resuelto

en dos fases, aplicando en la primera programación lineal y luego mejorando la solución

mediante “Branch and Bound”. El método es aplicado a la expansión de un sistema real, el

cual, no obstante es de baja dimensión, con no más de cuarenta nodos de consumo, y

considerando la ubicación de dos subestaciones, una existente y otra posible. Siguiendo con

la consideración dinámica del problema, Sanhueza y Rudnick (1995) minimizan el valor

presente de la inversión más operación y pérdidas de un sistema de distribución, mediante

el algoritmo de descomposición de Benders, no obstante la gran cantidad de variables, hace

que su aplicación sea para redes pequeñas, inferiores a 20 nodos.

En Vaziri et al. (2001) el modelo propuesto conserva la estructura dinámica, pero se incluye

esta vez la restricción de presupuesto de la empresa distribuidora, las restricciones técnicas

12

de subestaciones y alimentadores son incorporadas al modelo y no se realiza una revisión

ex - post de ellas, la función objetivo se modela de forma de plantear un problema de

programación entera mixta, el modelo de ejemplo sólo considera 5 centros de demanda y la

ubicación de una subestación existente y de otra posible.

Es importante señalar que existen trabajos que apuntan a la naturaleza probabilística del

problema, en este campo destaca el trabajo de Singh et al (2005), que incluye la

incertidumbre inherente a la proyección de la demanda, resuelve la expansión de un sistema

de distribución mediante Dantzig-Wolfe en que cada subproblema corresponde a un

escenario de demanda, la naturaleza estocástica del modelo genera un gran número de

variables (cercanas a 250.000) lo que vuelve a la metodología inaplicable en un caso real.

Finalmente se encuentra el trabajo de Paiva et. al (2005) que aborda la planificación

dinámica conjunta de la red de media tensión y de baja tensión de los sistemas de

distribución mediante programación lineal entera mixta, considerando una red de baja

tensión detallada, respetando los límites máximos de conductores, subestaciones y

transformadores, y cumpliendo una cierta regulación de tensión, no obstante, la aplicación

real del modelo es infactible, dado que su ejecución en un sistema de 38 nodos de media

tensión y 37 nodos en baja tensión tarda 29.305 segundos ( aproximadamente 8,15 horas).

2.2 Técnicas Meta-heurísticas

Dada la complejidad y dimensionalidad del problema a resolver, los algoritmos basados en

programación matemática no son capaces de considerar todas las variables y restricciones

del problema real, y sólo pueden ser utilizados para solucionar aplicaciones en sistemas

pequeños, lo que ha llevado a los investigadores en el último tiempo a buscar nuevas

prácticas que permitan tomar en consideración el tamaño real del problema a resolver y sus

principales restricciones, de manera de obtener buenas soluciones factibles en tiempo

razonable, pero sin garantizar la obtención del óptimo. Tal tendencia no es prohibitiva de

los sistemas de distribución, sino que representa la manera a través de la cual se están

resolviendo una enormidad de problemas complejos en la actualidad. Esta forma de

resolver se basa en meta-heurísticas, de acuerdo a Glover et al. (2003):

13

“Las meta-heurísticas son métodos que integran de diversas maneras, procedimientos de mejora local y estrategias de alto nivel para crear un proceso capaz de escapar de óptimos locales y realizar una búsqueda robusta del espacio de búsqueda. En su evolución, estos métodos han incorporado diferentes estrategias para evitar la convergencia a óptimos locales, especialmente en espacios de búsqueda complejos.” Estas técnicas toman conceptos desde la inteligencia artificial, la genética, la física, la

biología, entre las más utilizadas se cuentan los algoritmos evolutivos, los algoritmos

basados en colonias de hormiga, el intercambio de ramas, la búsqueda tabú y el temple

simulado2.

2.2.1 Planificación con sistemas expertos

Los primeros que usan este tipo de técnicas son Hsu y Chen (1990), quienes desarrollaron

un modelo basado en reglas que interactúan con el usuario, a través de un algoritmo

iterativo en que se ubican las subestaciones con el fin de minimizar las pérdidas en los

alimentadores, para posteriormente asignar a cada subestación el consumo más cercano. Se

debe señalar que no considera el trazado de la red, sino que únicamente la distancia entre el

punto de consumo y la subestación, el modelo es aplicado a un caso de dos posibles

subestaciones y 23 nodos de consumo.

En la literatura es posible notar que los sistemas expertos no resuelven el problema en

forma independiente, sino que necesitan de la interacción con el planificador, este es el caso

de Hsu y Chen (1990), Brauner y Zobel (1994) y Lo y Nashid (1996), por lo cual este tipo

de heurística ha sido paulatinamente abandonada por los investigadores, quienes sólo la han

seguido utilizando en combinación con otros meta-heurísticos.

2.2.2 Planificación con intercambio de ramas

El estudio pionero que introdujo esta metodología fue de Aoki et al (1990), cuyo objetivo

exclusivo era trazar la red óptima, para ello se parte de una solución inicial radial, luego se

incorpora una nueva rama que genera un bucle, y luego se saca una rama para eliminar

dicho bucle. La decisión de la rama a incorporar y de la rama a eliminar está sujeta a las

restricciones de capacidad en los conductores y caídas de tensión en los nodos, el proceso

2 Para mayor detalle ver Anexo C referente a diversas metodologías meta-heurísticas.

14

se repite iterativamente hasta que no se mejora la solución. Una modificación a este estudio

fue propuesta en Nara et al. (1992), donde la técnica intercambio de ramas (branch

exchange) es utilizada en etapas sucesivas, primero se realiza una iteración completa para

tener una solución inicial (primera etapa), luego se permite la adición y sustracción de una

rama, aunque empeore la solución, y continúa el proceso (segunda etapa), si el árbol

resultante es mejor que el árbol inicial se reemplaza, el número de veces en que se realiza

este proceso debe ser indicado por el planificador, es importante destacar que con esta

técnica los tiempos de ejecución comienzan a ser razonables, así trazar la red para un

sistema de 59 nodos tarda aproximadamente un minuto.

En 1997 esta técnica nuevamente es utilizada para el trazado de la red, Goswami (1997),

pero esta vez no sólo aplicada a un único árbol de expansión (una única subestación como

nodo generador del árbol), sino que a un sistema con más de una subestación, para lo cual

se propone partir del árbol de mínima expansión asociado a cada subestación, para luego

intercambiar ramas al interior de una misma red (intercambio intra-zona) e intercambiar

ramas entre redes diferentes (intercambio inter-zonas). Peco (2001) también realiza el

intercambio intra e inter zona, toma la ubicación de subestaciones, transformadores y

consumos como datos de entrada al modelo, respeta los límites de transporte de los

conductores, la regulación de tensión y las restricciones geográficas de la zona en análisis;

se debe destacar que realiza la optimización completa del sistema de distribución,

analizando mediante técnicas de auto-aprendizaje la confiabilidad de la red, siendo

aplicable a una red de gran tamaño; de hecho en el trazado de una red de media tensión que

conecta 75 subestaciones con 6.740 transformadores se demora tan sólo 23 minutos.

En la línea de lograr la aplicabilidad de la metodología a sistemas reales y obtener buenos

resultados, Míguez et al. (2002) propone una mejora consistente en realizar en una primera

fase el trazado de la red por medio de intercambio de ramas, y en una segunda fase incluir

nodos de trasbordo que mejoren la solución (nodos de Steiner) , ello dado que la distancia

no es la única variante relevante en el trazado de la red sino que también lo son los flujos

que transportan los conductores, y con la presencia de estos nodos auxiliares es posible

considerar tal situación, el método propuesto tarda cuatro segundos en trazar la red asociada

a 387 cargas y 9 transformadores.

15

En términos generales, de la literatura revisada, se desprende que la metodología de

intercambio de ramas permite abarcar problemas reales de sistemas de distribución, no

obstante, sólo aborda la problemática referida al trazado de la red, sin realizar la ubicación

de las subestaciones y/o transformadores, por lo que constituye una herramienta que por sí

sola no resuelve el problema de planificación de una red de distribución.

2.2.3 Planificación con temple simulado (Simulated Annealing)

Esta metodología ha sido poco empleada en el problema de planificación de sistemas de

distribución, principalmente se ha usado en problemas relacionados, tales como la

reconfiguración de redes (Chang y Kuo, 1994) y la ampliación de redes por el efecto de la

generación distribuida (Ponce de Leao y Matos, 1994). Su poco uso es producto de la gran

sensibilidad que presenta frente a los parámetros de control, una mala sintonización implica

necesariamente malos resultados, por lo que requiere un gran esfuerzo en la correcta

determinación de ellos, situación que ha motivado el abandono paulatino de esta técnica

como solución a problemas de optimización combinatorial, producto de la existencia de

metodologías alternativas menos sensibles a los parámetros de control.

2.2.4 Planificación con búsqueda tabú (Tabu Search)

La búsqueda tabú ha sido utilizada ampliamente en la resolución de problemas complicados

asociados a la optimización combinatorial, y la planificación de los sistemas de distribución

no ha sido la excepción. Uno de los primeros estudios en esta área fue Nara et al. (1998), en

el que se estudia la expansión del sistema, considerando la incorporación de nuevos

alimentadores y la localización de alimentadores de reserva que aumentan la confiabilidad

de la red.

Sin embargo, los principales aportes con esta técnica fueron desarrollados por Ramírez-

Rosado y Domínguez-Navarro (2004 y 2006). En Ramírez-Rosado y Domínguez-Navarro

(2004) se utiliza esta técnica abordando la característica no determinística del problema, a

través de la incorporación de lógica difusa en la definición de la demanda. El modelo es

mono-etapa, la función a minimizar es multi-objetivo y considera la minimización de los

costos de inversión, del valor esperado de la energía no suministrada y del riesgo,

16

entendiendo el riesgo como la posibilidad de sobrepasar la capacidad de los alimentadores

y de no cumplir con la regulación de tensión. Como se trata de una optimización multi-

objetivo, el resultado es un conjunto de soluciones en equilibrio paretiano, obtenidas a

través de búsqueda tabú, por lo tanto, la alternativa final debe ser escogida de entre ellas, en

este caso se propone el criterio de Max-mín para su obtención. El modelo es de expansión,

por lo que recibe la ubicación de las subestaciones y alimentadores existentes y de las

posibles ubicaciones de las nuevas subestaciones y alimentadores, se aplica a una caso real

de tamaño medio dado por 182 consumos, una subestación existente y dos posibles

subestaciones, es importante señalar que también realiza la ubicación de alimentadores de

reserva. Los mismos autores en un estudio posterior, Ramírez-Rosado y Domínguez-

Navarro (2006), resuelven el mismo problema, pero esta vez incorporando una

modificación a la búsqueda tabú denominada NMTS (siglas de su nombre en inglés New

Multiobjective Tabu Search), en donde su principal característica es intensificar la

búsqueda de la solución en las tres funciones objetivos del modelo de optimización.

En suma esta técnica ha mostrado ser eficiente en la solución de problemas de

planificación, dada su posibilidad de evitar quedar atrapada en óptimos locales, lo que la

convierte en una herramienta atractiva en la resolución de problemas combinatoriales

complejos.

2.2.5 Planificación con colonias de hormigas (Ant Colony System)

Esta es una metodología que no ha sido muy aplicada en problemas de distribución, no por

cuanto sea una mala herramienta sino por que constituye una meta-heurística introducida

recién en el año 1996 (Dorigo, 1996) y por tanto aún no ha sido completamente

desarrollada. En relación a la planificación de sistemas de distribución destaca el trabajo de

Gómez et. Al. (2004), en el que se realiza una planificación en una única etapa, se

considera como dato de entrada las posibles ubicaciones para las nuevas subestaciones y la

ubicación de subestaciones y centros de transformación existentes, respeta la capacidad de

los conductores y subestaciones, la topología radial de la red, y una determinada regulación

de tensión. El modelo es aplicado a un área urbana con 201 centros de transformación

17

abastecidos desde una única subestación, demorando en su ejecución, entre 26 minutos y 93

minutos dependiendo de la calidad de la solución buscada.

Esta metodología presenta la virtud de tener en cada iteración una mejor solución que en la

iteración anterior y por ende fijando el número de iteraciones o de colonias de hormiga se

pueden obtener buenos resultados en un tiempo razonable, sin embargo, dicho tiempo es

adecuado en sistemas pequeños puesto que con miles de nodos sería inviable, dado que

cada colonia realiza un proceso completo de construcción de red, y por tanto muchas

colonias implica muchos procesos a completar.

2.2.6 Planificación con algoritmos evolutivos

El primer trabajo que emplea los algoritmos genéticos o evolutivos para su resolución fue

Miranda et al. (1994), en el cual, la función no sólo incluye los costos de instalación y

expansión tanto de conductores como subestaciones y/o transformadores, sino que además

considera un indicador de calidad de tensión y un índice de confiabilidad de la red, a los

cuales se les asigna un costo. Como dato de entrada recibe la ubicación de las nuevas

posibles subestaciones, y realiza una optimización multi-etapa, por tanto indica el momento

en que se deben llevar a cabo las inversiones; el método es probado en un sistema 50 nodos,

con dos subestaciones existentes y con dos posibles nuevas ubicaciones. También en el

marco de una optimización multi-etapa, Ramírez-Rosado y Bernal-Agustín (1998)

resuelven un modelo de planificación de expansión, que entrega la ubicación y tamaño

tanto de subestaciones como de alimentadores, el modelo incluye los costos no lineales

asociados a la operación (costos de pérdidas) sin linealizarlos, como dato de entrada recibe

las posibles rutas de los alimentadores y posibles ubicaciones, en la resolución de un caso

real resuelve la expansión de una red de 417 nodos en 15,25 horas, lo cual ya comienza a

ser atractivo desde el punto de vista práctico. En un estudio posterior Ramírez-Rosado y

Bernal-Agustín (2001), incluyen en su modelo la planificación multi – objetivo,

minimizando los costos de inversión y la energía no suministrada, es decir la confiabilidad

no es valorizada en cuanto a costo (función objetivo como minimización de una

combinación lineal de costos) sino que es incluida como un objetivo en el problema, y por

tanto se obtiene un conjunto de soluciones (no una única solución como en la optimización

18

mono – objetivo) en equilibrio paretiano. Luego, es función del planificador elegir la

solución final de entre el conjunto de soluciones encontradas. Es necesario mencionar que

la disminución de la energía no suministrada se logra con la incorporación de alimentadores

auxiliares que se encuentran en estado normalmente abierto. El modelo fue probado en un

sistema de 417 nodos con un horizonte de tres años, donde se obtuvo el conjunto de

soluciones paretianas, sin embargo no se indica su tiempo de ejecución.

Otro trabajo importante de destacar es el realizado por Carvalho et al (2000), en el que se

incorpora la incertidumbre al problema de planificación, incertidumbre que es modelada a

través de un árbol de escenarios posibles. El procedimiento empleado no es el de optimizar

el valor esperado de los distintos escenarios (procedimiento habitual), ya que de esta

manera “lo único que se consigue es una población de soluciones que son muy buenas en

promedio pero que son un desastre en un escenario particular” (Carvalho et al 2000), en su

lugar, propone una metodología en que cada escenario constituye un subproblema, cada

población evoluciona de acuerdo a su propio escenario para luego evolucionar tomando en

consideración su costo esperado en los demás escenarios. En Ferreira et al (2001), estudio

del que también participa Carvalho, se realiza la expansión del sistema de distribución y su

reconfiguración, lo interesante de este modelo es que es aplicado a un sistema de media

tensión compuesto por 54 subestaciones y 8.964 nodos, tardando sólo 28 minutos.

Finalmente se debe mencionar el trabajo de Díaz-Dorado (2002, 2003) por su aplicabilidad

a un sistema real, si bien únicamente realiza el trazado de la red, recibiendo como dato de

entrada la ubicación de subestaciones, transformadores y consumos y no considera la

dimensión temporal del problema, sí incluye en el análisis la topología vial, esto es, que el

trazado de la red se realiza sólo sobre las calles de la zona en estudio. También se debe

señalar que en este trabajo se aborda el problema de los alimentadores de respaldo para

darle más seguridad a la red de distribución de media tensión. Esta metodología fue

aplicada a un caso real con 3 subestaciones, 242 transformadores y 1.852 nodos tardando

60.000 iteraciones en encontrar la solución final.

La utilización de esta meta-heurística ha sido abordada ampliamente por los investigadores

en planificación de sistemas de distribución y como gran acierto se encuentra su aplicación

a redes de tamaño real.

19

En resumen, y tomando en consideración los estudios antes señalados, es posible afirmar

que las metodologías basadas en programación matemática han sido abandonadas por los

investigadores para abordar el tema de la planificación de sistemas de distribución, ello

dada su imposibilidad de resolver problemas cercanos a la realidad, y en contrapartida, han

seguido el camino del desarrollo y aplicación de meta-heurísticas, que si bien no permiten

encontrar el óptimo, representan una muy buena aproximación a la solución de problemas

reales.

20

3. METODOLOGIA DESARROLLADA

3.1 Antecedentes Generales

Considerando la revisión bibliográfica realizada, es posible inferir que las técnicas de

programación matemáticas no son adecuadas para resolver problemas de planificación de

sistemas de distribución, ello debido a que sólo son capaces de resolver ejercicios de

tamaño reducido (Gonen y Foote, 1981, Ponnavaikko et al, 1987, Gönen y Ramírez-

Rosado, 1986, Vaziri et al, 2001), y en caso de abordar problemas de mayor envergadura,

los tiempos de ejecución crecen exponencialmente con el tamaño de la entrada (Paiva et. al.

2005). Por lo cual la planificación de sistemas de distribución, a partir de la década de los

90 ha sido ampliamente explorada a través de técnicas meta-heurísticas, que permiten

responder problemas de mayor dimensionalidad (Peco, 2001, Ferreira et al, 2001, Díaz-

Dorado 2002, Díaz-Dorado 2003), con la desventaja de no ser capaces de encontrar el

óptimo de la función objetivo que caracteriza al problema en cuestión. No obstante, se debe

tener siempre presente que en la mayoría de las ocasiones en ingeniería se buscan buenas

soluciones, dado que las óptimas son imposibles de conseguir.

De la revisión también es posible constatar, que si bien los investigadores que utilizan

técnicas meta-heurísticas abordan problemas de mayor dimensionalidad en comparación

con los que utilizan técnicas de programación matemática, en la mayoría de los casos tales

aumentos de tamaño no representan, en absoluto, problemas reales y en el mejor de los

casos resuelven problemas reales de dificultad media, en zonas donde no existe gran

cantidad de consumos (Ramírez-Rosado y Bernal-Agustín, 1998, Míguez et al, 2002,

Ramírez-Rosado y Domínguez-Navarro, 2004). Excepciones a esto, lo constituyen los

estudios de Díaz-Dorado (1999) y de Peco (2001) en los que realmente se resuelven

problemas de gran tamaño, aplicables a provincias completas de España, sin embargo, el

modelo de Peco, que muestra una optimización completa tanto del sistema de media tensión

como del de baja tensión, no realiza la ubicación de los transformadores, sino que los

considera como datos de entrada al problema, por lo que la resolución en términos

generales hace referencia a la elección de la ruta óptima en baja tensión y a la ruta y

21

respaldo correspondientes en media tensión, desconociendo la relación existente entre

ubicación del transformador y la red asociada al mismo, siendo su principal acierto la

incorporación del trazado vial como restricción de la optimización, de forma tal que las

redes asociadas a un determinado transformador no crucen por zonas prohibidas, sino que

respeten el callejero. Por otro lado, el modelo de Díaz-Dorado (1999), incorpora en el

algoritmo la ubicación óptima de transformadores, y si bien realiza la optimización

conjunta de la red de baja tensión con la de media tensión, la relación que se establece entre

ambas es a través de simplificaciones, así al planificar la red de baja tensión, se asume que

la red de media tensión está dada por el árbol de mínima expansión, lo que constituye una

simplificación relevante, pero que permite una aproximación a la resolución del problema.

Su mayor falencia es que no manifiesta explícitamente la posibilidad de considerar la

restricción vial, de hecho en una investigación posterior basada en el estudio en cuestión,

queda de manifiesto la ausencia de la topología vial como restricción a la solución del

problema (Díaz-Dorado, 2003).

En el contexto señalado, la presente investigación seguirá en la línea de la optimización de

sistemas reales, pero esta vez considerando la interacción que se produce entre los centros

de transformación y la red, respetando la topología vial de la zona a optimizar. Se debe

reiterar el interés regulatorio de contar con un modelo de planificación que pueda optimizar

el sistema de distribución únicamente considerando la ubicación y el tamaño de las cargas,

es decir que sea capaz de trazar la red, calcular las capacidades óptimas de los conductores

asociados a ella, obtener la ubicación y capacidad de subestaciones y transformadores. A

este tipo de planificación se le conoce como “greenfield planning”, caracterizándose por

una gran complejidad, dada por el enorme número de variables de decisión y por la gran

cantidad de consumos a suministrar (tamaño elevado de la entrada), siendo este

precisamente el problema que busca resolver esta investigación. Sin embargo, considerando

la enormidad de variables involucradas en el problema, se abordará sólo lo referente a la

planificación de redes de distribución eléctrica en su componente de baja tensión, ello

debido a que representa un problema en sí mismo, que no ha sido lo suficientemente

abordado. De la revisión bibliográfica muy pocos se refieren al tema de la planificación de

baja tensión, ya sea en forma independiente o de manera conjunta (Peco 2001, Paiva et. al.

22

2005), lo que lo convierte en un tema de gran interés a resolver y que además podría ser

utilizado en trabajos futuros, como una componente de un modelo que aborde íntegramente

la planificación tanto en media como en baja tensión.

También al igual que en los dos estudios citados, dada la gran cantidad de variables a

abordar, se considera un modelo de solución estático, es decir, la planificación del sistema

tomará en cuenta sólo una etapa de análisis, en la cual, se utilizarán las demandas

pronosticadas para el último año del horizonte de planificación, con lo que el conjunto de

inversiones a realizar no presentará un cronograma de actividades, por tanto no responde a

la pregunta ¿cuándo invertir?, sino que supone que todas las obras necesarias deben ser

construidas en el mismo instante, es decir al inicio del período de planificación.

Con las consideraciones anteriores el modelo a resolver puede representarse mediante la

siguiente formulación matemática (Díaz-Dorado, 1999), siendo la ecuación (3.1) la función

objetivo que incluye los costos fijos y variables de los transformadores y de la red de baja

tensión, la ecuación (3.2) garantiza el equilibrio de flujo en los nodos del sistema, mientras

que las ecuaciones (3.3) y (3.4) limitan la capacidad de los transformadores y conductores,

respectivamente, a sus valores máximos nominales, las ecuaciones (3.7), (3.8) y (3.9)

garantizan que las caídas de tensión no pasen de un valor determinado y finalmente la

ecuación (3.12) fuerza la radialidad de la red3.

( )( )

( )( )( , ) ,

min ik ik ik ik ijk ijk ijk ijki Trafos k TT i i j R k TC i j

g y f c xπ ϖ λ∈ ∈ ∈ ∈

+ + +∑ ∑ ∑ ∑ (3.1)

( )( )

( ),i jik ijk ik

k TT i j N k TC i j

y x x b i N∈ ∈ ∈

+ − = ∀ ∈∑ ∑ ∑ (3.2)

0 , ( )ik ik iky V i N k TT iπ≤ ≤ ∀ ∈ ∀ ∈ (3.3)

0 ( , ) , ( , )ijk ijk ijkx U i j R k TC i jλ≤ ≤ ∀ ∈ ∀ ∈ (3.4)

{ }0,1 , ( )ik i N k TT iπ ∈ ∀ ∈ ∀ ∈ (3.5)

3 Garantiza radialidad siempre y cuando no existan nodos de bifurcación, en cuyo caso se deben utilizar métodos heurísticos que rompan los enmallamientos que se pueden producir, el método más utilizado se conoce como load splitting, en el cual se determina el nodo de la malla al que llega potencia por dos ramas, en cuyo caso se divide el nodo y las ramas que salen de él, repartiendo de manera adecuada la carga.

23

{ }0,1 ( , ) , ( , )ijk i j R k TC i jλ ∈ ∀ ∈ ∀ ∈ (3.6)

( )( ),

( ) ( ) ( , )i ij j ji ijk jik ijkk TC i j

v D v D G x x i j R∈

+ − + = − ∀ ∈∑ (3.7)

0 (1 ) ( , )ij ijD D i j Rλ≤ ≤ − ∀ ∈ (3.8)

miniV v i N≤ ∀ ∈ (3.9)

( )

0 1ikk TT i

i Nπ∈

≤ ≤ ∀ ∈∑ (3.10)

( )

0 1 ( , )ijkk TT i

i j Rλ∈

≤ ≤ ∀ ∈∑ (3.11)

( ) ( , ) ( , )

, ( , )ik ijkk TT i i N k TC i j i j R

N i N i j Rπ λ∈ ∈ ∈ ∈

− = ∀ ∈ ∀ ∈∑ ∑ ∑ ∑ (3.12)

El detalle de las variables es el siguiente:

• N : número de nodos de la red.

• R : conjunto de ramas factibles.

• TT(i) : conjunto de tipos de transformadores posibles de instalar en el nodo i.

• TC(i) : conjunto de posibles tipos de conductores a instalar en la rama (i,j).

• λijk : variable binaria que indica si existe la rama entre los nodos (i,j)

utilizando el conductor tipo k.

• πik : variable binaria que indica si existe un transformador del tipo k instalado

en el nodo i.

• xijk : variable real que representa el modulo de la potencia que cruza por la rama

(i,j) a través del conductor tipo k.

• yik : variable real que indica el modulo de la potencia que inyecta el

transformador tipo k instalado en el nodo i.

• gik : costo fijo del transformador tipo k instalado en el nodo i.

• ωik : costo por unidad transformada en el transformador tipo k del nodo i.

• vi : módulo de la tensión en el nodo i.

24

• Dij : variable de holgura4 asociada a las caídas de tensión en el nodo i producto

del flujo que viene desde el nodo j.

• Gij : variable de proporcionalidad que relaciona el flujo entre el nodo i y el

nodo j, con la caída de tensión en el nodo i producto del flujo que se mueve

desde j.

• D : máxima variación de caída de tensión permitida.

• Vmin : menor modulo de voltaje permitido en el ejercicio de planificación.

3.2 Breve Explicación de la Metodología Desarrollada

Para resolver el modelo señalado y en atención a su imposibilidad de solucionarlo vía

programación matemática se presenta una metodología heurística que será explicada paso a

paso, siguiendo su aplicación para el caso de Macul, comuna de Santiago, compuesta de

20.215 consumos, repartidos en una superficie de 12,9 kilómetros cuadrados.

Como ya se ha hecho referencia, encontrar el óptimo para un problema de estas

dimensiones, es imposible de realizar en un tiempo razonable, al menos con las

restricciones computacionales presentes en la actualidad. Por lo cual se propone una meta-

heurística, cuyo corazón está constituido por tres técnicas principales, por una técnica de

cluster denominada k-means que será importante para la determinación de la ubicación de

los transformadores y las redes asociadas a ellos, por una técnica llamada diagramas de

Voronoi, que permitirá realizar una asignación inteligente de los consumos, y finalmente

por una meta-heurística de optimización denominada búsqueda tabú, mediante la cual, se

podrán mejorar las soluciones encontradas.

3.3 ¿Cómo abordar el problema?

Dado un conjunto de nodos, representados por su ubicación en el plano cartesiano, se desea

conocer el número de redes, configuración y diseño, asociada a cada transformador, es

decir en primer término se requiere crear subconjuntos de consumos que sean abastecidos

4 Variables de holgura necesarias debido a que a priori no se conoce cuales son los nodos que se conectarán para formar la red.

25

por un mismo transformador para luego trazar su red. Por ejemplo, si se tienen diez nodos,

se pueden realizar 1.023 subconjuntos distintos, donde cada subconjunto es abastecido por

un único transformador. Ello de acuerdo a la siguiente expresión:

( )

10 1010

1 1

10 10 10 10 10!... 2 1 1.023

1 2 10 ! 10 !i ii i i= =

+ + + = = = − =

− ∑ ∑

Además, si se considera que al interior de cada grupo el transformador puede tomar

cualquiera de las posiciones, entonces se tiene:

( )

10 10

1 1

10 10 10 10 10!1 2 ... 10 5.120

1 2 10 ! 10 !i i

i ii i i= =

⋅ + ⋅ + + ⋅ = ⋅ = ⋅ =

− ∑ ∑

Por lo tanto, para un caso sencillo de 10 nodos, existen 5.120 posibles soluciones a evaluar.

No obstante, se debe señalar que tal número constituye una cota superior para el conjunto

de soluciones factibles, dado que muchos de los subconjuntos, producto de una determinada

configuración de los consumos, no tienen sentido práctico, debido a que están constituidos

por nodos que se encuentran alejados.

26

1 2 3 4 5 6 7 8 9 101

2

3

4

5

6

7

8

9

10

Figura 3.1: Ejemplo 10 nodos

En la figura anterior se puede apreciar claramente que no todos los subconjuntos son

viables, de hecho sólo aquellas combinaciones que agrupan nodos vecinos son factibles de

analizar. Por lo cual, para conocer en forma aproximada el número de combinaciones

factibles, se procede a limitar las agrupaciones a aquellas que están conectadas por medio

de arcos pertenecientes a la triangulación de Delaunay, de acuerdo a la siguiente figura.

1 2 3 4 5 6 7 8 9 10

1

2

3

4

5

6

7

8

9

10

Figura 3.2: Triangulación de Delaunay para el ejemplo de 10 nodos

[m]

[m]

[m]

[m]

27

Es decir sólo las agrupaciones, que contengan nodos unidos a través de los arcos señalados

en la figura serán consideradas, con lo que se limitan los subconjuntos a los casos vecinos.

Se debe señalar brevemente, que la triangulación de Delaunay se refiere a aquella, en que

cada circunferencia circunscrita a cada triángulo de la red no contiene ningún vértice

perteneciente a otro triángulo de la red5, identificando como consumos (nodos) vecinos a

quienes se encuentran unidos por una arista de un polígono de la triangulación. Realizando

esto, se obtiene que el número de subconjuntos posibles6 para la configuración utilizada

como ejemplo, es del orden de 4.300 casos, menor a los 5.120 iniciales. Si se quieren

restringir aún más los casos posibles, se pueden evaluar únicamente las combinaciones que

se producen entre cada nodo y sus nodos más cercanos (conectados por una única arista),

con lo que el número de casos factibles es de7 197. Dicha cantidad no constituye un número

elevado de combinaciones, por lo que podría ser resuelto sin inconvenientes por un método

tradicional de programación matemática. No obstante el problema que se busca resolver en

el presente trabajo, tiene una dimensionalidad mayor, de hecho considerando los 20.215

consumos se tendría como cota superior casi infinitas combinaciones (220215-1).

5 La triangulación de Delaunay constituye el dual del diagrama de Voronoi, ambos serán explicado es detalle en el capítulo 5. 6 Subconjuntos factibles dados por aquellas combinaciones que representan un subgrafo de la triangulación de Delaunay. 7 La triangulación de Delaunay depende de la distribución espacial de los consumos y por tanto el número de subconjuntos posibles variará de un caso a otro dependiendo de tal o cual configuración.

28

3.6 3.65 3.7 3.75 3.8 3.85 3.9 3.95 4 4.05 4.1

x 104

6000

7000

8000

9000

10000

11000

12000

Figura 3.3: Ubicación de los consumos comuna de Macul

Si se consideran únicamente las combinaciones posibles entre cada nodo y sus vecinos

(calculados a través de la triangulación de Delaunay, y acotados a no más de tres elementos

por grupo), se tienen 242.483 combinaciones posibles, lo que ratifica que el problema en

cuestión no puede ser resuelto a través de técnicas convencionales. Surgiendo

inevitablemente la siguiente pregunta, ¿Cómo abordar el problema?.

La estrategia propuesta para conseguirlo esta basada en la técnica conocida como “Dividir

y Conquistar”, que básicamente consiste en resolver subproblemas del mismo tipo que el

problema principal pero de menores dimensiones, es decir, dividir Macul en zonas de

menor tamaño donde cada una de ellas representa un subproblema, de manera de disminuir

el número de combinaciones al resolver problemas con menos consumos (la dificultad del

problema crece exponencialmente con la entrada), con lo cual la suma de las

combinaciones posibles en cada subproblema es mucho menor que el total de

combinaciones del problema completo, lográndose de esta manera afrontar de forma

razonable el problema en cuestión. Específicamente los pasos fundamentales de esta técnica

son:

[m]

[m]

29

1. Plantear el problema de manera que pueda ser descompuesto en k problemas distintos,

del mismo tipo que el problema principal, pero de menor tamaño. Por tanto si el tamaño

de la entrada es n, entonces el tamaño de cada subproblema, denotado por nk, debe

cumplir que 0≤ nk ≤ n, este proceso se denomina división.

2. Cada subproblema se debe resolver en forma independiente. Lo interesante de esta parte

del procedimiento es que abre la posibilidad para realizar cada uno de los subproblemas

en forma paralela, utilizando distintos computadores para cada uno de ellos, con lo que

es posible obtener importantes ahorros en los tiempos de ejecución.

3. Finalmente se deben combinar las soluciones obtenidas en el paso dos para así lograr la

solución del problema global.

Por tanto, la forma de solucionar el problema en cuestión es dividir la zona de gran tamaño

a planificar, en zonas regulares de menor tamaño, para después aplicar a cada una de esas

mini-zonas, un proceso de optimización, que se denomina proceso de micro-optimización,

luego para combinar cada una de las soluciones y encontrar los ahorros, producto de ver el

problema en forma global, se realiza un proceso denominado macro-optimización, en

particular se desarrollan dos metodologías base de macro-optimización, una basada en

diagramas de Voronoi y otra basada en la búsqueda tabú, para finalmente mostrar la

combinación de ambas y los ahorros correspondientes que se producen. En los siguientes

capítulos se explicarán en detalle cada una de las alternativas mencionadas, que se ilustran

en el siguiente esquema:

30

Figura 3.4: Diagrama simplificado del algoritmo propuesto

31

4. PROCESO DE MICRO-OPTIMIZACION

4.1 Descripción General

Tal y como se señaló en el capítulo anterior la división en mini-zonas permite acercarse a la

solución del problema, ya que logra disminuir el número de variables involucradas y el

gran número de combinaciones que se producen entre ellas. Este capítulo se concentra en el

desarrollo de la metodología propuesta para la optimización de cada mini-zona,

manteniendo la misma función objetivo y restricciones del problema completo, esto es,

buscando la ubicación y capacidad de transformadores, la topología de la red asociada a

cada uno de ellos, el tipo de conductor para cada tramo de la red, respetando las

restricciones viales, las caídas de tensión, la radialidad de la red, todo ello en el marco de la

minimización de la inversión en transformadores y conductores más los costos asociados a

las pérdidas.

La metodología desarrollada puede ser aplicada a cualquier mini-zona de tamaño n x m, en

particular, para entender el algoritmo se mostrará la aplicación para mini-zonas de 500

metros x 500 metros. Una vez que el procedimiento completo sea revisado, se realizará el

proceso de micro-optimización para distintos tamaños de mini-zonas, de forma que sea

posible apreciar el efecto de tal elección en el resultado final.

32

3.6 3.7 3.8 3.9 4 4.1

x 104

7000

8000

9000

10000

11000

12000

Figura 4.1: División en mini-zonas

Para cada una de las zonas señaladas en la figura anterior, se requiere agrupar los consumos

asignando un transformador a cada agrupación, de manera tal que se evite realizar la

enumeración completa de todas las posibles alternativas (subconjuntos), es decir se debe

conseguir una agrupación inteligente de los consumos, la forma propuesta para lograrlo es a

través de un algoritmo de búsqueda local combinado con análisis de cluster. Para

comprender la técnica empleada, se realizará una pequeña reseña referente al análisis de

cluster8 para luego explicar el algoritmo propuesto.

4.2 Análisis de Cluster

El análisis de cluster es una técnica estadística multivariante, cuyo objetivo es dividir un

conjunto de elementos en grupos, de manera que las características de los elementos

pertenecientes a un mismo grupo sean muy similares entre sí, situación denominada

cohesión interna, y las características de elementos pertenecientes a distintos grupos sean

diferentes, situación conocida como aislamiento externo del grupo. Para conocer tal

similitud se hace necesaria la existencia de medidas que indiquen el grado de parecido,

8 Para mayor información refiérase al anexo C

[m]

[m]

33

medidas de proximidad, o diferencia, medidas de distancia, que existen entre dos elementos

que se quieren agrupar.

En particular, la técnica de cluster que se empleará en el presente trabajo, es el algoritmo de

k-means, que permite clasificar un conjunto de n datos en k subconjuntos, donde la cantidad

de grupos a formar, k, es un dato de entrada del algoritmo. Éste, en términos sencillos está

compuesto por los siguientes pasos:

1. Elección de k datos de los n a agrupar, estos constituyen los k centroides iniciales.

Se calculan las distancias de los datos a cada uno de los centroides. Cada dato es

asignado al centroide más cercano, formándose k grupos.

2. Para cada uno de los grupos se calcula el nuevo centroide como el valor medio de

todos los datos asignados a él.

3. Se repite el proceso 2 y 3 hasta que se satisface un criterio de convergencia

determinado.

La medida de distancia utilizada por el algoritmo corresponde a la distancia euclidiana,

dada por:

2( , ) ( ) ( )T T

X X X Xd x x x xµ µ µ µ= − = − ⋅ − (4.1)

Donde:

• d : distancia euclidiana.

• x : vector de posiciones de los datos.

• Xµ : valor medio de los datos (centroide).

El criterio de parada está dado por el mínimo entre un número máximo de iteraciones

permitidas y la variación de la distorsión entre dos iteraciones sucesivas. El número

máximo de iteraciones es un dato de entrada al algoritmo y dependerá de la convergencia

presentada en el problema a resolver. En tanto que la distorsión es la suma de todas las

distancias a su respectivo centroide.

34

2

1

( )i

k

ii x C

D i x µ= ∈

= −∑∑ (4.2)

Donde:

• D(i) : distorsión al finalizar la iteración i.

• k : número de clusters.

• Ci : cluster i-ésimo.

De la expresión anterior se desprende que el criterio de parada será ( ) ( 1)D n D n ε− + ≤ 9

A modo de ejemplo en la figura (4.2) se emplea la técnica para crear tres subconjuntos

utilizando como criterio la cercanía entre los nodos, en la iteración 1 se parte con la

ubicación aleatoria de los tres centros, señalados mediante triángulos, a cada uno se le

asignan los nodos más cercanos (identificados en la figura por un mismo color), para luego

mover tales centros al centroide del subconjunto, dicho proceso se repite, en este caso

durante 12 iteraciones, dado que más iteraciones no presentan mejoras a la solución, lo que

se aprecia claramente en la tabla 4.1.

Tabla 4.1: Evolución de la distorsión en el caso de ejemplo

IteraciónDistorsión

(Km)Inicial 5230

1 4957

2 4504

3 3775

4 3459

5 3226

6 2966

7 2752

8 2633

9 2615

10 2611

11 2609

12 2609

9 Con ε, definido por el planificador, no obstante usualmente está entre 0.5 % y 1%.

35

Se debe notar que entre la iteración 11 y 12 no existe variación de la distorsión, de no

haberse logrado la convergencia el algoritmo se detiene cuando se alcanza un número

máximo de iteraciones, el cual en este trabajo es de 200 iteraciones.

3.805 3.81 3.815 3.82 3.825 3.83 3.835 3.84 3.845 3.85

x 104

7700

7750

7800

7850

7900

7950

8000

8050

8100

3.805 3.81 3.815 3.82 3.825 3.83 3.835 3.84 3.845 3.85

x 104

7700

7750

7800

7850

7900

7950

8000

8050

8100

3.805 3.81 3.815 3.82 3.825 3.83 3.835 3.84 3.845 3.85

x 104

7700

7750

7800

7850

7900

7950

8000

8050

8100

3.805 3.81 3.815 3.82 3.825 3.83 3.835 3.84 3.845 3.85

x 104

7700

7750

7800

7850

7900

7950

8000

8050

8100

3.805 3.81 3.815 3.82 3.825 3.83 3.835 3.84 3.845 3.85

x 104

7700

7750

7800

7850

7900

7950

8000

8050

8100

3.805 3.81 3.815 3.82 3.825 3.83 3.835 3.84 3.845 3.85

x 104

7700

7750

7800

7850

7900

7950

8000

8050

8100

.

Figura 4.2: Ejemplo de aplicación de k-means

Iteración 1 Iteración 3

Iteración 5 Iteración 7

Iteración 9 Iteración Final

[m]

[m] [m]

[m] [m]

[m] [m]

[m]

[m] [m]

[m]

[m]

36

4.3 Metodología de Micro-Optimización

Del apartado anterior se desprende que k-means permite una elección inteligente de

subconjuntos, de hecho si los datos de entrada están dados por los consumos y los

centroides representan a los transformadores, se puede realizar una buena ubicación de los

mismos, sin necesidad de aumentar los tiempos de ejecución, situación que si se produce

probando todas las combinaciones. Sin embargo, ¿es suficiente sólo con k-means para

realizar la ubicación óptima de transformadores y red asociada?. La respuesta es no, ello

dado que k-means por si mismo no entrega el número de transformadores, sino que sólo

agrupa las cargas en un número elegido a priori de subconjuntos, y no incluye la relación

que existe entre los consumos asignados a un transformador con el mismo, a través de la

red que los conecta, ni menos aún respeta las restricciones geográficas, con lo que

consumos cercanos pero imposibles de conectar son indiferentes para k-means.

En Moreno et al. (2006) se realiza una aproximación a la determinación de un parque

óptimo de transformadores para una zona determinada. Mediante esta técnica de cluster, no

obstante, en tal trabajo se realiza únicamente la ubicación de los transformadores, que son

elegidos previamente a través de una optimización vía programación matemática, con lo

que se disocia la ubicación del transformador de su elección, es decir, existe la posibilidad

que transformadores que son óptimos para una determinada carga puntual, puede que ya no

lo sean cuando la carga a satisfacer está distribuida en el plano, dado que tal asignación no

consideró las restricciones viales, existencia de caminos para trazar la red, ni los costos

asociados a la topología de la misma, situaciones todas que hacen posible dudar de la

bondad de la elección realizada por separado de la ubicación. Es por ello que en el presente

trabajo se busca optimizar la red de baja tensión sin disociar la elección de la capacidad y

ubicación de un transformador con su trazado y por tanto con el costo de su red asociada.

El algoritmo propuesto consiste básicamente en un procedimiento de descenso en donde

para cada mini-zona se comienza con la ubicación de un transformador, después se calcula

el costo de la red asociada, que respeta la topología vial, y el costo del transformador que

satisface la demanda, luego se realiza el mismo procedimiento para el caso de dos

transformadores, así sucesivamente hasta que se encuentra el óptimo. El supuesto que

37

sustenta la metodología es que en la medida que aumenta el número de transformadores en

una mini-zona, disminuye el costo asociado a la red y aumenta el costo de transformación,

situación que hace posible encontrar un mínimo. Al final del presente capítulo se mostrará

la validez real de dicho supuesto.

Figura 4.3: Proceso de micro-optimización para una mini-zona

El diagrama de flujo simplificado del algoritmo propuesto se muestra en la figura (4.3),

antes de explicar en detalle cada una de sus etapas, se deben especificar los supuestos

empleados, en primer término es necesario establecer que el período de estudio a planificar

corresponde a 15 años, la elección de este horizonte se debe por un lado a la necesidad de

realizar una planificación de largo plazo y por otro a un interés comparativo, dado que el

estudio regulatorio conocido en Chile como VAD10 utiliza el mismo período, con lo cual es

10 VAD: Valor agregado de distribución, que busca remunerar a la distribuidora por los costos en que incurre al llevar la energía que compra a los generadores hasta los consumidores finales. Como la distribución constituye un monopolio natural, es la autoridad quien debe fijar tal valor, el que posteriormente será traspasado mediante tarifa a los consumidores. Tal fijación se realiza cada 4 años y consiste en determinar cuales son los costos de una empresa distribuidora ficticia, empresa modelo, que presta eficientemente el servicio en la misma zona de concesión, o una similar, que la distribuidora regulada. Es importante señalar que: “El concepto que está detrás de la definición de la empresa modelo, corresponde a la simulación de una situación de competencia, cuando aparece un nuevo prestador del servicio con costos y tecnologías actuales,

38

posible contrastar los resultados obtenidos mediante esta metodología con los obtenidos en

el último estudio tarifario. Es por esta necesidad de comparación que se utilizarán los datos

de costos del último informe de VAD, realizado el año 2004, es decir se tomará tal año

como punto de partida del horizonte de planificación, teniendo presente siempre que tal

estudio considera tanto el crecimiento horizontal, aparición de nuevos centros de consumos,

como el crecimiento vertical de la demanda, aumento en el consumo de los clientes ya

existentes. Por el contrario, en el presente trabajo sólo se considera el crecimiento en el

consumo de energía y potencia de los clientes existentes a lo largo del horizonte de estudio.

Otra consideración que se debe tener en cuenta es que en la investigación aquí expuesta,

sólo se realiza la optimización de la red de baja tensión suponiendo que toda la distribución

se realiza mediante redes aéreas, en tanto que el estudio de VAD considera además redes de

distribución subterráneas en aquellos lugares donde la empresa regulada las posee, por

tanto los resultados obtenidos finalmente no serán del todo comparables, pero sí permitirán

observar la bondad de la solución encontrada, realizando un cotejo con los costos en redes

aéreas, número de transformadores empleados, largo de red utilizada, capacidad de

transformación instalada, entre otros parámetros relevantes de comparación.

Para fines del estudio y mostrar la metodología desarrollada se supone un crecimiento

uniforme en toda el área de concesión de 2,75 % en la demanda de potencia, con lo que

aparece un nuevo supuesto, éste es, asumir que es posible conocer la demanda máxima

coincidente de cada uno de los consumos asignados a un mismo transformador, lo cual en

distribución eléctrica de baja tensión es una tarea complicada que sólo puede ser resuelta de

manera aproximada, debido a que casi la totalidad de los clientes conectados a la red de

baja tensión sólo poseen medidores de energía con lo que no es posible contar con un

historial de demanda que permita realizar proyecciones mediante métodos predictivos

clásicos. Debido a que tal proyección es una tarea en si misma que depende de múltiples

variantes, tales como uso de suelo, crecimiento económico, proyectos inmobiliarios, gestión

de la demanda, entre otros, no será resuelta en el presente trabajo cuyo objetivo es plantear

una metodología adecuada al problema de planificación de redes de baja tensión y por tanto

cuya eficiencia le permite acceder al mercado o bajar los precios, de forma tal que los prestadores existentes deben adaptarse al nuevo precio de equilibrio o simplemente desaparecer” (CNE, 2003).

39

se adoptará la solución propuesta por Inecon11 en el estudio de VAD 2004 (Systep e Inecon

2004), la que consiste básicamente en la determinación de una función del factor de carga

que depende del número de clientes que pertenecen a una determinada agrupación, de tal

manera que conocida la energía que consume una agrupación de clientes sea posible

determinar la potencia máxima coincidente de dicho grupo y con ello dimensionar en forma

óptima las instalaciones. Esta metodología es adecuada dado que las lecturas disponibles

son en esencia de energía, siendo datos confiables, en tanto la curva de factor de carga es

una aproximación que se obtuvo de una muestra representativa de 2000 transformadores

que poseen tanto lectura de energía como de potencia. Así realizando subconjuntos de entre

esos 2000 clientes, a través de simulaciones de Montecarlo, fue posible la construcción de

la expresión para el factor de carga12, señalada en la ecuación (4.3), con la cual es posible,

conociendo la energía, calcular la demanda máxima coincidente para cualquier conjunto de

clientes.

Referente a los supuestos relacionados con la demanda se debe indicar que las cargas se

asumieron del tipo (P + j Q), con un factor de potencia idéntico para todos los consumos de

0,93 inductivo.

500(%)

40%

Clientes si ClientesFc

en otro caso

βα δ ⋅ − ≤=

(4.3)

Donde:

• Fc : factor de carga del grupo de clientes

• Clientes : número de clientes de la agrupación.

• α : 0,1687

• β : 0,1577

• δ : 6,3314%.

11 Ingenieros y Economistas Consultores SA www.inecon.cl 12 En este trabajo se supondrá como correcto el trabajo de ajuste de factor de carga realizado por Inecon en “Estudio para el Cálculo de las Componentes de Costo del Valor Agregado de Distribución (VAD), Área Típica 1: Chilectra” (Systep e Inecon, 2004)

40

También se debe constatar que al tratarse de una planificación desde cero el único dato de

entrada lo constituye la demanda de los consumos y su posición, la cual corresponde a la

ubicación georreferenciada de cada uno de los medidores de la mini-zona en cuestión. Sin

embargo la sola ubicación de los consumos no es suficiente, dado que consumos que de

acuerdo a su distancia se encuentran cercanos, podrían estar separados por un accidente

geográfico que no permita la asociación entre ellos. Otra situación posible es que existan

consumos al interior de una zona urbana, que pertenezcan al mismo subconjunto pero que

sean imposibles de unir dado que no existe red vial que los conecte. Para evitar tales

situaciones se propone considerar el trazado vial en el proceso de optimización, por lo cual

se requiere conocer la georreferenciación de todas las calles, o tramos de calles, que

pertenecen a la mini-zona, y la pertenencia de cada uno de los consumos a una única calle,

de esta forma será posible asociar consumos que puedan ser conectados y se evitará el paso

a través de zonas prohibidas.

Por lo cual, como etapa previa al proceso de micro-optimización, se debe realizar para cada

una de las mini-zonas el trazado vial, la asignación de los consumos, y la determinación de

la conectividad vial.

4.3.1 Etapa previa: determinación de la red vial

La necesidad de esta etapa previa, tal y como ya se mencionó, surge del objetivo de lograr

una agrupación posible de los consumos, de forma que las asignaciones propuestas por la

metodología sean replicables en la realidad. Para ello se debe considerar que para toda la

zona en análisis se posee una base de datos con la posición de los consumos y la demanda

de energía de cada uno de ellos, que pueden ser fácilmente ingresados a la metodología. Sin

embargo, con las calles sucede algo más engorroso, dado que los datos disponibles de ellas,

corresponden a una cobertura de ARCVIEW13, es decir corresponden a una representación

vectorial de las calles en un sistema de información geográfica (SIG), entendiendo un SIG

como un sistema basado en computador capaz de trabajar con datos georreferenciados, en

el cual se realiza la entrada, gestión, manipulación, análisis y salida de dichos datos

13 Paquete de programas SIG que trabaja con representaciones vectoriales de cada objeto geográfico ya sea a través de puntos, líneas, o polígonos.

41

(Aronnof, 1995), debido a tal situación, el acceso a las coordenadas de las calles no es

inmediato, dado que su representación está en el formato de poli-líneas (representación

vectorial) y no como una sucesión de puntos, no obstante, tal representación vectorial, esta

implícitamente basada en la sucesión de tramos, por ende, en este trabajo los datos

señalados se consiguieron con la creación de un programa en Avenue, lenguaje de

programación propio de ARCVIEW 3.2, mediante el cual se pudo obtener la posición

inicial y final de cada tramo que compone una misma calle. Situación que se puede apreciar

en la figura (4.4), donde se muestra el trazado vial para una mini-zona, en ella los puntos

representan a los consumos y los asteriscos representan los vértices de los tramos de calles

obtenidos desde la cobertura en ARCVIEW.

3.785 3.79 3.795 3.8 3.805 3.81

x 104

7050

7100

7150

7200

7250

7300

Figura 4.4: Trazado vial para una mini-zona

Una vez que se conoce la topología vial es de suma importancia, para garantizar que la red

de baja tensión se trace a través de ella, conocer a que calle pertenece cada consumo, para

conseguir este objetivo se toma como supuesto, que cada consumo esta asociado al tramo

de calle más cercano, asignación que es realizada con el procedimiento general que se

explica a continuación:

[m]

[m]

42

1. Se calcula la ecuación de la recta para todos los tramos de la mini-zona,

almacenando los vértices que unen un tramo y su ecuación correspondiente.

Recuérdese que dados dos vértices (X1,Y1) y (X2,Y2) , la recta que los une es:

( )2 11 1

2 1

Y YY X X Y

X X

−= ⋅ − +

− (4.4)

Para los casos en que la pendiente es infinita, es decir en aquellos donde el tramo es

paralelo al eje Y (X2=X1), se modificó la posición de uno de los vértices en tan sólo

unos centímetros, de forma que no se indefiniese la función (ecuación 4.4). Además

en los casos en que existe redundancia de información, esto es cuando los tramos,

no representan intersecciones de calles, sino que simplemente son divisiones en una

misma cuadra, se muestrearon tales vértices de manera obtener la misma

información en un número menor de tramos, con lo que se disminuye el número de

ecuaciones a calcular y por ende el tiempo de iteración de la metodología. Ejemplo

típico de esto, lo constituyen las rotondas en que la información disponible asigna

tramos cada un metro, ya que se trata de emular una circunferencia mediante

polígonos regulares con sobre 100 aristas, no obstante tal exceso de información es

en la práctica irrelevante, por lo que se opta aproximar tales rotondas por decágonos

regulares.

2. Se calcula la distancia entre todos los consumos y todos los tramos de calles, a

través de la ecuación que determina la distancia entre un punto y una recta. Los

cálculos aprovechan el ordenamiento matricial de los datos, con lo que es posible

obtener, sin necesidad de un proceso iterativo, una matriz en que el elemento dij,

indica la distancia entre la recta que representa al tramo i y el consumo j.

3. Se asigna cada consumo a su tramo más cercano. Se debe tener presente que la

distancia calculada indica la distancia perpendicular entre el consumo y la recta, si

se denomina como proyección del consumo sobre la recta, al punto en la recta en el

que se mide tal distancia, se consideran como candidatos factible de asignación,

aquellos tramos en que la proyección del consumo sobre la recta pertenece a un

43

tramo, es decir que se encuentre contenido entre el vértice inicial y final sobre los

que se traza dicho tramo. Con lo que se garantiza que los consumos sean asignados

al tramo de recta más cercano, situación real, lo que no necesariamente coincide con

la recta más cercana. Por lo tanto cada consumo es asignado al tramo de calle

factible más cercano de acuerdo a la distancia euclidiana que los separa.

Con el procedimiento anterior es posible determinar una buena aproximación sobre la

pertenencia de un consumo a una determinada calle, lo que será de gran utilidad a la hora

de trazar la red. En la figura 4.5 se observa la aplicación del procedimiento a una mini zona,

en ella los puntos representan a los consumos y las cruces a sus proyecciones sobre el

trazado de las calles.

Figura 4.5: Asignación de los consumos a una calle

Por tanto ahora será posible trazar la red de baja tensión soslayando los accidentes

geográficos, dado que se asume que el trazado vial también los evita, así será imposible

trazar una red a través de un cerro, dado que no existirá calle que lo atraviese, sino que por

3.798 3.8 3.802 3.804

x 104

7070

7080

7090

7100

7110

7120

7130

7140

7150

7160

3.785 3.79 3.795 3.8 3.805

x 104

7050

7100

7150

7200

7250

[m]

[m]

[m]

[m]

44

el contrario, será rodeado por la red vial, con esto no sólo se considera la distancia como

parámetro de trazado de la red sino que se utiliza la distancia de comunicación sobre un

grafo determinado (red vial), es decir la distancia vial que une un punto A y B, lo que no

necesariamente coincide con la distancia a campo traviesa entre ambos puntos, logrando

obtener mayor información y por ende una mejor aproximación para resolver el problema

real.

Sin embargo, aún queda un problema importante a resolver en esta etapa previa, el cual esta

dado por evitar asociar en un mismo subconjunto elementos que en la práctica no puedan

ser unidos, debido a la ausencia de red vial que los conecte. En este caso es necesario

señalar, que la zona que se busca planificar es eminentemente urbana, no obstante la

metodología propuesta puede resolver indistintamente zonas de abastecimiento rural y

urbanas, y por cierto una mezcla de ambas. La única distinción al respecto es que si en una

mini-zona no existe trazado vial, lo que probablemente corresponderá a una zona rural, la

distancia a utilizar será simplemente la distancia a campo traviesa, por lo que el problema

en discusión no tiene cabida, ya que cualquier subconjunto será posible. Situación que no

ocurre cuando si existe red vial, caso típicamente urbano, en el que el trazado no puede

pasar por zonas edificadas y debe entonces respetar a cabalidad el callejero, es decir se

unirán en una misma red sólo aquellos consumos que puedan ser comunicados a través de

la red vial. Para evitar entonces la asignación a priori de cargas no comunicadas, se divide

cada mini-zona en islas viales, donde cada isla vial corresponde al conjunto tramos de red

conectados en que es posible acceder a cualquiera de los tramos de la isla desde cualquier

tramo de ella mediante una sucesión de tramos intermedios que los unen.

En términos matemáticos, sea el trazado vial en la mini-zona un grafo G (V, E) no

orientado, con V el conjunto de vértices y E el conjunto de arcos (vértices y tramos de la

red vial respectivamente). El grafo se asume no orientado14, puesto que para efectos de la

red eléctrica, no es de importancia conocer el sentido de las calles. De acuerdo a la teoría de

grafos se tienen las siguientes definiciones:

14 Grafo no orientado, también denominado grafo no dirigido es un par G=(V,E), con V conjunto finito de vértices y E conjunto de arcos, donde un arco es un par no ordenado (u,v) con u,v pertenecientes a V y u distinto de v.

45

• Se dice que entre los vértices vo y vk existe un recorrido de longitud k si existe una

sucesión de vértices y aristas de la forma {(vo, v1), (v1, v2), (vi, vi+1), …, (vk-1, vk)}.

• Se denomina camino de longitud k entre los vértices u y v pertenecientes a V, a un

recorrido de longitud k desde el vértice u al vértice v que tiene k aristas diferentes

entre sí.

• Si existe un camino P desde u hasta v se dice que v es alcanzable desde u mediante

P.

• Se dice que el grafo es conexo si dos vértices cualquiera pertenecientes a V están

conectados por un camino de longitud k, con k: {1,...,E}.

• La relación, u es alcanzable desde v y v es alcanzable desde u, sobre el conjunto de

los vértices V del grafo es una relación de equivalencia. Las clases de equivalencia

son el conjunto de vértices sobre los que se puede establecer entre todos sus vértices

la relación de equivalencia y finalmente las componentes conexas de G, son todos

los grafos (subconjuntos del grafo principal) generados a partir de las clases de

equivalencia.

A modo de ejemplo en la figura 4.6 se presenta un grafo en donde es posible observar tres

componentes conexas, una está demarcada por una circunferencia, otra por un rectángulo, y

la tercera corresponde al resto del grafo que no se encuentra delimitado.

46

3.88 3.89 3.9 3.91 3.92

x 104

8050

8100

8150

8200

8250

8300

8350

8400

8450

8500

8550

Figura 4.6: Componentes conexas de la red vial

De la figura y de las definiciones anteriores se desprende que el número de islas viales al

interior de una mini-zona es igual al número de componentes conexas del grafo que

representa a la red vial al interior de dicha mini-zona, donde cada una de tales islas

constituye una red conexa. Por lo tanto el ejercicio a realizar consiste precisamente en

determinar el número y estructura de cada componente conexa, denominada en este trabajo

isla vial. Para ello se realiza una algoritmo constructivo, se encuentra en primer término la

matriz de tramos coincidentes, cuya variable Xij, indica si el tramo i con el tramo j tienen un

vértice en común, el valor uno indica que sí existe vecindad y el valor cero indica la no

existencia de vértices comunes, posteriormente se comienza en un arco cualquiera del grafo

total, y por medio de la matriz de tramos comunes se identifican los tramos vecinos, los

cuales pertenecen claramente a la misma isla vial, luego se incorporan progresivamente los

vecinos de los vecinos encontrados, y así sucesivamente hasta que no es posible incluir más

vecinos, de esta manera se construye una isla (subgrafo conexo), si todos los tramos (arcos)

de la mini-zona son incluidos implica que la red vial de la mini-zona es conexa, de lo

contrario se elige un vértice que no pertenezca a la isla encontrada y se vuelve a realizar el

procedimiento, secuencia que se repite hasta que no queden tramos sin asignar.

[m]

[m]

47

Una vez que se tienen las islas viales, y teniendo en consideración que todos los consumos

al interior de cada una de ellas son posibles de comunicarse a través de la red vial, se debe

incorporar una pequeña modificación al algoritmo propuesto en el diagrama de flujo de la

figura 4.3 (referente a la micro-optimización), esta es que en vez de realizar la metodología

para cada mini-zona se realizará para cada isla de cada mini-zona, con lo cual se evita la

asignación de consumos entre zonas sin conectividad vial, con esta consideración se puede

comenzar con el análisis de cada una de las etapas ahí señaladas. Considérese que el

algoritmo parte con la asignación de i transformadores, en particular con i igual a uno.

4.3.2 Ubicación y asignación de los transformadores

La ubicación preliminar de los transformadores se realiza vía k-means sin la consideración

de la red vial de cada isla, sino que únicamente en atención a la distancia euclidiana de los

consumos, tal como se observó en la explicación de k-means, el algoritmo parte con la

ubicación de los centros en cualquier posición, elegidos aleatoriamente entre los consumos,

con lo cual no se garantiza obtener siempre una misma solución, para minimizar tal efecto,

se usan tres lanzamientos, es decir se realiza la ubicación de i centros tres veces para así

escoger el caso de menor distorsión.

Tabla 4.2: Menor distorsión por número de lanzamientos

Nº de

Lanzamientos

Distorsión

Total (Km)

Nº de

Lanzamientos

Distorsión

Total (Km)1 409132 10 396566

2 402308 11 397209

3 396766 12 405501

4 397964 13 401698

5 397355 14 398206

6 400994 15 394098

7 392883 16 385206

8 390408 17 392108

9 386930 18 388492

10 395619 19 396934

La elección particular de tres lanzamientos se debe por un lado a reconocer la naturaleza no

determinística del método k-means, y con ello asumir que un único lanzamiento no entrega

48

necesariamente la mejor respuesta, y por otro no incrementar sin necesidad los tiempos de

ejecución, dado que se podrían, en el extremo, realizar cientos de lanzamientos para así

elegir con mayor probabilidad una mejor elección, con un tiempo de ejecución también

cientos de veces mayor. No obstante de la tabla 4.2, donde se muestra la menor distorsión

total para 300 mini-zonas cuando se realizan distintos lanzamientos, se puede observar que

no existen grandes beneficios en realizar para cada ubicación de centros un número

superior a 3 lanzamientos, por lo que se elige dicho número en virtud que representa un

buen mix entre calidad de la solución y tiempo de ejecución asociado.

Una vez que se realiza la ubicación preliminar de los transformadores, estos de acuerdo a la

metodología ya planteada, referente a la asignación de las calles, son re-ubicados en la calle

más cercana, de forma que también su conexión a los consumos asociados respete la

topología de la red vial de su mini-zona correspondiente.

Luego de esto, al conocerse ya la ubicación sobre la red vial de cada transformador y sus

consumos asociados, se asigna considerando la tasa de crecimiento de la demanda la

capacidad de cada uno de ellos, siguiendo los siguientes pasos:

1. Se calcula la demanda media que debe satisfacer el transformador en el año base,

esto es, se suman las energías de cada uno de los consumos asignados al

transformador y se divide por el número de horas del período (8760 horas).

2. Se obtiene el factor de carga a partir de la expresión (4.3) considerando el número

de clientes asociados al transformador.

3. Se obtiene la demanda máxima coincidente (Dmax) de los consumos para el año

base, a partir de la demanda media (Dm) y del factor de carga (Fc)

maxmax

m mc

c

D DF D

D F= ⇒ = (4.5)

4. Se asigna el menor transformador capaz de abastecer la evolución de la demanda

máxima coincidente a lo largo del horizonte de estudio.

Si no existe un transformador capaz de satisfacer la demanda de sus consumos asociados,

es decir uno de los i transformadores cubre una demanda superior a la que es capaz de

49

entregar el mayor transformador disponible15, entonces se vuelve a realizar el proceso de k-

means, pero esta vez con i+1 ubicaciones, proceso que se realiza hasta que todas las

localizaciones tienen asignado un transformador (capacidad de transformación).

Por tanto al finalizar el proceso se tiene la ubicación y capacidad de cada transformador

más la ubicación de cada uno de los consumos que deben abastecer. El siguiente paso es

determinar la topología y costos de la red de baja tensión que los conecta con las cargas que

deben suministrar, por lo que es necesario calcular el costo de los conductores empleados y

el costo de las pérdidas asociadas a la red.

4.3.3 Trazado de red

El criterio empleado para obtener el trazado de la red se basa primordialmente en la

distancia que existe entre los consumos, además, con el fin de incorporar la incidencia del

flujo en la red, el transformador se moverá a una nueva ubicación una vez que la red óptima

sea escogida, de manera de estar aproximadamente en un nodo donde la red se encuentre

equilibrada, es decir que la diferencia entre los flujos que salen de él no sea considerable.

Es por esto que el trazado de la red consistirá básicamente en trazar el árbol de mínima

expansión con raíz en la ubicación del transformador. Entendiéndose a tal árbol como el

grafo no dirigido de menor distancia que conecta todos los nodos sin generar ningún ciclo16

(grafo acíclico), y siendo la raíz del árbol el único vértice del grafo que no tiene un arco que

lo preceda.

Se debe señalar que el problema del árbol de mínima expansión es un problema clásico de

optimización combinatorial. Fue formulado por primera vez en 1926 por Boruvka,

precisamente en un problema de electrificación, luego de ello esta modelación ha sido

aplicada para enfrentar numerosos problemas en variadas áreas como telecomunicaciones,

sistemas de transporte, entre otros, a través de procedimientos que han permitido su

solución, los cuales debido a su complejidad algorítmica hacen del árbol de mínima

expansión un problema del tipo P, es decir, tales algoritmos resuelven el problema en

tiempo polinomial. Estos fueron desarrollados en forma casi paralela por Kruskal (1956) y

15 La tabla con las capacidades y costos de los transformadores disponibles se muestra en el Anexo D 16 En un grafo no dirigido un camino {V0, V1, V3, …, VK} forma un ciclo si V0=VK y los Vi son distintos

50

Prim (1957), ambos corresponden a algoritmos voraces, lo que significa que en cada

iteración escogen la mejor alternativa para ese instante sin considerar los pasos futuros.

Considerando un grafo G (V, E) donde cada arco E tiene un peso (valor) asociado, que en el

caso en cuestión corresponde a la distancia que existe entre los nodos que comunica el arco,

el algoritmo de Kruskal se puede resumir en los siguientes pasos:

1. Se marca el arco con menor peso. Si hay más de uno se escoge cualquiera de ellos.

2. De los arcos que quedan, se marca el que tenga menos peso, nuevamente si hay más

de uno se escoge cualquiera de ellos.

3. Repetir el paso 2 siempre y cuando el arco escogido no forme un ciclo con los ya

marcados.

4. El algoritmo termina cuando existen n-1 arcos marcados, siendo n el número de

nodos del grafo.

En tanto el algoritmo de Prim se puede resumir como sigue:

1. Se marca un nodo cualquiera como nodo de partida, denominado raíz del árbol, con

lo que se inicializa.

2. Se agrega al árbol aquel vértice que este conectado a cualquier vértice del árbol por

el arco de menor peso.

3. Se repite el paso 2 siempre que el arco que se incluye conecte un vértice que

pertenece al árbol con uno que aún no pertenece a él.

4. El proceso termina cuando todos los vértices pertenecen al árbol.

Dado que ambos algoritmos presentan la misma complejidad O(n log n), con n el número

de vértices (tamaño de la entrada), se opta arbitrariamente, por utilizar el algoritmo de Prim

en el trazado de la red en atención a su fácil implementación computacional. En la figura

siguiente se puede apreciar su aplicación para un transformador y sus cargas asociadas.

51

Figura 4.7: Árbol de mínima expansión

Sin embargo, en ella es fácilmente apreciable que la aplicación directa del Algoritmo de

Prim no respeta las zonas prohibidas dado que se observan cruces a través de las zonas

urbanas (entre calles), lo que se evita si se considera el trazado vial como restricción para el

trazado de la red de baja tensión. Por lo tanto para guiar el camino del algoritmo se utilizan

las proyecciones de los consumos sobre las calles en vez de su posición real, guardando

siempre la distancia desde los consumos a su proyección ya que esta constituye una

aproximación a la longitud de los empalmes a emplear. Sin embargo, tal información si

bien permite que consumos que pertenecen a una misma calle queden conectados, no

garantiza que no existan cruces en zonas distintas a las esquinas, por lo cual se incluyen

nodos auxiliares que permitan señalar de mejor manera las rutas posibles del algoritmo,

estos nodos son los vértices de los tramos de calle, lo que ayuda a garantizar bifurcaciones

sólo en las intersecciones de tramos, y otros nodos extras en aquellos tramos que si bien

pertenecen a la mini-zona no poseen consumos de manera de permitir las uniones de

consumos a través de tramos que no los poseen. En términos sencillos el algoritmo

empleado es:

3.785 3.79 3.795 3.8 3.805 3.81

x 104

7050

7100

7150

7200

7250

3.793 3.794 3.795 3.796 3.797 3.798 3.799

x 104

7180

7200

7220

7240

7260

7280

7300

[m] [m]

[m] [m]

52

1. Se inicializa el árbol con la posición del transformador (raíz del árbol).

2. Se agrega al árbol aquel nodo aún no incluido, real o auxiliar, que esté más cercano

a cualquiera de los nodos del árbol, siempre y cuando tal nodo pertenezca al mismo

tramo.

3. Se repite el paso 2 hasta que todos los nodos del tramo son incluidos.

4. Se agrega al árbol aquel nodo aún no incluido, real o auxiliar, más cercano a los

vértices del conjunto de tramos ya incluidos que pertenezca a un tramo vecino,

definiendo tramo vecino a aquel que comparte un vértice con el tramo en cuestión.

5. Se repite el paso 2 y 3 para el nuevo tramo incluido.

6. Se repite el paso 4 y 5 hasta que todas las proyecciones de los consumos sobre los

tramos de calle, sean agregados, situación que hace que el algoritmo finalice.

Del paso 6 se desprende que el criterio de parada no esta dado por el uso de todos los

nodos, reales (proyecciones de los consumos) y auxiliares, con lo que posiblemente

caminos que sigue el algoritmo a través de nodos auxiliares no conectan nodos reales Para

soslayar tal efecto se lleva a cabo un proceso de poda, en que todos aquellos nodos

auxiliares que no entregan información, es decir que sólo sirvieron para ampliar el espacio

de búsqueda, pero que finalmente no conectaron nodos reales son eliminados, de manera de

tener únicamente el árbol de mínima expansión en que todas las hojas17 del árbol son nodos

reales. Ejemplo del trazado de la red se presenta en la figura 4.8.

17 Si (u, v) es el último arco en el camino desde la raíz del árbol hasta el vértice v, entonces se dice que u es el padre de v y v es hijo de u. La raíz es el único nodo del árbol que no tiene padre. Un nodo sin hijo se denomina hoja y el resto de los nodos se denominan nodos internos.

53

Figura 4.8: Trazado de la red de baja tensión

Si bien en la figura anterior, se aprecia claramente el trazado de la red de baja tensión

respetando la topología vial, y que la posición del transformador se ubica aproximadamente

en el centroide de la red, lo que ayuda a garantizar una buena solución, dado que de esta

manera los flujos se reparten en forma equilibrada, tal situación no es garantizable para

todos los casos, debido a que la elección del centroide se realiza en la etapa de k-means, sin

la consideración vial, sino que de acuerdo a la cercanía de consumos pertenecientes a una

misma isla de una mini-zona determinada, con lo cual la proyección de dicho centroide

sobre el tramo de calle más cercano, no necesariamente coincide con el centroide de línea

de la red de baja tensión trazada (situación que si ocurre en la figura 4.8). Es decir en tal

ubicación no se produce el mejor equilibrio entre los flujos que salen del transformador,

razón por la cual se realiza la reubicación de los transformadores mediante el equilibrio de

la red, metodología descrita a continuación.

Equilibrio de red

En esta sub-etapa se lleva acabo la re-localización de cada uno de los transformadores

desde su posición inicial dada por la proyección del centroide calculado con k-means sobre

el tramo de red más cercano, a una nueva posición en que los flujos que salen desde el

transformador sean lo más parecidos posibles, ello en virtud de que es imposible equilibrar

totalmente la red (flujos iguales por todas las ramas que salen del transformador), dado que

3.84 3.85 3.86 3.87 3.88 3.89

x 104

6900

6950

7000

7050

7100

7150

7200

7250

7300

7350

7400

3.84 3.845 3.85 3.855 3.86

x 104

7050

7100

7150

7200

7250

7300

[m] [m]

[m] [m]

54

para disminuir el espacio de búsqueda constituido por cualquier posición (x, y)

perteneciente a la red, se consideran como ubicaciones factibles del transformador sólo

aquellos nodos incluidos en la red, ya sea se trate de consumos o de nodos auxiliares, por

tanto el equilibrio total de la red puede que no pertenezca al conjunto de posiciones

factibles.

Para llevar a cabo el equilibrio en cuestión, se propone un algoritmo iterativo, puesto que

no existe una metodología directa para encontrarlo, de hecho se debe hacer notar que el

centroide de una figura compuesta por tramos no necesariamente pertenece a la figura, sino

que puede ubicarse externo a ella, lo que no garantiza encontrar el equilibrio de red

buscado. La metodología propuesta se basa en el hecho que un movimiento del

transformador, del que se supone salen dos ramas, desde su posición inicial hacia el nodo

hijo de la rama de mayor flujo, hará que tal flujo disminuya en ∆P y por tanto la rama de

menor flujo aumentará en ∆P. El algoritmo simplificado es el siguiente:

1. Se calculan los flujos que salen por ambas ramas del transformador. Se define

equilibrio como el valor absoluto de la diferencia entre los flujos.

2. Se ubica el transformador en el nodo hijo con mayor flujo.

3. Se revisa el número de ramas que salen desde la nueva posición

Si el número de ramas es 2

3.1. Se calculan los flujos que salen por ambas ramas

3.2. Se repiten los pasos 2 y 3 hasta que el equilibrio no disminuya más.

Si el número es mayor que 2

3.4 Se parte desde los hijos de la nueva posición, la que no se considera factible, y

se realiza el proceso 3, siempre y cuando por la rama se mejore el equilibrio

4. El proceso finaliza cuando no es posible seguir ningún camino de la red que mejore

el equilibrio. Nótese que si un camino empeora el equilibrio, no se continúa la

búsqueda a través de él, con lo que no se revisan todas las ubicaciones sino sólo las

que están en la dirección del descenso.

55

Figura 4.9: Equilibrio de red

En la figura 4.9 se muestra la aplicación del algoritmo de equilibrio para dos redes, en ellas

el triángulo de mayor tamaño representa la posición inicial del transformador, mientras que

el triángulo de menor tamaño corresponde a la posición de equilibrio de la red, los nodos no

asignados corresponden a los nodos auxiliares no utilizados en el trazado de la red

(producto del proceso de poda). Se debe destacar que el equilibrio de red incorpora mejoras

en la solución final, puesto que disminuye los costos producto de una mejor asignación de

los conductores, de hecho el ahorro producto de su incorporación oscila entre 1,5% a 3%

respecto a la solución que no incorpora el equilibrio. Por ejemplo, en una corrida del

modelo para la comuna de Macul, considerando mini-zonas de 500 por 500 metros, se

obtiene un costo de 1.906.194.90118 pesos si no se considera el equilibrio, en cambio al

incluirlo, el nuevo costo es de 1.820.926.206 pesos, lo que representa un ahorro de 4,47 %,

no obstante el incremento en el tiempo de ejecución para este ejemplo es de 114 %,

aumentando desde 3,05 minutos a 6,55 minutos. Por lo que, evidentemente, existe un trade

off entre tiempo de ejecución y calidad de la solución, el que se vuelve más importante en

la medida que la zona a optimizar crece, situación que se analizará en detalle al finalizar el

18 Los datos presentados en este párrafo corresponden a valores promedio obtenidos a partir de 20 corridas distintas del modelo. Para más detalles refiérase a la sección Iteraciones y Resultados del presente capítulo.

3.785 3.79 3.795 3.8 3.805 3.81

x 104

7050

7100

7150

7200

7250

3.8 3.805 3.81 3.815 3.82

x 104

7700

7750

7800

7850

7900

7950

[m] [m]

[m] [m]

56

presente capítulo, una vez que todas las etapas del proceso de micro-optimización se

encuentren explicitadas.

4.3.4 Selección óptima de conductores

Una vez que se conoce el trazado de la red de baja tensión asociada a cada uno de los

transformadores de la mini-zona, ya sea incluyendo o no el equilibrio de red, es necesario

conocer cuanto vale dicha ruta óptima, es decir se debe valorizar el trazado, en cuanto uso

de material y longitud del mismo. Del apartado anterior, se conoce la distancia existente

entre cada uno de los nodos y por ende la distancia de cada uno de los tramos que tienen

asociado algún tipo de conductor. El valor del conductor asociado a cada tramo dependerá

del tipo de material empleado y del flujo que por él atraviesa, por lo que es necesario llevar

a cabo una selección óptima de conductores, de manera que el conductor escogido para

cada tramo minimice los costos de inversión más pérdidas.

La selección óptima de conductores ha sido abordada en numerosas investigaciones

(Adams y Laughton, 1974, Wall et al, 1979, Tram y Wall, 1988, Mandal y Pahwda, 2002),

siendo uno de los procedimientos más usados en planificación el de separar el problema de

selección del resto de la red, esto es, elegir un conductor pseudo óptimo para cada uno de

los tramos en función exclusiva de los flujos que lo atraviesan y las variables eléctricas y

económicas relacionadas con el flujo en cuestión, sin considerar el efecto que tal elección

tiene aguas abajo de la red (Mandal y Pahwda, 2002). Dado que el procedimiento ya ha

sido realizado y no constituye un aporte original al problema de planificación, en el

presente trabajo se opta por usar los resultados obtenidos en el estudio de VAD del año

200419 (Systep e Inecon, 2004), no obstante tal metodología será igualmente presentada, de

manera de constatar las variables involucradas en el proceso de optimización de redes de

baja tensión, en lo referente a selección de conductores.

Antes de ello, para utilizar en forma directa tal metodología es fundamental conocer los

flujos de potencia que circulan por cada uno de los tramos, tarea que no es trivial, dada la

considerable cantidad de cargas involucradas en cada una de las redes, situación que hace

19 El uso de los mismos valores se realiza para poder tener un marco comparativo que permita analizar los resultados obtenidos en la investigación aquí propuesta.

57

necesario realizar algún tipo de simplificaciones que permitan obtener buenas soluciones,

sin necesidad de resolver un algoritmo de flujo AC exacto para encontrar la respuesta, es

decir sin la utilización de herramientas tradicionales para flujos de potencias tales como los

métodos de descenso de Newton, Gauss, y simplificaciones de los mismos. En ellos la

componente matricial20 es relevante, y en el caso de redes de baja tensión el número de

cargas es elevado y por tanto la dimensión de las matrices involucradas en tales

procedimientos también lo son, situación que produce gastos excesivos de memoria y

tiempo de ejecución producto de la necesidad de invertir y trabajar con grandes matrices,

tiempos que afectan el ejercicio de planificación puesto que en el algoritmo propuesto se

resuelven miles de flujos de potencia, siendo conveniente aprovechar la característica radial

de la red de baja tensión, y realizar supuestos, cuya ejecución no incluye en la planificación

más error que el posible asociado a la proyección de la demanda.

Modelo de flujo de potencia

El elemento característico de las redes de baja tensión es su topología radial, por lo que en

el flujo de potencia hay una relación directa entre las cargas entre un nodo con su nodo

padre17 y con sus nodos hijos17, sin existir intercambios entre nodos de un mismo padre,

situación que permite identificar y formular el problema en términos simples, a diferencia

de lo que sucede con redes enmalladas donde los flujos y voltajes en cada uno de los

consumos inciden en el resto de la red.

En el problema a resolver, las cargas están representadas por un modelo PQ, es decir se

asume que se conoce su potencia activa y reactiva, y por ende implícitamente su potencia

aparente, las cargas en su totalidad se consideran de naturaleza inductiva con un factor de

potencia de 0,93, además se considera que la red se encuentra equilibrada, supuesto que si

bien es difícil de adoptar en la operación21 de un sistema de distribución real, en el cual las

cargas asignadas a cada fase no se encuentran del todo bien distribuidas, en un ejercicio de

planificación se asume que se tomarán las medidas año a año para que la red si se encuentre

equilibrada, dado que ello implica mejoras en la operación del sistema y por tanto se asume

20 Las matrices son del tipo n x n, con n el número de nodos (cargas) conectados a la red.

58

que en el largo plazo existen los incentivos suficientes para que la red se encuentre en dicho

estado, entonces al asumir el equilibrio se puede resolver la red trifásica de acuerdo a su

equivalente monofásico. En atención a lo mencionado, la primera ley de Kirchhoff en una

red radial esta dada por la ecuación 4.6 (Peco, 1999):

∑=

++=R

kkiii SSLLS

1

(4.6)

i

iA

iiii Z

V

SZIL ⋅=⋅=

2

)(

22

(4.7)

Donde: • Si : es la potencia aparente al comienzo del tramo i. • Li : son las pérdidas en el tramo i. • SLi : es la demanda aparente del nodo i. • R : es el número de ramas que salen del nodo i. • Zi : es la impedancia del tramo i. • Ii : es la corriente que circula a través del tramo i. • VA(i) : es el voltaje aguas arriba del nodo i.

Desarrollando la ecuación 4.7 se tiene que:

( )( )

( )( ) ( )

2

)(

22

2

)(

22

2

)(

222

2

)(

2

iA

iii

iA

iiiii

iA

iiii

iA

iii

V

QPxj

V

QPrxjr

V

QPxjr

V

QjPL

+⋅⋅+

+⋅=⋅+⋅

+=⋅+⋅

⋅+=

Con:

• Pi : es la potencia activa al comienzo del tramo i. • Qi : es la potencia reactiva al comienzo del tramo i. • ri : es la resistencia del tramo i. • xi : es la reactancia del tramo i.

Reemplazando Li en la ecuación 4.6 y anotando las variables en su expresión compleja, se

tiene que la potencia aparente al principio del tramo i es:

( ) ( )( )∑

=

⋅++⋅+++⋅

⋅++⋅

=⋅+R

kkkii

iA

iii

iA

iiiii QjPQLjPL

V

QPxj

V

QPrQjP

12

)(

22

2

)(

22

)(

21 La operación se refiere a la actividad diaria de explotación de las redes de distribución, estos es maniobras a ejecutar en caso de falla de algún componente, reconfiguración de redes, inyección adicional de reactivos, etc.

59

Igualando la parte real del lado derecho de la ecuación con la parte real del lado izquierdo,

y haciendo lo mismo con la parte imaginaría es posible obtener la expresión para la

potencia activa y reactiva, respectivamente, para una red de topología radial.

( )∑

=

+++⋅

=R

kki

iA

iiii PPL

V

QPrP

12

)(

22

(4.8)

( )∑

=

+++⋅

=R

kki

iA

iiii QQL

V

QPxQ

12

)(

22

(4.9)

Donde

• PLi : es la demanda activa del nodo i. • QLi : es la demanda reactiva del nodo i.

Las expresiones (4.8) y (4.9) por sí solas no son suficientes para determinar los flujos que

circulan a través de los distintos tramos de la red, debido a que no se conoce el voltaje

aguas arriba del tramo, por lo que es necesario encontrar una tercera relación que permita

calcular |VA(i)|2 en función de Pi y Qi, de tal forma de tener tres ecuaciones con tres

incógnitas y así resolver el sistema para encontrar las variables en cuestión. Sin embargo,

puesto que se trata de una red de distribución de baja tensión se puede realizar una

simplificación importante, la que consiste en despreciar los términos cuadráticos de las

ecuaciones (4.8) y (4.9), ello dado que en los sistemas de distribución las pérdidas de cada

tramo son pequeñas en relación al flujo que los atraviesa (Rudnick et al, 1997, Peco, 1999),

de forma tal que al considerarse como cero el valor de Pi2 + Qi

2, y suponiendo que �VA(i) � 2

siempre es distinto de cero (para que la función no se indefina), se tienen las siguientes

ecuaciones simplificadas que fueron utilizadas en el presente trabajo:

∑=

+=R

kkii PPLP

1

(4.10)

∑=

+=R

kkii QQLQ

1

(4.11)

En las cuales se puede apreciar la independencia tanto de los flujos activos como reactivos

del voltaje en los nodos, posibilitando de esta manera, un cálculo rápido y simplificado en

60

el que partiendo desde los nodos extremos (hojas del grafo), se van agregando las

demandas aguas arriba, para así conocer los flujos en todos los arcos del grafo que

representa la red de baja tensión. Al implementar tal procedimiento se puede establecer el

flujo que circula por cada tramo. Nótese que las ecuaciones para la determinación del flujo

son independientes del tipo de conductor, no dependen de la impedancia de la línea, con lo

que el procedimiento de calcular los flujos para luego elegir el conductor es válido en el

marco de los supuestos realizados.

Metodología de selección de conductores

Para comprender la forma en que se realiza la selección, se deben tener presentes los

elementos fundamentales que en ella intervienen, por un lado se tienen los costos fijos

representados por la inversión necesaria en cada uno de los conductores que se realiza al

inicio del período de estudio, y por otro lado, los costos variables representados por los

costos asociados a las pérdidas de energía y potencia que dependen de la cantidad de

corriente que circula por cada conductor y que se producen durante todo el horizonte de

estudio, variando año a año producto del crecimiento de la demanda. En consideración a lo

anterior, para poder realizar una comparación entre los costos que se producen en los

distintos años, se recurre a la técnica tradicional de evaluación de proyectos, denominada

valor actual neto o también conocida como valor presente, en la que se incluyen, además de

los costos de inversión y operación de cada tipo de conductor22, variables como la

depreciación y valor residual de los conductores y parámetros como la tasa de descuento,

que identifica el riesgo del proyecto, y la tasa de impuesto.

Así, el valor actual neto de un determinado conductor por unidad de longitud ($/km.) será

una función que varía con respecto a la corriente que lo atraviesa, siempre y cuando dicha

corriente no sobrepase sus límites térmicos, además se debe reiterar que el período de

análisis corresponde a 15 años y señalar que para el cálculo de la depreciación y el valor

residual se considera una vida útil de 30 años para los conductores.

Entonces la expresión para el valor actual neto de un conductor tipo i, VANi (I), será:

22 El listado de conductores disponibles con sus respectivos precios, se encuentra en el anexo D

61

( )

15, ,

,00

(1 )( )

1

i k i ki i k

k

CL Timp Dep TimpVAN I INV

r=

⋅ − − ⋅= +

+∑ (4.12)

Donde

• INVi,0 : inversión inicial en un conductor del tipo i.

• CL(I)i,k : costo de pérdidas del conductor i en el año k para un valor de corriente I.

• Timp : tasa de impuestos que para efectos de la evaluación se consideró en 17 %.

• Depi,k : depreciación del conductor i en el año k.

Es importante explicitar la relación que existe entre las pérdidas y la corriente que los

atraviesa, tales relaciones y datos fueron obtenidos íntegramente del informe de VAD

período 2004-2008 (Systep y Inecon, 2004):

“Se consideran las pérdidas de potencia y de energía del conductor. El cálculo se realiza según las siguientes ecuaciones:

12expffcon1000

rICPP 2

i2k

pik ⋅⋅

⋅

⋅⋅ρ=

8760fcp1000

rICPE

i2k

eik ⋅

⋅

⋅⋅ρ=

Donde CPPi

k : Costo de pérdidas de potencia del conductor de tipo i el año k. [$] CPEi

k : Costo de pérdidas de energía del conductor de tipo i el año k. [$] Ik : Corriente en el año k. [Amp] fcon : Factor de coincidencia en alta tensión de las demandas presentes en la punta del

sistema (0,85). fexp : Factor de expansión de las pérdidas de potencia en alta tensión, en horas de punta del sistema eléctrico (1,016). fcp : Factor de carga de las pérdidas Considerando un factor de carga de 32% se calcula el factor de carga de las pérdidas según:

( ) 5,1fcfcp = Finalmente, el costo total de pérdidas se obtiene de la suma de costos de pérdidas de energía y potencia”

62

La ecuación (4.12) establece el VAN de un determinado conductor como función de la

corriente que circula por él, entonces, si por cierto tramo atraviesa un flujo P, que

determina implícitamente una corriente I, bajo un escenario determinado de crecimiento de

demanda, se evalúa la función de VAN de todos los conductores para tal corriente I,

escogiéndose como alternativa óptima, aquel conductor cuyo VAN sea el menor para dicha

corriente. Así los resultados obtenidos para la tasa supuesta de 2.75 % fueron:

Tabla 4.3: Resultado selección óptima de conductores

Corriente

Mínima (A)

Corriente

Máxima (A)

Sección

(mm2)Costo ($/km)

Tipo de

Conductor

0 22 16 259.827 Cobre

23 25 35 331.750 Aluminio

26 41 50 404.400 Aluminio

42 87 120 658.161 Aluminio

88 131 240 1.496.998 Aluminio

132 625 300 1.874.000 Aluminio

Lo que es interpretado por el algoritmo de la siguiente manera, si la corriente que circula

por un tramo de la red se encuentra entre 0 y 22 A, entonces se utilizará un conductor de

cobre de 16 mm2 en dicha sección, de igual manera se procederá para todos los tramos de la

red en concordancia con lo establecido en la tabla 4.3.

4.3.5 Cálculo de pérdidas de energía

De la etapa anterior, es posible conocer cual es el mejor conductor para un tramo a partir

del flujo que por él circula, dicha elección se realiza en atención exclusiva al tramo en

análisis, es decir sin la consideración de los tramos aguas abajo del tramo calculado, y por

ende sin la consideración de su acción en las caídas de tensión en el resto de la red. Por esta

razón se incorpora a la función objetivo el costo de las pérdidas de energía, que

implícitamente incorporan en el proceso de optimización las caídas de tensión, debido a que

actúan como una penalización a las caídas de voltaje (Sanhueza, 1994, Fawzi et al, 1983),

63

dado que un incremento en ellas (disminución de los voltajes) implica un aumento de las

pérdidas23 y por ende de su costo final.

Para poder valorizar las pérdidas de energía se debe tener presente, que el ejercicio de

planificación considera demanda de potencia, y por tanto se tiene para cada red el valor de

las pérdidas de potencia coincidentes entre los consumos que son abastecidos por un mismo

transformador. Tales pérdidas de potencia constituirán el indicador fundamental para el

posterior cálculo de las pérdidas de energía, por lo que su determinación es de vital

importancia. Del desarrollo de la ecuación (4.7) se tiene que las pérdidas activas24 están

dadas por:

( )2 2

2

( )

i

i i i

ACTIVAS

A i

r P QL

V

⋅ += (4.13)

De cuya ecuación se conoce el flujo activo y reactivo, puesto que fueron calculados en la

etapa anterior para cada tramo del trazado de la red, y además se conoce la resistencia, dado

que al realizar la elección del conductor, es posible determinar sus características técnicas

en función del tipo de conductor escogido y del largo del tramo de red, por lo que la única

variable desconocida es el voltaje aguas arriba del nodo i, VA(i). Para determinarla,

considérese la ecuación (4.14) que representa la aplicación de la ley de ohm a un tramo de

una red radial.

( )A i i i iV V I Z= + ⋅ (4.14)

Recordando que tales variables constituyen cantidades fasoriales, entonces la expresión

cartesiana de la ecuación (4.14), donde el subíndice R representa la parte real y el subíndice

I la parte imaginaria, es:

( ) ( ) ( )( ) ( )A i R A i I iR iI iR iI i iV jV V jV I jI r jx+ = + + + ⋅ +

Despejando la parte real y la parte imaginaria para Vi, se tiene:

( )iR A i R i iR i iIV V r I x I= − + (4.15)

23 Situación claramente apreciable en la ecuación (4.7) donde una disminución del voltaje genera una aumento en las pérdidas. 24 Las pérdidas activas son las que generan costos, dado que representan energía que se deja de vender producto de su disipación en forma de calor (efecto joule �I� 2R)

64

( )iI A i I i iR i iIV V x I r I= − − (4.16)

De donde para determinar |Vi|2 basta con sumar los cuadrados de las ecuaciones (4.15) y

(4.16), obteniéndose la siguiente relación:

( ) ( )( ) ( ) ( )2 2 2 2 2 2 2( ) ( ) ( ) ( ) ( ) ( )2 2i A i R A i I iR iI i i i iR A i R iI A i I i iR A i I iI A i RV V V I I r x r I V I V x I V I V= + + + + − + − −

( ) ( )22 2 2

( ) ( ) ( ) ( ) ( )2 2i A i i i i iR A i R iI A i I i iR A i I iI A i RV V I Z r I V I V x I V I V= + ⋅ − + − − (4.17)

No obstante la relación anterior está expresada en términos de corriente, toda vez que en la

etapa de selección óptima de conductores se calcularon los flujos de potencia, por lo es

necesario reescribirla en función de los datos disponibles. Para ello se utiliza el hecho que

la potencia compleja es el resultado del voltaje por el conjugado de la corriente, entonces

desarrollando y despejando la potencia activa y reactiva se tiene:

( ) ( )( ) ( )

( ) ( )

( ) ( )

i i A i R A i I iR iI

i A i R iR A i I iI

i A i I iR A i R iI

P jQ V jV I jI

P V I V I

Q V I V I

+ = + ⋅ +

= +

= −

(4.18)

Reemplazando (4.18) en (4.17) y notando que |Ii|2=|Si|

2 / |VA(i)|2, finalmente la expresión

para el voltaje es:

( ) ( ) ( )iiiiii

iA

iiiAi QxPrxr

V

QPVV ⋅+⋅⋅−+⋅

++= 222

2

)(

222

)(

2 (4.19)

En virtud de la relación (4.17), es posible calcular la magnitud del voltaje en cualquier

nodo, siempre y cuando se conozca el voltaje en el nodo aguas arriba (nodo padre). Como

el único voltaje que se conoce a priori es el voltaje en el transformador (nodo raíz) y los

parámetros de flujo de potencia y impedancias del conductor ya fueron calculados en la

etapa previa, sólo basta con recorrer la red aguas abajo del transformador de manera de ir

progresivamente calculando todos los voltajes. Sin perjuicio de lo anterior la relación

señalada puede ser simplificada, dado que en ella el término cuadrático que depende de los

parámetros de la línea es marginal con respecto al término lineal, razón por la cual también

se puede despreciar, entonces la expresión implementada en el presente trabajo para el

cálculo del voltaje en los nodos es:

65

( )iiiiiAi QxPrVV ⋅+⋅⋅−= 22

)(

2 (4.20)

Al conocer el voltaje en los nodos, se pueden calcular las pérdidas de potencia activa de

acuerdo a la ecuación (4.13). Si durante todas las horas del año se tuviese la misma

demanda, bastaría con multiplicar las pérdidas, obtenidas a partir de (4.13), por 8760

horas25 y así obtener las pérdidas de energía para un determinado año, sin embargo tal

situación no ocurre, puesto que el cálculo de pérdidas se realiza para el escenario de

demanda máxima coincidente de cada red. Para incorporar esta situación y dado que es

imposible realizar un cálculo para cada punto de demanda de la curva de carga, se opta por

aproximar las pérdidas de energía mediante las pérdidas medias de energía. Para lo cual se

considerarán las siguientes definiciones:

• Factor de carga, Fc, es la relación entre la potencia media de la curva de carga y la

potencia máxima, también denominada potencia punta. En (4.21) E es la cantidad

de energía consumida en el período T.

mediaC

punta punta

EP TFP P

= = (4.21)

• Factor de carga de las pérdidas, Fp, es la relación entre las pérdidas medias de

energía y las pérdidas de potencia en el escenario de mayor demanda (potencia de

punta).

mediaP

punta

LF

L= (4.22)

De esta forma las pérdidas medias de potencia serán FpLpunta, situación que hace necesario

estimar Fp, siendo interesante destacar la relación existente entre el factor de carga de las

pérdidas con el factor de carga26, dada por:

2c p cF F F< < (4.23)

En virtud que en este trabajo el factor de carga se supone conocido y depende del número

de consumos de la red, ecuación (4.3), bastaría entonces determinar la relación que permita

25 Número de horas de un año de 365 días

66

calcular el factor de carga de las pérdidas a partir del factor de carga. Dicha relación a

buscar no es genérica, producto que depende de la curva de carga de los consumos a

suministrar, no obstante, existen investigaciones en que se analizan diferentes curvas de

carga para obtener ecuaciones que reflejen en forma aproximada el comportamiento común

de tales factores (Buller y Woodrow 1928, Gustafson y Baylor 1988, Gustafson y Baylor,

1989). En particular, en esta investigación se utiliza una de las aproximaciones propuestas

por Gustafson y Baylor (1988), dada por:

20.08 0.92P C CF F F= ⋅ + ⋅ (4.24)

Con lo que las pérdidas medias de energía el tramo i, Lenergía,i, serían:

8760ii

P ACTIVASENERGÍAL F L= ⋅ ⋅ (4.25)

Como las pérdidas de energía representan energía que no se vende, pero que igualmente es

comprada por la distribuidora al generador, estas deben ser valorizadas al precio de venta

de energía del generador al distribuidor, el cual se consideró en 18,4527 $/kWh (Synex,

2004). Si además se considera que existe un crecimiento de la demanda, y por tanto

pérdidas distintas para cada uno de los años del horizonte de estudio, lo que implica costos

distintos a través del período, no es posible sumar tales costos de manera directa, sino que

se debe utilizar el método de valor actual neto, con lo que el costo de las pérdidas de

energía es:

( )

( ), ,0

1 1

1

1

jN T

ENERGÍA i

jPÉRDIDAS ENERGÍAi j

L gC C

r= =

⋅ += ⋅

+∑∑ (4.26)

Donde

• CPÉRDIDAS : costo total de las pérdidas de la red para todo el horizonte.

• CENERGÍA : costo unitario de energía.

• N : número de tramos de la red.

• T : número de años del horizonte de evaluación

26 Para un desarrollo completo de la relación entre el factor de carga y el factor de carga de las pérdidas véase Gonen (1986) páginas 52-61. 27 Valor calculado a partir de los precios de nudo y estructura de recargos vigentes el 31 de diciembre de 2003.

67

• g : tasa anual de crecimiento de las pérdidas.

• t : tasa de descuento anual.

4.3.6 Iteraciones y resultados

En virtud de las etapas anteriores es posible obtener el costo de los transformadores, el

costo de los conductores empleados en el trazado óptimo y el costo de las pérdidas para

cada isla perteneciente a una mini-zona. Sea entonces el costo total de una isla a planificar:

( ), , , ,1

j

j i k i k i k ik

CT Ctrafo Cred Cpérdidas=

= + +∑ (4.27)

Con

• CTj,i : costo total de j redes óptimas en la isla i.

• Ctafok,i : costo del k-ésimo trasformador ubicado óptimamente en la isla i.

• Credk,j : costo de la red óptima asociada al transformador k en la isla i.

• Cpérdidask,i : costo de las perdidas de la red óptima asociada al

transformador k en la isla i.

Considerando la ecuación 4.27 y producto que ya se conocen las distintas etapas que

intervienen en el proceso de micro-optimización es posible clarificar con más detalle el

algoritmo usado para encontrar las redes óptimas sobre una isla perteneciente a una mini-

zona determinada.

Se inicializa el contador en 0.

1. Si la carga puede ser suministrada por un único transformador (T=1) se ubica el

transformador en el centro de carga, en caso contrario se inicializa el algoritmo en el

paso 4.

2. Para dicha posición se calcula CT, siendo necesario calcular:

2.1 Ctrafo, a través de la asignación de capacidad

2.2 Cred, a partir del trazado óptimo y selección óptima de conductores.

68

2.2.1 En caso de realizar el equilibrio de red, se recalcula el tamaño del

transformador.

2.3 Cpérdidas, mediante el cálculo de las pérdidas de energía

3. Se almacenan las variables relevantes que dieron origen a CT, ubicación, tamaño y

costo del transformador, trazado de la red, conexiones y conductores usados con sus

respectivos costos y costos de pérdidas de cada red. Al costo de red se le incorpora

un costo relacionado con los postes que se deben usar.

4. Se realiza la ubicación de (T+1) transformadores, utilizando el método de k-means.

5. Se repite el paso 2 para cada posición obteniéndose CT para el conjunto de

configuraciones de la isla.

6. Se realiza 3 siempre y cuando el costo total de la presente iteración sea menor al de

la iteración anterior.

7. El contador se aumenta en una unidad. Se repite 4-5-6 hasta que el CT de la

iteración actual es mayor que el CT de la iteración anterior, encontrándose un valle

en la función objetivo y por tanto determinando un mínimo en la función.

8. Se repite el paso 7 hasta que el contador llega a un número máximo, dicho número

representa el número de iteraciones adicionales que se realizan luego de encontrado

el primer mínimo de manera de ampliar el espacio de búsqueda. Finalmente se

escoge la alternativa que representa un menor costo28.

A continuación se analizarán algunos resultados para comprender con mayor detalle el

algoritmo propuesto:

Relevancia de la búsqueda

Nótese que si el número máximo, denominado búsqueda, es igual a uno, significa entregar

como solución óptima para la isla el primer mínimo que se encuentra, es decir, determina el

número de transformadores y redes asociadas cuyo costo es menor que el que provoca la

adición de un nuevo transformador con su respectiva red. Si la búsqueda es mayor que uno,

28 Un ejemplo completo del algoritmo de micro-optimización se encuentra en el anexo E

69

implica seguir buscando en el espacio de las soluciones durante (búsqueda-uno) iteraciones

extras, para finalmente quedarse con el menor de los costos obtenidos.

No obstante, en el procedimiento implementado finalmente se utiliza un alcance de uno,

esto se basa en el hecho que tras encontrar un mínimo, la incorporación de un

transformador adicional aumenta los costos por unidad de capacidad debido a las

economías de escala29 que existen en estos elementos y al aumento de capacidad instalada

que necesariamente se produce. Por ejemplo, si para una determinada isla se encuentra que

el mínimo local se logra con un transformador de tamaño M que abaste un conjunto de C

clientes con un consumo de energía E, un factor de carga Fc(C) y una demanda de potencia

P, si luego se ubica un nuevo transformador los clientes y la energía asociada se reparte

entre dos elementos y por tanto se cumple que:

1 2C C C= + (4.28)

1 2E E E= + (4.29)

Sin embargo, la potencia total que se debe suministrar es mayor que P, dado que tanto C1

como C2 son menores que C, y como el factor de carga disminuye con el descenso del

número de clientes, los factores de carga de C1 y C2 son menores que el factor de carga de

C, cumpliéndose que:

1 1

11 1

1 1( ) ( )

( ) ( ) ( ) ( )

E ET TFc C Fc C

Fc C Fc C Fc C Fc C> ⇒ > ⇒ > (4.30)

2 2

22 2

1 1( ) ( )

( ) ( ) ( ) ( )

E ET TFc C Fc C

Fc C Fc C Fc C Fc C> ⇒ > ⇒ > (4.31)

Sumando (4.31) y (4.32) se tiene:

1 2 1 2 1 2

1 2 1 2

( )

( ) ( ) ( ) ( ) ( ) ( )

E E E E E E ET T T T T T

Fc C Fc C Fc C Fc C Fc C Fc C

+

+ > ⇔ + > (4.32)

Reemplazado de acuerdo a (4.21), entonces:

29 En el caso de los transformadores el costo por unidad de capacidad ($/kVA) disminuye en la medida que aumenta el tamaño (capacidad) del transformador.

70

1 2P P P+ > (4.33)

Por lo cual los transformadores deberán satisfacer una potencia de diseño mayor,

introduciendo un delta de costo adicional que se ve incrementado producto de las

economías de escala presentes en transformación, con lo que la suma del costo de ambas

unidades será mayor que el costo del transformador M. Costo que probablemente no se

alcance a justificar con la posible disminución en costos de redes, toda vez que se conoce

que en la siguiente iteración luego del mínimo, el costo total va en aumento. También se

debe destacar que iteraciones adicionales representan incrementos en costos

computacionales y por ende mayores tiempos de ejecución, lo que constituye un problema

cuando la dimensionalidad de la zona a optimizar aumenta.

En la tabla 4.4 se muestra el costo total de la red y el tiempo para distintos valores de

búsqueda, aplicados a la zona de análisis dada por la comuna de Macul.

Tabla 4.4: Variación del costo total con la búsqueda

Búsqueda Costo Total ($) Tiempo (min)

1 1.836.355.360 3,6

2 1.833.496.191 3,9

3 1.831.117.948 4,3

4 1.851.841.019 5,0

5 1.820.760.267 5,3

6 1.826.747.204 5,7

7 1.834.920.708 6,7

8 1.827.443.448 7,2

9 1.839.715.440 7,6

10 1.831.849.273 8,7

11 1.823.315.893 9,3

12 1.831.028.015 10,3

13 1.823.774.388 11,5

14 1.830.555.495 12,6

15 1.836.080.005 13,7

Donde es posible ratificar el hecho que incrementos en la búsqueda aumentan

considerablemente los tiempos de ejecución, sin implicar disminuciones apreciables en los

costos totales de la red, en efecto, el costo promedio de la tabla anterior es de

71

$ 1.831.933.377, con una desviación estándar de $ 7.658.349 que representa sólo un 0,42 %

del costo promedio total, lo que no implica diferencias significativas entre los datos, siendo

las diferencias en costo atribuibles a la característica no determinística de la metodología

propuesta30. Todo lo cual ratifica la decisión de realizar el diseño de la red en consideración

del primer mínimo encontrado en el proceso de optimización31.

Efecto del equilibrio de red

Tal como ya se señaló, el equilibrio de red consiste en mover el transformador a un punto

tal que los flujos que salen por ambos extremos sean lo mas parecidos posibles, de manera

de incorporar indirectamente en el trazado de red, realizado en base a distancia, el flujo

circulante por cada conductor y así evitar que por un extremo del transformador se alimente

a gran parte de la red mientras que por la otra se abastezca una pequeña parte de ella, lo que

trae como resultado mover más energía por un lado transformador lo que implica secciones

mayores durante gran parte del trazado y por ende mayores costos. No obstante, se debe

recordar que la posición del transformador a partir de la cual se traza la red, no es realizada

arbitrariamente sino que a través de un proceso de cluster en que la posición esta dada por

el centro de carga del conjunto de consumos asociados a él, por lo que, en principio la red

debiese encontrarse equilibrada, pero dada la presencia de calles, que restringen el trazado

de ella, el punto de equilibrio de la configuración de baja tensión puede modificarse,

apareciendo entonces la necesidad de encontrarlo. Para conocer si la incorporación del

equilibrio de red, provoca mejoras a la optimización de la red, se analizan tres casos:

• Caso 1, sin equilibrio, en este no se realiza la reubicación de los transformadores a

través del equilibrio de red.

• Caso 2, con equilibrio en la etapa final, en que el equilibrio no se realiza en cada

iteración del algoritmo (sin el paso 2.2.1) sino que únicamente se equilibran y

recalculan costos una vez que se ha elegido la mejor configuración para la isla.

30 Para una mejor comprensión revisar el anexo referido a complejidad Algorítmica y el apartado de Convergencia del presente capítulo. 31 En el anexo F se presentan, a modo de ejemplo, los resultados para algunas mini-zonas, notando en ellos el comportamiento creciente del costo total con la adición de un nuevo transformador, luego de haber encontrado el mínimo.

72

• Caso 3, con equilibrio, se realiza el algoritmo señalado, incorporando en cada

iteración el equilibrio de la red.

Para los tres casos en cuestión se realizaron 20 ejecuciones del algoritmo32, denominadas

lanzamientos, obteniéndose los siguientes costos y tiempos de ejecución promedios:

Tabla 4.5: Efecto del equilibrio de red

Costo Total

($)

Tiempo

(min)Caso 1 1.906.194.901 3,05

Caso 2 1.833.157.697 3,56

Caso 3 1.820.926.206 6,55

Se observa que la inclusión del equilibrio de red implica reducciones de costo promedio de

73 y 85 millones de pesos en el caso 2 y 3 respectivamente, tal relación de ahorro se

encuentra presente en todos los lanzamientos ejecutados, situación que se puede apreciar en

la figura 4.10.

MM ($)

1.740 1.760

1.780 1.800 1.820 1.840

1.860 1.880 1.900

1.920 1.940

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Lanzamientos

Caso 1 Caso 2 Caso 3

Figura 4.10: Efecto de la inclusión del equilibrio en la optimización

32 El resumen de las ejecuciones del algoritmo se encuentran en el Anexo G.

73

Es posible constatar además, que el tiempo de ejecución del caso 3, es el doble que el

tiempo de ejecución del caso 1, con un ahorro en costo de 4,47 %, en tanto que el tiempo de

ejecución del caso 2 es tan sólo un 16 % superior al caso en que no se realiza equilibrio,

pero con un ahorro comparable al caso 3 de 3,98 %, razón por la cual, en beneficio de la

eficiente ejecución del algoritmo con miras a su aplicación en un zona de mayor tamaño

como Santiago, se opta por incluir el equilibrio de red sólo en la etapa final, dado que

presenta ahorros importantes en un tiempo de ejecución menor.

Convergencia

Cabe recordar que el problema a resolver de acuerdo a su complejidad algorítmica

corresponde a un problema del tipo NP-completo, y por tanto la solución aquí propuesta no

es capaz de resolver el problema mediante un algoritmo determinístico, entendiéndolo

básicamente como aquel que entrega la misma la solución cada vez que es ejecutado. En

cambio, lo hace a través de un procedimiento con una parte no determinística, en particular

la componente no determinística del algoritmo propuesto se presenta en la formación de los

cluster para la ubicación de los transformadores. De hecho, en el apartado referente a tal

tema, fue posible constatar la distorsión que se produce en k-means para distintos

lanzamientos, distorsión que era similar, pero no igual, por lo que se tomó como decisión

dejar como ubicación el resultado que presentará menor distorsión al ejecutarse tres veces

el procedimiento de cluster, para un número determinado de transformadores. En efecto,

producto de dicha componente no determinística, los resultados de la optimización también

son distintos cada vez que se ejecuta el procedimiento, lo que en apariencia podría restarle

confiabilidad, pero ¿Qué tan distintos son los costos para cada lanzamiento?, en la tabla 4.6

se presentan los resultados para 20 ejecuciones de la metodología. En ella es posible

apreciar la similitud tanto en tiempo de ejecución como en costo total entre los distintos

lanzamientos o ejecuciones de la metodología propuesta, de donde se obtiene un costo total

promedio de $ 1.833.157.697 y un tiempo de ejecución promedio de 3,52 minutos, con

desviaciones estándar de $ 7.095.766 y 0,07 minutos. Es importante señalar que la

desviación estándar de los costos representa tan solo el 0,39 % del costo promedio total.

Notando entonces, por un lado la naturaleza no-determinística del algoritmo, al observar

74

resultados distintos en cada ejecución, y por otro la pequeña dispersión de sus resultados,

permitiendo la toma de decisiones a través de ellos.

Tabla 4.6: Confiabilidad del algoritmo

Lanzamiento Costo Total ($) Tiempo (min)

1 1.829.211.042 3,62

2 1.828.334.867 3,57

3 1.832.120.157 3,52

4 1.833.232.594 3,52

5 1.843.371.158 3,62

6 1.820.042.332 3,59

7 1.831.159.158 3,54

8 1.835.060.121 3,56

9 1.838.797.878 3,43

10 1.840.474.314 3,54

11 1.820.073.227 3,43

12 1.839.395.779 3,59

13 1.837.076.387 3,47

14 1.839.113.483 3,42

15 1.827.007.437 3,41

16 1.833.870.373 3,54

17 1.831.409.165 3,46

18 1.837.760.035 3,68

19 1.838.682.217 3,47

20 1.836.962.215 3,57

Tamaño de la mini-zona

Este apartado tiene como objetivo estudiar el algoritmo propuesto, determinando el tamaño

de división que minimiza los costos, para así posteriormente utilizar dicho tamaño en la

optimización de Santiago. Por tanto se ejecuta el procedimiento considerando diferentes

tamaños posibles de mini-zonas.

Al realizar tal ejercicio se obtiene como resultado el gráfico presentado en la figura 4.10,

que muestra que para zonas de pequeño tamaño, inferiores a 200 x 200, tanto los tiempos

de ejecución como los costos totales son mayores que el resto de los casos, esto se debe a

que en mini-zonas pequeñas hay más posibilidades de instalar transformadores de menor

tamaño dado que se abastece un menor número de consumos, y producto de las economías

de escala en la capacidad de transformación se presentan mayores costos. Los tiempos

75

mayores se explican debido a que la zona a optimizar debe ser dividida en un mayor

número de mini-zonas, con lo que el procedimiento debe ser ejecutado en más

oportunidades. A partir de las mini-zonas de 300 x 300 se observa un comportamiento

bastante constante del costo total y un aumento progresivo en los tiempos de ejecución. El

tiempo adicional se produce debido a que se aumenta el espacio de soluciones factibles al

aumentarse el número de nodos de una determinada mini-zona, con lo que el algoritmo

tarda más tiempo en encontrar el óptimo que se mantiene sin grandes variaciones

mostrando la calidad del mismo. Los menores tiempos33 se producen cuando la división es

de 300 y 400 metros, en tanto que los menores costos se producen cuando la división es de

500 y 600 metros, presentando el mejor balance entre tiempo de ejecución y calidad de la

solución la división en zonas de 500 metros, puesto que permite abarcar una zona mayor

que las divisiones más rápidas y por ende manejar un universo de soluciones factibles

mayor en un tiempo ligeramente superior.

-

1.000

2.000

3.000

4.000

5.000

6.000

50 80 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300

Tamaño de la mini-zona

Co

sto

(M

M$

)

0

2

4

6

8

10

12

14

16

18

Tie

mp

o (

min

)

Costo Total Tiempo

Figura 4.11: Costo y tiempo total v/s tamaño de la mini-zona

33 Los datos de tiempo y costo para cada tamaño de división se encuentran en el Anexo G.

76

5. PROCESO DE MACRO-OPTIMIZACION

En el capítulo 4 se realizó la optimización de cada una de las mini-zonas en que fue

dividida la región a planificar, sin embargo tal procedimiento constituye meramente una

buena aproximación a la solución del problema, dado que la división de la región es

arbitraria y responde sólo a una partición regular de la misma, dejando la posibilidad

abierta a que consumos pertenecientes a una mini-zona determinada pudiesen ser asignados

y por ende alimentados desde otra mini-zona aledaña a un menor costo. Para incorporar

este efecto y reconociendo que la solución puede ser mejorada, en este capítulo se aborda

globalmente el problema, en base a los resultados de la micro-optimización, sin olvidar que

debido a la dimensionalidad del mismo, su solución fue sólo posible gracias a la partición

de él. Por tanto la mirada global, apunta necesariamente a emplear el proceso de micro-

optimización como base de la solución.

En línea con lo anterior en este capítulo se proponen y desarrollan tres alternativas para

mejorar la solución encontrada, la primera se basa en los diagramas de Voronoi y busca la

creación de zonas irregulares a las cuales aplicarles el proceso de micro-optimización, de

tal forma que se garantice que cada consumo quede asociado con sus vecinos cercanos, la

segunda consiste en analizar si es más económico reemplazar redes vecinas por una única

red que satisfaga dichos consumos, procedimiento que es efectuado mediante enumeración

completa cuando la zona es pequeña y mediante búsqueda tabú cuando la dimensionalidad

del problema hace imposible la revisión de todas las combinaciones factibles. Finalmente,

la tercera es la aplicación secuencial de las dos anteriores.

5.1 Macro-Optimización Vía Diagramas de Voronoi

Para comprender la metodología propuesta se expone primero una breve reseña referente a

la definición y propiedades básicas de los diagramas de Voronoi, para posteriormente

explicar en detalle el procedimiento empleado, mostrando nuevamente su aplicación

práctica para la comuna de Macul.

77

5.1.1 Diagramas de Voronoi

El concepto básico de los diagramas de Voronoi, dice relación con conocer la influencia

que realizan determinados elementos de un conjunto sobre el resto de los elementos del

mismo. La primera aproximación fue realizada en 1644 por Descartes, señalando que el

sistema solar consistía en vórtices, donde la materia giraba en torno a la estrella más

cercana, situación que producía polígonos convexos para cada área de influencia de las

estrellas. No obstante, fue hasta Dirichlet (1850) y Georgy Voronoi (1908), cuando se

formalizó el concepto, el cual además, con distinto nombre ha sido aplicado a varias ramas

de la ciencia, tales como geología, meteorología, denominándose polígonos de Theissen, y

en física y química conociéndose como regiones de Wigner-Seitz.

Conceptualmente un diagrama de Voronoi es el resultado de asociar todas las ubicaciones

del espacio euclidiano con el más cercano de los p puntos, del mismo espacio, elegidos

como centros. En términos matemáticos, sea P un conjunto de n puntos distintos en el

espacio euclidiano {p1,…, pi,..., pn}, denominados puntos generadores, un punto x del plano

pertenece al área de influencia del punto generador pi, denominada polígono de Voronoi,

Vi, si y solo si el punto x esta más cerca de pi que de cualquier otro punto generador. Esto

es:

{ }/ ,i i jV x x p x p j i= − < − ∀ ≠ (5.1)

Por tanto, el diagrama de Voronoi representa al conjunto de todos los polígonos de Voronoi

{V1,…, Vi, ..., VN} del espacio euclidiano provocados por los puntos generadores {p1,…,

pi,..., pn} respectivamente.

78

2 3 4 5 6 7 8 9

2

3

4

5

6

7

8

9

Figura 5.1: Diagrama de Voronoi para 30 centros

Entre sus definiciones y propiedades más importantes se cuentan:

1. Dos puntos generadores pi y pj son vecinos si comparten una arista. Una arista es la

bisectriz perpendicular del segmento que une pi con pj

2. Un vértice es un punto equidistante a tres generadores y es la intersección de tres

aristas.

3. Un polígono de Voronoi es convexo o no acotado.

4. Un polígono de Voronoi es no acotado si su punto generador pertenece a la

envolvente convexa del conjunto de puntos generadores.

5. Dentro del círculo con centro en un vértice de Voronoi y que pasa por tres puntos

generadores no puede existir ningún otro punto generador, y tal círculo constituye el

mayor de todos los círculos que puede construirse sin que contenga dentro a otro

generador distinto del tomado como centro del círculo.

6. Si se toma como centro de un círculo cualquier punto del plano y se traza una

circunferencia que pase por un solo punto generador, dicho punto es interior a una

región de Voronoi. Si toca exactamente a dos puntos generadores, separa

exactamente a dos regiones de Voronoi, por tanto pertenece a una arista. Si se puede

dibujar una circunferencia que toque a tres puntos generadores, es un vértice de

Voronoi.

[x]

[y]

79

Si bien este desarrollo, constituye una idea que formalmente va a cumplir un siglo, su

difícil implementación provocó que no se le brindara la atención merecida durante largo

tiempo. Sin embargo, en las últimas décadas, con el avance de la geometría computacional

ha tomado gran importancia, tanto en el campo de sus aplicaciones como en el campo de su

propio desarrollo algorítmico (Okabe et al, 1992). Su aplicación inmediata se da en

problemas de distancia, tales como encontrar el vecino más cercano, encontrar todos los

vecinos más cercanos, encontrar el mayor círculo vacío, esto es, dado un generador p

encontrar el mayor círculo que no contiene ningún punto indeseado, o en el caso del menor

círculo, encontrar el menor círculo que agrupa a un conjunto de n puntos en el plano.

También se usa en cluster geométrico y en robótica, donde se aplica a la planificación del

movimiento (Yap, 1987). Además, se debe destacar el trabajo de Akabane Kenichi et al.

(2002), que utiliza esta metodología en la ubicación de centros de control de calidad de

potencia, en cuya ubicación intervienen variables eléctricas tales como la caída de tensión y

la demanda de corriente de cada consumo, convirtiendo a esta técnica en una atractiva

manera de afrontar la ubicación óptima de transformadores.

5.1.2 Procedimiento de optimización vía Voronoi

En consideración a la característica de asignación de los diagramas de Voronoi, es posible

plantear, como hipótesis, que si a cada transformador se le asignan los consumos más

cercanos se obtendrán menores costos. No obstante, la planificación desde cero toma en

cuenta únicamente la posición de los clientes y por ende la asignación a través de Voronoi

es inviable, dado que no existen los centros iniciales para trazarlos, situación resuelta a

través de la micro-optimización que proporciona la planificación de la red y como

subproducto la ubicación de los transformadores, surgiendo entonces las posibilidad de

utilizar tales ubicaciones como centros de los polígonos de Voronoi, y para cada uno de

ellos realizar el proceso de micro-optimización con el objeto de planificar la red. En suma,

se realiza el mismo procedimiento de micro-optimización que se describió en el capítulo 4

pero esta vez aplicado a zonas irregulares, de distinto tamaño y forma, dadas por los

80

polígonos de Voronoi. Entonces, el algoritmo del proceso de macro-optimización propuesto

es:

1. Realizar el proceso de micro-optimización de la zona a planificar, esto es dividir la

región en mini-zonas y optimizar cada una de ellas. Obteniendo la ubicación de los

transformadores de distribución.

2. Construir el diagrama de Voronoi utilizando como puntos generadores la ubicación

de los transformadores.

3. Para cada polígono de Voronoi realizar el proceso de micro-optimización.

Si bien los diagramas de Voronoi poseen una definición sencilla y fueron enunciados hace

gran data, su aplicación a modelos de gran tamaño no está resuelta del todo, al menos en lo

que se refiere al problema de asignación de consumos en las zonas no acotadas. De hecho

tal como se puede apreciar en la figura 5.2 el diagrama de Voronoi realiza algunos

polígonos cuyos vértices están fuera de la zona de análisis (fuera del rectángulo indicado en

la figura 5.2), entendiendo esta como la delimitada por los consumos de la zona de

planificación, y por polígonos que poseen un vértice ubicado en infinito (regiones no

acotadas), representando esto un problema a la hora de identificar que vértices de tramos de

calle y que consumos están incluidos en cada uno de ellos.

81

Figura 5.2: Diagrama de Voronoi para la comuna de Macul

Para resolver tal inconveniente se propone una modificación al diagrama de Voronoi que

consiste en acotar las regiones que presentan vértices en infinito y alterar los polígonos que

presentan vértices fuera de la zona de análisis, de tal forma que todos los polígonos luego

de la modificación sean acotados y por ende posibilitar la correcta asignación de los

consumos.

En primer término se procede a ejecutar el trazado de Voronoi, obteniendo zonas acotadas

interiores, zonas acotadas con vértices exteriores y zonas no limitadas, permaneciendo las

primeras inalterables en el proceso de modificación, las que se encuentran identificadas en

la figura 5.3. Luego de lo cual se define un polígono regular denominado polígono frontera

(polígono trazado en 5.3), cuyo vértice inferior está dado por el menor valor de la

coordenada x e y de entre todos los consumos a satisfacer, y el vértice extremo por la mayor

coordenada x e y de los mismos consumos, tal polígono sirve de cota para las siguientes dos

etapas y representa la zona a planificar.

-1 0 1 2 3 4 5

x 104

-0.5

0

0.5

1

1.5

2

2.5

3

3.5x 10

4

3.2 3.4 3.6 3.8 4 4.2 4.4 4.6

x 104

4000

6000

8000

10000

12000

14000

Polígonos interiores

Polígonos con vértices exteriores

Polígonos no acotados

[m]

[m] [m]

[m]

82

3.5 3.6 3.7 3.8 3.9 4 4.1

x 104

6000

7000

8000

9000

10000

11000

12000

Figura 5.3: Identificación zonas interiores diagrama de Voronoi

Modificación de zonas acotadas con vértices exteriores

De la figura 5.3 se desprende automáticamente que secciones del polígono frontera actúan

de aristas para las zonas de Voronoi que se desean acotar, y por ende el problema se

resuelve básicamente encontrando la intersección entre la arista del polígono frontera con la

recta que une el tramo que sale desde un vértice interior de la zona a limitar a un vértice

fuera de dicha zona, con lo que se obtiene un nuevo vértice del polígono, situación que se

repite para otro tramo, dado que el polígono es cerrado y convexo con lo que debe existir

una arista desde el exterior a la zona interior distinto al ya empleado, encontrando el otro

vértice que permite cerrar el polígono, y así eliminado todos aquellos vértices fuera de la

frontera. Atención especial reciben aquellos polígonos ubicados en las esquinas de la

frontera, cuyos tramos que salen de la zona lo hacen por distintas aristas de la frontera, y

por tanto encontrar sólo los vértices de intersección no resuelve la situación, ya que el

tramo que une tales puntos podría dejar fuera a consumos que sí pertenecen a la zona, para

evitarlo se incluye como vértice del nuevo polígono, el vértice del polígono frontera que se

encuentra en la esquina próxima, con lo que además de las dos aristas que se forman entre

los vértices interiores y las aristas de la frontera, se generan dos nuevas aristas entre tales

[m]

[m]

83

puntos de intersección y el nuevo vértice incluido. Se logra entonces, la correcta asignación

de todos los consumos.

3.5 3.6 3.7 3.8 3.9 4 4.1

x 104

6000

7000

8000

9000

10000

11000

12000

Figura 5.4: Identificación y cierre de polígonos con vértices exteriores

Cierre de las zonas no acotadas

Este procedimiento es parecido al anterior con la salvedad que es imposible trazar una recta

entre un punto interior y el punto ubicado en infinito, puesto que no tiene definida una

posición real en el plano cartesiano, requiriendo un paso adicional para conseguirlo, lo

primero que se realiza es reconocer cuales son aquellos polígonos que no están acotados

dado que la delimitación entre ellos es la que se presenta difusa. Es imposible determinar la

pertenencia cuando el límite es una arista imaginaria que va desde un vértice que existe a

otro que no. Se debe notar además que los polígonos de Voronoi no acotados, en algún

segmento ya sea dentro de la zona a planificar o fuera de ella, son vecinos de otro polígono

de Voronoi no acotado, por lo que la separación entre ellos es fundamental para la correcta

asignación de pertenencia.

Tal límite entre zonas se establece teniendo presente que cada polígono, creado a partir de

las zonas no acotadas, debe agrupar a los puntos más cercanos a sus determinados centros,

dado en este trabajo por la ubicación de los transformadores. Siendo el desafío la definición

[m]

[m]

84

de la separación que cumpla tal objetivo. Si se tuviesen sólo dos centros generadores, el

límite entre ambos vendría dado únicamente por una recta perpendicular al tramo que los

une, pero la existencia de más centros generadores hace que el trazado de Voronoi se

complique, complejidad que aumenta con el número de centros. Sin embargo, como la

asignación conflictiva depende únicamente de ambos polígonos y los demás polígonos de

Voronoi ya se encuentran trazados, es posible utilizar tal metodología pero considerando

los ya construidos, lo que se resume a continuación:

1. Se identifican los centros generadores de los polígonos no acotados, lo cuales se

consiguen generando la envolvente convexa34 de todos los centros generadores

(ubicaciones de todos los transformadores), ya que en ella, sus vértices coinciden

con los centros de las zonas no acotadas, y por tanto dos vértices consecutivos de la

envolvente convexa señalan dos zonas no acotadas que en alguna parte del espacio

presentan una arista común que debe ser definida.

34 Un punto x ∈ Rn es combinación convexa de los puntos x1, …, xm ∈ Rn si existe α1, …, αn ∈ R, tal que

1 1 2 21

... 1, 0 1,...,m

m m i ii

x x x x con i mα α α α α=

= + + + = ≥ ∀ =∑

La envolvente convexa de un conjunto A, es el conjunto de todas las combinaciones convexas de puntos de A

1 1

, , 1, , 0 1,...,m m

ni i i i i

i i

Envolvente z R z x x A i mα α α= =

= ∈ = = ∈ ≥ ∀ =

∑ ∑

85

3.6 3.7 3.8 3.9 4 4.1

x 104

7000

7500

8000

8500

9000

9500

10000

10500

11000

11500

Figura 5.5: Envolvente convexa de los centros generadores

2. En cada segmento, dado por la unión de dos vértices consecutivos de la envolvente

convexa, se identifica la recta perpendicular al punto medio de dicho segmento, lo

que divide al plano en dos partes. Tal recta pasa por el vértice común de los

polígonos no acotados, y por tanto la nueva arista va desde dicho vértice común al

punto de intersección entre la recta y la correspondiente arista del polígono frontera,

siempre y cuando el vértice común sea interior a la zona de planificación.

3. Con las nuevas aristas formadas más las aristas creadas en la etapa anterior, se

cierran los polígonos no acotados, teniendo nuevamente atención con lo que sucede

en los polígonos ubicados en las esquinas de la frontera. Básicamente en cada

polígono se toma la sucesión de vértices interiores, y aquellos vértices que

coinciden con aristas ya trazadas, a través de la envolvente convexa o del

acotamiento de polígonos con vértices reales exteriores, se unen a los nuevos

vértices dados por el fin de la arista (intersección de la arista con el polígono

frontera), de manera de cerrar el polígono y eliminar los vértices del polígono

exteriores a la zona de planificación.

[m]

[m]

86

Resultados del procedimiento vía Voronoi

Con los procedimientos anteriores es posible acotar en forma determinística cada uno de los

polígonos, permitiendo la asignación unívoca entre consumos y transformadores, en virtud

de lo cual, cada uno de los polígonos de Voronoi puede representar una mini-zona a

optimizar, conteniendo un conjunto de cargas y un trazado vial determinado.

A modo de ejemplo, se considera como caso base, la ubicación de 284 transformadores con

una capacidad total de 54 MVA, obtenidos a partir del proceso de micro-optimización,

cuyo costo total, incluida la red y las pérdidas, es de $1.837.274.567, se tiene el siguiente

diagrama de Voronoi para la comuna de Macul.

3.6 3.7 3.8 3.9 4 4.1

x 104

7000

7500

8000

8500

9000

9500

10000

10500

11000

11500

Figura 5.6: Diagrama de Voronoi para una solución de la micro-optimización

Es posible apreciar que la zona de planificación queda dividida en mini-zonas irregulares, y

cada una de ellas representa una agrupación de consumos cercanos. Una vez que se tiene la

nueva asignación de consumos a cada zona, se procede a realizar la misma metodología

expuesta en el capítulo 4, con el fin disminuir los costos encontrados con dicho

procedimiento. Sin embargo, en un primer análisis, esto no sucede tan claramente,

[m]

[m]

87

obteniéndose un costo de $ 1.832.819.289, ligeramente inferior al caso base, para 375

transformadores y redes con una capacidad instalada de 54 MVA. Es decir, aparecen más

transformadores cuya capacidad promedio es menor, ello debido a que las nuevas mini-

zonas son en promedio más pequeñas que las zonas de 500 x 500 utilizadas en la micro-

optimización, con lo cual nace la pregunta ¿qué sucede si se aumenta la dimensionalidad de

los polígonos irregulares?. Para responder esta interrogante, se requiere en primer término

aumentar el tamaño de los polígonos de Voronoi sin perder la información obtenida desde

la micro-optimización, vale decir, sin desconocer que la ubicación de los transformadores

obtenidos corresponden a una correcta relación entre capacidad de transformación, redes y

consumos abastecidos, por lo cual se propone que los puntos generadores del diagrama de

Voronoi sean sólo algunas de las ubicaciones determinadas en el proceso previo. Tales

ubicaciones corresponden a la de todos los transformadores que son superiores a una

determinada cota, entre mayor es la cota menor es el número de transformadores que

satisfacen la restricción y por tanto es menor el número de puntos generadores, lo que

determina polígonos de Voronoi de mayor tamaño. En la tabla 5.1 se presenta el resultado

de aplicar la metodología propuesta para distintos valores de cota y por tanto para distinto

número de polígonos.

Tabla 5.1: Aplicación diagrama de Voronoi

Cota (kVA)Número de

PolígonosCosto Total ($)

Número de

Trafos

Capacidad

Instalada

(MVA)

Tiempo

(min)

10 252 1.832.819.289 375 54,33 3,19

15 238 1.825.087.305 363 54,40 3,09

30 228 1.822.069.744 356 54,06 3,10

45 221 1.815.174.431 354 53,86 3,08

75 211 1.804.476.363 336 53,22 2,93

100 203 1.789.638.270 331 52,86 3,03

150 183 1.773.583.766 301 52,50 2,90

300 100 1.765.329.035 229 47,48 3,22

500 15 2.366.757.645 113 41,16 21,24

Se puede observar que en la medida que aumenta el tamaño de la cota y por ende el tamaño

de los polígonos, se produce un mayor ahorro con respecto al caso base, en el caso en que

88

la cota es de 500 kVA sólo existen 15 polígonos y por ende la zona que cubre cada uno de

ellos es mayor, lo que trae consigo mayores tiempo de ejecución y un empeoramiento de la

solución al incrementarse los costos relacionados con las pérdidas. Los mayores ahorros en

el caso analizado se producen tomando como cota 300 kVA y son en promedio del orden de

4 %.

3.7 3.8 3.9 4

x 104

7000

7500

8000

8500

9000

9500

10000

10500

11000

11500

Figura 5.7: Diagrama de Voronoi generado por transformadores de 300 kVA

Caso simplificado

Si bien se pudo constatar que la división adecuada en polígonos regulares incluye ahorros al

proceso de micro-optimización, se tiene que los tiempos de ejecución aumentan

considerablemente, ya que en total se realizan dos procesos de micro-optimización más la

generación del diagrama de Voronoi, por lo que el proceso completo al menos duplica los

tiempos de ejecución, situación relevante si se busca aplicar la metodología completa a una

zona de mayor tamaño, en donde duplicar el tiempo puede significar llegar a las 10 horas

de proceso, restándole efectividad a la metodología global. Para soslayar este problema e

incorporar el hecho que el uso del diagrama de Voronoi produce mejoras en la solución se

[m]

[m]

89

propone realizar una primera ubicación aproximada de los transformadores, de manera de

evitar la primera etapa de micro-optimización, y trazar el diagrama de Voronoi para la cota

adecuada de la nueva configuración y luego aplicar el proceso no simplificado a las nuevas

zonas irregulares.

El procedimiento simplificado consiste en no determinar la influencia de la red ni de la

conectividad de la red vial en la asignación del número de transformadores y de la

capacidad de los mismos, sino que únicamente tomar en cuenta la cantidad de consumo a

abastecer, la potencia de diseño necesaria y la capacidad de los transformadores disponibles

para abastecer dicha demanda. El algoritmo simplificado queda dado por:

1. Se divide la zona de planificación en zonas regulares de 500 x 500 metros.

2. Para cada mini-zona:

2.1 Se calcula la potencia de diseño de la mini-zona bajo el supuesto que es

suministrada por un único transformador.

2.2 Para la potencia de diseño se asigna el menor transformador que es capaz

de suministrarla (tomando en consideración el crecimiento de la

demanda). Si no existe un transformador dentro del dominio factible que

es capaz de hacerlo, se asigna el de mayor capacidad. Se define como

demanda no satisfecha el delta entre la potencia de diseño y la capacidad

del transformador instalado.

2.3 Si la demanda no satisfecha es cero se pasa a 3, en caso contrario se pasa

a 2.2, definiendo al potencia de diseño como la demanda no satisfecha.

3. Una vez que se conoce el número de transformadores esos son ubicados a través

del mismo algoritmo de cluster utilizado en el capítulo 4, por lo que la ubicación

queda dada por el centro de carga de los consumos asociados a cada cluster.

4. Para cada cluster se calcula la potencia de diseño y se asigna el transformador

óptimo correspondiente.

Con esta metodología se obtiene una ubicación preliminar de los transformadores en tan

sólo 10 segundos, la que si bien no corresponde a una ubicación necesariamente factible

90

dado que no se está considerando el costo de las redes y la conectividad vial, si incorpora

una primera aproximación a la agrupación de los consumos a través de los clusters

formados, y así se consiguen puntos generadores en forma rápida que incluyen la

información acerca de los centros de carga. Al realizar el mismo procedimiento que en el

apartado anterior, dejando como puntos generadores a los mayores a una determinada cota,

se obtienen los resultados presentados en la tabla 5.2.

Tabla 5.2: Aplicación diagrama de Voronoi al caso simplificado

Cota (kVA)Número de

PolígonosCosto Total ($)

Número de

Trafos

Capacidad

Instalada

(MVA)

Tiempo

(min)

10 102 1.760.168.472 255 48,48 2,86

15 101 1.760.628.472 260 48,56 2,84

30 99 1.755.170.145 264 48,16 2,87

45 99 1.758.860.082 257 48,11 2,84

75 97 1.764.630.418 263 48,40 2,86

100 97 1.763.638.774 259 48,13 2,85

150 97 1.757.196.385 261 48,20 2,85

300 88 1.780.345.629 254 47,35 3,00

500 68 1.764.515.664 240 47,68 3,53

Se aprecia que la variación del costo total producto de la elección de la cota es menor que

en el caso no simplificado, esto se debe que al no considerarse como restricción la

topología vial, no existen componentes conexas al interior de cada polígono que obliguen a

optimizar cada una de ellas de manera independiente, lo que necesariamente implica la

presencia de al menos un transformador por cada componente conexa o isla vial que se

produce, llevando esto a un mayor número de transformadores de menor tamaño. Como en

este caso tal situación no ocurre, el transformador a utilizar siempre será el que pueda

abastecer mayor cantidad de carga, dado que por economías de escala es lo que conviene, y

por tanto el número de tafos pequeños es menor, con lo que para las distintas cotas el

número de puntos generadores no varía considerablemente, manteniéndose nuevamente

ahorros del orden de 4 %. Es decir, el procedimiento simplificado no altera la calidad de la

solución y mejora los tiempos de ejecución al eliminar la necesidad de realizar dos veces el

proceso de micro-optimización.

91

5.2 Macro-Optimización Vía Búsqueda Tabú

En la metodología desarrollada, explicada en extenso en el capítulo 4, se sostiene que la

optimización de una red de baja tensión de gran tamaño, se puede llevar a cabo con buenos

resultados y en un tiempo razonable si la región a planificar se divide en regiones de menor

dimensión, denominadas en este trabajo mini-zonas, donde en cada una de ellas, se realiza

el proceso de micro-optimización de manera independiente, teniendo como ventaja

disminuir la dimensionalidad del problema y con ello los tiempos de ejecución, sin

embargo, como probable desventaja surge la posibilidad de pérdida de información, que se

produce al realizar la división de la zona a planificar, tal pérdida no significa que

elementos desaparezcan o se eliminen, sino que se refiere a la ceguera del algoritmo frente

a cercanías y relaciones entre elementos que pertenecen a distintas mini-zonas vecinas.

La figura 5.8 es un acercamiento a la división planteada en la figura 4.1, donde se puede

apreciar que no necesariamente el mejor resultado se obtendrá de la división en mini-zonas,

de hecho los consumos de la mini-zona 4 podrían ser repartidos entre las mini-zonas 2 y 3 y

eventualmente presentar un menor costo global.

Figura 5.8: Desventaja de la división en mini-zonas

3.9 3.91 3.92 3.93 3.94 3.95

x 104

8300

8350

8400

8450

8500

8550

8600

8650

8700

3.88 3.9 3.92 3.94 3.96

x 104

7800

8000

8200

8400

8600

8800 1 1 2

3

4

5 6

2

3 4

[m] [m]

[m] [m]

92

Para poder incorporar el efecto positivo de la interrelación entre las distintas mini-zonas,

sin perder las ventajas de dividir el problema, se formula una metodología que luego de la

aplicación del proceso de micro-optimización, tiene como hipótesis, en base a lo señalado,

la posibilidad de mejorar la solución encontrada si se analizan las relaciones entre zonas

vecinas, mediante la búsqueda de ahorros al unir en una única red y por ende en un único

transformador redes vecinas alimentadas desde transformadores distintos. Por tanto, la

necesidad inmediata que surge, es realizar tales agrupaciones de la mejor forma posible con

atención a la naturaleza combinatoria del problema. De hecho, tal como se analizó en el

capítulo 3, si se buscan agrupaciones posibles entre 10 consumos, distribuidos

uniformemente en el plano se tienen del orden de 1000 casos, los que crecen en la medida

que aumenta el número de nodos a asociar, por ejemplo, si se tienen 200 ubicaciones

distribuidas uniformemente en el plano, es posible agruparlas en 1,60x106 (2200-1)

subconjuntos, no obstante muchos de ellos no tienen sentido práctico, producto que asocian

redes que no son vecinas entre sí.

Para lograr una buena aproximación a la vecindad entre redes y con esto a las

combinaciones posibles, se propone el uso de la triangulación de Delaunay, la que también

será utilizada para la recombinación de redes, por lo que a continuación se realiza una breve

descripción de esta metodología y su relación con los ya explicados polígonos de Voronoi.

5.2.1 Triangulación de Delaunay

Una triangulación, básicamente corresponde a una subdivisión de una determinada área en

triángulos, es decir, dado un conjunto de puntos en el plano P, una triangulación de P se

define como una familia maximal de triángulos interiores disjuntos cuyos vértices son los

puntos de P y en cuyo interior no hay ningún punto de P. Se dice que una triangulación T1

es mejor que T2 cuando el menor ángulo de los triángulos de T1 es mayor que el menor de

los ángulos de los triángulos de T2, por tanto la mejor combinación será aquella que

maximiza el ángulo mínimos de los triángulos.

En particular, una triangulación de P es una triangulación de Delaunay si y sólo si la

circunferencia circunscrita de cualquier triángulo de T no contiene puntos de P. Con ello,

los triángulos formados tenderán a maximizar sus ángulos mínimos y las aristas conectarán

93

nodos cercanos, siempre y cuando no se intersecten entre sí. Por tanto la triangulación de

Delaunay no es otra cosa que el grafo dual del diagrama de Voronoi, en que las aristas

corresponden a la unión de los puntos generadores que comparten un eje de Voronoi y a la

unión de puntos generadores vecinos ubicados en zonas no acotadas. Entre sus propiedades

se cuentan:

• Cada triángulo posee como vértices a los puntos generadores del diagrama de

Voronoi.

• La frontera corresponde a la envolvente convexa de los puntos generadores.

• Maximiza el mínimo ángulo, por lo que constituye la mejor triangulación dado que

genera los triángulos más equiláteros posibles.

A continuación se presenta, a modo de ejemplo, la triangulación de Delaunay para 30

puntos generadores distribuidos uniformemente en una región de 100 por 100 metros.

0 10 20 30 40 50 60 70 80 90 1000

10

20

30

40

50

60

70

80

90

100

.

Figura 5.9: Ejemplo de la triangulación de Delaunay

Con esta técnica se busca entonces disminuir el número de combinaciones factibles, dado

que es posible conocer cuales son las redes vecinas, a través de las aristas de la

[m]

[m]

94

triangulación, y con ello evitar analizar aquellas combinaciones entre redes alejadas. De

esta forma los subconjuntos de n elementos entre los m disponibles se realizarán sólo entre

aquellos que estén conectados mediante el grafo definido a través de la teselación en

cuestión, lo que dependerá de la distribución de los consumos en el plano, por lo que es

imposible determinar una expresión analítica para el número total de combinaciones. No

obstante, es factible para cada distribución espacial, construir las combinaciones que

cumplan la restricción de vecindad. Así, para una localización de 10 consumos es posible

realizar 800 subgrupos, número que se incrementa exponencialmente con el tamaño de la

entrada, de hecho 15 consumos producen 25.248 combinaciones, 16 consumos generan

52.141 subconjuntos, 17 ubicaciones provocan 102.509 subgrupos y 18 localizaciones

tienen 214.063 combinaciones35. En estos casos se calcularon todas las posibles

combinaciones de los m datos de entrada en subconjuntos de 1 hasta m, siempre y cuando

estuviesen comunicados por aristas de la triangulación. Si ahora sólo se consideran todos

los posibles grupos de 2 y 3 elementos que cumplan con la teselación se tiene:

35 Cada grupo corresponde a una distribución uniforme de los n elementos en una superficie de 10.000m2, se debe señalar que los subconjuntos indicados que representan las combinaciones posibles son el resultado de un caso particular de n elementos, por lo que los números señalados no son generales pero brindan igualmente un indicador del orden de magnitud de las combinaciones factibles.

95

0

500

1000

1500

2000

2500

3000

3500

5

21

37

53

69

85

101

117

133

149

165

181

197

213

Nodos Distribuidos Uniformemente

Co

mb

inacio

nes

0

50

100

150

200

250

300

350

400

450

500

Tri

an

gu

lacio

nes

Número de Combinaciones Número de Triangulaciones

Figura 5.10: Aumento de la triangulación producto del aumento en la entrada

En este caso el número de combinaciones crece linealmente con el tamaño de redes a

combinar, producto que, como se aprecia en el mismo gráfico, el número de triángulos que

se forma con la adición de un nuevo nodo en la red también se incrementa casi linealmente,

y como la conexión esta limitada por las aristas de los triángulos de la teselación, buscando

sólo combinaciones de dos y tres elementos, es fácil notar que las combinaciones de dos

elementos sin repetición corresponden necesariamente a las aristas de la triangulación que

dependen del número de triángulos formados y los conjuntos de tres elementos

corresponden por un lado los triángulos de la teselación más aquellos formados por aristas

que parten de un mismo vértice pero que pertenecen a triángulos distintos, en virtud de lo

cual al considerar sólo combinaciones de dos y tres elementos el factor que hace aumentar

el número de combinaciones al incrementar el tamaño de la entrada es la formación de un

nuevo triángulo en la teselación y como su comportamiento es lineal con el número de

nodos también lo será el número de combinaciones de dos y tres elementos formadas a

partir de él, toda vez que se está suponiendo una distribución espacial uniforme de los

nodos.

De donde, si se asume como supuesto que las recombinaciones se realizarán sólo uniendo

de dos y de tres redes con sus respectivos transformadores, de todas maneras las

96

combinaciones para la zona de análisis continúan siendo elevadas. Como referencia para el

caso de 200 redes se tienen del orden de 3000 combinaciones, además si se considera que

cada combinación implica un nuevo cálculo de conductores, posición y tamaño del nuevo

transformador, pérdidas y flujos por la nueva red, el problema de combinación se vuelve

inmanejable a través de técnicas convencionales de optimización, por lo cual se proponen

dos vías de acción. Por un lado, reconocer la utilidad de dividir un problema de gran

dimensión en problemas menores, situación que queda en evidencia en el capítulo 4, y por

tanto dividir la zona de planificación en vecindarios, siendo cada uno de ellos

independientes y buscando al interior de ellos la mejor recombinación posible. Por otro

lado, es asumir que el problema debe ser abordado en forma global de manera de buscar la

mejor reagrupación posible, lo cual sin duda no puede ser resuelto en forma determinística

por lo que se recurre al uso de una meta-heurística que ayude a encontrar una buena

solución para el problema, no necesariamente la óptima, para lo cual se utiliza la técnica

conocida como búsqueda tabú.

5.2.2 Resolución mediante vecindarios

Esta metodología consiste en aprovechar las ventajas de dividir el problema principal en

problemas más pequeños, reducción del número de combinaciones factibles, y de realizar

una agrupación inteligente de las distintas redes a través de los polígonos de Voronoi, para

lo cual se eligen como puntos generadores aquellos transformadores con capacidad

instalada superior a una determinada cota, por ejemplo 300 kVA, y cada polígono de

Voronoi incorpora al resto de los transformadores más cercanos, lo que implica asociar al

mismo polígono la red correspondiente a cada uno de los transformadores agrupados,

formando de esta manera distintos vecindarios, agrupaciones de redes, a los que se les

realizará el proceso de macro-optimización basado en la unión de redes. Tal proceso, en

atención a que la división del problema trae consigo una disminución considerable de los

casos factibles, realiza la recombinación mediante enumeración completa, esto es que cada

una de las combinaciones posibles al interior de un vecindario será revisada, escogiendo el

conjunto de combinaciones que produzca más ahorro con respecto al caso base. Se debe

tener presente que la referencia a conjunto de combinaciones indica que la solución final

97

encontrada para cada vecindario corresponde a una combinación de combinaciones que

producen ahorro, siempre y cuando dichas combinaciones no presenten redes comunes. Por

ejemplo, sean A, B, C, D y E redes de un mismo vecindario, si se toman todas las

combinaciones posibles se tiene:

• Grupos de 1 red : A-B-C-D-E

• Grupos de 2 redes : AB-AC-AD-AE-BC-BD-BE-CD-CE-DE

• Grupos de 3 redes : ABC-ABD-ABE-ACD-ACE-ADE-BCD-BCE-BDE-CDE

• Grupos de 4 redes : ABCD-ABCE-ABDE-ACDE-BCDE

• Grupos de 5 redes : ABCDE

Con lo que la solución final será la mejor combinación de los grupos anteriores, con el

cuidado de no utilizar en la solución final más de una vez la misma red. Así por ejemplo

una posible solución final puede ser A-BE-CD.

Para evitar trabajo innecesario y no evaluar la totalidad de las combinaciones, se opta por

realizar la evaluación sólo en aquellas combinaciones factibles, definiendo la factibilidad en

forma secuencial, y por ende cuando una combinación satisface la secuencia, se considera

como candidata para formar parte en la combinación final. Entonces:

1. Serán combinaciones factibles en etapa 1 todas aquellas combinaciones del

vecindario que se encuentren conectadas por al menos dos vértices del polígono de

Voronoi o análogamente por una arista de la triangulación de Delaunay del

vecindario correspondiente, esto con el fin de evitar que la combinación entre redes

se superponga a alguna red que no pertenece a la combinación, y así evitar la

duplicación de redes sobre una zona determinada.

2. Serán combinaciones factibles en etapa 2 todas aquellas combinaciones factibles en

etapa 1, que no producen componentes conexas en la representación de grafo de la

red vial, es decir sólo serán factibles aquellas combinaciones que se encuentren

comunicadas a través de la red vial sin la formación de islas viales, ya que ello

implicaría la necesidad de al menos un transformador por cada isla formada,

situación que se aleja del objetivo de combinar redes para disminuir los costos.

98

3. Serán combinaciones factibles todas aquellas combinaciones factibles en etapa 2,

que al realizarse tal combinación el costo total es menor que la suma de los costos

totales de cada una de las redes que forman la combinación. Por tanto, las

combinaciones factibles serán en resumen, las realizadas entre vecinos conectados

vialmente que generen ahorros con respecto a la no realización de la combinación.

Una vez que se conoce el ahorro que se produce con cada una de las combinaciones

factibles, se debe proceder a combinarlas a fin de encontrar la solución final. Siguiendo con

el ejemplo, luego del análisis de factibilidad, las combinaciones podrían ser:

• Grupos de 1 red : A-B-C-D-E

• Grupos de 2 redes : AB-AD-BC- BE-CE

• Grupos de 3 redes : ABD-ACD-BDE-CDE

• Grupos de 4 redes : ABDE

• Grupos de 5 redes : (Combinación no factible)

De esta forma las combinaciones finales factibles serían:

• ABDE-C

• ABD-CE

• ABD-C-E

• ACD-BE

• ACD-B-E

• DCE-AB

• DCE-A-B

• AB-CD-E

• AD-BC-E

• AD-BE-C

• AD-CE-B

• AD-B-C-E

• BC-A-D-E

99

• BE-A-C-D

• CE-A-B-D

Como se conoce el ahorro de cada combinación factible, la solución final vendrá dada por

aquella que agrupe de mejor forma las combinaciones anteriores, de manera que produzca

el mayor ahorro posible, dicho procedimiento es realizado mediante enumeración completa.

El inconveniente de la metodología descrita es que se permiten todas las agrupaciones,

siendo altamente probable que muchas de ellas no produzcan ahorros e igualmente generen

aumentos en los tiempos de ejecución, ello producto que las combinaciones de varias redes

implican la optimización de una zona mayor, con lo que el tiempo de procesamiento crece,

y también lo hace necesariamente el tamaño de la red de distribución, aumentando en

exceso las pérdidas asociadas, y por tanto incrementado los costos en relación al caso en

que todas las redes se mantienen independientes. De hecho como se muestra en la tabla 5.3,

en que la cota se estableció en 300 kVA, si se permiten agrupaciones de dos, tres, hasta

nueve redes, escogiendo nueve como cota superior dado que corresponde al máximo

número de redes al interior de un vecindario, se tiene que un aumento en el número de

elementos a combinar provoca un aumento en el tiempo de ejecución con un incremento

menor en el ahorro asociado.

Tabla 5.3: Ahorro v/s número de combinaciones con cota en 300 kVA

Número de redes a

combinarAhorro ($) Tiempo (min)

2 46.093.449 2,07

3 48.673.315 3,14

4 48.759.939 3,73

5 49.265.430 4,18

6 49.744.881 4,47

7 50.246.559 4,55

8 50.246.559 4,54

9 50.246.559 4,55

Es más, si se analiza el caso de 500 kVA, se observa que el aumento en el número de

elementos a combinar incrementa los tiempos de ejecución, esto se debe a que como

100

existen menos puntos generadores el tamaño del polígono es mayor y por tanto el número

de redes al interior de un vecindario también es mayor, con lo cual el número de

combinaciones de n elementos crece, probándose más casos y por ende consumiendo más

tiempo en su solución. En efecto, para el caso de cota en 500 kVA se obtiene que, si se

realizan combinaciones de dos elementos se logra un ahorro de $ 67.335.440 en un tiempo

de 4 minutos. Al aumentar a tres los elementos a combinar en cada vecindario, el tiempo

crece a 10 minutos con un ahorro que aumenta a tan sólo $ 74.643.055, si el número es 4 el

ahorro es de $ 74.935.026, manteniéndose casi inalterable, en un tiempo de 33 minutos. Se

debe señalar además, que para un incremento adicional al mencionado fue imposible lograr

la convergencia, toda vez que el número de combinaciones era elevado, puesto que uno de

los vecindarios posee 52 redes, lo que da un número de combinaciones posibles de

2.598.960, haciendo inmanejable la búsqueda de una solución.

De lo anterior es posible deducir que el incremento de combinaciones si bien aumenta los

ahorros también produce mermas en la velocidad de solución del problema, por lo que se

necesita encontrar una forma de producir ahorros relevantes pero sin la necesidad de

tiempos extremos de ejecución. Para evitar tal problema, se propone la utilización cíclica

del procedimiento planteado, pero sólo considerando combinaciones de dos redes, ello con

el fin de comparar sólo casos que toman menos tiempo ya que abordan una zona de

planificación menor y además son más probables de generar ahorros que las combinaciones

entre un número superior de redes. El algoritmo propuesto es:

1. Dividir la zona de planificación en vecindarios a través del diagrama de Voronoi

2. Para cada vecindario realizar todas las combinaciones posibles de dos elementos.

2.1 Determinar todas las combinaciones factibles y el ahorro que producen.

3. Combinar las redes factibles de manera de originar la solución final.

4. Actualizar la red incluyendo las combinaciones realizadas.

5. Repetir pasos anteriores hasta que no existan ahorros en la recombinación de redes.

El desarrollo cíclico de la metodología anterior, se explica en que si bien las combinaciones

de dos redes son más probables que sean factibles, ello no garantiza que combinaciones de

101

más de dos redes no lo sean, por lo cual al permitir que la nuevas redes formadas, puedan

seguir combinándose ya sea con redes nuevas o con redes no combinadas en la etapa

anterior, implícitamente rescata el hecho de la posibilidad de combinaciones entre un

número superior de ellas, pero evitando la evaluación de todas las combinaciones posibles,

lo que implica un ahorro en tiempos de ejecución.

Utilizando este procedimiento se obtienen lo siguientes resultados.

Tabla 5.4: Ahorros por la recombinación de redes

Cota (kVA) Ahorro ($)Tiempo

(min)10 0 0,09

15 3.975.755 0,44

30 9.568.937 0,62

45 15.351.388 0,77

75 19.462.245 1,03

100 25.966.288 1,18

150 43.120.248 2,29

300 53.915.232 6,62

500 76.392.742 16,25

Donde además es posible notar que los ahorros aumentan en la medida que la cota utilizada

para la creación de los vecindarios también crece, ello es debido a que el número de

polígonos que cubre la zona de planificación disminuye, con lo cual cada vecindario agrupa

a un mayor número de redes. En este escenario entonces es válido preguntar por que no

ampliar al máximo la zona de análisis, es decir utilizar un único vecindario que incluya

todas las redes a combinar. Tal como se mencionó, dicho problema, al ser de una

complejidad combinatoria elevada, será resuelto mediante búsqueda tabú en la siguiente

sección.

5.2.3 Resolución mediante búsqueda tabú

De manera de comprender el procedimiento propuesto, se realizará una pequeña reseña

acerca de la búsqueda tabú, para posteriormente explicar la forma en que fue aplicada al

problema de combinación de redes, incluyendo la formulación y los resultados encontrados.

102

Búsqueda tabú

La búsqueda tabú constituye una meta-heurística, es decir un algoritmo heurístico de

optimización, genérico e independiente del problema a optimizar, que se adapta con

pequeñas modificaciones a la resolución de un problema determinado. Entendiéndose por

algoritmo heurístico a un proceso simple, que supone la obtención de una buena solución,

no necesariamente óptima, de un modo relativamente fácil y rápido en problemas de alta

complejidad (NP, NP-completos). Fue propuesta por Fred Glover en la década de los 80, y

desde esa fecha ha sido utilizada con éxito en una gran variedad de problemas tales como

planificación de maquinarias, diseño de topología de redes, reconocimiento de patrones,

asignación de rutas, localización y asignación de recursos, es decir, en una multitud de

problemas de optimización combinatorial (Glover, 1995).

Básicamente la búsqueda tabú consiste en un algoritmo iterativo que explora el espacio de

soluciones sin entramparse necesariamente en un óptimo local, para ello se permiten

movimientos que empeoran la solución, a la vez que los últimos movimientos se almacenan

en una lista, y no pueden ser realizados en las siguientes iteraciones (lista tabú), de forma

de evitar ciclos durante el proceso de optimización, es decir, la búsqueda tabú es una

combinación de búsqueda local con memoria de corto plazo. Otro elemento a considerar,

además de la lista tabú tendiente a evitar ciclos, es el denominado criterio de aspiración, el

cual consiste en que si alguno de los movimientos prohibidos almacenados en la lista tabú,

cumple una determinada condición, típicamente si mejora la solución, puede ser liberado y

utilizado en el proceso de optimización, fenómeno conocido como olvido estratégico. En

virtud de lo anterior y considerando que X es el conjunto de todas las posibles soluciones, x

cualquier solución, N(x) el conjunto de todas las soluciones vecinas a x (N(x) ⊂ X), T la

lista tabú, el algoritmo simplificado es:

1. Se elije una solución factible inicial x, con x ∈ X, inicializándose la mejor solución

en x* : = x, e inicializando el contador k y la lista tabú.

2. Si N(x)-T = vacío, pasar a 4. En otro caso se toma la solución n(x), considerando la

siguiente subrutina:

103

a. Se evalúan todas las soluciones de N(x), ordenándose de mejor a peor.

b. Se escoge la mejor solución n1(x) ∈ N(x)

c. Si n1(x) ∉ T, entonces n(x)=n1(x). En otro caso, si n(x) es mejor que

x*(criterio de aspiración), entonces n(x)=n1(x). Si n(x) no es mejor que x*,

entonces elegir la segunda mejor solución de N(x) y repetir c.

3. x = n(x). Si x mejora la solución entonces x* : = x

4. Si el número de iteraciones es máximo ó N(x)-T = vacío ó la solución no mejora

luego de un número determinado de iteraciones, entonces finaliza. Sino actualiza T

= [T; x], k=k+1 y se retorna a 2.

Del algoritmo se desprende que su elemento fundamental es la lista tabú, y en particular, lo

es la elección del tamaño de la lista, es decir, el número máximo de movimientos que serán

considerados prohibidos. Así una lista de tamaño N garantizará que no se van a crear ciclos

de largo inferior a N. La elección de este parámetro es un dato de entrada al problema, y

normalmente la forma de implementarlo es a través de una lista circular, en la cual el

último movimiento se pone al principio de la lista y el último elemento de la lista, si es que

ésta se completa, es liberado de la prohibición.

Esta meta-heurística constituye una herramienta poderosa que ha sido ampliamente

utilizada, en particular, en el sector eléctrico ha sido empleada en planificación de la

expansión de redes de transmisión (Da Silva et al, 2001, Wen y Chang, 1997) en

localización óptima de condensadores (Huang et al, 1996), por mencionar sólo alguna de

sus aplicaciones.

Combinación de redes vía búsqueda tabú.

El objetivo de la búsqueda tabú en este trabajo, es entregar una buena combinación entre

redes, de manera de disminuir los costos obtenidos del proceso de micro-optimización. En

la siguiente figura se muestra un conjunto de redes, demarcadas por la envolvente convexa

que engloba a todos los consumos de cada una de ellas, y donde los puntos más grandes,

representan la posición del transformador, indicando algunas zonas que al unirse

posiblemente constituirían mejoras a la función objetivo, observando además, que si un

104

transformador es utilizado en una combinación ya no puede ser utilizado en otra, por lo que

la elección del conjunto de mejores combinaciones no es trivial, toda vez que el número de

combinaciones posibles aumenta exponencialmente con el número de transformadores.

Figura 5.11: Posibilidad de combinación de redes

Así lo que se busca es el mejor mix entre las posibles combinaciones, siempre y cuando

cada red combinada sea utilizada en una única combinación, lo que se representa de

acuerdo a la siguiente estructura:

1 1 2 1 2 4 4

En donde el largo de la estructura representa el número de redes totales en el área de

análisis, la posición en la estructura identifica a una determinada red, y el valor al interior

de la estructura indica la combinación utilizada, es decir en la solución mostrada se tienen

20 redes a combinar, en que las redes 2-3-5 se unen a través de la combinación 1, las redes

4-7 lo hacen mediante la combinación 2, las redes 13-14 son mezcladas por la combinación

4. Para conseguir tal resultado el algoritmo propuesto es el siguiente:

[y]

[x]

105

1. Se realiza la triangulación de Delaunay tomando como vértices la posición de los

transformadores.

2. Se realizan todas las posibles combinaciones de transformadores y redes asociadas,

siempre y cuando se encuentren conectadas por una arista de la triangulación y

exista conexión vial entre las redes (sin generación de componentes conexas).

3. Para cada combinación se calcula el ahorro que se produce al realizarla, en caso de

no existir ahorro la combinación deja de ser factible.

4. Se ordenan de mayor a menor las combinaciones factibles, de acuerdo al ahorro que

producen.

5. Se inicializa la solución escogiendo como valor inicial la combinación que produce

el mayor ahorro de la lista anterior (Mejor Movimiento)

6. Se escoge la siguiente mejor combinación (mejor ahorro)

a. Si la nueva combinación no une redes que ya han sido incluidas en la

solución, se adiciona a ella.

b. Si la nueva combinación utiliza al menos una red que pertenece a la

solución actual, se agrega la nueva combinación (empeoramiento de la

solución y/o aumento del espacio de búsqueda) y se eliminan de la solución

todas aquellas combinaciones anteriores que involucren redes contenidas en

la nueva combinación. Las combinaciones eliminadas pasan a la lista tabú, y

por tanto no pueden ser utilizadas hasta que salgan de ella (el número de

iteraciones que permanecen en la lista, se denomina largo tabú y es definido

a priori).

7. Se disminuye en uno el contador de la lista tabú, para cada combinación en ella

incluida. Sí para una determinada combinación el contador llega a cero, significa

que puede dejar la lista tabú y por tanto es agregada nuevamente a la lista de

combinaciones factibles.

8. Se ordena de mayor a menor la lista actual de combinaciones factibles.

9. Se vuelve al paso 5. El proceso se detiene si:

a. Se alcanza el número máximo de iteraciones

b. La lista de soluciones factibles es vacía.

106

Aplicando la metodología propuesta, en forma iterativa tal como se explicó en el caso de

macro-optimización por vecindarios, es posible obtener un ahorro de $ 78.054.181,

representando un 4 % del costo del caso base, en un tiempo de 19 minutos. Observándose

que existe una leve mejoría con respecto a la recombinación basada en vecindarios,

mostrando un ahorro 2 % superior al mejor ahorro señalado en la Tabla 5.3.

A modo de ejemplo a continuación se presentan dos figuras, la primera representa la salida

del proceso de micro-optimización (252 redes), en tanto que la segunda indica la salida del

proceso de macro-optimización (190 redes), en ambos casos los transformadores están

indicados por un punto y los consumos asociados a cada red están encerrados a través de su

envolvente convexa.

3.6 3.65 3.7 3.75 3.8 3.85 3.9 3.95 4 4.05 4.1

x 104

6000

7000

8000

9000

10000

11000

12000

Figura 5.12: Configuración de redes producto de la micro-optimización

[m]

[m]

107

3.6 3.65 3.7 3.75 3.8 3.85 3.9 3.95 4 4.05 4.1

x 104

6000

7000

8000

9000

10000

11000

12000

Figura 5.13: Configuración de redes producto de la macro-optimización

5.3 Macro-Optimización: Unión Diagramas de Voronoi y Búsqueda Tabú

Considerando las bondades de las dos metodologías propuestas, en este algoritmo

finalmente se propone la realización secuencial de ellas. De tal forma de incluir la

asociación inteligente producto del diagrama de Voronoi y la incorporación de información

adicional y de mejora de la función objetivo a través de la recombinación de redes gracias a

la búsqueda tabú. Por tanto la secuencia recomendada de aplicación sería la siguiente:

1. Micro-optimización simplificada, sin las restricciones viales ni consideración de la

red eléctrica.

2. Trazado del diagrama de Voronoi tomando como puntos generadores la ubicación

de los transformadores obtenidas en el paso anterior.

3. Micro-optimización completa y detallada para cada uno de los polígonos de

Voronoi.

[m]

[m]

108

4. Macro-optimización de recombinación entre todas las redes obtenidas luego del

proceso de micro-optimización.

Con esta solución se presentan los mayores ahorros con respecto al caso base dado por la

aplicación exclusiva del proceso de micro-optimización explicado en el capítulo 4, en

efecto el ahorro total es de $ 135.972.397 (197 redes) representando un descuento de 7.4 %

respecto del caso base.

3.6 3.65 3.7 3.75 3.8 3.85 3.9 3.95 4 4.05 4.1

x 104

6000

7000

8000

9000

10000

11000

12000

Figura 5.14: Configuración de redes luego de la macro-optimización secuencial

[m]

[m]

109

6. PLANIFICACION OPTIMA DEL GRAN SANTIAGO

Este capítulo ilustra la aplicabilidad de la metodología propuesta a la planificación de una

zona de gran tamaño, en particular se mostrará la posibilidad de acción de los distintos

mecanismos sobre los consumos de baja tensión, suministrados por CHILECTRA en la

Región Metropolitana36, abasteciendo del orden de 1.300.000 clientes distribuidos en una

superficie aproximada de 2.118 km2. Se debe recordar que los datos de demanda utilizados

como base del estudio corresponden a datos actualizados a diciembre del año 2003, ello

producto que el estudio tarifario 2004, tomó como base dicha fecha y por ende las

comparaciones con tales resultados sólo son posibles si se toma la misma referencia. A tal

fecha, la compañía distribuidora contaba con 9.333 kilómetros de redes de baja tensión,

20.285 transformadores de distribución con una capacidad total instalada de 2.456 MVA

suministrando un total de 3.917 GWh, correspondientes a consumos de energía de los

clientes conectados a través de la red de baja tensión37.

En esta sección sólo se mostrarán los resultados finales obtenidos, con una breve

explicación, puesto que la metodología corresponde a lo explicado en extenso en los

capítulos anteriores, mostrándose la aplicación de cada procedimiento a la totalidad de la

zona de concesión de CHILECTRA.

6.1 Aplicación del Proceso de Micro-Optimización

Este procedimiento reviste gran importancia puesto que corresponde a la estructura

fundamental de todas las metodologías propuestas, ya que los procesos de macro-

optimización la utilizan como dato de entrada.

36 La zona de análisis incluye a la ciudad de Santiago, capital de Chile, con una población al 31 de diciembre del 2003 de 5.3 millones de habitantes. 37 Las ventas totales de energía para el año 2003 fueron de 8.696 GWh, repartiéndose 3.917 GWh a clientes de baja tensión y 4.779 GWh a clientes de media tensión.

110

Del capítulo 4 fue posible encontrar que un tamaño adecuado para la zona de análisis era de

500 x 500 metros. También se pudo mostrar que en el proceso iterativo asociado a la micro-

optimización, al encontrar un valle en la función de costo se está, con alta probabilidad, en

presencia de un mínimo global. Además se observó que en la metodología propuesta, el

equilibrio de red sólo es significativo al finalizar el proceso iterativo, todas conclusiones

que son aplicadas a la micro-optimización del Gran Santiago. Así, la división de la zona a

planificar se muestra en la siguiente figura.

0 1 2 3 4 5 6

x 104

0

1

2

3

4

5

6

7x 10

4

Figura 6.1: División en mini-zonas del gran Santiago

[m]

[m]

111

Existe un total de 3103 mini-zonas a optimizar, las que para 10 lanzamientos del algoritmo,

tabla 6.1, entregan un costo promedio de $ 71.027.164.452 en un tiempo de ejecución

promedio de 168,3 minutos correspondientes a 2,8 horas38.

Tabla 6.1: Micro-optimización del gran Santiago

Lanzamiento Costo Total ($) Tiempo (min)

1 70.973.285.445 173,5

2 71.158.531.278 167,8

3 70.921.325.234 167,6

4 70.951.990.818 167,6

5 71.098.651.683 167,3

6 71.067.957.121 168,9

7 70.972.409.405 167,4

8 71.003.831.236 167,0

9 71.014.399.273 167,4

10 71.109.263.030 168,7

De tales simulaciones, es posible obtener que el largo promedio de la red de baja tensión es

7.828 Km, que se utilizan 12.039 transformadores con una capacidad total instalada en

baja tensión de 2.861 MVA, con pérdidas de energía para el año base de 54.142 MWh.

Si bien, la red trazada corresponde sólo a una red área de baja tensión, y por tanto no

reconoce las zonas subterráneas del área de planificación, ni tampoco su relación directa

con la red de distribución de media tensión, es posible cotejar, de todas formas, el orden de

los resultados obtenidos, con los estudios de VAD realizados en la fijación tarifaria

utilizada como referencia, de manera de comprobar la coherencia de las salidas obtenidas.

Por ejemplo, en el caso de las pérdidas para el año inicial, en donde se ve reflejado tanto el

trazado como el tipo de conductores seleccionados, se tiene que en el estudio encargado por

la empresa distribuidora, en adelante estudio de la distribuidora (Systep e Inecon, 2004), las

pérdidas corresponden a 75.312 MWh y en el estudio encargado por la Comisión Nacional

de Energía, en adelante estudio de la CNE (Synex, Mercados Energéticos y Jadresic

Consulting, 2004), ascienden a un valor de 35.580 MWh, ubicándose el resultado aquí

38 La tabla completa para todos los lanzamientos, con el desglose de costos e infraestructura se presenta en el

112

obtenido entre ambos valores. En cuanto a los kilómetros de red, el resultado obtenido es

menor tanto al estudio de la distribuidora como al estudio de la CNE, cuyos valores son

9.050 km y 9.075 km respectivamente, este hecho no debe ser explicado por si sólo, sino

que debe considerarse lo que sucede con los transformadores. En el estudio de la

distribuidora el número óptimo es de 7.247 y en el estudio de la CNE es de 8.416 unidades,

por lo tanto, con la metodología propuesta se obtiene un resultado absolutamente coherente,

toda vez que el número de transformadores obtenido es mayor y el largo de red es menor39

que en los estudios citados, situación que acontece dada la división arbitraria de la gran

zona de planificación en mini-zonas de optimización, en las cuales al respetar el tendido

vial y por ende al no trazar redes entre zonas no vialmente conectadas, se fuerza a que en

cada isla vial de cada una de las mini-zonas, exista al menos un transformador.

6.2 Aplicación del Proceso de Macro-Optimización

Para evitar el posible exceso de transformadores y eventuales costos extras asociados a la

división arbitraria del área de análisis, se desarrollaron metodologías adicionales para

realizar una fragmentación inteligente del problema, las cuales serán aplicadas al Gran

Santiago. Debido a que la comparación es con respecto al proceso de micro-optimización y

tal metodología es no determinística, se tomará como base un lanzamiento particular de la

metodología, para que en los procesos de macro-optimización la referencia sea la misma.

En suma, los resultados para dicho lanzamiento con un tiempo de ejecución de 167

minutos, son:

• Costo total : $ 70.973.296.670

• Costo total + pérdidas : $ 79.981.055.629

• Número de transformadores : 12.052 unidades

• Largo de red : 7.822 kilómetros

• Capacidad instalada : 2.859 MVA.

Anexo H 39 En las redes de distribución se tiene que los transformadores con sus redes asociadas tienen una relación inversamente proporcional, en el caso extremo si cada consumo tuviese su propio transformador la red de distribución de baja tensión sería cero.

113

Resultando por tanto, un total de 12.052 redes asociadas a sus respectivos transformadores,

lo que se puede visualizar en la figura 6.2, donde cada red esta acotada por la envolvente

convexa de los consumos que la componen.

114

Figura 6.2: Redes del caso base: micro-optimización

[m]

[m]

[m]

[m]

115

6.2.1 Metodología basada en diagrama de Voronoi

Se realiza el trazado del diagrama de Voronoi, considerando como puntos generadores de

los polígonos, a la ubicación de los transformadores obtenidos en la etapa de micro-

optimización, para luego aplicar a cada nueva mini-zona irregular el proceso de micro-

optimización completo. Se debe recordar que los mejores resultados se obtuvieron cuando

los puntos generadores correspondían a aquellos asociados a transformadores superiores a

300 kVA, y por tanto en esta aplicación, se emplea tal condición como base para elaborar

los polígonos de Voronoi de Santiago. Con ello, en la figura 6.2, es posible apreciar la

aplicación de esta técnica para la zona en cuestión.

Con esta metodología se obtuvo un costo menor que el caso base, arrojando los siguientes

resultados:

• Costo total : $ 70.098.342.446

• Costo total + pérdidas : $ 78.133.902.585

• Número de transformadores : 11.966 unidades

• Largo de red : 8.210 kilómetros

• Capacidad instalada : 2.895 MVA.

Lo que constituye una mejora de 2,31 % (aproximadamente dos mil millones de pesos) con

respecto al caso base considerando las pérdidas. Para clarificar los resultados, se aplicó el

mismo procedimiento, pero ahora considerando como centro de los polígonos a aquellos

transformadores superiores a 500 kVA, obteniendo lo siguiente:

• Costo total : $ 69.384.475.120

• Costo total + pérdidas : $ 78.256.523.843

• Número de transformadores : 11.355 unidades

• Largo de red : 8.347 kilómetros

• Capacidad instalada : 2.869 MVA.

116

En ambos casos, es posible apreciar una disminución en el costo total, asociado a la mejor

asignación de los consumos, lo que se traduce en un menor número de transformadores y

por consiguiente un mayor largo de red. Se debe señalar que los tiempos de simulación

fueron de 179 y 252 minutos respectivamente, sin considerar el tiempo requerido por el

caso base.

117

Figura 6.3: Diagrama de Voronoi aplicado a Santiago

6.2.2 Metodología simplificada basada en diagrama de Voronoi

Se desarrolló el diagrama de Voronoi pero sin utilizar el proceso de micro-optimización

para la generación de los polígonos, sino que las ubicaciones generadoras provienen de un

proceso de micro-optimización simplificado, que no considera ni el trazado de la red ni el

trazado vial y sólo incluye en el análisis la demanda y la elección y ubicación del

0 1 2 3 4 5

x 104

0

1

2

3

4

5

6

x 104

3.4 3.6 3.8 4 4.2 4.4

x 104

0.7

0.8

0.9

1

1.1

1.2

1.3

1.4

1.5

x 104

[m]

[m]

[m]

[m]

118

trasformador adecuado, ello con el fin de evitar los 167 minutos asociados al caso base. De

esta forma, el procedimiento simplificado requiere sólo 14 minutos para su ejecución, luego

de lo cual se realiza el diagrama de Voronoi y se aplica el procedimiento de micro-

optimización completo para cada uno de los polígonos formados.

Al igual que en el caso anterior, se consideraron como puntos generadores las ubicaciones

de aquellos transformadores, que de acuerdo al procedimiento de micro-optimización

simplificado son superiores a 300 kVA y luego a 500 kVA, con lo cual, los resultados para

el primer caso son:

• Costo total : $ 70.505.021.797

• Costo total + pérdidas : $ 78.722.075.399

• Número de transformadores : 11.815 unidades

• Largo de red : 8.261 kilómetros

• Capacidad instalada : 2.892 MVA.

Y para el caso de 500 kVA son:

• Costo total : $ 70.337.529.277

• Costo total + pérdidas : $ 78.729.180.328

• Número de transformadores : 11.447 unidades

• Largo de red : 8.292 kilómetros

• Capacidad instalada : 2.874 MVA.

Si bien, en ambos casos los ahorros no superan el 2%, se debe señalar la ventaja en tiempo

que esta metodología brinda, toda vez que sólo demora 170 y 240 minutos,

respectivamente, sin necesidad de los 167 minutos adicionales del caso base.

119

6.2.3 Metodología basada en vecindarios

Este procedimiento busca incorporar las posibles economías producto de unir redes vecinas,

esto es, hacer que zonas aledañas que tienen su propio transformador y red sean unidas de

manera de suministrarlas a través de un único transformador con sólo una red asociada,

para ello se divide la zona en vecindarios utilizando los polígonos de Voronoi, para luego

en cada uno de los vecindarios encontrar la mejor combinación de redes, de forma de lograr

una disminución en el costo total.

Entonces, cada uno de los vecindarios está formado por todas las redes que quedan al

interior de un polígono de Voronoi, los que son creados tomando como puntos generadores

la ubicación de todos los trasformadores del caso base, cuya capacidad sea superior o igual

a 500 kVA. Aplicando tal procedimiento, se obtienen 4.103 vecindarios para Santiago, tal

como se aprecia en la figura 6.4, en particular, en su figura inferior es posible notar como

cada vecindario (polígonos convexos de líneas gruesas), contiene un conjunto de redes a

combinar (polígonos convexos de líneas delgadas).

Así, en cada vecindario se encuentra la mejor combinación, es decir la que produce

mayores ahorros, entre las redes que lo componen. Siendo el ahorro final, la sumatoria de

los ahorros producidos en cada uno de los vecindarios. De esta forma, el ahorro total

obtenido, con respecto al caso base, es de $ 2.824.076.757 lo que representa un ahorro de

3,53 %, ejecutándose el procedimiento en 178 minutos. El resumen de los resultados

obtenidos es el siguiente:

• Costo total : $ 67.338.746.724

• Costo total + pérdidas : $ 77.156.978.872

• Número de transformadores : 9.357 unidades

• Largo de red : 8.187 kilómetros

• Capacidad instalada : 2.741 MVA.

120

Figura 6.4: Creación de vecindarios para la recombinación de redes

[m]

[m]

[m]

[m]

121

6.2.4 Metodología basada en búsqueda tabú y único vecindario

Al igual que en el caso anterior se buscan las economías producto de la unión de redes

aledañas, pero esta vez sin la realización de vecindarios, sino que buscando la mejor

combinación de entre todas las redes que se obtienen luego del proceso de micro-

optimización. Dada la gran cantidad de combinaciones posibles, se opta por la heurística

búsqueda tabú para conseguirlo. Además, para disminuir el espacio de búsqueda de la

solución, que en este caso constituye encontrar el conjunto de mejores combinaciones entre

redes, se evitan aquellos casos en que se busca unir redes alejadas o separadas por alguna

red intermedia, para ello se realiza la triangulación de Delaunay, entre todas las redes del

caso base, representadas por su transformador asociado. Esta triangulación, para el caso de

Santiago se presenta en la figura 6.5.

122

Figura 6.5: Triangulación de Delaunay para Santiago

De esa manera, sólo se consideran como redes factibles a combinar, aquellas que

inicialmente se encuentran unidas a través de aristas de la triangulación (ver 5.2.2),

reduciendo considerablemente el espacio de búsqueda al combinar únicamente redes

vecinas.

Con este procedimiento y requiriendo un tiempo de ejecución40 de 254 minutos, se

obtuvieron los siguientes resultados:

• Costo total : $ 65.463.843.208

• Costo total + pérdidas : $ 76.041.409.699

• Número de transformadores : 8.404 unidades

40 Este tiempo incluye sólo el requerido para la realización de la metodología de macro-optimización, sin considerar el tiempo necesario para la realización del caso base que entrega las redes iniciales.

Aristas de la Triangulación de Delaunay

[m]

[m]

123

• Largo de red : 8.746 kilómetros

• Capacidad instalada : 2.664 MVA.

De donde se obtiene un ahorro de $3.939.645.930, que representa una disminución de 4,93

% con respecto al caso base.

6.2.5 Metodología secuencial Voronoi-búsqueda tabú

La metodología aquí señalada busca aprovechar la utilización de mini-zonas irregulares y

los ahorros que se producen al combinar redes, para lo cual se realiza secuencialmente

sobre Santiago la aplicación de los polígonos de Voronoi y luego sobre las redes ahí

resultantes, el proceso de recombinación.

Se hace necesario responder a la siguiente interrogante, ¿Qué metodología de Voronoi y

que metodología de recombinación de redes utilizar?. Frente a lo primero, para el

procedimiento de mini-zonas irregulares se opta por el proceso de Voronoi simplificado,

ello por el ahorro de tiempo que involucra, puesto que los puntos generadores de los

polígonos no provienen del proceso de micro-optimización (167 minutos) sino de una

simplificación del mismo (14 minutos), y así sólo se requiere de un única aplicación de la

metodología de micro-optimización (170 minutos) sobre las mini-zonas irregulares

formadas en el proceso simplificado. Respecto a la recombinación de redes se utiliza la

metodología de macro-optimización basada en búsqueda tabú, la cual es aplicada sobre un

único gran vecindario representado por la totalidad de Santiago. Esta elección es producto

que presenta mayores ahorros que la metodología de macro-optimización basada en

vecindarios. Por lo tanto, el proceso aquí ejecutado es el siguiente:

1. Micro-optimización Simplificado (14 minutos)

2. Micro-optimización Completa (170 minutos)

3. Macro-optimización de búsqueda tabú con único vecindario (207 minutos)

124

Al realizar esta aplicación secuencial se obtiene un ahorro final de $ 4.901.118.462 que

representa una disminución de 6,13 % con respecto al caso base. Los resultados obtenidos

son:

• Costo total : $ 64.422.594.684

• Costo total + pérdidas : $ 75.079.937.167

• Número de transformadores : 7.686 unidades

• Largo de red : 8.935 kilómetros

• Capacidad instalada : 2.625 MVA.

125

7. CONCLUSIONES Y TRABAJOS FUTUROS

7.1 Conclusiones

La principal contribución de la presente investigación está dada por el desarrollo de una

metodología capaz de dar respuesta al problema de planificación de redes de distribución,

cuando ésta es del tipo greenfield planning, es decir cuando los únicos datos de entrada son

la ubicación y el consumo de los clientes. Este procedimiento busca minimizar el costo de

inversión en transformadores y conductores más el costo de pérdidas, entregando como

resultado el costo, capacidad y ubicación de los transformadores de distribución, el costo y

tipo de los conductores utilizados y el trazado de las redes asociadas a cada transformador.

En la sección referida al Estado del Arte, se pudo constatar que el problema en cuestión ha

sido abordado ampliamente, inicialmente a través de herramientas tradicionales de

programación matemática, con las cuales sólo era posible enfrentar problemas de tamaño

reducido. En la medida que los problemas a resolver fueron aumentando de tamaño, dichas

metodologías perdieron poder de resolución, dando paso al uso de heurísticas, mediante las

cuales, si bien, no se garantiza la obtención del óptimo global, es posible obtener buenas

soluciones a problemas complejos de gran tamaño. Es en esta línea, que la presente tesis

aborda la planificación de redes de distribución, logrando resolver la optimización del gran

Santiago, el cual abastece a cerca de 1.300.000 clientes distribuidos en una superficie

aproximada de 2.118 km2.

Esta metodología muestra la aplicabilidad del procedimiento “Dividir y Conquistar”, en

cuanto Santiago fue dividido en zonas de menor tamaño, disminuyendo considerablemente

la característica combinatoria del problema, y optimizando en forma independiente cada

una de las mini-zonas, con lo cual se logró encontrar solución al problema en tan sólo 167

minutos. Tiempo que podría mejorar, toda vez que es posible aplicar proceso paralelos en

su solución, por ejemplo, si el problema es dividido en n mini-zonas, n/2 podrían ser

realizadas en un computador y las otras n/2 en otro computador, en forma simultánea.

Como la optimización entre mini-zonas es independiente, el tiempo de ejecución podría ser

disminuido aproximadamente a la mitad y así los tiempos disminuirían progresivamente en

126

la medida que se incorporan nuevas estaciones de trabajo a la resolución del problema, lo

que constituye un acierto de la metodología de micro-optimización propuesta.

Del proceso de optimización realizado sobre cada mini-zona (micro-optimización), fue

posible constatar la relación existente entre el número de transformadores y la red asociada

a cada transformador, observando que un análisis acoplado entre la red y el transformador

permite encontrar una combinación óptima de ellos, es decir un mix capaz de minimizar

para cada mini-zona el costo de transformación, conductores y pérdidas. Siendo posible

mostrar, que dicho óptimo se obtiene en el mínimo del primer valle, que se encuentra en la

curva de costo total, la cual indica el costo de inversión más pérdidas en función del

número de transformadores instalados, donde tal costo se obtiene de la elección y ubicación

óptima de i transformadores (vía cluster), y donde para cada uno de ellos se determina la

red óptima, tanto en trazado como en elección de conductores. Así al realizar la

metodología para innumerables lanzamientos fue posible mostrar, que si al instalar un

transformador adicional, i+1 transformadores, existía un incremento en el costo total,

entonces el mínimo esta dado por la instalación óptima de i transformadores con sus

respectivas redes asociadas, situación que permite disminuir los tiempos de ejecución, al

acotar el espacio de búsqueda, ya que elimina la necesidad de encontrar los costos que se

obtendrían con la instalación de un número mayor a i+1 transformadores. En efecto, al

realizar la metodología sobre la comuna de Macul, para distintos valores de búsqueda,

entendiendo ésta como el número de iteraciones adicionales, luego del primer valle

encontrado en la curva de costos totales, no fue posible encontrar una mejoría significativa

en el costo final. Es decir, el aumento del espacio de búsqueda no trajo consigo la

disminución de costos, y por tanto no hubo presencia de nuevos mínimos en cada mini-

zona.

También es importante destacar, la consideración de la red vial a la hora de realizar el

trazado, ya que esto por un lado evita el paso de redes a través de accidentes geográficos,

donde no existen redes viales (cerros, mesetas, etc.), y por otro lado permite la

determinación correcta de las redes, al considerar la conectividad real existente entre los

distintos consumos, logrando así su correcta valorización y posterior consideración en la

curva de costo total.

127

El procedimiento aquí propuesto si bien es no determinístico, es decir para los mismos

valores cada vez que es ejecutado no entrega necesariamente los mismos resultados, sí

presenta resultados bastantes similares cada vez que es empleado, valores cuya desviación

no debiese afectar al planificador en las diversas decisiones a tomar. Es así como para 20

lanzamientos de la metodología sobre la comuna de Macul, la desviación estándar del costo

total sólo representa el 0,39 % del costo promedio total para todas las ejecuciones, y en el

caso de Santiago para 10 ejecuciones representa el 0,11 % del costo promedio total,

permitiendo concluir la consistencia de sus resultados para la toma de decisiones.

En consideración, a la forma de solución planteada en la metodología de micro-

optimización, se puede inferir inmediatamente que tal mecanismo, al no considerar las

posibles ventajas de combinar zonas vecinas, puede ser perfeccionado. De esta

investigación, se pudo mostrar que tal perfeccionamiento se puede dar a través de dos

caminos, uno mediante la agrupación de consumos cercanos a través de los polígonos de

Voronoi y otro mediante la recombinación de redes vecinas. Para una mejor visualización

de las conclusiones, se presenta a modo de ejemplo el resumen de las metodologías de

macro-optimización aplicadas a Santiago.

Tabla 7.1: Metodologías de macro-optimización sobre Santiago41.

Micro-Optimización

Caso BaseDiagrama de

Voronoi

Diagrama de

Voronoi

simplificado

Unión de

Redes vía

Vecindarios

Unión de

Redes vía

Búsqueda

Tabú

Polígonos de

Voronoi y

Búsqueda

Tabú

Costo total (MM$) 70.973 70.098 70.505 67.338 65.463 64.422

Costo total + pérdidas

(MM$) 79.981 78.133 78.722 77.156 76.041 75.079

Número de

Transformadores (#)12.052 11.966 11.815 9.357 8.404 7.686

Largo de Red (Km) 7.822 8.210 8.261 8.187 8.746 8.935

Capacidad Instalada

(MVA)2.859 2.895 2.892 2.741 2.664 2.625

Tiempo de Ejecución

(min)167 346 184 345 421 391

Macro-Optimización

41 Las metodologías de Macro-Optimización incluyen el tiempo requerido para la Micro-Optimización, puesto que esta constituye su input. Sólo el procedimiento “Diagrama de Voronoi simplificado”, prescinde del tiempo adicional, puesto que emplea como input un proceso simplificado.

128

Mediante la utilización de los polígonos de Voronoi, fue posible agrupar a los consumos

por su característica de cercanía y con ello lograr una reducción de costos al aplicar sobre

cada polígono el proceso de micro-optimización, con lo cual se obtuvo para el caso de

Macul un ahorro cercano al 4 % y para el caso de Santiago uno de 2 % con respecto al

proceso de micro-optimización respectivo. Es importante mencionar que los polígonos se

forman a partir de puntos generadores, probándose en la presente investigación que estos

pueden provenir de la ubicación de los transformadores, ya sean obtenidos del proceso de

micro-optimización o de un proceso simplificado (sin consideración de la red), con el

consecuente ahorro de tiempo, en el caso de Santiago se cambia una ejecución de 176

minutos por una de 14 minutos, a los polígonos así obtenidos se les aplica, de igual forma,

el proceso de micro-optimización completo.

En cuanto a la recombinación de redes vecinas, esta metodología encuentra economías al

suministrar mediante una única red y por ende bajo un único transformador, a redes

aledañas, siempre y cuando esto sea posible. Abordándose el problema desde dos

perspectivas, una mediante la división de la zona de planificación en vecindarios, y en cada

uno de ellos, analizar las posibilidades de combinación, y otra, sin la realización de

división, sino que determinando las combinaciones factibles en toda la zona de

planificación a través de la búsqueda tabú. Tanto en el caso de Macul como su posterior

aplicación a Santiago, fue posible constatar la ventaja que presenta el análisis de un único

vecindario, puesto que evita la no consideración de combinaciones entre redes que

pertenecen a vecindarios distintos. Así, para el caso de Santiago, al utilizar vecindarios se

obtuvo un ahorro de 3,5 % y en el caso de un único vecindario el ahorro creció a un 4,9 %,

sin embargo se debe señalar que la metodología de mayor ahorro, al poseer un espacio de

búsqueda mayor, requiere más tiempo en su ejecución, necesitando 76 minutos adicionales

para encontrar la solución.

Se debe constatar, que el mejor resultado obtenido se produce al realizar la aplicación

secuencial del diagrama de Voronoi y la recombinación de redes a través de un sólo

vecindario. Con lo que es posible aprovechar tanto el abastecimiento de grupos de

consumos cercanos entre sí como los ahorros que se producen al unir redes vecinas en una

129

única red. De hecho el ahorro obtenido con este procedimiento en serie es de 7,4 % para el

caso de Macul y de 6,1 % para el caso de Santiago.

Finalmente, y en relación a la validez de los resultados encontrados, se debe considerar que

la presente investigación sólo determinó redes aéreas, y en cambio los estudios de

referencia para el gran Santiago, dados por los estudios de VAD 2004-2008, tanto de la

empresa distribuidora como de la autoridad consideran además redes subterráneas, por lo

que un parangón directo no es posible, pero sí lo es la verificación del orden de los

resultados obtenidos. En efecto, el número de transformadores y kilómetros de red

extraídos del modelo42 son 7.686 unidades y 8.935 km, respectivamente, tales valores para

los estudios de referencia son de 7.247 unidades y 9.050 km para el estudio de la

distribuidora y de 8.416 unidades y 9.075 km para el estudio de la autoridad. Lo que ratifica

la bondad de la metodología propuesta.

No se debe perder de vista, que el principal acierto de la metodología planteada, más allá de

los resultados numéricos, que pueden variar de acuerdo a la definición de precios y/o

expectativas de crecimiento, es la certeza de resolver un problema de gran tamaño, con la

consideración conjunta de redes y transformadores sobre una red vial que permite

determinadas conexiones, con lo cual el problema es solucionado sin la necesidad de

excesivas simplificaciones, en un tiempo razonable, toda vez que un ejercicio de

planificación en ningún caso necesita ser resuelto en forma instantánea. En particular, es el

planificador quien puede optar discretamente por el tiempo requerido en la solución, de

hecho el resultado de la micro-optimización para Santiago se consigue entre 167 y 170

minutos, siendo voluntad del planificador realizar el proceso de macro-optimización para la

disminución de costos, etapa que toma cerca de 200 minutos en ejecutarse. Por tanto, en tan

sólo tres horas es posible obtener una primera buena aproximación a la planificación desde

cero de una zona de gran tamaño, lo que representa la gran ventaja de la división en mini-

zonas y de la metodología desarrollada.

42 Considerando como modelo final a la metodología que presenta un menor costo total, es decir al procedimiento secuencial de diagrama de Voronoi y Recombinación Tabú de redes.

130

7.2 Trabajos Futuros

La optimización de una red de distribución eléctrica de gran tamaño constituye un

problema de gran complejidad, que no puede ser resuelto a través de métodos

determinísticos, por lo que necesariamente para su resolución se requieren de

simplificaciones y aproximaciones, situación que se ha podido constatar a lo largo del

presente trabajo. Bajo esta perspectiva, siempre existen posibilidades de mejora para lograr

una visión real de la empresa modelada y con ello dar una señal justa de precios tanto a

consumidores como a la empresa regulada, por lo que se proponen las siguientes líneas de

investigación para continuar el trabajo aquí planteado:

• Consideración dinámica del ejercicio de planificación: Dentro de los supuestos de

desarrollo del algoritmo se encuentra la consideración estática del problema, lo que

significa determinar en el año base las instalaciones que abastecerán la demanda

durante todo el horizonte de estudio, ello producto que el crecimiento de la demanda

considerado es pequeño y por tanto si conductores y transformadores fueron

diseñados óptimamente para dicha tasa, son capaces de soportar el incremento de

demanda durante todo el período. Sin embargo si la tasa hubiese sido mayor, en la

práctica se requerirían instalaciones adicionales de refuerzo, ya sea nuevos

transformadores con la consiguiente re-configuración de la red y/o ampliaciones de

las secciones de la misma, efectos que no se encuentran incluidos en la metodología

propuesta. A fin de garantizar la generalidad de modelo sería importante realizar la

optimización dinámica, es decir indicar cuando deben ser llevadas a cabo las

inversiones, situación que aumenta la complejidad del problema dado que incluye la

relación inter-temporal de las decisiones, pero que constituiría un aporte en la

planificación de sistemas de distribución.

• Consideración conjunta de la red de media tensión: Otro desarrollo importante y

desafiante es la realización de la optimización de la red de distribución completa,

esto es considerando tanto la media como la baja tensión. Así, un sistema con una

red de media tensión predominante, presenta un alto número de transformadores de

131

distribución y una red de baja tensión pequeña, en cambio una compañía con una

red de baja tensión dominante, posee transformadores de mayor capacidad y por

ende un menor número de ellos, lo que genera una mayor red de baja tensión.

Existiendo una multitud de posibles soluciones entre ambos casos, por lo que resulta

fundamental preguntarse acerca de la combinación óptima entre media tensión y

baja tensión, relación que al desacoplar el problema no es considerada, lo que hace

una línea atractiva de investigación la solución conjunta del problema de

planificación de sistemas de distribución.

• Consideración de las instalaciones de generación distribuida: La irrupción de

medios de generación que inyectan su energía directamente sobre el sistema de

distribución, hace que surjan nuevas interrogantes con respecto a como considerar

su efecto en el valor de una empresa distribuidora. Por ejemplo, se hace necesario

considerar quien se hará cargo de las instalaciones necesarias para acceder a la

generación distribuida. Instalaciones tales como equipos de control, protecciones,

refuerzo de alimentadores, entre otros, deben ser debidamente remunerados, ya sea

por el generador distribuido o por la tarifa regulada.

Otro punto, es considerar las ventajas en la regulación de tensión y disminución de

pérdidas que trae consigo la generación distribuida, con lo cual, el valor presente del

costo de las pérdidas, necesariamente es menor si es que existen proyectos de

generación distribuida en la zona de planificación, haciéndose necesario,

posiblemente, a la hora de determinar las tarifas, conocer cuales son los posibles

lugares de generación distribuida y el tipo de instalaciones necesarias, de manera de

descontar tales ahorros de la tarifa y por ende no remunerar a la empresa

distribuidora por costos inexistes. En suma, al crecer la generación distribuida, se

vuelve no despreciable su consideración en la planificación de las redes de

distribución, puesto que son éstas, las encargadas de evacuar su energía, y las que

asumen sus eventuales costos y/o ahorros.

Se debe recalcar que el problema de planificación de redes de distribución, está abierto

tanto a su solución como modelación. Día a día los sistemas crecen en tamaño y en

132

normativas, por lo que las variables involucradas también lo hacen, lo cual conlleva a que

los investigadores constantemente exploren nuevas formas de planteamiento y rutas

alternativas de solución, en virtud de lo cual los trabajos futuros propuestos y la

metodología aquí desarrollada, sólo buscan ser un aporte y no agotan, en absoluto, la

exploración a la solución del complejo problema enfrentado.

133

BIBLIOGRAFIA

Adams, R.N y Laugton, M.A. (1974). Optimal Planning of Power Network Using

Mixed Integer Programming. IEE Proceedings, 121(2), 139-147.

Akabane, K., Nara, K., Mishima, Y. y Tsuji, K. (2002, junio). Optimal Geographical

Allocation of Power Quality Control Centres by Voronoi Diagram. Documento

presentado en 14th Power Systems Computation Conference, Sevilla, España.

Anders, G.J., Vainberg, M., Horrocks, D.J., Foty, S.M. y Motlis, J. (1993). Parameters

Affecting Economic Selection of Cable Sizes. IEEE Transactions on Power Delivery,

8(4), 1661-1667.

Aoki, K., Nara, K., Satoh, T., Kitagawa, M. y Yamanaka, K. (1990). New Approximate

Optimization Method for Distribution System Planning. IEEE Transactions on Power

Systems, 5(1), 126-132.

Berg, S.V. y Tschirhart, J. (1988). Natural monopoly Regulation: Principles and

Practice. Cambridge: Cambridge University Press.

Brauner, G. y Zobel, M. (1994). Knowledge Based Planning of distribution Networks.

IEEE Transactions on Power Systems, 9(2), 942-948.

Buller, F. y Woodrow, C. (1928). Load Factor-Equivalent Hour Value Compared.

Electrical World, 92(2), 59-60.

Carvalho, P.M.S., Ferrerira, L.A.F.M, Lobo, F.G. y Barruncho, L.M.F. (2000).

Distribution Network Expansion Planning Under Uncertainty: A Hedging Algorithm in

an Evolutionary Approach. IEEE Transactions on Power Delivery, 15(1), 413-416.

Crawford, D. M. y Holt, S.B. (1975). A Mathematical Optimization Technique for

Locating and Sizing Distributions Substations, and Deriving Their Optimal Service.

IEEE Transactions on Power Apparatus and System, 94(2), 230-235.

134

Chang, H.C. y Kuo, C.C. (1994). Network Reconfiguration in Distribution Systems

Using Simulated Annealing. Electric Power System Research, 29, 227-238.

Comisión Nacional De Energía. (2003). Bases para el cálculo de las componentes de

costo del valor agregado de distribución. Santiago, Chile: Ministerio de Economía.

Da Silva, E.L., Areiza, J.M., De Oliveira, G.C. y Binato, S. (2001). Transmission

Network Expansion Planning Under a Tabu Search Approach. IEEE Transactions on

Power Systems, 16(1), 62-68.

Díaz-Dorado, E., Cidras, J. y Miguez, E. (2002). Application of Evolutionary

Algorithms for the Planning of Urban Distribution Networks of Medium Voltage. IEEE

Transactions on Power Systems, 17(3), 879-883.

Díaz-Dorado, J.P. (1999). Herramientas para la planificación de redes de baja tensión

y media tensión urbanas. Ph.D. tesis, Departamento de Ingeniería Eléctrica,

Universidad de Vigo, España.

Díaz-Dorado, E., Cidras, J. y Miguez, E. (2003). Planning of Large Rural Low voltage

Networks Using Evolution Strategies. IEEE Transactions on Power Systems, 18(4),

1594-1600.

Dorigo, M., Maniezzo, V. y Colorni, A. (1996). The Ant System: Optimization by a

Colony of Cooperating Agents. IEEE Transaction on Systems, Man and Cybernetics-

Part B: Cybernetics, 26(1), 29-41.

Ferreira, L.A.F.M., Carvalho, P.M.S., Jorge, L.A., Grave, S.N.C y Barruncho, L.M.F.

(2001). Optimal Distribution Planning by Evolutionary Computation – How to Make it

Work. Transmission and Distribution Conference and Exposition IEEE/PES, 469-475.

Fawzi, T.H., Ali, K.F. y El-Sobki, S.M. (1983). A New Planning Model for Distribution

Systems. IEEE Transactions on Power Apparatus and System, 102(9), 3010-3017.

135

Garey, M.R. y Jonson, D.S. (1979). Computers and Intractability: A Guide to the

Theory of NP- Completeness. Nueva York: Freeman.

Glover, F. y Kochenbeger, G. editors. (2003). Handbook of Metaheuristics. EE.UU.:

Kluwer Academic Publishers.

Glover, F. (1995). Tabu Search Fundamentals and Uses. Technical Report, Graduate

School of Business, University of Colorado.

Gómez, J.F, Khor, H.M., De Oliverira, P.M., Ocque, L., Yusta, J.M., Villasana R. y

Urdaneta, J. (2004). Ant colony system Algorithm for the Planning of Primary

Distribution Circuits. IEEE Transactions on Power Systems, 19(2), 996-1004.

Gonen, T. (1986). Electric Power Distribution System Engineering. Nueva York:

McGraw-Hill.

Gonen, T. y Foote, B.L. (1981). Distribution System Planning Using Mixed Integer

Programming. IEE Proceedings, 128(2), 70-79.

Gonen, T. y Ramírez-Rosado, I.J. (1986). Review of Distribution System Planning

Models: A Model for Optimal Multistage Planning. IEE Proceedings 133(7), 397-408.

Gordon, A.D. (1981). Classification. Londres: Chapman and Hall.

Goswami, S.K. (1997). Distribution system Planning using branch exchange technique.

IEEE Transactions on Power Systems. 12(2), 718-723.

Gustafson, M.W. y Baylor, J.S. (1988). The Equivalent Hours Loss Factor Revisited.

IEEE Transactions on Power Systems, 3(4), 1502-1508.

Gustafson, M.W. y Baylor, J.S. (1989). Approximating the System Loss Equation. IEEE

Transactions on Power Systems, 4(3), 850-855.

Hindi, K.S. y Brameller, A. (1977). A Design of Low Voltage Distributions Networks:

A Mathematical Programming Method. IEE Proceedings, 124(1), 54-58.

136

Hsu, Y. y Chen, J.L. (1990). Distributions Planning Using a Knowledge-based Expert

System. IEEE Transactions on Power Delivery, 5(3), 1514-1519.

Huang, Y.C., Yang, H.T. y Huang C.L. (1996). Solving the Capacitor Placement

Problem in a Radial Distribution System Using Tabu Search Approach. IEEE

Transactions on Power Systems, 11(4), 1868-1873.

Khator, S. y Leung, L. (1997). Power Distribution Planning: A Review of Models and

Issues. IEEE Transactions on Power Systems. 12(3), 1151-1159.

Lee, K.Y. y El-Sharkawi, M.A. editors. (2004). Modern Heuristic Optimization

Techniques with Applications to Power Systems. EE.UU.: IEEE Power Engineering

Society.

Lo, K.L., y Nashid, I. (1996). Interactive Expert System for Optimal Design of

Electricity Distribution Systems. IEE Proceedings, Generation, Transmission and

Distribution. 143(2), 151-156.

Mandal, S. y Pahwa, A. (2002). Optimal Selection of Conductors for Distribution

Feeders. IEEE Transactions on Power Systems. 17(1), 192-197.

Masud, E. (1974). An iterative Procedure for sizing and timing distribution substations

using optimizations techniques. IEEE PES Winter Meeting, pp.1281-1286.

Miguez, E., Cidras, J, Diaz-Dorado, E. y Garcia-Dornelas, J.L. (2002). An Improve

Branch Exchange Algorithm for Large Scale Distribution Network Planning. IEEE

Transactions on Power Systems, 17(4), 931-936.

Miranda, V., Ranito, J.V. y Proenca L.M. (1994). Genetic algorithms in Optimal

Multistage Distribution Network Planning. IEEE Transactions on Power Systems, 9(4),

1927-1923.

137

Montagnon, F.M., (1999). Planificación de la Expansión de Sistemas Eléctricos vía

algoritmos Genéticos. M.Sc. tesis, Departamento de Ingeniería Eléctrica, Pontificia

Universidad Católica de Chile.

Moreno, J., Moreno, R., Mocarquer, S. y Rudnick, H. (2006, noviembre).

Determinación de un Parque Óptimo de Transformadores para una Empresa Modelo

de Distribución. Documento presentado en III Congreso Internacional de la Región

Andina IEEE, Quito, Ecuador.

Nara, K., Satoh, T., Kuwabara, H., Aoki, K., Kitagawa M. y Ishihara, T. (1992).

Distribution System Expansion Planning by Multistage branch Exchange. IEEE

Transactions on Power Systems, 7(1), 208-214.

Nara, K., Hayashi, Y., Muto, S. y Tuchida, K. (1998). New Algorithm for Distributions

feeders Expansion Planning in Urban Area. Electric Power Systems Research, 46(3),

185-193.

Nara, K., OmI, H. y Mishima, Y. (2002, junio). Optimal Configuration of Power

Delivery System for Customized Power Supply Services. Documento presentado en 14th

Power Systems Computation Conference, Sevilla, España.

Okabe A., Boots, B. y Sugihara, K. (1992). Spatial Tessellations: Concepts and

Applications of Voronoi Diagrams. Chichester, Reino Unido.: John Wiley & Sons.

Paiva, P.C., Khor, H.M., Dominguez-Navarro, J.A., Yusta, J.M. y Urdaneta A.J. (2005).

Integral Planning of Primary – Secondary Distribution Systems Using Mixed Integer

Linear Programming. IEEE Transactions on Power Systems, 20(2), 1134-1143.

Papadimitriu, C.H. y Steiglitz, K. (1998). Combinatorial Optimization: Algorithms and

Complexity. Nueva York: Dover Publications Inc.

138

Peco, J.P. (2001). Modelo de Cobertura Geográfica de una Red de Distribución de

Energía Eléctrica. Ph.D. tesis, Departamento de Electrotecnia y Sistemas, Escuela

Técnica Superior de Ingeniería, Universidad Pontificia Comillas de Madrid, España.

Ponce De Leao, M.T. y Matos, M.A. (1995). Distribution planning with fuzzy loads.

International Transactions in Operational Research, 2(3), 287-296.

Ponnavaikko, M., Rao, K. y Venkata S.S. (1987). Distribution System Planning through

a Quadratic Mixed Integer Programming Approach. IEEE Transactions on Power

Delivery, 2(4), 1157-1163.

Ramírez-Rosado, I.J. y Gonen, T. (1991). Pseudo-dynamic Planning for Expansion of

Power Distribution systems. IEEE Transactions on Power Systems, 6(1), 245-254.

Ramírez-Rosado, I.J. y Bernal-Agustín, J. (1998). Genetic Algorithms Applied to the

Design of Large Power Distribution Systems. IEEE Transactions on Power Systems,

13(2), 696-703.

Ramírez-Rosado, I.J. y Bernal-Agustín, J. (2001). Reliability and Cost Optimization for

Distribution Network Expansion Using and Evolutionary Algorithm. IEEE Transactions

on Power Systems, 16(1), 111-118.

Ramírez-Rosado, I.J. y Domínguez-Navarro, J.A. (2004). Possibilistic Model Based on

Fuzzy Sets for the Multiobjetive Optimal planning of electric Power Distribution

Networks. IEEE Transactions on Power Systems, 19(4), 1801-1810.

Ramírez-Rosado, I.J. y Domínguez-Navarro, J.A. (2006). New Multiobjective Tabu

Search algorithm for Fuzzy Optimal Planning of Distribution Systems. IEEE

Transactions on Power Systems, 21(1), 224-233.

Rudnick, H., Sanhueza, R. y Harnisch, I. (1997). Reconfiguration of Electric

Distribution Systems. Revista Facultad de Ingeniería, Universidad de Tarapacá, Chile,

4, 41-48.

139

Sanhueza, R. (1994). Planificación de la Expansión de un Sistema de Distribución vía

Algoritmo de Descomposición de Benders. M.Sc. tesis, Departamento de Ingeniería

Eléctrica, Pontificia Universidad Católica de Chile, Chile.

Sanhueza, R., Rudnick, H. (1995, noviembre). Un algoritmo de descomposición para la

planificación multi años de sistemas eléctricos de distribución. Documento presentado

en Congreso Chileno de Ingeniería Eléctrica, Punta Arenas, Chile.

Singh, K., Philpott, A. y Wood, K. (2005). Dantzig-Wolfe Decomposition for Solving

Multistage Stochastic Capacity Planning Problems. University of Auckland, New

Zealand.

Systep e Inecon. (2004). Estudio para el Cálculo de las Componentes de Costo del

Valor Agregado de Distribución (VAD), Área Típica 1: Chilectra. Santiago, Chile:

Autor.

Synex, Mercados Energéticos y Jadresic Consulting. (2004). Estudio de Costos de

Componentes del Valor Agregado de Distribución (VAD), Área 1. Santiago, Chile:

Autor.

Temraz, H.K. y Salama, M.M.A. (2002). A Planning Model for Sitting, Sizing and

Timing Distribution Substations and Defining the Associate Service Area. Electric

Power Systems Research, 62(2), 145-151.

Tram, H.N. y Wall, L. (1988). Optimal Conductor Selection in Planning Radial

Distribution Systems. IEEE Transactions on Power Systems, 3(1), 200-206.

Thompson, G.L. y Wall, D.L. (1981). A Branch and Bound Model for Choosing

Optimal substation Locations. IEEE Transactions on Power Apparatus and System,

100(5), 2683-2687.

140

Vaziri, M., Tomosovic, K., Bose, A. y Gonen, T. (2001). Distribution Expansion

Problem: Formulation and Practicality for a Multistage Globally Optimal Solution. PES

Winter Meeting, 3, 1461-1466.

Voronoi, G.M. (1908). Nouvelles applications des parametres continus a la theorie des

formes quadratiques. deuxieme Memoire: Recherches sur les parallelloedres primitifs.

J. Reine Angew. Math., 134, 198-287.

Wall, D., Thomson, G. y Northcote-Green, J. (1979). An optimization Model for

Planning Radial Distributions Networks. IEEE Transactions on Power Apparatus and

Systems, 98(3), 1061-1065.

Wen, F. y Chang, C.S. (1997). Transmission Network Optimal Planning Using the Tabu

Search Method. Electric Power System Research, 42, 153-163.

Willis, H., Powell, R. y Vismor, T. (1985). A Method for Automatically Assesing Load

Transfer Cost in Substation Optimization Studies. IEEE Transactions on Power

Apparatus and Systems, 104(10), 2771-2778.

Willis, H., Tram, H. y Powell, R. (1987). Substation Sitting and Capacity Selection

Based on Diversity Maximization. IEEE Transactions on Power Systems, 2(3), 692-

699.

Yap C.K. (1987). Algorithmic motion planning. En Schwartz y Yap. (Ed.), Advances in

Robotics 1: Algorithmic and Geometric Aspects of Robotics (pp. 95-143). New Jersey,

EE.UU.: Lawrence Erlbaum Associates.

Youssef, H.K. y Hackam, R. (1988). Dynamic solution of Distribution Planning in

Intermediate Time Range. IEEE Transactions on Power Delivery, 3(1), 341-348.

141

A N E X O S

142

ANEXO A: COMPLEJIDAD ALGORITMICA

Para comprender la complejidad algorítmica y en particular lo relacionado con el tipo de

problemas NP-completos, a los que se hace referencia en la presente tesis, se deben tener

presentes algunas definiciones básicas43.

Un algoritmo es una secuencia ordenada de pasos (conjunto de reglas) que conduce a la

resolución de cualquier instancia de un problema específico. Esta secuencia debe ser

precisa, es decir el algoritmo debe expresarse sin ambigüedad, debe ser determinista, o sea

todo algoritmo debe responder del mismo modo ante las mismas condiciones, y finalmente

debe ser finita, esto es, debe finalizar en un número finito de pasos.

Otro concepto que se debe tener presente es el de complejidad algorítmica, el cual se refiere

a los recursos computacionales, que son necesarios para ejecutar un algoritmo en función

de los datos de entrada del problema, específicamente la complejidad se define como el

número de operaciones elementales requeridas en función de la entrada, para resolver el

problema en cuestión. Muchas veces encontrar a cabalidad el número de operaciones

necesarias es un proceso complejo y que no entrega demasiada información, ello dado a

que el algoritmo puede tener un determinado escenario en que no se utilicen todos sus

pasos (mejor caso) y otro en que todas las etapas sean utilizadas (peor caso), por lo cual se

suele determinar la cota superior de la complejidad de un algoritmo O(n), denominado

orden de crecimiento, como el número de operaciones requeridas en el peor de los casos

para solucionar un problema cuyo tamaño de datos en la entrada es n.

En términos matemáticos, sean F y G funciones definidas en el conjunto de los números

naturales, entonces F, G: N � N, se establece que el orden de crecimiento de G es menor o

igual que el de F, lo que escribe como G=O(F), si existe una constante k > 0, tal que G(n) ≤

k F(n) para todo n perteneciente a N (con n suficientemente grande, dado que no importa lo

que suceda para valores pequeños). Por ejemplo:

2 2( ) 45 7 log( ) 1 ( )G n n n n n G O n= ⋅ + ⋅ + ⋅ + ⇒ = (A.1)

43 Para más información ver Papadimitriu y Steiglitz (1998)

143

La jerarquía de ordenes en forma creciente es O(1) ⊂ O(log(n)) ⊂ O(n) ⊂ O(nlog(n))

⊂ O(n2) ⊂ O(n3) ⊂ O(2n) ⊂ O(n!) ⊂ O(nn), de manera aclaratoria, se debe tener en

cuenta que O(F) no es una única función sino que es un conjunto de funciones, que acotan

superiormente la complejidad del algoritmo. Con esta definición de complejidad es posible

saber cuando un algoritmo F es más eficiente que otro G para resolver un mismo problema,

si F=O(G) pero G ≠ O(F) se dice que F es más eficiente que G.

El estudio de la complejidad algorítmica ha llevado a los investigadores a clasificar los

algoritmos en los siguientes grupos:

• Problemas de clase P (Polynomial time): Son aquellos problemas para los cuales

existe un algoritmo que se encuentra acotado en forma polinomial, es decir que en

el peor de los casos existe una función polinomial con el tamaño n de las entradas,

que limita superiormente la ejecución del algoritmo, del tipo O(nk). Ejemplos

clásicos de este tipo de problemas son el problema del camino mínimo, que consiste

en encontrar el menor camino desde un vértice origen al resto de los vértices, y el

problema del ciclo de euler, que consiste en encontrar un ciclo que pase por cada

arco de un grafo sólo una vez.

• Problemas de clase NP (Nondeterministic Polynomial time): Un problema es NP si

y sólo si puede resolverse mediante un algoritmo no determinístico en tiempo

polinomial, entendiendo como algoritmo no determinístico aquel que escoge en

forma arbitraria un determinado curso de acción cada vez que se le presentan una

serie de alternativas posibles. Es decir, que los problemas de clase NP son

verificables en tiempo polinomial, ellos es, que dada una solución factible para el

problema, encontrada luego de una secuencia de elecciones, se puede verificar que

es correcta en un tiempo polinomial del tamaño de la entrada, por tanto presenta una

etapa de elección dominada por cierta arbitrariedad y una etapa de comprobación.

La clase P es un subconjunto de la clase NP ya que se podría construir un algoritmo

que resolviera los problemas de la clase P, con las mismas dos etapas que se usan en

los problemas de la clase NP, sin embargo, el problema es que existen soluciones

acotadas polinomialmente para todos los problemas P, pero no para todos los de la

144

clase NP. Para que ambas clases fuesen iguales todos los problemas NP deberían ser

del tipo O(nk), situación que a la fecha es un problema abierto.

• Problemas de clase NP-Completos: Un problema es NP-completo si todos los

problemas de la clase NP pueden reducirse a él, representan los problemas más

difíciles de la clase NP y posiblemente no forman parte de los problemas de

complejidad P (afirmación que aún no ha sido probada ni desmentida), dado que de

existir una solución polinómica para un problema NP-completo entonces todos los

problemas de NP también la tendrían. Ejemplos de este tipo de problemas son, el

problema del camino máximo, dado dos vértices de un grafo encontrar el camino de

mayor distancia que los une, y el problema del ciclo hamiltoniano, que consiste en

encontrar un ciclo simple que contiene a cada vértice del grafo.

145

ANEXO B: DESCRIPCION DE META-HEURISTICAS

Para entender que es una meta-heurística, el primer paso es comprender el término

heurística, vocablo que etimológicamente proviene del griego heuriskein que significa

encontrar o descubrir. En la actualidad dicho término se comenzó a utilizar con los inicios

de la inteligencia artificial, específicamente representan mecanismos sencillos que permiten

resolver problemas difíciles (NP, NP-completos), de manera relativamente fácil y rápida,

encontrando una buena solución para ellos, pero sin garantizar la obtención de una solución

óptima. Estas técnicas se pueden clasificar en heurísticas de:

• Construcción: algoritmos que van agregando componentes a una solución parcial,

hasta que se logra obtener una solución que cumple todas las restricciones y que no

es posible mejorar.

• Mejora: algoritmos que parten de una solución inicial factible, y buscan en la

vecindad de la solución, algún cambio posible, de manera que la solución actual

mejora, los cambios se realizan hasta que se cumple un determinado número de

iteraciones o cuando ya no se producen mejorías. En este tipo de algoritmos,

mención especial, merece el intercambio de ramas (Branch – Exchange) en la

planificación de sistemas de distribución, en particular, en lo referente a la

formación de redes radiales, el que consiste en la adición de un tramo de red, de

manera que se forme un ciclo en el trazado, para posteriormente quitar la mejor

rama que elimine tal ciclo.

• Descomposición: algoritmos que dividen el problemas principal en subproblemas de

tamaño y dificultad menor, que luego de resolverlos al ir uniéndolos permiten tener

una solución al problema mayor, la técnica más conocida de descomposición es la

heurística divide y vencerás.

• Reducción: algoritmos que consisten en identificar ciertas condiciones que debe

poseer la solución final, de forma de acotar el espacio de búsqueda, haciendo más

fácil el proceso de optimización.

146

Otro mecanismo heurístico que no se ciñe necesariamente a la clasificación anterior, y que

en la mayoría de las oportunidades actúa como complemento de algún otro procedimiento,

es el denominado sistema experto, el cual consiste en emular el conocimiento que tienen los

expertos humanos frente a un determinado problema, conocimiento que es representado por

un conjunto de reglas del tipo IF-THEN, las cuales son aplicadas por el computador para

resolver el problema en cuestión.

La característica de los heurísticos anteriores, es que su utilización e implementación va a

depender fuertemente del problema que buscan resolver, lo cual constituye una falencia,

dado el esfuerzo adicional que ello significa, no obstante en el último tiempo, han aparecido

algoritmos heurísticos que, en términos generales, son genéricos e independientes del

problema de optimización que intentan resolver, a este tipo de metodologías se les conoce

como meta-heurísticas. En particular Glover et al. (2003) las define como:

“Las meta-heurísticas son métodos que integran de diversas maneras, procedimientos de mejora local y estrategias de alto nivel para crear un proceso capaz de escapar de óptimos locales y realizar una búsqueda robusta del espacio de búsqueda. En su evolución, estos métodos han incorporado diferentes estrategias para evitar la convergencia a óptimos locales, especialmente en espacios de búsqueda complejos.” Siendo sus principales ventajas, la versatilidad, esto es que son necesarias pequeñas

modificaciones para adaptar las meta-heurísticas a la resolución de distintos problemas, y la

aplicabilidad eficaz, es decir, que se puede aplicar a problemas difíciles encontrando buenas

soluciones en tiempos razonables. Su principal desventaja, es que no se puede conocer la

calidad de la solución encontrada, por tanto, no se puede saber que tan cerca se encuentra el

resultado encontrado del óptimo global del problema.

A continuación se explicarán brevemente las características fundamentales de las meta-

heurísticas que han sido citadas a lo largo de este trabajo, de forma de aclarar los aspectos

relevantes de los algoritmos genéticos, las colonias de hormiga, el temple simulado

(Simulated Annealing) y la búsqueda tabú.

147

B.1 Algoritmos Genéticos

Esta meta-heurística se basa en la teoría de la evolución de las especies, en la que se

sostiene que con el paso de las generaciones, sólo los genes de los individuos mejor

adaptados permanecen en el tiempo, mientras que la información de aquellos individuos

que no se pudieron adaptar desaparece junto con ellos. De esta manera, las especies logran

adaptarse a los cambios del ambiente y producto de la reproducción, sobrevivir a través de

los años.

Tomando en cuenta esta optimización natural de las especies, los investigadores han

aplicado el mismo procedimiento para resolver diversos problemas de optimización, para

ello, se debe crear una población inicial, compuesta por un número determinado de

individuos, donde cada uno de ellos representa una solución al problema, cada individuo

(solución factible) se encuentra codificado en un vector de unos y ceros (emulando la

cadena de ADN), la bondad de una solución está dada por una función denominada fitness,

que típicamente representa la evaluación del individuo en la función objetivo a optimizar, o

en el inverso de dicha función. Luego de esto, para que exista modificación al material

genético, es decir para que aparezca una nueva población de soluciones y se siga el proceso

de evolución natural, se realizan lo siguientes procedimientos:

• Selección: este operador determina que individuos forman parte de una nueva

población, dicha elección se realiza, la mayoría de las veces en forma elitista,

considerando a los n mejores individuos de una población, de acuerdo a su función

de fitness. Otra forma de selección es asignando una determinada probabilidad de

selección en función del fitness de cada individuo, en la selección proporcional, la

probabilidad de escoger a un individuo para que forme parte de la nueva generación

es directamente proporcional a su valor de fitness. También se realiza selección por

torneo, en donde se escogen aleatoriamente dos individuos de la población, y se

deja para la nueva población el de mejor fitness, esta situación se repite hasta que se

seleccionan los n individuos de la nueva generación.

• Cruce: este operador emula el proceso reproductivo de las especies, es decir, recoge

la información de dos individuos para generar uno nuevo, por tanto se crea una

148

nueva solución a partir de dos soluciones ya existentes. Es importante mencionar,

que no todos los individuos de una generación se cruzan, sino que como parámetro

de control se establece una probabilidad de cruce, la que típicamente es superior a

0,7. Existen varias formas de realizar este procedimiento, por ejemplo en el cruce

de punto simple, se escoge aleatoriamente una posición del vector que describe a un

individuo. Sea X la posición y N el largo del vector, el hijo 1 estará compuesto por

la información que va desde la posición uno a la posición X del padre 1 más la

información del padre 2 que va desde la posición X hasta la posición N,

análogamente el hijo 2 tendrá X información del padre 2 y N-X información del

padre 1.

Padre 1: 1 0 0 1 1 0 1 1 Padre 2: 0 1 1 1 1 1 0 0

Si X es igual a 3, entonces:

Hijo 1: 1 0 0 1 1 1 0 0 Hijo 2: 0 1 1 1 1 0 1 1

Muy parecido al anterior, es el cruce de multi-punto, en que se eligen más

posiciones de cruce, y por tanto los hijos tendrán más de un tramo de información

de cada padre. Otro cruce importante, es el cruce uniforme, en que cada variable

que conforma a los nuevos individuos se seleccionada aleatoriamente y con

igualdad de probabilidad desde los padres.

• Mutación: este operador trata de emular los fenómenos aleatorios que se producen

en el proceso de evolución de las especies, modificando la estructura genética de los

individuos en forma aleatoria, cuyo objetivo es crear diversidad en la población, es

decir, en el caso de la solución de un problema de optimización ayuda a escapar de

óptimos locales. En términos prácticos lo que se realiza es cambiar el valor de uno

de los bit del individuo, es decir, si la posición escogida tiene un valor 1 se cambia

por un valor 0, no todos los elementos de un individuo son alterados, el parámetro

controlador es la probabilidad de mutación, la cual al igual que en la naturaleza es

pequeña, teniendo un valor del orden de 0,001 en la casi totalidad de los problemas

resueltos con esta metodología.

149

Con la aplicación sucesiva de los procedimientos antes señalados se logra emular el

proceso de evolución de las especies, produciendo sucesivamente nuevas generaciones que

toman lo mejor de la generación anterior, el proceso termina cuando se cumple un número

máximo de iteraciones o cuando el fitness de los individuos ya no mejora.

B.2 Temple Simulado (Simulated Annealing)

Esta meta-heurística se inspira en el proceso físico de templar un metal, esto es reblandecer

un metal a una temperatura elevada para luego enfriarlo lentamente, de manera de lograr

una cristalización óptima. Para comprender la analogía en cuestión, se debe tener en

consideración que en un material cualquiera, todas las partículas que lo componen se

encuentran con diferentes niveles de energía de acuerdo a una cierta distribución

estadística, el menor de dichos niveles de energía se denomina estado fundamental y se

presenta cuando la temperatura es de 0º K (-273º C). Así, la modelación teórica del proceso,

establece que si un metal se encuentra en un estado Si con un nivel de energía Ei, al

producirse una pequeña perturbación al estado original, y generarse un nivel de energía Ej,

el nuevo estado será Sj si la diferencia entre Ej-Ei es menor o igual a cero (disminución de la

energía producto de la perturbación), en caso que esto no suceda, el sólido pasará al estado

Sj con probabilidad ( ){ }j iE E k T

e− − ⋅

, donde k es la constante de Boltzman y T es la

temperatura del sólido, es decir, durante el proceso de enfriamiento el sólido podrá pasar a

estados superiores de energía con mayor probabilidad en la medida que la temperatura es

alta, a medida que la temperatura decrece, esta probabilidad es menor, llegando un

momento en que los saltos sólo se producen hacia escenarios de menor energía. Por tanto, la

probabilidad de que el sólido se encuentre en el estado Si con una energía Ei es:

1( )i

E jk T

j

E

k Ti

e

P X S e−

⋅

−

⋅= = ⋅∑

(B.1)

Teniendo en consideración lo anterior, se puede entender la analogía entre el proceso de

recocido o temple y la resolución de un problema de optimización combinatorial, señalando

las siguientes asociaciones, el estado Si representa una solución factible del problema, Ei es

150

el valor de la función objetivo evaluada en la solución, y la temperatura representa la

variable de control, ella maneja la probabilidad de aceptación de una solución que empeora

localmente la solución encontrada hasta la fecha. Así, el algoritmo simplificado de esta

meta-heurística es:

1. Se comienza el algoritmo con una solución factible S=S1. Se inicializan los parámetros

de control, esto es la temperatura inicial T = To y No, que representa el número de

configuraciones que se probarán a temperatura To.

2. Para cada configuración de 1 a No

a. Se realiza un cambio a la solución actual, y se evalúa la función objetivo,

obteniéndose Ej.

b. Si la solución mejora, entonces la solución actual es la solución asociada a

Ej, es decir S=Sj.

c. Si la solución empeora, entonces la solución actual es la solución asociada a

Ej, es decir S=Sj. Si y solo si se cumple que ( ){ }j iE E k T

e− − ⋅

> RANDOM (0,1),

de lo contrario la solución actual se mantiene S=S.

d. Se vuelve a 2 hasta que se realizan los No cambios.

3. Se determina si se cumple el criterio de parada. Sí se cumple, se finaliza el algoritmo,

sino se sigue con el paso 4. El criterio de parada suele ser un número determinado de

iteraciones, o un cierto número de iteraciones en que el valor de la función objetivo no

mejora.

4. Se determina To y No para la siguiente iteración y se vuelve al paso 2

Se observa que la dificultad principal, está en emular correctamente el proceso de

enfriamiento del metal, es decir en escoger una temperatura inicial y variarla en la medida

que avanza el proceso de optimización, ya que es dicha temperatura la que controla la

probabilidad de permitir empeoramientos en la solución, es decir la posibilidad de escapar

de mínimos locales, esta temperatura va disminuyendo, de manera de expandir en un

comienzo el espacio de búsqueda, mayor probabilidad de aceptar cambios a mayor

temperatura, y de refinar la solución al final del proceso, a menor temperatura existe menor

151

probabilidad de permitir cambios que empeoran la solución. Los parámetros principales del

proceso de enfriamiento y que se deben determinar para poder realizar el algoritmo son, la

temperatura inicial To, la temperatura final Tf, el número de transiciones Nk a la temperatura

Tk, y la tasa de variación de la temperatura Tk+1=G(Tk) Tk. Si bien existen, en la literatura,

metodologías aproximadas para cada uno de estos parámetros, se debe señalar, que su

correcta selección dependerá del problema en cuestión, por lo que una adecuada

sintonización de tales parámetros es un problema complicado, que la mayoría de las veces

se resuelve a prueba y error, siendo ésta, la principal desventaja del Temple Simulado, dada

su alta sensibilidad a la elección de parámetros.

B.3 Colonias de Hormigas

Este enfoque de solución de problemas de optimización pertenece a la corriente

denominada de inteligencia colectiva. La idea básica es que un sistema compuesto de una

multitud de agentes que siguen reglas simples, al actuar en forma cooperativa, pueden

lograr objetivos complejos, situación que se visualiza cabalmente en las colonias de

hormigas, en particular en su proceso de recolección de comida, donde ellas parten de

manera desordenada (aleatoria) en busca de alimento, y con el paso del tiempo forman

rutas óptimas para llegar a ellos. Para entender tal comportamiento, se debe tener presente

que las hormigas dejan un rastro químico, liberación de feromonas, que puede ser detectado

por el resto de las hormigas, así la elección de un determinado camino se hace en función

de la cantidad de feromona que puede percibir en la ruta, es decir se escogerá con mayor

probabilidad aquel camino que contenga una mayor concentración de feromonas, de no

existir feromona en la rutas, la primera elección se realiza de manera aleatoria, con lo cual

los caminos más prometedores (menores distancias) entre el hormiguero y la fuente de

alimento tendrán mayor concentración de feromonas, ello dado a que los caminos más

cortos son recorridos más rápidamente y por tanto el retorno de dicha hormiga comienza

antes, de esta forma el camino más corto tendrá un nivel de feromona ligeramente mayor al

resto de las rutas, con lo que tal camino es elegido con mayor probabilidad por las demás

hormigas de la colonia, este proceso también es ayudado por el ambiente, dado que la

feromona se evapora con el paso del tiempo, con ello la feromona de los caminos menos

152

prometedores disminuye progresivamente, porque son visitados cada vez por menos

hormigas. De esta forma, a la larga se consigue que toda la colonia se desplace por la ruta

de menor distancia para la recolección del alimento.

Figura B.1: Comportamiento de las hormigas

Su aplicación en optimización se realiza en problemas de grafos, en ellos cada hormiga

artificial tiene la misión de construir una solución del problema, cada adición a la solución

parcial construida, se realiza a través de una regla de decisión estocástica, que incluye

información heurística e información del resto de las hormigas. Luego de la construcción o

durante el proceso, las hormigas evalúan la solución y depositan feromona en las

conexiones utilizadas, que servirá de información para el resto de las hormigas artificiales.

Además se realiza la evaporación, es decir la eliminación de feromona en cada iteración del

problema, de manera de favorecer la exploración en nuevas zonas de búsqueda. Se debe

señalar también, que en el caso de las colonias artificiales de hormigas se aplican

decisiones globales, que permiten extraer información de la colonia completa, y tomar

medidas que favorezcan la resolución del problema, así se puede incluir la adición de

feromona adicional en el mejor camino encontrado en cada iteración.

El pseudo-código de esta meta-heurística es el siguiente:

1. Establecer la feromona inicial();

153

2. Mientras (el criterio de término no esté satisfecho)

a. Crear las hormigas de una colonia();

b. Para (cada Hormiga de la colonia);

{Mover hormiga ( )} hasta completar ruta;

Mover hormiga ( )

Para (todo el vecindario factible)

Calcular probabilidades de movimiento;

Fin para

Nodo seleccionado = seleccionar el movimiento ( )

Fin para

c. Actualizar feromona

d. Destruir hormigas

Fin mientras

3. Si se cumple criterio, entonces terminar. Típicamente el criterio de parada esta dado

por el número de colonias a evaluar, esto es por el número de veces que se repite el

paso 2.

Donde Pij es la probabilidad de pasar del nodo i al nodo j, τij es la feromona existente entre

el nodo i y el nodo j, ηij es la información heurística entre el nodo i y el j, esta información

típicamente es el inverso de la distancia (no necesariamente distancia euclidiana, sino que

una cierta métrica en el espacio de las propiedades) entre el nodo i y el nodo j, Nik es el

conjunto de nodos alcanzables desde el nodo i y que aún no han sido visitados por la

hormiga k. En tanto α y β constituyen parámetros que establecen un equilibrio entre la

importancia de la información heurística y de la información de la memoria dada por la

cantidad de feromona. Se debe señalar que la selección del movimiento y la actualización

de la feromona, dependerá de la estrategia escogida, así por ejemplo se puede incluir

feromona sólo en el mejor camino realizado por una hormiga de una colonia, o se puede

actualizar entre cada hormiga de una misma colonia, decisiones que dependerán del

planificador. Al igual que en la mayoría de los procedimientos heurísticos, se requiere de la

( ) [ ]( ) [ ]

ki

Nlilil

ijijij NjsitP

ki

∈⋅

⋅=∑∈

,)(βα

βα

ητ

ητ

154

toma de decisión sobre un cierto número de parámetros, de los que finalmente dependerá la

calidad de la solución encontrada.44

B.4 Búsqueda Tabú

Dada la importancia de esta meta-heurística en el desarrollo de la presente tesis, las

características y aspectos fundamentales de su algoritmo, así como su ejecución y

principales supuestos se encuentran descritos en el cuerpo de este trabajo (ver 5.2.3

Resolución mediante búsqueda tabú).

44 Para más información consultar Dorigo et al (1996)

155

ANEXO C: ANALISIS DE CLUSTER

El análisis de cluster, también denominado análisis de conglomerados, es una técnica

estadística multivariante, cuyo objetivo es dividir un conjunto de elementos en grupos, de

manera que las características de los elementos pertenecientes a un mismo grupo sean muy

similares entre sí, situación denominada cohesión interna, y las características de elementos

pertenecientes a distintos grupos sean disímiles, situación conocida como aislamiento

externo del grupo. Para conocer tal similitud, se hace necesaria la existencia de medidas

que indiquen el grado de parecido o diferencia que existen entre dos elementos que se

quieren agrupar, estas medidas se pueden clasificar en medidas de proximidad y en medidas

de distancia, las primeras miden el grado de parecido entre dos objetos, de tal forma que

entre mayor sea su valor, mayor probabilidad existe que el método de cluster empleado los

clasifique en el mismo grupo, ejemplo de estas son los coeficientes de congruencia, de

correlación, de Jacard, de acuerdo simple, entre otros, en tanto que los segundos, miden el

grado de diferencia entre dos elementos de la muestra, por tanto entre mayor sea la medida,

menor es la probabilidad que la metodología los clasifique juntos, ejemplos de ésta son la

distancia euclidiana, la distancia métrica de Chebychev, la distancia manhatan, por

mencionar algunas (Gordon, 1981). Es importante señalar además, que las técnicas de

cluster han sido abordadas en dos grandes grupos:

C.1 Métodos Jerárquicos

Representan métodos sucesivos, en que durante una etapa, sólo uno de los elementos del

espacio a clasificar cambia de grupo. El algoritmo simplificado, suponiendo n objetos a

clasificar, es el siguiente:

1. Primero se calculan las distancias entre todos los pares de objeto, lo que equivale a

decir que se comienza el algoritmo con la existencia de n cluster {C1, ...,CN}.

2. Se buscan los dos cluster más cercano (de acuerdo a la medida de distancia

empleada), se unen y pasan a formar un único cluster.

3. Se repite el paso dos hasta que no quedan pares de comparación

156

Existen varios tipos de enlaces para realizar las uniones entre dos cluster, las más usadas

son:

• Enlace simple: considera la distancia entre los elementos más cercanos de ambos

cluster.

• Enlace promedio: considera la distancia promedio entre los elementos de ambos

cluster a combinar.

• Enlace completo: considera la distancia entre los elementos más alejados de ambos

cluster.

Este método, si bien realiza la clasificación completa, no indica el número de cluster

localizados, sino que dada la partición realizada, es el tomador de decisión, quién

selecciona el número de cluster adecuado a su interés. No obstante, cabe mencionar un

criterio bastante utilizado en esta toma de decisión, criterio de Mojena, basado en la

distancia a la que se forma cada grupo, denominada distancia de aglomeración,

identificando aquellas iteraciones, en que tales distancias presentan grandes variaciones,

matemáticamente se tiene:

j Xd X k σ> + ⋅ (C.1)

• dj : representa la distancia de aglomeración j.

• X : representa la media de las distancias de aglomeración.

• Xσ : representa la desviación estándar de las distancias de aglomeración.

• k : multiplicador, típicamente entre 2,5 y 3,5.

C.2 Métodos de Partición

Estos métodos clasifican al conjunto de datos en un número prefijado de grupos, de manera

que parten en una solución factible e iteran de acuerdo al algún criterio de búsqueda local.

En la presente investigación se utiliza, en particular, un tipo de técnica denominada k-

meas, cuyo algoritmo simplificado, considerando n elementos a clasificar es:

157

1. Elección de k datos de los n a agrupar, estos constituyen los k centroides iniciales.

Es decir, un dato de entrada al algoritmo es el número de grupos a ubicar k.

2. Se calculan las distancias de los datos a cada uno de los centroides. Cada uno de los

datos es asignado al centroide más cercano, formándose k grupos

3. Para cada uno de los grupos se calcula el nuevo centroide como el valor medio de

todos los datos asignados a él.

4. Se repite el proceso 2 y 3 hasta que se satisface algún criterio de convergencia.

Se debe tener presente, que la distancia no representa necesariamente distancia espacial,

entendida como coordenadas (x,y) en el plano cartesiano de la geometría analítica, sino que

representa la distancia de los datos en el espacio de las propiedades y características de los

mismos. Es en este entendido, que la distancia más empleada a la hora de realizar k-means

es la distancia euclidiana, dada por:

2( , ) ( ) ( )T T

X X X Xd x x x xµ µ µ µ= − = − ⋅ − (C.2)

• d : distancia euclidiana.

• x : vector de posiciones de los datos

• Xµ : valor medio de los datos (centroide).

El criterio de parada, esta dado por el mínimo entre un número máximo de iteraciones y la

variación de la distorsión entre dos iteraciones sucesivas. El número máximo de iteraciones

es un dato de entrada al algoritmo y dependerá de la convergencia presentada en el

problema a resolver. En tanto, que la distorsión es la suma de todas las distancias a su

respectivo centroide.

2

1 i

k

ii x C

D x µ= ∈

= −∑∑ (C.3)

Donde k es el número de cluster, Ci es el cluster i-ésimo, y el criterio de parada será

( 1) ( )D n D n+ ≤ (C.4)

158

Este algoritmo presenta una mayor convergencia que el método jerárquico, y es utilizado en

problemas en que el número de datos a clasificar es elevado, siendo ocupado en temas tan

variados como la biología, la sociología, la física, entre otros (Gordon, 1981), teniendo

como gran desventaja la elección a priori del número de agrupaciones a realizar.

159

ANEXO D: COSTO DE CONDUCTORES Y TRANSFORMADORES

Los costos usados tanto de transformadores como de conductores corresponden a valores a

diciembre del 2003, de manera que los resultados obtenidos puedan ser cotejados con la

última fijación tarifaria de distribución (VAD 2004-2008), no obstante constituyen entradas

al modelo y por tanto pueden ser modificados sin inconvenientes, teniendo sólo un carácter

referencial.

Tabla D.1: Listado de transformadores, capacidades y precios

Capacidad KVA Precio ($)

Costo de

Instalación

($)

Costo Total

($)

5 420.264 57.987 478.251

10 631.350 76.141 707.491

15 751.673 86.488 838.161

30 941.840 102.843 1.044.683

45 1.145.144 120.327 1.265.471

75 1.396.163 141.914 1.538.077

100 1.564.892 178.793 1.743.685

150 1.912.722 208.706 2.121.428

300 2.921.638 295.473 3.217.111

500 3.999.705 388.187 4.387.892

750 11.697.880 1.097.123 12.795.003

1000 13.583.330 1.272.286 14.855.616

Tabla D.2: Listado de conductores de cobre desnudo

Sección (mm2) Precio ($/km)Resistencia

(ohm/km)Capacidad (A)

16 259.827 1,12 121

25 416.532 0,732 168

35 527.742 0,523 205

70 1.118.166 0,261 325

12 1.892.592 0,152 462

160

Tabla D.3: Listado de conductores de aluminio desnudo

Sección (mm2) Precio ($/km)Resistencia

(ohm/km)Capacidad (A)

70 492.003 0,479 260

120 658.161 0,279 370

240 1.496.998 0,14 538

300 1.874.000 0,112 625

Tabla D.4: Listado de conductores de aluminio preensamblado

Sección (mm2) Precio ($/km)Resistencia

(ohm/km)Capacidad (A)

25 262.001 1,166 260

35 331.750 0,829 370

50 404.400 0,583 538

70 695.201 0,415 625

161

ANEXO E: APLICACION PROCESO DE MICRO-OPTIMIZACION

En este anexo se presenta un ejemplo detallado del proceso de micro-optimización aplicado

a una mini-zona, en este caso el número de islas de la mini-zona es uno, por lo que la

topología de la isla es equivalente a la topología de la mini-zona.

1. Datos de entrada: posición y consumo de los clientes.

3.955 3.96 3.965 3.97 3.975 3.98 3.985 3.99 3.995

x 104

8900

8950

9000

9050

9100

9150

9200

9250

9300

9350

9400

Figura E.1: Ubicación de consumos en una mini-zona.

2. Etapa Previa:

2.1 Trazado de Calles

2.2 Asignación de cada cliente a su calle más cercana

[m]

[m]

162

3.94 3.95 3.96 3.97 3.98 3.99 4 4.01

x 104

8800

8900

9000

9100

9200

9300

9400

9500

Figura E.2: Trazado de calles y asignación de consumos

3. Proceso iterativo

3.1 Se comienza con un transformador en el centro de carga, se calcula el

transformador óptimo, el trazado y la red óptima, incluyendo las pérdidas,

para dicha ubicación, obteniéndose un costo total de $ 29.135.137

[m]

[m]

163

3.94 3.95 3.96 3.97 3.98 3.99 4 4.01

x 104

8900

9000

9100

9200

9300

9400

Figura E.3: Ubicación y red inicial

3.2 Se realiza el mismo procedimiento pero está vez ubicando dos

transformadores mediante k-means. De donde se obtiene un costo total de

$ 22.571.818

3.3 Se repite 3.2 agregando en cada iteración un nuevo transformador hasta que el

costo total de la iteración actual sea mayor que el de la iteración anterior. Para

el caso de tres ubicaciones se tiene un costo total de $ 20.504.002, en tanto

para el caso de cuatro ubicaciones su costo total es de $ 21.049.672. Notando

entonces que en el caso de tres localizaciones se produce un mínimo (el costo

tanto en la iteración anterior como en la posterior es mayor).

[m]

[m]

164

3.94 3.95 3.96 3.97 3.98 3.99 4 4.01

x 104

8900

9000

9100

9200

9300

9400

Figura E.4: Ubicación y red del primer mínimo encontrado

3.4 Si se encuentra un mínimo, se realizan B búsquedas adicionales, es decir se

repite 3.3 durante B iteraciones más, en este ejemplo se utiliza un valor de B

igual a tres, por lo tanto se realizan tres iteraciones posteriores a la iteración

cuatro, con lo que finalmente se prueban siete localizaciones para los

transformadores. El costo total en las etapas de búsqueda es $ 21.850.121, $

22.054.774 y $ 24.393.131 para las iteraciones cinco, seis y siete,

respectivamente. Notándose el comportamiento creciente de la función

objetivo luego de haber encontrado el mínimo (Figura E.6).

[m]

[m]

165

3.94 3.95 3.96 3.97 3.98 3.99 4 4.01

x 104

8900

9000

9100

9200

9300

9400

Figura E.5: Ubicación y red en la última iteración

4. Elección del óptimo: Se escoge la red que tenga menor costo total, se debe señalar

que en términos generales el primer mínimo que se encuentra es el mínimo global

de la función costo total, tal y como se muestra en este ejemplo (ver Tabla E.1 y

Figura E.6)

Tabla E.1: Evolución de la función de costo total

Número de

Transformadores

Costo

Transformadores

($)

Costo Redes

($)

Costo Postes

($)

Costo Pérdidas

($)Costo Total ($)

1 4.387.892 6.682.436 6.169.980 11.894.829 29.135.137

2 6.434.222 6.186.815 5.901.720 4.049.061 22.571.818

3 6.364.284 5.493.175 6.438.240 2.208.303 20.504.002

4 8.485.712 4.788.479 6.348.820 1.426.661 21.049.672

5 10.229.397 4.468.437 5.633.460 1.518.827 21.850.121

6 11.217.596 3.858.079 5.722.880 1.246.199 22.044.754

7 12.377.930 4.343.621 6.259.400 1.412.181 24.393.131

[m]

[m]

166

1 2 3 4 5 6 70

0.5

1

1.5

2

2.5

3x 10

7 Evolucion Costo

Costo Trafos

Costo Red

Costo perdidas

Costo poste

Costo total

Figura E.6: Evolución de la función objetivo

5. Equilibrio de Red: Una vez que se conoce la solución óptima se procede a

recalcularla considerando el equilibrio de la red.

3.94 3.95 3.96 3.97 3.98 3.99 4 4.01

x 104

8900

9000

9100

9200

9300

9400

Figura E.7: Equilibrio de la red óptima

[m]

[m]

Número de Transformadores

[$]

167

Es decir, se reubican los transformadores al interior de su propia red, de tal forma

que los flujos que salen de él, lo hagan de la manera más simétrica posible. En la

figura anterior, la nueva ubicación para los transformadores esta dada por los

triángulos de mayor tamaño, con ello se procede a recalcular los conductores

óptimos y las pérdidas asociadas a la nueva ubicación, logrando un costo total

final de $ 19.403.014, manteniéndose constante el costo de transformadores y el

costo de postes, pero mostrando un ahorro en el costo de red y en el costo de las

pérdidas, dado que sus nuevos costos son de $ 4.789.200 y $ 1.811.290,

respectivamente.

6. Datos de Salida, finalmente para cada mini-zona optimizada se obtiene:

o Ubicación, capacidad y costo de los transformadores usados.

o Trazado óptimo y conductores óptimos en la red asociada a cada

transformador.

o Evaluación de pérdidas de cada red.

o Asignación de clientes a cada transformador.

168

ANEXO F: COSTO MINIMO EN LA OPTIMZACION DE UNA MINI-ZONA

En este anexo se muestra, a modo de ejemplo, el comportamiento típico de la evolución del

costo total en una mini-zona cuando se adiciona un nuevo transformador en el proceso

iterativo de la micro-optimización. Se observa en todos los casos de ejemplo, que luego de

la obtención del mínimo, la adición de un nuevo transformador incrementa el costo total.

Por tanto, se puede asumir que dado el problema y formulación propuesta, encontrar un

mínimo indica altas probabilidades de ser el mínimo global para el procedimiento iterativo

desarrollado. En consideración que se trata de un procedimiento heurístico que de todas

formas no garantizará el óptimo global del problema de planificación, se opta por tomar el

primer mínimo como resultado del proceso de micro-optimización y así evitar tiempos

innecesarios que se producen al ampliar el espacio de búsqueda.

169

Figura F.1: Ejemplos de la evolución del costo total

1 2 3 4 5 6 70

0.5

1

1.5

2

2.5

3x 10

7 Evolucion Costo

Costo Trafos

Costo Red

Costo perdidas

Costo poste

Costo total

1 2 3 4 5 6 7 8 9 100

1

2

3

4

5

6

7

8x 10

7 Evolucion Costo

Costo Trafos

Costo Red

Costo perdidas

Costo poste

Costo total

1 2 3 4 5 6 70

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2x 10

7 Evolucion Costo

Costo Trafos

Costo Red

Costo perdidas

Costo poste

Costo total

1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 60

2

4

6

8

10

12

14

16x 10

6 Evolucion Costo

Costo Trafos

Costo Red

Costo perdidas

Costo poste

Costo total

1 2 3 4 5 6 70

2

4

6

8

10

12

14

16x 10

6 Evolucion Costo

Costo Trafos

Costo Red

Costo perdidas

Costo poste

Costo total

1 2 3 4 5 6 70

0.5

1

1.5

2

2.5

3x 10

7 Evolucion Costo

Costo Trafos

Costo Red

Costo perdidas

Costo poste

Costo total

[$] [$]

[$] [$]

[$] [$]

Número de Transformadores

Número de Transformadores

Número de Transformadores Número de Transformadores

Número de Transformadores

Número de Transformadores

170

ANEXO G: RESULTADOS DE LA MICRO-OPTIMIZACION

En este anexo se presenta un resumen de las simulaciones llevadas a cabo en el proceso de

micro-optimización.

Tabla G.1: Simulaciones equilibrio de red

Lanzamiento Caso 1 Caso 2 Caso 31 1.915.868.486 1.819.211.042 1.814.417.744

2 1.913.864.348 1.828.334.867 1.814.401.933

3 1.906.295.104 1.832.120.157 1.809.303.832

4 1.898.273.931 1.833.232.594 1.823.131.953

5 1.880.259.698 1.843.371.158 1.833.629.354

6 1.915.533.246 1.820.042.332 1.825.299.580

7 1.915.392.226 1.831.159.158 1.810.900.718

8 1.906.087.288 1.835.060.121 1.835.284.128

9 1.912.671.177 1.838.797.878 1.823.501.787

10 1.897.075.493 1.840.474.314 1.818.447.722

11 1.909.780.204 1.820.073.227 1.814.360.503

12 1.894.187.485 1.839.395.779 1.823.147.005

13 1.902.515.472 1.837.076.387 1.817.932.071

14 1.901.192.837 1.839.113.483 1.824.850.808

15 1.905.007.141 1.827.007.437 1.819.594.060

16 1.899.845.910 1.833.870.373 1.810.123.631

17 1.918.636.374 1.831.409.165 1.834.507.060

18 1.923.085.978 1.837.760.035 1.820.942.119

19 1.908.678.780 1.838.682.217 1.818.704.757

20 1.899.646.844 1.836.962.215 1.826.043.357

Tabla G.2: Evolución de la solución para distintos tamaños de mini-zonas

Tamaño Costo Total ($) Tiempo (min)

50 5.142.173.463 16,05

80 3.460.282.100 8,83

100 2.938.271.479 6,73

200 1.994.601.112 3,47

300 1.831.187.098 2,91

400 1.844.106.829 3,10

500 1.820.611.695 3,51

600 1.812.085.048 3,71

700 1.844.859.332 4,40

800 1.849.453.227 5,24

900 1.886.337.132 6,60

1000 1.879.219.829 7,44

1100 1.984.453.927 8,92

1200 2.038.969.994 10,65

1300 2.008.777.457 15,37

171

ANEXO H: RESULTADOS APLICACIÓN GRAN SANTIAGO

En este anexo se presenta un resumen de las simulaciones llevadas a cabo al aplicar la

metodología propuesta sobre la zona de Santiago. Se debe señalar que en las tablas

siguientes, la columna “Costo Total” solo incluye las instalaciones y por tanto no incorpora

el costo de las pérdidas de energía.

Tabla H.1: Micro-optimización del gran Santiago - parte I

Lanzamiento Costo Total ($) Costo Trafo ($) Costo Red ($) Costo Poste ($) Costo Pérdidas ($)

1 70.973.285.445 34.672.416.755 20.258.652.430 16.042.216.260 9.007.758.959

2 71.158.531.278 34.817.163.991 20.277.421.967 16.063.945.320 8.995.927.581

3 70.921.325.234 34.583.730.789 20.298.686.725 16.038.907.720 9.243.883.086

4 70.951.990.818 34.623.047.046 20.271.168.432 16.057.775.340 9.044.286.627

5 71.098.651.683 34.745.361.629 20.291.759.074 16.061.530.980 9.174.612.710

6 71.067.957.121 34.726.526.986 20.266.039.055 16.075.391.080 8.914.897.021

7 70.972.409.405 34.677.106.949 20.246.111.436 16.049.191.020 9.002.683.762

8 71.003.831.236 34.653.134.387 20.302.489.449 16.048.207.400 9.194.046.187

9 71.014.399.273 34.685.264.930 20.275.382.903 16.053.751.440 9.011.177.497

10 71.109.263.030 34.779.883.821 20.282.334.269 16.047.044.940 9.070.216.805

Tabla H.2: Micro-optimización del gran Santiago - parte II

LanzamientoLargo Red

(km)

Número de

Transformadores

Capacidad

Instalada

(MVA)

Pérdidas de

Energía

(MWh)

Tiempo

(min)

1 7.823 12.052 2.859 53.794 173,5

2 7.834 12.022 2.867 53.723 167,8

3 7.821 11.971 2.853 55.204 167,6

4 7.829 12.065 2.857 54.012 167,6

5 7.832 12.030 2.861 54.791 167,3

6 7.837 12.109 2.864 53.240 168,9

7 7.826 12.063 2.862 53.764 167,4

8 7.826 12.001 2.858 54.907 167,0

9 7.828 12.023 2.867 53.815 167,4

10 7.825 12.053 2.862 54.167 168,7