ActualidadAnálisis de datosDiseño y distribución en plantaGestión de almacenesInteligencia artificialLocalización de instalacionesLogística
Tendencia

Localización de varios almacenes mediante agrupación geoespacial

Utilizando Python (Machine Learning)

En un artículo anterior, desarrollamos un modelo capaz de determinar la localización de una instalación (almacén), de acuerdo a un conjunto de ubicaciones existentes (clientes); estas ubicaciones tenían una ponderación determinada (peso, por ejemplo demanda), y basamos nuestro desarrollo en el algoritmo de Centro de Gravedad.

El valor agregado del modelo consistía en la integración de una capa de mapa de calor (para graficar la densidad), un proceso de geocodificación y el uso de un entorno geográfico real. El alcance de este modelo se encuentra determinado por la localización de una sola instalación (depósito, almacén, etc.), y en los casos en los que se requiera determinar múltiples localizaciones, el modelo no aplica.

La pregunta siguiente que nos hacemos es ¿Cómo determinar la localización de múltiples instalaciones? En realidad, hay muchas respuestas para este interrogante, y gran parte de ellas conducen a la agrupación geoespacial (Clustering).

¿Qué es la agrupación geoespacial (Clustering)?

La agrupación geoespacial es un método que se utiliza para asociar un conjunto de objetos espaciales en grupos denominados «clusters«. Los objetos que conforman cada grupo presentan un grado de similitud asociado a un atributo o varios atributos en particular.

El objetivo de la agrupación geoespacial, consiste en determinar una relación entre atributos espaciales (coordenadas, ubicación) y no espaciales (demanda, por ejemplo).

En la literatura encontraremos varios tipos de agrupación geoespacial, cada uno con un enfoque particular, y un campo de aplicación específico; entre los cuales podemos encontrar:

  • Agrupación de particiones
  • Agrupación jerárquica
  • Agrupación Fuzzy
  • Agrupación basada en densidad

En nuestro caso, que pretendemos determinar la localización de varias instalaciones, considerando la ponderación y ubicación de los puntos existentes, requerimos de un modelo capaz de relacionar atributos espaciales (coordenadas) y no espaciales (peso de cada nodo). Que nos permita, primero agrupar los puntos dados (ubicaciones), y eventualmente, aplicar un algoritmo de Centro de Gravedad, para determinar localizaciones potenciales.

Para tales efectos, vamos a utilizar la agrupación de particiones, que se caracteriza, entre otras, por:

  • Agrupar los puntos espaciales en subconjuntos
  • Cada punto agrupado pertenece solo a un subconjunto (clúster)
  • Cada subconjunto tiene al menos un punto

Vale la pena destacar que en cuanto a la agrupación de participaciones, en esta categoría encontraremos varios métodos de partición, y nosotros utilizaremos el método K-Means, un algoritmo de aprendizaje automático (Machine Learning) no supervisado. Para ello utilizaremos Python.

clustering
Agrupación por particiones

Para sintetizar, el objetivo de este artículo será el de emplear un algoritmo de aprendizaje automático capaz de agrupar nuestros nodos en clusters, de acuerdo a atributos espaciales (coordenadas) y no espaciales (ponderación); para luego, utilizar un algoritmo de Centro de Gravedad en cada clúster para determinar la localización de múltiples instalaciones (almacenes, depósitos, etc.).

