Problemas combinatorios, heurísticas y metaheurísticas

Problemas de optimización.

En el contexto científico la optimización es el proceso de tratar de encontrar la mejor solución posible para un determinado problema. En un problema de optimización existen diferentes soluciones, un criterio para discriminar entre ellas y el objetivo es encontrar la mejor. De forma más precisa, estos problemas se pueden expresar como encontrar el valor de unas variables de decisión para los que una determinada función objetivo alcanza su valor máximo o mínimo. El valor de las variables en ocasiones está sujeto a unas restricciones.

Se pueden encontrar una gran cantidad de problemas de optimización estudiados clásicamente en ingeniería industrial y aplicados a problemas o decisiones logísticas (servicio al cliente o procesamiento de pedidos, inventarios, transporte y localización).

1. Problemas de asignación de recursos (AP = Assignment Problem).

Problema clásico de optimización cuyo propósito es hallar la forma de asignar un conjunto \(I\) de recursos disponibles (personas, máquinas, robots, computadores, instalaciones…) para la realización de un conjunto \(J\) de actividades o de lugares (puestos de trabajo, operaciones productivas, tareas de ensamble, tareas computacionales… ) al menor costo posible y suponiendo que cada recurso se destina a una única actividad o lugar y que cada actividad o lugar solo puede ser ejecutada por por uno de los recurso. Se supone, por tanto que el número de recursos disponibles es igual al número de actividades a realizar o de lugares a ocupar, siendo tal número igual a \(n= |I| = |J|\).

Por ejemplo, suponga un AP con \(n=4\), como se observa en la siguiente figura:

El número de asignaciones posibles es \(4!=24\).

El AP en cuestión, a pesar de la simpleza de su enunciado, tiene numerosas aplicaciones prácticas dentro de la Ingeniería Industrial, y específicamente dentro de las decisiones logísticas, ya que lo de tener que decidir cómo repartir unidades de recursos productivos entre unidades de actividades productivas, cuando los costos de asignación son lineales o pueden suponerse como tales, forma parte de muchas decisiones habituales en la prácticas. Entre las aplicaciones del problema de asignación se encuentran las siguientes:

  • Asignar instalaciones a localizaciones.

  • Asignar cuotas de producción de fábricas a centros de distribución con demanda.

  • Asignar stocks de productos a almacenes.

  • Emparejar vehículos con rutas de reparto o de recogida.

  • Definir dónde instalar bodegas para e-commerce

  • Asignar centros de distribución a regiones.

El AP se puede formular matemáticamente como sigue:

  • Conjuntos

    • \(I\): conjunto de recursos, \(I=\{1,2,...,n \}\)
    • \(J\): conjunto de actividades o lugares, \(J=\{1,2,...,n \}\)

Se supone que: \(|I| = |J| = n\)

  • Parámetros

\(c_{ij}\): costo de asignar el recurso \(i \in I\) a la actividad o lugar \(j \in J\).

  • Variables de decisión

\[\begin{align} x_{ij} = \begin{cases} 1:~ \text{si el recurso } i \text{se asigna a actividad o lugar } j \\ 0:~ \text{dlc } \end{cases} \end{align}\]

  • Función objetivo

\[ min Z = \sum_{i \in I} \sum_{j \in J} c_{ij}x_{ij} \]

  • Restricciones

Cada recurso se asigna a una única actividad o lugar:

\[ \sum_{j \in J} x_{ij} = 1~~~ \forall i \in I \]

Cada actividad o lugar recibe un único recurso:

\[ \sum_{i \in I} x_{ij} = 1~~~ \forall j \in J \]

Naturaleza de la variable

\[ x_{ij} \in \{0,1 \} ~~~ \forall i \in I, j \in J \]

Ejemplo problema AP en R

Una empresa planea ubicar 4 fábricas en 4 parques industriales disponibles. Cada combinación fábrica–parque tiene un costo logístico anual estimado, que incluye:

  • transporte a mercados,

  • acceso a proveedores,

  • costos operativos del parque industrial.

Los costos asociados (en millones de pesos/año) son los siguientes:

Fábrica/Parque P1 P2 P3 P4
F1 14 5 8 7
F2 2 12 6 5
F3 7 8 3 9
F4 2 4 6 10

El modelo matemático sería

Conjuntos

  • \(I= \{1,2,3,4 \}\): fábricas
  • \(J= \{1,2,3,4 \}\): parques industriales

Parámetro

\(c_{ij}\): costo de ubicar fábrica \(i \in I\) en el parque industrial \(j \in J\) (Tabla de costos).

Variable de decisión

\[\begin{align} x_{ij} = \begin{cases} 1:~ \text{si la fábrica } i \text{se asigna al parque industrial } j \\ 0:~ \text{dlc } \end{cases} \end{align}\]

  • Función objetivo

\[ min Z = \sum_{1}^4 \sum_{1}^4 c_{ij}x_{ij} \]

  • Restricciones

Cada fábrica se asigna a un solo parque industrial:

\[ \sum_{1}^4 x_{ij} = 1~~~ \forall i \in I \]

Cada parque industrial recibe una única fábrica:

\[ \sum_{1}^4 x_{ij} = 1~~~ \forall j \in J \]

Naturaleza de la variable

\[ x_{ij} \in \{0,1 \} ~~~ \forall i \in I, j \in J \]

Librerías necesarias
# Cargar librerías
library(ompr)
library(ompr.roi)
library(ROI)
library(ROI.plugin.symphony)
library(magrittr)
Definición de datos
# Parámetro costos
costos <- matrix(c(14, 5, 8, 7, 2, 12, 6, 5, 7, 8, 3, 9, 2, 4, 6, 10),
  nrow = 4,
  byrow = TRUE
)

n <- nrow(costos)
Modelo
# Modelo
modelo <- MIPModel() %>%
  
  # Variable binaria x[i,j]
  add_variable(x[i, j], i = 1:n, j = 1:n, type = "binary") %>%
  
  # Función objetivo
  set_objective(
    sum_expr(costos[i, j] * x[i, j], i = 1:n, j = 1:n),
    "min"
  ) %>%
  
  # Cada fábrica a un solo polígono
  add_constraint(
    sum_expr(x[i, j], j = 1:n) == 1,
    i = 1:n
  ) %>%
  
  # Cada polígono recibe una sola fábrica
  add_constraint(
    sum_expr(x[i, j], i = 1:n) == 1,
    j = 1:n
  )
Resolver con solver
# resultado 
resultado <- solve_model(
  modelo,
  with_ROI(
    solver = "symphony",
    verbosity = 1
  )
)
Extracción de la solución
# extracción de la solución
solucion <- get_solution(resultado, x[i, j]) %>%
  dplyr::filter(value > 0.5)
solucion