• Author / Uploaded
• MariaFernandaOchoaBermudez

Citation preview

1

TEORÍA DE GRAFOS RUTA MAS CORTA

Juan Sebastian Fernandez Buitrago 20142007158 Nelson Mauricio Bejarano Bejarano 20142007073

Junio 2019.

Universidad Distrital Francisco José de Caldas Facultad de ingeniería. Ingeniería eléctrica. Investigacion de operaciones II. Algoritmos en R para ruta más corta

2 RESUMEN

En este documento se realizan diferentes programas para implementar rutas más cortas en distintos tipos de grafos; empezando con la adecuación del entorno de programación R Studio y sus complementos requeridos para el desarrollo de los códigos; seguido de esto, se muestran algunos algoritmos metodológicos que permiten la solución de problemas en específico y por último se muestra en el compilador de R el resultado de la implementación de cada código realizado.

INTRODUCCIÓN En la vida diaria la modelación de redes plantea la resolución de múltiples problemas de programación matemática mediante la implementación de algoritmos especiales creados para tal fin, conocidos como Algoritmos de optimización de redes. Dentro de los problemas más comúnmente resueltos mediante la modelación de redes se encuentran los modelos de transporte, transbordo además de los muy conocidos modelos de determinación de cronograma de actividades para proyectos como lo son el PERT y el CPM. (Flujo en redes (recuperado el 26 de agosto del 2018), dentro de los algoritmos de optimización uno de los más habituales es el algoritmo de la ruta más corta que consiste, en una modalidad de problemas de redes, en la cual se debe determinar el plan de rutas que genere la trayectoria con la mínima distancia total, que una un nodo fuente con un nodo destino, sin importar el número de nodos que existan entre estos. En este documento se abarcan diferentes problemas de manera individual, que permitan objetar soluciones empleadas mediante el uso de software R, y la implementación de soportes tecnológicos conocidos como librerías, que permiten el uso de funciones para encontrar soluciones de problemas de tipo complejo.

Algoritmos en R para ruta más corta

3 DESARROLLO En el desarrollo de los códigos en R, se hizo necesario instalar librerías como graph, gtools, igraph, optrees y las librerías propias del sistema. A continuación se muestra los diferentes códigos y ejercicios implementados para ruta más corta. 1. Código para construcción del grafo

El código implementado anteriormente se utiliza para crear un grafo a través de una matriz

2. Código ruta más corta ida y distancia Algoritmos en R para ruta más corta

4

El código permite que mediante un grafo ya creado se pueda calcular la distancia entre dos vértices mostrando el valor de la distancia y los vértices implicados. Para esta prueba se desea calcular la distancia más corta entre los vértices 2 a 5.

3. Código ruta más corta de vuelta y distancia

El código complementa la función de encontrar ahora el camino inverso no solo la ida sino también el regreso

4. Código distancia total ida y vuelta de la ruta mas corta

Algoritmos en R para ruta más corta

5

Este código complementa el uso de los dos códigos anteriores permitiendo encontrar el camino más corto desde un vértice y retornar a él.

5. Código ruta más corta con dos caminos

Con este código se modificó el grafo inicial colocando un camino paralelo de 5 a 3 cuya arista tiene un valor de 6 y se realiza lo mismo del código 3.

6. Código ruta más corta grafo no dirigido Algoritmos en R para ruta más corta

6

Se encuentra la ruta más corta y su distancia entre dos vértices de un grafo no dirigido.

7. Código ruta más corta desde nodo fuente

Habilitando el paquete OPTREES implementamos el siguiente código que me permite encontrar la ruta más corta desde un nodo fuente hacia los demás junto con la distancia

8. Código ruta más corta con pesos negativos

Algoritmos en R para ruta más corta

7

En este código se implementa el mismo grafo pero su ponderado se considera en una arista negativa.

9. Código para camino Hamilton

En este código se implementa un grafo completo y no dirigido para calcular un camino Hamilton.

10. Código rutas más cortas según número de vértices para nodo fuente Algoritmos en R para ruta más corta

8

Para el grafo del código 1, se implementa este código que permite encontrar la ruta más corta desde un vértice fuente a los demás vértices, para este ejemplo el vértice fuente es el 1

Algoritmos en R para ruta más corta

9 CONCLUSIONES:  Mediante la implementación de los paquetes de igraph y optrees del programa R Studio se reduce un sin número de problemas, sin embargo su implementación está sujeta a realizar determinados procesos limitado por su dificultad de modificación.  Dado que los programas presentados permiten la solución e diferentes tipologías de grafos, es posible implementar estas herramientas en el análisis de modelos estocásticos, redes de comunicaciones y problemas de la vida cotidiana. REFERENCIAS  Flujo en redes (recuperado el 26 de agosto del 2018) https://www.ingenieriaindustrialonline.com/herramientas-para-el-ingenieroindustrial/investigaci%C3%B3n-de-operaciones/teor%C3%ADa-de-redes/ HOMEWORK Pacho is a bus driver who travels every day from Bogotá to different destinations in the country, Pacho's GPS has provided different possible routes to get to Cartagena. Pacho wants to save fuel for which it is necessary to calculate the most optimal route, Pacho's GPS has thrown the following routes: Bogotá Tunja Bucaramanga Manizales Medellín Santa Marta Cartagena

Bogotá

Tunja

Bucaramanga

Manizales

Medellín

0 139 0 308 419 0 0

141 0 282 0 0 0 0

0 282 391 519 391 0 0

308 0 0 0 196 0 824

419 0 0 196 0 836 1008

Santa Marta 0 0 0 0 836 0 239/230

Cartagena 0 0 0 824 1008 239/230 25

All routes are in Km, /: Means two alternate routes. a. Calculate the most optimal route from Bogota to Cartagena. b. If Pacho wants to go to Cartagena through Santa Marta first, which route is the most optimal? c. Calculate the best return route if Pacho were only to Santa Marta. d. Calculate the most optimal routes from Bogotá to all the other destinations that the GPS shows to Pacho.

Algoritmos en R para ruta más corta