Supply Chain Design con Optimización lineal en Python

Supongamos que una empresa que tiene presencia en 12 ciudades diferentes ha decidido que es momento de abrir sus propios centros de distribución. Sin embargo, existen 5 localidades en donde sería viable implementarlos. ¿Cómo escoger la opción de mayor costo-efectividad?. Este tipo de situaciones han sido ampliamente abordadas en la Investigación de Operaciones usando Programación Lineal. En este tutorial mostraré como implementar este tipo de modelos matemáticos usando Python, de manera concisa y fácilemnte escalable.

Para contextualizar, la progrmación lineal u optimización lineal es una técnica usada para encontrar los mínimos o máximos de una función lineal. Muchas decisiones de interés comercial pueden ser planteadas de esta manera, como por ejemplo la formulación de alimentos balanceados, distribución de la capacidad de producción, entre otras.

Específicamente, un modelo de programación lineal requiere definir una función objetivo y de restricciones para delimitar las posibles soluciones. En nuestro caso, buscamos minimizar el costo de transporte a partir de la apertura de centros de distribución, siempre y cuando permitan atender adecuadamente la demanda de los clientes en 12 diferentes ciudades. A continuación explicaré como plantear el problema y resolverlo usando Python.

Los paquetes que vamos a utilizar son Numpy, Pandas y PuLP. Adicionalmente, el notebook y los datos usados para el ejercicio pueden descargarse en el siguiente enlace:

Comenzamos con la importación de los paquetes necesarios:

import pandas as pd
import pulp
import numpy as np        

A continuación usaremos pandas para leer el archivo excel que contiene los datos de la ubicación y capacidad de los centros de distribución, la demanda y ubicación de los clientes, y las distancias entre clientes y centros de distribución, así como los costos fijos de operación y costos variables de transporte.

archivo = 'facility_location.xlsx'
df = pd.ExcelFile(archivo)
names = df.sheet_names        

La variable 'names' contiene los datos de todas las hojas del archivo excel. Para facilitar las cosas, crearemos un diccionario con los nombres de las hojas como 'keys' y los datos como valores. Posteriormente, convertiremos la información en listas o 'arrays' dependiendo la necesidad.

information = {k: df.parse(k, index_col=0) for k in names}

centros_distri = information['Oferta'].index.tolist()

fábricas = information['Demanda'].index.tolist()

capacity = dict(information['Oferta']['Capacidad'])

demand = dict(information['Demanda']['Cantidad'])

d = np.array(information['Distancias'].values)

cKm = np.array(information['Costo km'].values)

# Crear una matriz de costo de transporte multiplicando distancias por costo km
x = d * cKm

y = information['Oferta']['Costo fijo'].values

cost = np.array([])
for n in range(5):
    cost = np.concatenate((cost, x[:, n]))
}        

Lo que sigue es crear una lista de pares que representen la ruta que conecta los centros de distribución con los puntos de consumo usando 'lists comprehension', para posteriormente tabular cada ruta con su respectivo costo. Además, creamos un diccionario para relacionar a los centros de distribución con sus costos fijos de operación.

pairs = [(i, j) for i in centros_distri for j in fábricas]

price_per_route = {k: v for k, v in zip(pairs, cost)}

fixed_cost = {k: v for k, v in zip(centros_distri, y)}        

Como señalamos, la intención de nuestro modelo es minimizar el costo de transporte considerando la posibilidad de abrir uno o más centros de distribución (CD) para satisfacer la demanda, lo que se puede representar en la siguiente función:

El primer término de la ecuación es la sumatoria del costo por km multiplicado por la cantidad transportada, y el segundo término corresponde a la sumatoria del costo fijo de operación de un centro de distribución por la variable binaria Y, que es 0 en caso de que el centro sea descartado y 1 si se implementa. Tanto la cantidad transportada como la variable binaria son las variables de decisión.