En el desarrollo de este ejercicio emplearemos:

  • Colaboratory: Este es un entorno de programación y ejecución virtual de Python desarrollado por Google. Nos permitirá no tener la necesidad de realizar ninguna instalación en nuestros equipos. Todo lo que desarrollemos lo ejecutaremos en un cuaderno virtual.
  • Python: Este será el lenguaje de programación que vamos a utilizar, y advertimos: No es necesario tener conocimientos previos, y el objetivo del artículo no es convertirnos en programadores expertos. Utilizaremos fragmentos de códigos, librerías disponibles, y explicaremos lo necesario para configurar nuestro desarrollo de acuerdo a los objetivos específicos de nuestros modelos.
  • SkLearn: Las librerías son a Python, lo que las apps son a un teléfono celular. Esta es quizá una de las características más a tractivas de este lenguaje: Casi que existe una librería para cada necesidad. En este caso, SKLearn, es una librería que integra un conjunto de métodos de aprendizaje automático y minería de datos.
  • K-MeansEste es un módulo de SKLearn que contiene el algoritmo de agrupación KMeans, el cual separa muestras en n grupos de varianza igual, minimizando un criterio conocido como inercia o suma de cuadrados dentro del grupo.
  • Matplotlib: Es una biblioteca completa para crear visualizaciones estáticas, animadas e interactivas en Python. Nos permitirá visualizar nuestros nodos y nuestras localizaciones solución.
  • Pandas: Es un paquete de Python que proporciona estructuras de datos rápidas, y flexibles, diseñadas para que el trabajo con datos estructurados (tabulares, multidimensionales, potencialmente heterogéneos) y de series de tiempo sea fácil e intuitivo.
  • NumpyEs una librería que nos permitirá efectuar operaciones matriciales en Python.

Para desarrollar estas herramientas, vamos a plantear un caso típico de localización de múltiples instalaciones a partir de la consideración de otros nodos (nodos de demanda, por ejemplo).

Caso de aplicación

El Departamento de Desarrollo Sostenible de la ciudad de Cali se encuentra implementando una estrategia piloto de recolección de aceite de cocina usado. Ha articulado este proyecto con una Universidad, la cual desarrolló 4 contenedores inteligentes (BIN’s) para la disposición del bioresiduo.

En investigaciones asociadas, la Universidad ha determinado que el reciclaje del aceite es un problema de densidad; esto quiere decir que es vital la ubicación de los contenedores (cobertura), para así mismo optimizar el proceso de disposición y recolección. El proyecto piloto piensa articular a las instituciones de educación como puntos potenciales de recolección. Por medio de las instituciones piensan socializar el programa con la comunidad. El primer reto del proyecto consiste en determinar la ubicación de los contenedores inteligentes (4 unidades). La información relacionada con las instituciones de educación que hacen parte del programa (ubicación geográfica / población estudiantil), se detalla a continuación:

NodoLugar (Colegios)LatitudLongitudPeso
0 Comfandi San Nicolás3,453591118-76,522548861494
1 Mayor de Santiago de Cali3,451577758-76,51023216908
2 Municipal Comfandi3,448107915-76,51074714697
3 Internado San Carlos3,446994135-76,515253251714
4 León de Greiff3,447979402-76,499932471731
5 Nuestra Señora de la Anunciación3,445152112-76,496413422297
6 Fernando de Aragón3,437355603-76,513837041265
7 Casa Evangélica3,437955337-76,522999471658
8 San Alberto Magno3,433028941-76,52707643604
9 Santa María Goretty3,433414486-76,50720662416
10 San Alberto Magno3,433157456-76,52673311584
11 San Ignacio de Loyola3,431786629-76,517334642350
12 Nuestro Futuro3,430629992-76,50360174964
13 Sabio Caldas3,429087807-76,51660508329
14 CREAD3,425060978-76,51488847774
15 Licomtec3,416664559-76,516733831818
16  Nuestra Señora De La Providencia3,419534772-76,495919891530
17 Real Suizo3,415208029-76,493237682106
18 Nuevo Edén3,415722099-76,53383559330
19 Católico3,413066071-76,53984374976
20 Santa María Stella3,427031556-76,551345051975
21 Santa Isabel3,40805355-76,50817223936
22 Compartir3,431957663-76,474955751563
23 Lancaster3,400770816-76,551774211219
24 Parroquial Divino Salvador3,397086588-76,542590331954
25 Reyes Católicos3,393316667-76,53735466399
26 Liceo Anglo del Valle3,387318719-76,519759371741
27 Laurence3,383420238-76,520789341111
28 Los Almendros3,381278208-76,520231441826
29 Bautista3,37720834-76,523278431772
30 Lacordaire3,378150837-76,544607361965
31 General José María Córdoba3,393573314-76,54932805841
32 El Hogar3,390745864-76,5503151770
33 Americano3,379093255-76,54688187650
34 Santa Filomena3,401969935-76,513450821401
35 Tomás Vasconi3,403040928-76,51731321474
36 República del Salvador3,404454636-76,521433081926
37 Los Andes3,429601077-76,537612161566
38Villacolombia3,445493943-76,501692022354
39Las Américas3,449220822-76,505940642043
40SantaFe3,442238267-76,509888852333
41Evaristo García3,440781776-76,51752778696
42Alfredo Vasquez Cobo3,435598366-76,51645491073
43Ciudad de Cali3,431143181-76,512721261275
44INEM3,482761991-76,499760831485
45Olaya Herrera3,478178519-76,512807091470
46Guillermo Valencia3,47449459-76,51366541248
47José Ignacio Rengifo3,471624543-76,51366542160
48Santo Tomás3,45830227-76,51645491776
49La Merced3,46271449-76,5024645706
50Pedro Antonio Molina3,482804827-76,487615792369
51Santa Librada3,46228612-76,523020952498
52República de Israel3,463656904-76,510532581510
53San Vicente Paul3,466227117-76,509502612330
54Manuel María Mallarino3,456760129-76,488517011464
55Sebastían de Belalcazar3,460229941-76,48521253628
56Liceo Departamental3,423860462-76,5385563364
57Libardo Madrid3,422061154-76,543834892439
58Metropolitano Santa Anita3,401691038-76,542182651815
59San José3,396935816-76,550315112230

