Optimización de Rutas de Distribución mediante CVRP Multiproducto en la Comercializadora de granos JS

Oscar David Maturana Muñoz
Angel Luis Durango Padilla
Jovvanis Andres Petro Maldonado
Alan David Petro Hernandez
Jose Julian Pacheco Diaz

🚛 Descripción del problema

La empresa Comercializadora de Granos JS S.A.S distribuye productos agrícolas como maíz amarillo, maíz amarillo trillado y maíz blanco trillado en el municipio de Cereté, Córdoba.

Sin embargo, presenta: - Retrasos en las entregas. - Altos costos logísticos. - Rutas no planificadas y uso ineficiente de la flota.

Objetivo: Desarrollar un modelo matemático de optimización basado en el CVRP multiproducto que minimice la distancia total recorrida.

📦 Datos del modelo

  • Matriz de distancias (km): Calculada con coordenadas de clientes vía Python. Distancias
  • Demanda de productos: Maíz amarillo, amarillo trillado y blanco trillado.
  • Capacidad de vehículos: Medida en bultos de 50 kg.
Vehículo Capacidad (bultos)
V1 100
V2 100
V3 80

Estos datos permiten parametrizar el modelo para generar escenarios y analizar impacto en costos y puntualidad.

⚙️ Formulación del modelo matemático

Conjuntos

  • \(I\): Nodos (0 = Bodega)
  • \(C\): Clientes (C = I  {0})
  • \(K\): Vehículos
  • \(P\): Productos

Parámetros

  • \(c_{ij}\): Distancia entre nodos i y j
  • \(d_{jp}\): Demanda del cliente j del producto p
  • \(Q_{k}\): Capacidad total del vehículo k
  • \(M_{p}\): Big-M para producto \(p\)

Variables de decisión

  • \(x_{ijk} = \begin{cases} 1 & \text{si el vehículo } k \text{ viaja de } i \text{ a } j \\ 0 & \text{en otro caso} \end{cases}\)
  • \(y_{ikp}\): Carga del producto p en el vehículo k al llegar al nodo i
  • \(u_{ik}\): Variable auxiliar para eliminación de subtours

📈 Función objetivo

Minimizar la distancia total recorrida por la flota de vehículos:

\[\min \sum_{i \in I} \sum_{j \in I} \sum_{k \in K} c_{ij} \cdot x_{ijk}\]

🧩 Restricciones (1/3)

  1. Visita Única a Clientes: \[\sum_{i \in I} \sum_{k \in K} x_{ijk} = 1 \quad \forall j \in C\]

  2. Conservación de Flujo: \[\sum_{i \in I} x_{ijk} = \sum_{j \in I} x_{jik} \quad \forall k \in K, \forall i \in I\]

  3. Salida y Entrada a la bodega: \[\sum_{j \in C} x_{0jk} \le 1 \quad \forall k \in K\] \[\sum_{i \in C} x_{i0k} \le 1 \quad \forall k \in K\]

🧩 Restricciones (2/3)

  1. Capacidad del Vehículo: \[\sum_{p \in P} y_{ikp} \le Q_k \quad \forall i \in I, \forall k \in K\]

  2. Balance de Carga: \[y_{jkp} \ge y_{ikp} - d_{pj} + M_p(x_{ijk} - 1) \quad \forall k \in K, \forall p \in P, \forall i \in I, \forall j \in C, i \ne j\] \[y_{jkp} \le y_{ikp} - d_{pj} + M_p(1 - x_{ijk}) \quad \forall k \in K, \forall p \in P, \forall i \in I, \forall j \in C, i \ne j\]

  3. Carga Solo en Nodos Visitados: \[y_{jkp} \le M_p \cdot \sum_{i \in I} x_{ijk} \quad \forall k \in K, \forall p \in P, \forall j \in C\]

🧩 Restricciones (3/3)

  1. Límite de Carga Inicial: \[y_{0kp} \le M_p \quad \forall k \in K, \forall p \in P\]

  2. Eliminación de Subtours (MTZ): \[u_{ik} - u_{jk} + C \cdot x_{ijk} \le C - 1 \quad \forall k \in K, \forall i, j \in C, i \ne j\]

  3. Satisfacción de Demanda: \[y_{0kp} \ge \sum_{j \in C} d_{pj} \cdot \sum_{i \in I} x_{ijk} \quad \forall k \in K, \forall p \in P\]

  4. No Negatividad: \[y_{jkp} \ge 0 \quad \forall k \in K, \forall p \in P, \forall j \in C\]