Teniendo en cuenta todo lo anterior, continuaremos con la formulación del modelo propiamente dicha. En este punto es importante resaltar brevemente la ventaja de usar PuLP para el problema de optimización, en detrimento de otras opciones como scipy.optimize, ya que PuLP permite trabajar con funciones con varios términos, es decir, podemos agregar más definiciones a la ecuación que modela nuestro problema, en este caso, la función del costo de operación.

El primer paso consiste en crear una variable (model) que es una instancia de la clase pulp.LpProblem. Aquí especificaremos el nombre del modelo y el tipo de otpmización (minimizar). A continuación definiremos las variables de decisión, por una parte la cantidad transportada desde los CD a los clientes, y por otra parte la decisión de abrir o no el CD. El planteamiento termina cuando incluimos en el modelo la función que pretendemos minimizar, tal como lo describimos en notación matemática.

model = pulp.LpProblem('Supply_cost_minimization', sense=pulp.LpMinimize)

route = pulp.LpVariable.dicts('cdist_fbrca', pairs, lowBound=0, cat='Integer')

c_dist = pulp.LpVariable.dicts('cdist', centros_distri, cat='Binary')

model += pulp.lpSum([price_per_route[i] * route[i] for i in pairs]
                     + [fixed_cost[i] * c_dist[i] for i in centros_distri])
        

Por lo general los modelos de programación lineal buscan la solución óptima de la función objetivo, sin que las variables de decisión excedan ciertos límites denominados restricciones o condicionantes. En el ejemplo en cuestión, las restricciones implican que la cantidad despachada de cualquier centro de distribución sea igual o menor a su capacidad, que la cantidad que llega a los clientes sea igual o mayor a su requerimiento, el número de centros debe ser por lo menos 1 y no más de 5. A estos condicionantes debemos agregar dos más: todos los valores deben ser números positivos, y como ya mencioné, la variable Y solo puede tomar el valor de 0 o 1.

Por último, incluiremos una importante restricción denominada restricción de conexión, que fuerce al modelo a satisfacer la demanda de los clientes únicamente desde los centros que están en operación. Esto se consigue con la inecuación final que señala que la cantidad transportada debe ser menor a la multiplicación de un número arbitrario (M) por la variable binaria, esto se traduce en que si un CD no será abierto (variable binaria igual a 0) la desigualdad no se cumple y por tanto esa opción se descarta.

M = information['Demanda']['Cantidad'].sum()*10
num_max_cent = 5
num_min_cent = 1

for i in centros_distri:
    model += pulp.lpSum(route[(i, j)] for j in fábricas) <= capacity[i]
    
for j in fábricas:
    model += pulp.lpSum(route[(i, j)] for i in centros_distri) >= demand[j]

for k in route.keys():
    model += route[k] - M*c_dist[k[0]] <= 0

model += sum(c_dist.values()) >= 1
model += sum(c_dist.values()) <= 5        

Lo que resta es resolver el modelo y averiguar si se econtró una solución factible(que respete las restricciones y cumpla con el objetivo). En caso que la respuesta sea óptima, continuaremos con la visualización de las cantidades transportadas y sus puntos de origen y destino.

model.solve()
pulp.LpStatus[model.status]

total_cost = pulp.value(model.objective)
print(f'El costo mínimo de transporte y operación es {total_cost}')

for v in model.variables():
    if v.varValue > 0:
        print(v.name, v.varValue)
        

Consideraciones finales

En este tutorial analizamos como resolver un problema de optimización usando el paquete PuLP de Python, que permite trabajar con funciones objetivo compuestas por varios términos, como en el caso del diseño de redes de distribución en donde se debe tener en cuenta costos variables de transporte, así como costos fijos de operación. Si bien el ejemplo trabajado abarca un número relativamente pequeño de variables, la forma en la que programamos la solución permite que sea fácilmente escalable, ya que lo único que deberíamos modificar sería el archivo que contiene los datos.

Finalmente, este tipo de modelos de optimización pueden ser ampliados para asemejarse más a situaciones reales al incluir la existencia de inventarios y mayor número de productos.