Arreola Silva E. Marisol
Garcia Nieto Luis

Introducción: En la Facultad de Ciencias, UNAM, los alumnos eligen su horario a conveniencia, de manera que se tiene una forma libre de elegir profesores, sin embargo, esto no sucede con los salones dentro de la facultad y puede suceder que en el cambio de salón de dos clases consecutivas, se tenga la necesidad de recorrer una considerable distancia o tiempo para llegar de un salón a otro. Así, en este proyecto nos interesa encontrar la forma más óptima(en tiempo) de trasladarnos de un lugar a otro. Consideraremos los principales sitios de interés dentro y fuera de la facultad.

Planteamiento.Sea G=[X,A, t] una red donde:

Si X es el conjunto de vértices, representará los sitios de interés, estos son:

1. Metro C.U (MCU)
2. Prometeo (PROM)
3. ABC
4. Intersección pasillo Edificio de Matemáticas- Edificio P y Edificio O, primer piso (PO1)
5. Intersección pasillo Edificio de Matemáticas- Edificio P y Edificio O, segundo piso (PO2)
6. Aula Magna I, Tlahuizcalpan (AM1)
7. Aula Magna II, Tlahuizcalpan (AM2)
8. Darwin (DARW)
9. Taller de finanzas, Tlahuizcalpan (T. FIN)
10. Taller de IdeO, Tlahuizcalpan (T. IDEO)
11. Copias (enfrente de servicios escolares) (COP)
12. Yelizcalli(Planta baja, salón 006) (YEL)
13. Tía Aly (TIA ALY)
14. Media luna (MLUNA)
15. Pulpo (PULPO)

• Si A representa el conjunto de aristas, éstas determinará un camino directo entre nuestros lugares objetivo.
• t es una función que representa el tiempo que nos toma llegar de un lugar a otro. Estos tiempos se medirán un numero considerable de veces para, posteriormente, obtener la media que será está función.
  

Solución con explicación. En este problema, buscamos la ruta más corta de un lugar a otro, por lo tanto, se utilizará el algoritmo de Floyd programado en R, este algoritmo tiene muchas ventajas, en particular, su forma matricial es sencilla de programar.

La siguiente matriz corresponde a la matriz de costos, el tiempo que toma ir direcamente del lugar i al lugar j en minutos, donde los lugares están acomodados por renglón y columna siguiendo el orden visto en el planteamiento.

require(Matrix)
require(dplyr)
library(readxl)
#Importación y limpieza de datos
DISTACIAS <- na.omit(read_excel("DISTACIAS.xlsx"))
View(DISTACIAS)
places<-c("MCU", "PROM", "ABC", "PO1", "PO2", "AM1", "AM2", "DARW", "TFIN", "TIDEO", "COP", "YEL", "TIA ALY", "MLUNA", "PULPO")
DISTANCIAS<-DISTACIAS%>%select(-1)%>% as.matrix()
Costos<-matrix(DISTANCIAS, nrow=15, ncol =15)%>%na.omit() %>%forceSymmetric()

#Construcción de una matriz que indique si el camino i a j existe
tmp=matrix(NA,ncol = 2)
row.names(Costos)=places
colnames(Costos)=places
for(i in 1:15){
  for (j in 1:15){
    if(Costos[i,j]>0 & Costos[i,j]<100){
      tmp=rbind(tmp,c(places[i],places[j]))
    }
  }
}
links=tmp[-1,]

A=c(rep(c(1:15),15))
places=c("MCU", "PROM", "ABC", "PO1", "PO2", "AM1", "AM2", "DARW", "TFIN", "TIDEO", "COP", "YEL", "TIA ALY", "MLUNA", "PULPO")
A<-matrix(A, ncol = 15, nrow = 15, byrow=F)

En el siguiente código implementamos el algoritmo de Floyd y mostramos una gráfica interactiva de la red (Es posible realizar zoom, deslizarse y reacomodar los nodos).