\[x_{ijk} \in \{0,1\} \quad \forall i\in I, j \in C, k\in K\]

📊 Datos de demanda

Tabla de Demanda por Punto y Producto:

Cliente Maíz Amarillo Amarillo Trillado Maíz Blanco
0 0 0 0
1 5 3 10
2 0 0 10
3 4 9 1
4 3 3 0
5 8 0 3
6 0 5 4
7 5 2 3
8 5 7 0
9 10 0 0
10 0 4 5
11 5 0 5
12 0 10 2
13 2 3 0
14 0 5 2
15 4 3 0
16 5 0 5
17 6 0 0
18 3 6 0
19 0 4 3
20 2 5 0
21 4 0 2
22 2 4 6
23 4 0 5
24 4 0 2
25 0 10 0
26 4 5 2
27 4 3 2
28 0 6 2
29 4 5 2
30 5 0 2

🗺 Distancia recorrida y Rutas Óptimas

El valor objetivo dado por la solucion del modelo es:

\(38.11 \quad\text{Kilometros }\)

Ruta óptima para cada vehículo:

  • Vehículo 1: \(0 \rightarrow 2 \rightarrow 8 \rightarrow 4 \rightarrow 3 \rightarrow 25 \rightarrow 16 \rightarrow 9 \rightarrow 12 \rightarrow 28 \rightarrow 15 \rightarrow 0\)
  • Vehículo 2: \(0 \rightarrow 14 \rightarrow 19 \rightarrow 30 \rightarrow 23 \rightarrow 7 \rightarrow 5 \rightarrow 6 \rightarrow\)
    \(22 \rightarrow 18 \rightarrow 17 \rightarrow 21 \rightarrow 20 \rightarrow 0\)
  • Vehículo 3: \(0 \rightarrow 29 \rightarrow 24 \rightarrow 27 \rightarrow 10 \rightarrow 1 \rightarrow 11 \rightarrow 26 \rightarrow 13 \rightarrow 0\)

Visiualizacion Ruta 1

📍 Visualización Ruta 2

Visualizacion ruta 3

Distribucion de cargas por vehiculo y producto

Cuadro 3: Carga inicial por vehículo y producto
Vehículo Maíz Amarillo Maíz Amarillo Trillado Maíz Blanco
V1 31 49 20
V2 39 31 30
V3 28 23 29

Comportamiento del vehiculo 1

Cliente Maíz Amarillo Maíz Amarillo Trillado Maíz Blanco
0 31 49 20
2 31 49 10
8 26 42 10
4 23 39 10
3 19 30 9
25 19 20 9
16 14 20 4
9 4 20 4
12 4 10 2
28 4 4 3
15 0 1 0
0 0 0 0

Comportamiento del vehiculo 2

Cliente Maíz Amarillo Maíz Amarillo Trillado Maíz Blanco
0 39 31 30
14 39 26 28
19 39 22 25
30 34 22 23
23 30 22 18
7 25 20 15
5 17 20 12
6 17 15 8
22 15 11 2
18 12 5 2
17 6 5 2
21 2 5 0
20 0 0 0
0 0 0 0

Comportamiento del vehiculo 3

Cliente Maíz Amarillo Maíz Amarillo Trillado Maíz Blanco
0 28 23 29
29 24 18 27
24 20 18 25
27 16 15 23
10 16 11 18
1 11 8 8
11 6 8 3
26 2 3 1
13 0 0 1
0 0 0 0

Conclusiones

la implementación del modelo de optimización CVRP multiproducto en la empresa Comercializadora de Granos JS S.A.S. permitió mejorar significativamente la eficiencia en la distribución de productos. El modelo logró minimizar las distancias recorridas, equilibrar las cargas entre los vehículos y satisfacer la demanda de todos los clientes sin superar las capacidades de transporte.

Esto se traduce en reducción de costos logísticos, mejores tiempos de entrega y mayor aprovechamiento de los recursos disponibles. Además, el modelo proporciona una herramienta analítica que facilita la planificación y la toma de decisiones operativas basadas en datos, representando una alternativa práctica y escalable para optimizar la logística de distribución en la empresa.