Para tales efectos, desarrollaremos un modelo que apoye el análisis preliminar y la localización de los múltiples contenedores. También, que tenga la capacidad de predecir el grupo (clúster) al que pertenecería un nodo nuevo.


Paso 1: Crear el entorno de trabajo en Colaboratory

Lo primero que vamos a hacer consiste en crear un entorno de trabajo en Google Colaboratory, así que vayamos allá: Abrir cuaderno nuevo.

Verán que tienen un lienzo para programar el modelo, así que en este cuaderno podemos ir generando las líneas de código que explicaremos en los pasos siguientes.

Paso 2: Importar las librerías necesarias

Respecto a las librerías, en la introducción del artículo hicimos una descripción de la funcionalidad de cada una, veamos como importarlas en nuestro entorno:

#Importar las librerías necesarias
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans

De esta manera, tenemos todo lo necesario para empezar a desarrollar nuestro código.

Paso 3: Importar los datos desde Excel

De acuerdo a las necesidades del modelo, podemos desarrollar un código que permita la entrada manual de la información, la captura de los datos desde entornos digitales (Internet, por ejemplo), o podemos, desde luego, alimentar nuestro modelo con información contenida en documentos externos, como es el caso de un archivo de Microsoft Excel.

Esta puede considerarse como una de las ventajas de utilizar Python, su capacidad de integrarse con cualquier fuente de datos. En nuestro caso, toda la información se encuentra contenida en un documento de Excel, el cual presenta el siguiente formato:

datos_excel

Ya veremos cómo, parte de estos datos son prescindibles y otros indispensables.

Puedes descargar el documento de Excel que utilizamos en este ejemplo: Base de datos

En Colaboratory, el siguiente fragmento permitirá cargar un archivo al entorno de ejecución:

from google.colab import files

uploaded = files.upload()

for fn in uploaded.keys():
  print('User uploaded file "{name}" with length {length} bytes'.format(
      name=fn, length=len(uploaded[fn])))

Al ejecutar este fragmento de código, se abrirá una ventana emergente del explorador que permitirá cargar nuestra base de datos, en nuestro caso el archivo tienen el nombre de cluster.xlsx.

La siguiente línea de código permitirá almacenar los datos contenidos en el documento en un Dataframe de nuestro entorno, dentro de la variable data.

#Leer el documento de Excel y almacenar los datos en la variable data
data = pd.read_excel('cluster.xlsx')

Podemos en cualquier momento confirmar si la carga de los datos se ha realizado correctamente, para eso imprimiremos las primeras cinco filas del  DataFrame:

data.head()

Al ejecutar esta instrucción tenemos la siguiente salida:

head_cluster

Paso 4: Graficar los puntos dados iniciales (Nodos)

Nuestros puntos iniciales, o las ubicaciones de partida son las instituciones de educación que nos otorga el planteamiento del problema.