for(k in 1:15){
  for(i in 1:15){
    for(j in 1:15){
      if((k != i)&(k != j)){
        if((Costos[i,k]+ Costos[k,j]) <= (Costos[i,j])){
          A[i,j]=A[k,j]
          Costos[i,j]=min(Costos[i,j], Costos[i,k]+Costos[k,j])
        }
      }
    }
  }
}

library(igraph) 
library('visNetwork') 
library(networkD3)
library(tidyverse)
# cDe Matriz a dataframe
data <- data.frame(
  from=links[,1],
  to=links[,2])

# Gráfico Interactivo
p <- simpleNetwork(data, height="250px", width="400px",        
        Source = 1,                 
        Target = 2,                 
        linkDistance = 4,          # distance between node. Increase this value to have more space between nodes
        charge = -200,                # numeric value indicating either the strength of the node repulsion (negative value) or attraction (positive value)
        fontSize = 14,               # size of the node names
        fontFamily = "serif",       # font og node names
        linkColour = "#880000",        # colour of edges, MUST be a common colour for the whole graph
        nodeColour = "white",     # colour of nodes, MUST be a common colour for the whole graph
        opacity = 0.99,              # opacity of nodes. 0=transparent. 1=no transparency
        zoom = T                    # Can you zoom on the figure?
        )
p

La siguiente función recibe como parámetros dos lugares (de acuerdo al indice en la matriz) de los considerados para el proyecto, y regresamos la trayectoria de rutas más cortas, la matriz de adyacencia de floyd y el costo que en este caso es el tiempo

floyd_us<-function(origen, destino){
  ant<-A[origen,destino]
  trayectoria<-c(destino)
  while(origen!=ant){
      trayectoria<-c(trayectoria, ant)
      ant<-A[origen,ant]
  }
  trayectoria<-c(trayectoria, origen)
  trayectoria=trayectoria%>%rev()
  Costo=0
  n=length(places[trayectoria])
  for(i in 1:(n-1)){
    Costo=Costo+ Costos[trayectoria[i],trayectoria[i+1]]
  }
  print("Trayectoria:")
  print(places[trayectoria])
  print("Tiempo (minutos):")
  print(Costo)
  
  
  df<-data.frame(from=places[trayectoria][-n], to=places[trayectoria][-1])
  p <- simpleNetwork(df, height="100px", width="100px",        
        Source = 1,                 # column number of source
        Target = 2,                 # column number of target
        linkDistance = 10,          # distance between node. Increase this value to have more space between nodes
        charge = -900,                # numeric value indicating either the strength of the node repulsion (negative value) or attraction (positive value)
        fontSize = 14,               # size of the node names
        fontFamily = "serif",       # font og node names
        linkColour = "#880000",        # colour of edges, MUST be a common colour for the whole graph
        nodeColour = "white",     # colour of nodes, MUST be a common colour for the whole graph
        opacity = 0.99,              # opacity of nodes. 0=transparent. 1=no transparency
        zoom = T                    # Can you zoom on the figure?
        )
p
  
}

Ejemplo 1.

floyd_us(3,5)

## [1] "Trayectoria:"
## [1] "ABC" "COP" "PO1" "PO2"
## [1] "Tiempo (minutos):"
## [1] 1.89

Ejemplo 2

floyd_us(7,13)

## [1] "Trayectoria:"
## [1] "AM2"     "AM1"     "TIA ALY"
## [1] "Tiempo (minutos):"
## [1] 2.17

Ejemplo 3

floyd_us(9,10)

## [1] "Trayectoria:"
## [1] "TFIN"  "TIDEO"
## [1] "Tiempo (minutos):"
## [1] 0.8

Así concluimos nuestro proyecto, ya que se cumplió el objetivo propuesto de manera rápida y eficaz. Posibles mejoras y extensiones serían el incluir más lugares de CU, más caminos o conexiones posibles entre los nodos, la capacidad de mostrar rutas adicionales con tiempos cercanos al óptimo, entre otros.