PDF de programación - ANÁLISIS DE ALGORITMOS DE LOCALIZACIÓN ÓPTIMA Y SU IMPLEMENTACIÓN EN SISTEMAS DE INFORMACIÓN GEOGRÁFICA

ANÁLISIS DE ALGORITMOS DE LOCALIZACIÓN

ÓPTIMA Y SU IMPLEMENTACIÓN EN SISTEMAS DE

INFORMACIÓN GEOGRÁFICA.



Tesis para optar
al título de Ingeniero Civil
en Informática

UNIVERSIDAD AUSTRAL DE CHILE

FACULTAD DE CIENCIAS DE LA INGENIERIA

ESCUELA DE INGENIERIA CIVIL EN INFORMATICA



PROFESOR PATROCINANTE:
Mauricio Ruiz-Tagle M.
PROFESOR CO-PATROCINANTE:
Martín Solar M.



TANIA DENISSE LETELIER SANTIBAÑEZ

VALDIVIA - CHILE

2003

AGRADECIMIENTOS

Quiero agradecer a:

Mauricio Ruiz-Tagle, profesor patrocinante, por su gran apoyo y orientación

durante el desarrollo de mi tesis.

Martin Solar, profesor co -patrocinante, por su apoyo desde mis primeras

busquedas de temas para la tesis.

Marcelo Neculman y Jimena Muñoz,de Forestal Valdivia S.A., por permitir

que mi trabajo de tesis sea una solución real a un problema real.



Gonzalo Paredes y Mauricio Acuña, por la orientación y el gran apoyo en

material bibliográfico.



Timothy Gibson, por su ayuda en donde mis conocimientos en inglés y

economía no fueron suficientes.



María Eliana de la Maza, por su disponibilidad a ayudar.



Quiero agradecer en forma especial a mi familia, mis padres y amigos, por la

preocupación en que éste proyecto concluyera con éxito.



Dedico esta tesis a mi hijo Andrés.

II

INDICE

1. Introducción..................................................................................1

1.1.
Preámbulo..................................................................................................... 1
1.2. Definición del problema............................................................................... 3
1.3. Antecedentes ................................................................................................ 6
Trabajos relacionados........................................................................................... 6
Realidad de la empresa......................................................................................... 7
1.4. Objetivos ...................................................................................................... 8
Objetivos Generales ............................................................................................. 8
Objetivos especificos ............................................................................................ 8

2. Localización óptima.....................................................................9

2.1.

Problema de localización óptima. ................................................................ 9
Problema de localización óptima en redes ........................................................... 9
Clasificación de problemas de localización en redes. ........................................ 10
Problemas P-Central........................................................................................... 14
Problemas P-Mediano ........................................................................................ 16
2.2. Algoritmos de localización óptima. ........................................................... 17
Algoritmo para Problemas P-Medianos. ............................................................ 18
Algoritmo para Problema P-Central Vértice...................................................... 20
Algoritmo para Problema 1-Mediano en árboles. .............................................. 21
Cálculo de rutas mínimas ................................................................................... 23

3. Herramientas de Desarrollo .................................................... 26

3.1. Herramienta SIG ........................................................................................ 26
¿Qué es un SIG? ................................................................................................. 26
Selección de la herrramienta SIG....................................................................... 34
ArcView ............................................................................................................. 37
Lenguaje de Programación ......................................................................... 40

3.2.

4. Descripción funcional del Sistema. ........................................ 42

4.1.
Ingreso de información. .............................................................................. 42
4.2. Obtención de la localización. ..................................................................... 44
4.3. Resultado e Informe de salida. ................................................................... 44
Salida visual....................................................................................................... 45
Archivo detallado............................................................................................... 45

5. Diseño e implementación del Sistema .................................... 46

5.1. Diseño......................................................................................................... 46
Diseño de Datos ................................................................................................. 46



III

Diseño Arquitectónico........................................................................................ 52
Diseño Procedimental ........................................................................................ 54
Diseño de Interfaz.............................................................................................. 60
Implementación.......................................................................................... 62
Implementación en Arcview .............................................................................. 62
Implementación en Visual Basic ........................................................................ 63

5.2.

6. Descripción de Funcionamiento del Sistema. ...................... 64

7. Pruebas ........................................................................................ 69

8. Conclusión................................................................................... 74

9. Bibliografía ................................................................................. 76



IV

INDICE DE ANEXOS

Anexo 1. Código fuente de proyectos en Visual Basic...................80

Localiza.vbp............................................................................................80

Cambia.vbp.............................................................................................110

Anexo 2. Scripts en Avenue del proyecto hecho en ArcView.......114

Script: Cambia.........................................................................................114

Script: Crear Tablas.................................................................................114

Script: Crea_TablaDd..............................................................................114

Script: Crea_TablaDda............................................................................114

Script: Crea_TablaSel..............................................................................115

Script: Crea_TablaDet.............................................................................116

Script: Crea_TablaRut.............................................................................116

Script: Crea_TablaOut.............................................................................117

Script: Nodo_Elegido..............................................................................117

Script: Localizar......................................................................................118



V

RESUMEN

Para minimizar sus costos, una empresa que cuenta con una red de

distribución debe asegurar que sus centros de distribución se ubiquen eficientemente.

Un programa computacional bien diseñado, junto con la información geográfica

correcta, puede lograr este objetivo de una manera que requiera poco esfuerzo

humano.

El problema planteado consiste en tener un número determinado de centros o

puntos que demandan la entrega de un bien o su recolección. En base a la ubicación

de todos estos centros se requiere encontrar la mejor localización de una planta

industrial que sea capaz de satisfacer los requisitos de todos los otros centros. Este

tipo de problema se denomina problema de localización óptima. Para resolver el

problema planteado, en primer lugar, se presenta un estudio sobre algunos tipos de

problemas de localización óptima y sus correspondientes algoritmos de solución.

Posteriormente, se realiza el diseño e implementación del prototipo en la herramienta

para Sistemas de Información Geográfica (SIG) y en el lenguaje de programación

elegidos, aplicando los algoritmos de solución a problemas de localización óptima

estudiados, para

finalmente

realizar pruebas al prototipo evaluando

su

comportamiento en la ejecución. El análisis, diseño e implementación, fue aplicado a

un problema de localización de canchas de acopio de madera, en parte de la

superficie de plantaciones de una empresa forestal.

El estudio de esta tesis se centra en la implementación, usando SIG, de

algoritmos que resuelvan problemas de localización óptima.



VI

SUMMARY

In order to minimize its costs, a company that uses a distribution network

must locate its distribution centers efficiently. A well-designed computer program,

coupled with accurate geographical information, can accomplish this objective in a

way that avoids labor -intensive practices.

The problem at hand involves the placement of an industrial facility within a

network of centers or points involved