Para graficar estos puntos utilizamos el sistema de coordenadas disponible: Latitud y Longitud. Así entonces, debemos extraer estos datos de la hoja de cálculo (DataFrame) que hemos importado al modelo; convertir estas coordenadas en una matriz bidimensional (Latitud y Longitud) y graficar los puntos:

#Graficar los nodos dados (ubicaciones)
Lat= data['Latitud']
Lon = data['Longitud']
Peso = data['Peso']
X = []
for i in range(len(data['Latitud'])):
    X.append(Lat[i])
    X.append(Lon[i])

X = np.array(X)

X = X.reshape(-1, 2,)


plt.scatter(Lat, Lon)
plt.show()

Al ejecutar este fragmento de código, tendremos:

ubicaciones iniciales

Podemos apreciar cómo se encuentran dispersos los nodos iniciales, formando parte un mismo conjunto que es la población. Las coordenadas son latitud y longitud. Los nodos son, una vez más recordamos, las instituciones educativas, de acuerdo al caso de estudio.

Paso 5: Agrupar los nodos geoespacialmente mediante Machine Learning

Cuando mencionamos Machine Learning, a menudo la primera consideración que tenemos es de complejidad. Pues bien, muchos de los algoritmos que hemos utilizado durante décadas son en realidad de aprendizaje automático, como por ejemplo la regresión lineal. El algoritmo de K-Means que emplearemos de forma automatizada mediante Python, utiliza centroides que minimizan la inercia, o el criterio de suma de cuadrados de cada clúster:

formula_cluster

Me pareció conveniente explicar un poco la teoría, pero vayamos a la práctica. Toda vez que tenemos los nodos del modelo, lo siguiente que debemos indicar es la cantidad de agrupaciones que queremos (clúster). Ya que el problema plantea la disposición de 4 contenedores, vamos a dividir la población de nodos en 4 conjuntos.

Luego, correremos el algoritmo K-Means, veamos cómo:

#Ejecutar el algoritmo KMeans
clusters = 4
KMean = KMeans(n_clusters=clusters)
KMean_g = KMean.fit_predict(X)
KMean.fit(X)

Lo siguiente que haremos será establecer los centroides de cada clúster, es decir, la ubicación de nuestros contendores. En primer lugar, el modelo nos dará las coordenadas. Utilizaremos la siguiente línea de código:

#Determinar los centroides de cada clúster
KMean.cluster_centers_

Al ejecutarla tendremos:

centroides

Estas son las coordenadas que indican el centro de cada uno de nuestros grupos de nodos. Y teóricamente ahí deberíamos disponer nuestros contenedores.

Paso 6: Graficar los clusters y los centroides (Localizaciones múltiples)

El siguiente paso consiste en graficar todas las coordenadas que ya tenemos: tantos los nodos iniciales, como los los centroides, o las localizaciones solución. Veamos cómo:

#Graficar todas las coordenadas (Puntos y centroides)
plt.scatter(X[:,0], X[:,1], c=KMean_g) #Puntos iniciales

#Centroides
plt.scatter(KMean.cluster_centers_[0][0], KMean.cluster_centers_[0][1], s=50, c='r')
plt.scatter(KMean.cluster_centers_[1][0], KMean.cluster_centers_[1][1], s=50, c='r')
plt.scatter(KMean.cluster_centers_[2][0], KMean.cluster_centers_[2][1], s=50, c='r')
plt.scatter(KMean.cluster_centers_[3][0], KMean.cluster_centers_[3][1], s=50, c='r')

Al ejecutar el fragmento tendremos:

centroides_II

Vemos cómo se han efectuado las agrupaciones de los nodos (colores), y los marcadores rojos indican los centroides. Este debería ser el final de nuestro desarrollo, sin embargo, no sé si lo han notado, siempre hemos hablado de centroides, nunca de centros de gravedad o centros de masa. Bien, no sé si también han identificado que en ningún momento hemos considerado el peso de cada nodo, en este caso la población estudiantil de cada institución.

¿Esto qué implica? Implica que hemos desarrollado un modelo que tiene exclusivamente consideraciones espaciales. De hecho, visualmente puede observarse cómo, básicamente los centroides se ubican en lo que podría considerarse el medio de cada clúster, sin ninguna consideración adicional aparente, por lo menos a la vista.

