Problema de transbordo

Los problemas de transbordo constituyen un subgrupo de los problemas de transporte en los que se permite el transbordo . En el transbordo, el transporte puede o debe pasar por nodos intermedios, posiblemente cambiando de modo de transporte.

El problema del transbordo tiene su origen en la Edad Media, cuando el comercio comenzó a convertirse en un fenómeno de masas. La principal prioridad era encontrar la ruta de menor coste. Sin embargo, el desarrollo tecnológico fue dando prioridad gradualmente a los problemas de transporte de menor duración.

Descripción general

El transbordo consiste en el envío de mercancías o contenedores a un destino intermedio y, posteriormente, a otro destino. Una posible razón es el cambio de medio de transporte durante el trayecto (por ejemplo, del transporte marítimo al transporte por carretera ), conocido como transbordo . Otra razón es la consolidación de varios envíos en uno mayor, para luego dividirlo en el destino (desconsolidación). El transbordo suele realizarse en centros logísticos . Gran parte del transbordo internacional se lleva a cabo en zonas aduaneras designadas , evitando así los controles y aranceles aduaneros, que de otro modo supondrían un importante obstáculo para un transporte eficiente.

Formulación del problema

Para formular completamente el problema del transbordo, se requieren algunas suposiciones iniciales:

El sistema consta de m orígenes y n destinos, con la siguiente indexación respectivamente: $i=1,\ldots ,m$ , $j=1,\ldots ,n$
Existe un producto uniforme que necesita ser enviado.
La cantidad requerida del bien en los destinos es igual a la cantidad producida disponible en los orígenes.
El transporte comienza simultáneamente en los orígenes y es posible desde cualquier nodo a cualquier otro (también hacia un origen y desde un destino).
Los costos de transporte son independientes de la cantidad enviada.
El problema de transbordo es un problema de programación lineal (LLP) único, ya que considera el supuesto de que todas las fuentes y sumideros pueden recibir y distribuir envíos al mismo tiempo (funcionan en ambas direcciones) ^{[ 1 ].}

Notaciones

$t_{r,s}$ : tiempo de transporte del nodo r al nodo s
$a_{i}$ : bienes disponibles en el nodo i
$b_{m+j}$ : demanda del bien en el nodo (m+j)
$x_{r,s}$ : cantidad real transportada del nodo r al nodo s

Formulación matemática del problema

El objetivo es minimizar $\sum \limits _{i=1}^{m}\sum \limits _{j=1}^{n}t_{i,j}x_{i,j}$ sujeto a:

$x_{r,s}\geq 0$ ; $\forall r=1\ldots m$ , $s=1\ldots n$
$\sum _{s=1}^{m+n}{x_{i,s}}-\sum _{r=1}^{m+n}{x_{r,i}}=a_{i}$ ; $\forall i=1\ldots m$
$\sum _{r=1}^{m+n}{x_{r,m+j}}-\sum _{s=1}^{m+n}{x_{m+j,s}}=b_{m+j}$ ; $\forall j=1\ldots n$
$\sum _{i=1}^{m}{a_{i}}=\sum _{j=1}^{n}{b_{m+j}}$

Solución

Dado que en la mayoría de los casos no existe una expresión explícita para la función objetivo, Rajeev y Satya sugieren un método alternativo . El método utiliza dos fases consecutivas para revelar la ruta de duración mínima desde los orígenes hasta los destinos. La primera fase consiste en resolver $n\cdot m$ problema de minimización del tiempo , en cada caso utilizando el resto $n+m-2$ Los nodos intermedios se utilizan como puntos de transbordo. Esto también permite un transporte de mínima duración entre todos los orígenes y destinos. Durante la segunda fase, se debe resolver un problema estándar de minimización de tiempo. La solución del problema de transbordo de minimización de tiempo es el resultado conjunto de la solución de estas dos fases.

Fase 1

Dado que los costos son independientes de la cantidad enviada, en cada problema individual se puede normalizar la cantidad enviada a 1. El problema ahora se simplifica a un problema de asignación de i a m+j . Sea $x'_{r,s}=1$ sea 1 si la arista entre los nodos r y s se utiliza durante la optimización, y 0 en caso contrario. Ahora el objetivo es determinar todos $x'_{r,s}$ que minimizan la función objetivo:

