Extensiones al problema de transporte: Limitación a los flujos entre nodos, modo de transporte, flujo mínimo entre origen-destino
Yelky Castro Jiménez
Víctor Mario Noble Ramos
2022-08-22
1 Problema básico
El problema de transporte puede ser formulado matemáticamente así:
1.1. Conjuntos.
\(O:=\) Conjunto de orígenes, \(\: i \in \{1, 2, ... ,n\}\)
\(D:=\) Conjunto de destinos, \(\: j \in \{1, 2, ... ,m\}\)
1.2. Parámetros.
\(d_{j}:=\) Demanda del destino j, \(j \in D\)
\(k_{i}:=\) Capacidad del origen i, \(i \in O\)
\(c_{ij}:=\) Costo de trasportar una unidad desde el origen i, al destino j, \(i \in O, j \in D\).
1.3. Variables de decisión.
- \(x_{ij}:=\) Cantidad de unidades a transportar desde el origen i, al destino j, \(i \in O, j \in D\\\)
1.4. Función objetivo.
\[ Min \: C_{Total}= \sum_{i \ \in \ O}\sum_{j \ \in \ D} c_{ij} \times x_{ij} \]
1.5. Restricciones.
1.5.1. Cumplimiendo de la demanda: Para cada destino \(j\) se debe satisfacer la demanda en su totalidad por la oferta de todos los orígenes \(i\).
\[\sum_{i \in O} x_{ij} = d_j, \: \forall \: j \in D\] 5.2. Limitación de la capacidad: La cantidad de unidades enviadas desde cada origen \(i\) hacia todos los destinos \(j\) no debe exceder a su capacidad.
\[\sum_{j \in D} x_{ij} \leq k_i, \: \forall \:i \in O\] 1.5.3. Dominio de variables: La cantidad unidades enviadas desde los origenes \(i\) hacia los destinos \(j\) debe ser un un numero real positivo \({\mathbb R}^{+}\).
\[ x_{ij} \geq 0 \: \: \forall \: i \in O, j \in D\]
2 Extensión limitación a los flujos entre nodos.
Se debe considerar el problema basico adicionando que entre cada posible conexión entre los nodos existe una capacidad máxima de flujo. Por lo anterior se debe crear un nuevo parametro que determine la capacidad máxima de tansmisión a través de la arista o conexión \((i,j)\).
El problema de transporte bajo la extensión “limitacion a los flujos entre nodos” puede ser formulado matemáticamente así:
2.1. Conjuntos.
\(O:=\) Conjunto de orígenes, \(\: i \in \{1, 2, ... ,n\}\)
\(D:=\) Conjunto de destinos, \(\: j \in \{1, 2, ... ,m\}\)
2.2. Parámetros.
\(d_{j}:=\) Demanda del destino j, \(j \in D\)
\(k_{i}:=\) Capacidad del origen i, \(i \in O\)
\(c_{ij}:=\) Costo de trasportar una unidad desde el origen i, al destino j, \(i \in O, j \in D\).
\(F_{ij}:=\)capacidad máxima de tansmisión a través de la arista o conexión \((i,j)\).
2.3. Variables de decisión.
- \(x_{ij}:=\) Cantidad de unidades a transportar desde el origen i, al destino j, \(i \in O, j \in D\\\)
2.4. Función objetivo.
\[ Min \: C_{Total}= \sum_{i \ \in \ O}\sum_{j \ \in \ D} c_{ij} \times x_{ij} \]
2.5. Restricciones.
2.5.1. Cumplimiendo de la demanda: Para cada destino \(j\) se debe satisfacer la demanda en su totalidad por la oferta de todos los orígenes \(i\).
\[\sum_{i \in O} x_{ij} = d_j, \: \forall \: j \in D\] 2.5.2. Limitación de la capacidad: La cantidad de unidades enviadas desde cada origen \(i\) hacia todos los destinos \(j\) no debe exceder a su capacidad.
\[\sum_{j \in D} x_{ij} \leq k_i, \: \forall \:i \in O\]
2.5.3. Limitación al flujo: La cantidad de unidades que se envien desde el nodo origen \(i\) hacia el nodo destino \(j\), no debe sobrepasar el flujo maximo permitido.
\[x_{ij} \leq F_{ij} \: \: \forall \: i \in O, j \in D\]
2.5.4. Dominio de variables: La cantidad unidades enviadas desde los origenes \(i\) hacia los destinos \(j\) debe ser un un numero real positivo \({\mathbb R}^{+}\).
\[ x_{ij} \geq 0 \: \: \forall \: i \in O, j \in D\]
3 Extensión modos de transporte
Se debe considerar el problema basico adicionando que no habrá un unico medio de transporte sinó multibles medios de transporte, y cuyo costo de envio será variable dependiendo el modo donde sea transportado. Por lo anterior se hace necesario crear un conjunto de modos de transporte y se debe indexar en el parámetro de costo y en las variables el nuevo indice que relaciona el modo de transporte
El problema de transporte bajo la extensión multimodal puede ser formulado matemáticamente así:
3.1. Conjuntos.
\(O:=\) Conjunto de orígenes, \(\: i \in \{1, 2, ... ,n\}\)
\(D:=\) Conjunto de destinos, \(\: j \in \{1, 2, ... ,m\}\)
\(M:=\) Conjunto de modos de transporte, \(\: k \in \{1, 2, ... ,l\}\)
3.2. Parámetros.
\(d_{j}:=\) Demanda del destino j, \(j \in D\)
\(Cap_{i}:=\) Capacidad del origen i, \(i \in O\)
\(c_{ijk}:=\) Costo de transportar una unidad desde el origen i, al destino j, en el modo de transporte k \(i \in O, j \in D, k \in M\).
3.3. Variables de decisión.
- \(x_{ijk}:=\) Cantidad de unidades a transportar desde el origen i, al destino j, en el modo de transporte k, \(i \in O, j \in D, k \in M\\\)
3.4. Función objetivo.
\[ Min \: C_{Total}= \sum_{i \ \in \ O}\sum_{j \ \in \ D} \sum_{k \ \in \ M} c_{ijk} \times x_{ijk} \]
3.5. Restricciones.
3.5.1. Cumplimiendo de la demanda: Para cada destino \(j\) se debe satisfacer la demanda en su totalidad por la oferta de todos los orígenes \(i\).
\[\sum_{i \in O}\sum_{k \ \in \ M} x_{ijk} = d_j, \: \forall \: j \in D\] 3.5.2. Limitación de la capacidad: La cantidad de unidades enviadas desde cada origen \(i\) hacia todos los destinos \(j\) no debe exceder a su capacidad.
\[\sum_{j \in D}\sum_{k \ \in \ M} x_{ijk} \leq Cap_i, \: \forall \:i \in O\] 3.5.3. Dominio de variables: La cantidad unidades enviadas desde los origenes \(i\) hacia los destinos \(j\) debe ser un un numero real positivo \({\mathbb R}^{+}\).
\[ x_{ijk} \geq 0 \: \: \forall \: i \in O, j \in D, k \in M\]
Observación 1: Si existe un parámetro asociado al límite de carga/transmisión por medio de transporte se debe adicionar una restricción de capacidad en la flota de transporte.
- \(Lim_k:=\) Capacidad maxima de el modo de transporte k, \(k \in M\).
3.5.4. Capacidad del modo de transporte: La cantidad de envio que se realice desde el nodo origen \(i\) al nodo destino \(j\) no debe sobrepasar la capacidad del modo de tranporte \(k\).
$$x_{ijk} \leq Lim_k \: \: \forall \: i \in O, j \in D, k \in M$$ 4 Extensión Flujo mínimo entre orígen - destino.
El problema considera las mismas condiciones iniciales del problema base, adicionalmente se debe garantizar un número minimo de unidades transportadas, si se decide que un origen atendera cierto destino (\(Min\)). Para lo anterior es necesario definir una nueva variable binaria que determine el estado de atención de un destino por parte de un origen.
\[y_{ij}:= \left\{\begin{matrix} 1, \ si \ el \ destino \ j \ es \ atendido \ por \ el \ origen \ i, \ i \in O, j \in D \\ 0, \ en \ caso \ contrario \end{matrix}\right.\]
¿ Que queremos modelar?
\[ \begin{matrix} Si \ y_{ij}=1 \rightarrow x_{ij}\geq Min \\ Si \ y_{ij}=0 \rightarrow x_{ij}=0 \ \ \ \ \ \ \ \end{matrix}\]
El problema de transporte bajo la extensión Flujo mínimo entre orígen - destino puede ser formulado matemáticamente así:
4.1. Conjuntos.
\(O:=\) Conjunto de orígenes, \(\: i \in \{1, 2, ... ,n\}\)
\(D:=\) Conjunto de destinos, \(\: j \in \{1, 2, ... ,m\}\)
4.2. Parámetros.
\(d_{j}:=\) Demanda del destino j, \(j \in D\)
\(k_{i}:=\) Capacidad del origen i, \(i \in O\)
\(c_{ij}:=\) Costo de trasportar una unidad desde el origen i, al destino j, \(i \in O, j \in D\).
\(Min:=\) Numero minimo de unidades a enviar del origen \(i\) al destino \(j\).
\(B:=\) Numero muy grande (lo suficientemente grande para no limitar el flujo).
4.3. Variables de decisión.
\(x_{ij}:=\) Cantidad de unidades a transportar desde el origen i, al destino j, \(i \in O, j \in D\\\)
\[y_{ij}:= \left\{\begin{matrix} \textrm{1, si el destino j es atendido por el origen i} \ i \in O, j \in D \\ \textrm{0, en caso contrario} \end{matrix}\right.\]
4.4. Función objetivo.
\[ Min \: C_{Total}= \sum_{i \ \in \ O}\sum_{j \ \in \ D} c_{ij} \times x_{ij} \]
4.5. Restricciones.
4.5.1. Cumplimiendo de la demanda: Para cada destino \(j\) se debe satisfacer la demanda en su totalidad por la oferta de todos los orígenes \(i\).
\[\sum_{i \in O} x_{ij} = d_j, \: \forall \: j \in D\] 4.5.2. Limitación de la capacidad: La cantidad de unidades enviadas desde cada origen \(i\) hacia todos los destinos \(j\) no debe exceder a su capacidad.
\[\sum_{j \in D} x_{ij} \leq k_i, \: \forall \:i \in O\]
4.5.3.Setup del flujo orígen-destino: Solo se podrá hacer envios desde el origen i hacia al destino j, si y solo si existe una atención entre el origen \(i\) y destino \(j\).
\[x_{ij} \leq B \times y_{ij} \: \: \forall \: i \in O, j \in D\]
4.5.4. Flujo mínimo orígen-destino: Si se decide que un origen \(i\) atienda a cierto destino \(j\) entonces se deberá enviar un número minimo de unidades desde dicho origen \(i\) hacia el destino \(j\).
\[ x_{ij} \geq Min \times y_{ij} \: \: \forall \: i \in O, j \in D\]
4.5.5. Dominio de variables:
- La cantidad unidades enviadas desde los origenes \(i\) hacia los destinos \(j\) debe ser un un numero real positivo \({\mathbb R}^{+}\).
\[ x_{ij} \geq 0 \: \: \forall \: i \in O, j \in D\]
- La atencion de un destino \(j\) por parte de un origen \(i\) es determinada por variables binarias.
\[ y_{ij} \in \{0,1\} \: \: \forall \: i \in O, j \in D\]