Pues bien, vamos a solucionarlo, para ello debemos retocar algunos de los pasos anteriores:

Paso 5 (Recargado): Agrupar los nodos geoespacialmente mediante Machine Learning (Considerando atributos espaciales y no espaciales)

Dentro de nuestro marco de datos (DataFrame) tenemos la información relacionada al peso de cada nodo (Población estudiantil). Pues bien, vamos a considerarla al ejecutar el algoritmo K-Means.

#Ejecutar el algoritmo KMeans (Considerando el peso de los nodos)
clusters = 4
KMean = KMeans(n_clusters=clusters)
KMean_g = KMean.fit_predict(X)
KMean.fit(X, sample_weight=Peso)

Lo siguiente que haremos será establecer los centroides de cada clúster, que ahora sí serán Centros de Gravedad; es decir, la ubicación de nuestros contendores. En primer lugar, el modelo nos dará las coordenadas. Utilizaremos la siguiente línea de código:

#Determinar los centroides de cada clúster
KMean.cluster_centers_

Al ejecutarla tendremos:

centroides_recargado

Los centroides han cambiado, ahora son centros de gravedad afectados por el peso de cada nodo. Es posible que incluso haya cambiado la agrupación de los nodos (composición de los clusters).

Paso 6 (Recargado): Graficar los clusters y los Centros de Gravedad (Localizaciones múltiples)

El siguiente paso consiste en graficar todas las coordenadas que ya tenemos: tantos los nodos iniciales, como los los Centros de Gravedad, o las localizaciones solución. Veamos cómo:

#Graficar todas las coordenadas (Puntos y centroides)
plt.scatter(X[:,0], X[:,1], c=KMean_g) #Puntos iniciales

#Centroides
plt.scatter(KMean.cluster_centers_[0][0], KMean.cluster_centers_[0][1], s=50, c='r')
plt.scatter(KMean.cluster_centers_[1][0], KMean.cluster_centers_[1][1], s=50, c='r')
plt.scatter(KMean.cluster_centers_[2][0], KMean.cluster_centers_[2][1], s=50, c='r')
plt.scatter(KMean.cluster_centers_[3][0], KMean.cluster_centers_[3][1], s=50, c='r')

Al ejecutar el fragmento tendremos:

Centros de gravedad

El resultado respecto a los centroides es diferente. La consideración de un atributo no espacial, en este caso el peso de cada nodo (población estudiantil de cada institución educativa), ha incidido en la ubicación propuesta de las localizaciones solución. Y este debería ser el final de nuestro modelo.

Hemos logrado agrupar nuestros puntos iniciales en clusters, y luego hemos determinado los Centros de Gravedad de cada uno de los clusters.

Por último, veamos una característica de la librería K-Means Análisis predictivo de nodos en clusters, es decir, de acuerdo a unas coordenadas dadas, podemos estimar el grupo al que pertenecerá un nuevo nodo.

Paso 7: Predicción de clusters

En primer lugar ejecutaremos una línea que nos permite identificar a cada nodo dentro de un grupo. Ya que tenemos 4 grupos, estos se identificarán de la siguiente manera: 0, 1, 2, 3.

KMean.labels_

Al ejecutar esta línea tendremos:

grupos_nodos

Vemos como cada una de las 60 instituciones educativas (nodos), tienen un identificador de grupo dentro del modelo.

Ahor, dadas las coordenadas de un nuevo nodo, podemos predecir el grupo al cual pertenecerá:

sample_test=np.array([-3.433,-76.22])
second_test=sample_test.reshape(1, -1)
KMean.predict(second_test)

Al ejecutar este fragmento tendremos:

nodos_prediccion

Es decir, el algoritmo predice que de acuerdo a las coordenada dadas, el nuevo nodo formaría parte del clúster 0.


Pudimos observar cómo varía el resultado dependiendo de la consideración de atributos netamente geoespaciales, y de atributos no espaciales, como la ponderación de cada nodo.

Atributos geoespaciales |

centroides_II

Atributos geoespaciales y de ponderación |