$T_{i,m+j}=\sum _{r=1}^{m+n}\sum _{s=1}^{m+n}{t_{r,s}\cdot x'_{r,s}}$ ,

de tal manera que

$\sum _{s=1}^{m+n}{x'_{r,s}}=1$
$\sum _{r=1}^{m+n}{x'_{r,s}}=1$
$x'_{m+j,i}=1$
$x'_{r,s}=0,1$ .

Corolario

$x'_{r,r}=1$ y $x'_{m+j,i}=1$ deben ser excluidos del modelo; por otro lado, sin el $x'_{m+j,i}=1$ La restricción de que la ruta óptima consista únicamente en $x'_{r,r}$ bucles de tipo que obviamente no pueden ser una solución viable.
En lugar de $x'_{m+j,i}=1$ , $t_{m+j,i}=-M$ se puede escribir, donde M es un número positivo arbitrariamente grande. Con esa modificación, la formulación anterior se reduce a la forma de un problema de asignación estándar , que se puede resolver con el método húngaro .

Fase 2

Durante la segunda fase, se resuelve un problema de minimización de tiempo con m orígenes y n destinos sin transbordo. Esta fase difiere en dos aspectos principales de la configuración original:

El transporte solo es posible desde un origen hasta un destino.
El tiempo de transporte de i a m+j es la suma de las duraciones provenientes de la ruta óptima calculada en la Fase 1. Digno de ser denotado por $t'_{i,m+j}$ para separarlo de los tiempos introducidos durante la primera etapa.

En forma matemática

El objetivo es encontrar $x_{i,m+j}\geq 0$ que minimizan

$z=max\left\{t'_{i,m+j}:x_{i,m+j}>0\;\;(i=1\ldots m,\;j=1\ldots n)\right\}$ , de tal manera que

$\sum _{i=1}^{m}{x_{i,m+j}}=a_{i}$
$\sum _{j=1}^{n}{x_{i,m+j}}=b_{m+j}$
$\sum _{i=1}^{m}{a_{i}}=\sum _{j=1}^{n}{b_{m+j}}$

Este problema es fácil de resolver con el método desarrollado por Prakash . El conjunto $\left\{t'_{i,m+j},i=1\ldots m,\;j=1\ldots n\right\}$ necesita dividirse en subgrupos $L_{k},k=1\ldots q$ , donde cada $L_{k}$ contienen el $t'_{i,m+j}$ -s con el mismo valor. La secuencia $L_{k}$ está organizado como $L_{1}$ contiene el valor más alto $t'_{i,m+j}$ 's $L_{2}$ el segundo más grande y así sucesivamente. Además, $M_{k}$ Los factores de prioridad positiva se asignan a los subgrupos. $\sum _{L_{k}}{x_{i,m+j}}$ , con la siguiente regla:

$\alpha M_{k}-\beta M_{k+1}=\left\{{\begin{array}{cc}-ve,&si\;\alpha <0\\ve,&si\;\alpha >0\end{array}}\right.$

a pesar de $\beta$ . Con esta notación el objetivo es encontrar todos $x_{i,m+j}$ que minimizan la función objetivo

$z_{1}=\sum _{k=1}^{q}{M_{k}}\sum _{L_{k}}{x_{i,m+j}}$

de tal manera que

$\sum _{i=1}^{m}{x_{i,m+j}}=a_{i}$
$\sum _{j=1}^{n}{x_{i,m+j}}=b_{m+j}$
$\sum _{i=1}^{m}{a_{i}}=\sum _{j=1}^{n}{b_{m+j}}$
$\alpha M_{k}-\beta M_{k+1}=\left\{{\begin{array}{cc}-ve,&si\;\alpha <0\\ve,&si\;\alpha >0\end{array}}\right.$

Extensión

Algunos autores como Das et al (1999) y Malakooti (2013) han considerado el problema de transbordo multiobjetivo.

Referencias

↑ "Problema de transbordo y sus variantes: una revisión" . ResearchGate . Consultado el 2 de noviembre de 2020 .

RJ Aguilar, Análisis y diseño de sistemas. Prentice Hall, Inc. Englewood Cliffs, Nueva Jersey (1973) págs. 209–220
HL Bhatia, K. Swarup, MC Puri, Indian J. pure appl. Math. 8 (1977) 920-929
RS Gartinkel, MR Rao, Nav. Res. Log. Quart. 18 (1971) 465-472
G. Hadley, Programación lineal, Addison-Wesley Publishing Company, (1962) págs. 368–373
PL Hammer, Nav. Res. Log. Quart. 16 (1969) 345-357
PL Hammer, Nav. Res. Log. Quart. 18 (1971) 487-490
AJ Hughes, DE Grawog, Programación lineal: Énfasis en la toma de decisiones, Addison-Wesley Publishing Company, págs. 300–312
HWKuhn, Registro de Investigación Naval, Trimestre 2 (1955) 83-97
A.Orden, Ciencias de la Gestión, 2 (1956) 276-285
S. Parkash, Proc. Indian Acad. Sci. (Math. Sci.) 91 (1982) 53-57
CS Ramakrishnan, OPSEARCH 14 (1977) 207-209
CRSeshan, VGTikekar, Proc. Indian Acad. Sci. (Math. Sci.) 89 (1980) 101-102
JKSharma, K.Swarup, Proc. Indian Acad. Sci. (Math. Sci.) 86 (1977) 513-518
W.Szwarc, Nav. Res. Registro. Cuarto de galón. 18 (1971) 473-485
Malakooti, B. (2013). Sistemas de operaciones y producción con objetivos múltiples. John Wiley & Sons.
Das, SK, A. Goswami y SS Alam. «Problema de transporte multiobjetivo con parámetros de costo, origen y destino en intervalos». European Journal of Operational Research, vol. 117, n.° 1, 1999, págs. 100-112.

[1] "Problema de transbordo y sus variantes: una revisión" . ResearchGate . Consultado el 2 de noviembre de 2020 .

[ 1 ].