Un acercamiento a elegir entre infinitas posibilidades (DDDM)
Actualmente me desempeño como responsable de ingeniería, en la implementación de un nuevo Sorter. Como introducción ,un Sorter es una maquina que distribuye paquetes a gran velocidad, haciendo como su nombre lo indica un proceso de ordenamiento.
La maquina que estamos instalando tiene la posibilidad de “ordenar” entre 126 destinos distintos. Operativamente para el comienzo de la operación tendremos 14 sectores, con 9 destinos cada uno (O los necesarios).
El problema aparece cuando hay que decidir que destinos tiene cada sector y como los elegimos. En el momento de atacar el mismo, surge la cantidad pseudo infinita de posibilidades existentes, de hecho el resultado de posibilidades combinatorias, esta dado por la formula de stirling de segunda especie:
Que para 126 destinos y 14 sectores, da un resultado del orden de 3x10 ^133
Para entender el orden de magnitud, tener en cuenta que la cantidad de átomos en el universo se estima en 10 ^80.
Lo que hice entonces fue conseguir un LOG (Registro de eventos) del clasificador actual, y empezar a trabajar en una solución pseudo-optima intentando que la diferencia de carga de trabajos entre sectores sea lo mas baja posible.
Comienzo importando las librerías que usaremos, y cargando el dataframe del LOG, curiosamente el dataframe perse únicamente nos servirá para genera un objeto “serie” que tenga la cantidad de recurrencias por destino. Algo bastante parecido a lo que se obtiene con una tabla pivot en Excel.
import pandas as pd
import matplotlib.pyplot as plt
import randomdf = pd.read_csv("LOG.csv")
Df_Group = df["descripcion_suc_destino"].value_counts()
En una primera instancia decidí armar un tensor dim 2 (14x9) donde tendré cada sector y cada rampa o destino. Creo uno para las cantidades (Q)y otro para los nombres (Names), que utilizare al final del programa.
Qsect = 14
Qdestinos = 9
Q = [[0 for x in range(Qdestinos)] for x in range(Qsect)]
Names = [["" for x in range(Qdestinos)] for x in range(Qsect)]La primer mejora que le haría al programa si lo reescribiera, es utilizar en vez de un objeto “list” para las cantidades, un objeto “array” de numpy (Veremos mas adelante el porque).
El paso siguiente consiste en empezar a completar el tensor Q, o en otras palabras, asignarle destinos a cada una de las salidas de la maquina.
Para esta primera aproximación a la solución, encontré que la mejor manera era ir tomando datos del mas grande al mas chicos de la serie Df_Group y empezar a asignar a los distintos sectores de la siguiente manera (imaginemos que hubiese 4 sectores) 1, 2 ,3,4–4,3,2,1–1,2,3,4…
#Completo los destinos
sector = 0
destino = 0
multiplo = 1
for i in Df_Group.index[:]:
if sector == 14:
sector = 13
destino = destino + 1
multiplo = -1
if sector == -1:
sector = 0
destino = destino + 1
multiplo = 1
Q[sector][destino] = Df_Group[i] #Agrego la cantidad de paquetes de ese destino
Names[sector][destino] = i #Agrego el nombre de ese destino
sector = sector + (1*multiplo) #Cambio de sector para elegir el siguiente valor (El multiplo sirve para saber si bajo o subo)Por ultimo una vez que tengo Q completo, calculo las medias de cada sector y la media de las medias para luego calcular la diferencia entre el mayor-media y menor-media.
Un breve paréntesis, es que como no use np.array, tuve que definir la función “media” yo mismo dentro del programa.
def mean(vect):
sum = 0
for i in vect:
sum = sum + i
mean = sum / len(vect)
return (mean)medias = [] #Genero un vector con las medias de cada sector
for i in Q:
medias.append(mean(i))
print("************")
print(f'Vector de medias: {medias}')
mediademedias = mean(medias)
print("media de medias: " + str(mediademedias))
print(f'Dispersion positiva: {((max(medias) - mediademedias)/mediademedias)*100} % Dispersion Negativa {((mediademedias- min(medias) )/mediademedias)*100}% ')
total = 0
for i in Q:
total = total + sum(i)
print(f'suma de paquetes {total}')
print(f'Rampas {Q}')
print("***********")
Es importante chequear en todo momento que la sumatoria de la cantidad de paquetes de la primer serie sea igual a la sumatoria de la cantidad de paquetes de Q. O sea, que no estemos “olvidándonos” algún destino.
El ploteo de las medias queda entonces:
Como resultado tenemos que el alejamiento de la media es para el sector mas cargado +20% y para el sector menos cargado -5%
Ahora empieza el proceso de optimización:
- Hice muchas pruebas hasta encontrar la mejor forma y computacionalmente mas barata
- No documente todas, simplemente me fui quedando con los mejores resultados y realizando pruebas exhaustivas sobre los mismos.
El proceso de optimización “CORE” esta definido en la siguiente funcion:
def exchange (v1,v2):
print("Inicio Cambio")
mayor = sum(v1) #To do el tiempo estoy chekeando cual es el mas grande, para no tener problemas de orden
v2 = v2[::-1] #Lo pongo de menor a mayor
menor = sum(v2)
print(f' Estado inicial: {mayor, v1,menor,v2} Tota: {mayor + menor}')
Inicial = (mayor - menor)/mayor #Guardo la dispersion inicial
Vtemp1 = v1 #Tomo vectores temprarios para poder mantener v1 y v2 como los vectores que estan bien cambiados, y en caso de necesitar volver a ellos
Vtemp2= v2
guardado = -1 #Este es el valor de k (iteracion sobre el vector mas pequeño) que se guarda, para siempre arrancar desde ahi
for i in range(len(Vtemp1)):
condicion = True
k = guardado #Aca retomo el valor guardado siempre de k
while condicion == True and k < 8:
k = k + 1
if Vtemp2[k]<Vtemp1[i]: #Si el valor del vector menor es MENOR al valor del vector MAYOR => hago el cambio
temp = Vtemp2[k]
Vtemp2[k] = Vtemp1[i]
Vtemp1[i] = temp
#print(k)
if sum(Vtemp1) > sum(Vtemp2): #Si el vector mayor sigue siendo el mayor entonces el cambio que hicimos esta OK y lo guardamos en v1 y v2
v1 = Vtemp1
v2 = Vtemp2
condicion = False #Como el cambio que hicimos esta OK, podemos saltar al proximo valor del vector mayor
guardado = k #Como sacamos un valor del vector menor, empezaremos de este mismo para seguir mejorando
else:
temp = Vtemp1[i] #En caso de que nuestro vector menor haya pasado a ser mayor, entonces volvemos para atras, la operacion
Vtemp1[i] = Vtemp2[k]
Vtemp2[k] = temp
return (v1,v2)La función esta Extracomentada ya que itere varias veces sobre el código para dar con la mejor manera. A rasgos generales, lo que computa es:
- Recibe 2 vectores de igual tamaño, el primero debe ser el mayor y el segundo el menor (V1-V2)
- El menor lo da vuelta
- Genero vectores temporarios, donde voy a trabajar
- Empiezo a iterar entre los vectores - siempre comparo cada valor de v1 con todos los de v2 hasta encontrar un posible cambio. El cambio lo realizo únicamente si: 1) el valor de v1 es mayor al de v2 2)el cambio no produce que v2>v1
- Cada vez que hago un cambio, guardo el cambio en Vx desde Vtempx
- Devuelvo los vectores con sus cargas redistribuidas
En cuanto a como activar la función exchange, se realiza con el siguiente código.
f = 0
b = 0
for j in range(500):
TdR = [0,1,2,3,4,5,6,7,8,9,10,11,12,13] #Tensor de rampas - Nombre de los sectores para ir cambiando aleatoriamente
f = random.choice(TdR)
b = random.choice(TdR)
if f != b :
if sum(Q[f]) > sum(Q[b]):
Q[f],Q[b] = exchange(Q[f],Q[b])
else:
Q[b], Q[f] = exchange(Q[b], Q[f])Lo único que hay que tener en cuenta acá es:
- Asegurarme de que B y F sean distintos, ya que si no empiezo a “perder” destinos
- Asegurarme de poner en orden los vectores (O sea que v1 sea el mayor) ya que es un MUST de la función exchange
El resultado depende de la capacidad computacional del equipo, pero 500 iteraciones me termina dando una media mas que aceptable del siguiente tipo :
Donde la diferencia entre el mayor y la media es del 2% y la del menor también.
Disclaimer: El sistema esta optimizado para un set de datos fijo, y en mi experiencia ante tantas iteraciones esta “OverFitted”. Por lo que cuando el set de datos cambie, o influya la variabilidad natural de la carga de trabajo las diferencias no se mantendrán en el 2%.
Por ultimo, ahora ya tenemos que destinos tenemos por sector, pero nos falta como ordenamos los destinos en cada sector. Luego de ver los siguientes gráficos nos damos cuenta que aunque la variabilidad media es igual por sector, la variabilidad por destinos es, obviamente, independiente.
En la implementación que estamos realizando particularmente, es físicamente conveniente que la mayor carga de trabajo este en las rampas del medio, por lo que reordenamos los destinos por rampa de forma normalizada y obtenemos:
El código para realizar la distribución por sector es el siguiente:
#Me genera una "distribucion Normal" de las salidas (CUIDADO AL AGREGAR MAS SALIDAS)
def normalize(v1):
Vfinal = []
indices = [8, 6, 4, 2, 1, 3, 5, 7, 9]
for i in indices:
Vfinal.append(v1[i - 1])
return (Vfinal)final = [] #Este es el vector que reemplaza a Q, y tiene los vectores de forma Normal
for i in Q:
final.append(normalize(i))
Para terminar lo que tenemos que hacer es matchear la cantidad de envíos con el nombre del destino, y llenar el tensor Names.
for i in range(len(final)):
for n in range(len(final[i])):
Names[i][n] = Df_Group[Df_Group == final[i][n]].index.tolist()
for i in Names:
print(i)Lo que nos permite esta manera de matcheo, es que en caso de que varios destinos tengan la misma cantidad de paquetes, poder elegir manualmente o por algún otro criterio, cual ira a cada salida física.
Sector 1: [['Destino 12 '], ['Destino 21'], ['Destino 33'], ['Destino 42'], ['Destino 126'], ['Destino 13'], ['Destino 78'], ['Destino 90'], ['Destino 94', 'Destino 76']]Como vemos el sector 1, puede elegir que el destino de su ultima rampa sea 94 o 76, mientras que otro sector se quedara con la restante.
Nos quedara por resolver ahora, si esta solución matemáticamente correcta, es operacionalmente compatible, o si existen casos donde tengamos que inmiscuirnos un poco mas y hacer cambios manuales. Sin embargo haber pasado de 3x10 ^133 posibilidades, a tal vez, algunas decenas, parece ser una mejora significativa