Centros de gravedad

    Integración con mapas de calor y entornos geográficos reales

    Uno de los puntos negativos del modelo que acabamos de desarrollar es quizá que no nos permite visualizar gráficamente la densidad de los puntos. Si observamos las gráficas, todos los puntos parecen tener el mismo tamaño, y si bien esta no es una consideración para el funcionamiento del algoritmo; en el análisis preliminar quisiéramos tener esta herramienta. Otra consideración adicional sería la posibilidad de graficar todos nuestros puntos, y los centros de gravedad de cada (clúster) en un entorno geográfico real.

    Pues bien, una de las ventajas fundamentales de Python consiste en que podemos integrar distintos desarrollos en nuestros modelos, tal es el caso del desarrollo que efectúanos en un artículo anterior (Mapas de calor y Entornos geográficos reales); de tal manera que podamos complementar nuestro modelo.

    No vamos a profundizar en la librerías, ni en la definición de las variables, para eso recomendamos leer el artículo. Veamos entonces, como complementamos este modelo:

    import folium
    import statistics
    from folium.plugins import HeatMap
    mediaLong = statistics.mean(Lon)
    mediaLat = statistics.mean(Lat)
    
    # Crear un objeto de mapa base Map()
    mapa = folium.Map(location=[mediaLat, mediaLong], zoom_start = 13)
    
    # Crear una capa de mapa de calor
    mapa_calor = HeatMap( list(zip(Lat, Lon, data["Peso"])),
                       min_opacity=0.2,
                       max_val=data["Peso"].max(),
                       radius=50, 
                       blur=50, 
                       max_zoom=1)
    
    #Creamos el marcador de Centro de Gravedad
    tooltip = 'Centro de gravedad'
    folium.Marker([KMean.cluster_centers_[0][0], KMean.cluster_centers_[0][1]], popup="Centro", tooltip = tooltip).add_to(mapa)
    folium.Marker([KMean.cluster_centers_[1][0], KMean.cluster_centers_[1][1]], popup="Centro", tooltip = tooltip).add_to(mapa)
    folium.Marker([KMean.cluster_centers_[2][0], KMean.cluster_centers_[2][1]], popup="Centro", tooltip = tooltip).add_to(mapa)
    folium.Marker([KMean.cluster_centers_[3][0], KMean.cluster_centers_[3][1]], popup="Centro", tooltip = tooltip).add_to(mapa)
    
    # Adherimos la capa de mapa de calor al mapa principal
    mapa_calor.add_to(mapa)
    mapa

    Al ejecutar este fragmento tendremos el siguiente resultado:

    Mapa de calorII

    Ahora tenemos un modelo capaz de agrupar nuestros nodos en clusters de acuerdo a atributos geoespaciales; capaz de determinar los centros de gravedad de cada cluster de acuerdo a atributos no espaciales (en nuestro caso la población de los nodos); capaz de complementarse con una capa de visualización de mapa de calor que nos permite apreciar la densidad y todo esto puede visualizarse en un entorno geográfico real.

    Consideraciones finales

    Ya lo expresamos anteriormente, la base del algoritmo K-Means es la consideración y minimización de la inercia, y en espacios de muy altas dimensiones, las distancias suelen inflarse, ya que esta no es una medida normalizada.

    Sin embargo, para los efectos que hemos empleado, el algoritmo suele arrojar resultados satisfactorios.

    El código completo de este desarrollo lo puedes encontrar en nuestro cuaderno: Localización de varias instalaciones mediante agrupación geoespacial y Centro de Gravedad (Python).

    Bryan Salazar López

    Ingeniero Industrial y Magíster en Logística Integral especializado en productividad y modelamiento de procesos bajo dimensiones de sostenibilidad, industria 4.0, transformación digital y modelos de optimización. Docente universitario de pregrado y posgrado con experiencia en la enseñanza de estos temas. Fundador de Ingenieriaindustrialonline.com, un sitio en donde se recogen las aportaciones de investigaciones, artículos y referencias relevantes para la industria.

    Deja una respuesta

    Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

    Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.

    Botón volver arriba
    Nuestros partners recogerán datos y usarán cookies para ofrecerle anuncios personalizados y medir el rendimiento.    Ver Política de privacidad
    Privacidad