La tarea de la entrega de bienes.

En esta publicación, veremos cómo Flexport utiliza las matemáticas y la ciencia de datos para resolver problemas de entrega y entregar productos a tiempo al menor costo posible.

Considere un escenario especulativo: el reenviador tiene diez salidas y un vuelo de destino para cualquier envío. La única decisión que se debe tomar es si asignar cada envío a este solo vuelo. Si no asignamos una carga específica al vuelo, supongamos que es posible moverlo de otra manera.

Cada envío tiene volumen y costo, y el vuelo tiene un volumen limitado. Puede considerarlo como un problema de mochila simplificado. Entonces, hay 1024-1 = 1023 posibles soluciones (no enviaríamos el avión completamente vacío).

Podríamos crear una hoja de cálculo para enumerar la solución completa y elegir la más rentable. Pero, ¿qué pasa si tiene las mismas diez salidas, pero dos vuelos? Esto es 59,049 soluciones en solo 10 envíos.

Un reenviador grande tiene más de diez salidas y, por supuesto, más de dos vuelos para elegir, lo que lleva a billones a billones de posibles soluciones. Entre ellos, solo millones son factibles, lo que significa que el método tradicional de hoja de cálculo puede encontrar al menos una solución factible. Pero no necesitamos solo soluciones viables. Necesitamos las mejores soluciones óptimas. ¿Cómo encontrarlos entre innumerables posibilidades? Una respuesta es usar programación entera.

La programación de enteros es una subsección de optimización discreta, un área de estudio de operaciones relacionadas con la minimización de alguna función objetivo sujeta a restricciones. Queremos minimizar los costos totales, siempre que los productos se entreguen a tiempo en los lugares correctos, apilados en ULD (Dispositivo de carga unitaria, un medio de embalaje de productos). Nos esforzamos por encontrar una solución óptima, pero en la práctica a veces no podemos lograrla. En este caso, estamos satisfechos con una solución buena o cercana. Aquí nos restringimos a un modelo simple en el que se puede lograr la solución óptima.

El primer paso para resolver este problema es recurrir a la literatura. La comunidad científica ha estado lidiando con el transporte de carga durante muchos años. Encontramos varios trabajos que recuerdan mucho nuestro problema. Tomamos muchos de los siguientes conceptos y notación de estos trabajos y agradecemos a los autores por su contribución a esta área.

Comenzamos definiendo la función objetivo. Para minimizar los costos, necesitamos comprender el concepto de peso estándar. En resumen, el peso estándar es el peso mínimo con el que el transportista acepta trabajar, independientemente del peso que se ofrezca realmente. Tenemos peso total, peso estándar y probabilidades de sobrecargas y, por el contrario, bajo peso. El peso estándar multiplicado por el peso insuficiente es una subestimación, por lo que podemos ignorar el peso insuficiente y centrarnos en el coeficiente de sobrecarga multiplicado por la propia sobrecarga.

La función objetivo es minimizar el costo total, definido como el peso total de todos los bienes asignados por ULD, multiplicado por el factor de carga. Por ejemplo, si ULD1 tiene 100 kilogramos de congestión y la tasa de congestión para ULD1 es de $ 4 por kilogramo, entonces el costo total de ULD 1 será de $ 400. Entonces, necesitamos alguna notación por sobrepeso y por su valor.

Permitir$$$y_j^E$  es el peso de ULD j por encima del estándar y$$$c_j^E$  - factor de costo para el mismo ULD. Necesitamos calcular$$$y_j^Ec_j^E$ para todos$$$j$ . Si$$$j \in {1, 2, 3}$ , entonces la función objetivo será$$$y_1^Ec_1^E+y_2^Ec_2^E+y_3^Ec_3^E$ . Se derrumba a$$$\sum y_j^Ec_j^E$ . Queremos minimizar el valor, por lo que nuestro objetivo final:

$$

$$\text{min} \sum_{j} y^E_j c^E_j$$

Valor por $$$c_j^E$no es un valor calculado. Este parámetro se obtiene de una hoja de cálculo o base de datos. Pero$$$y_j^E$ lo definimos como el peso de sobrecarga total para ULD$$$j$ , que podemos calcular como el peso total de todos los suministros asignados por ULD (denotarlo$$$y_j$ ), menos el peso estándar de este ULD. El peso estándar es específico para el tipo ULD y también es un parámetro. Permitir$$$U_j^P$  es el peso estándar para ULD$$$j$ en kilogramos. Luego, la cantidad de peso extra para ULD$$$j$ define como$$$y_j^E=y_j-U_j^P$ .
El peso total de la ULD, por supuesto, depende de los pesos asignados a la ULD y su peso. Por lo tanto, necesitamos una expresión para calcularlo, incluidos los detalles mencionados anteriormente.

Esto es simplemente la suma de los pesos asignados por ULD. ¿Cómo indicar que se ha asignado un lote de productos a un ULD específico? Para hacer esto, no necesitamos un parámetro, sino una variable de solución. Una variable de decisión es algo que el solucionador puede controlar mientras minimiza la función objetivo.

Deja que el parámetro$$$g_i$ representa el peso bruto de la carga$$$i$ en kilogramos.
Por ejemplo,$$$g_4=500$ significa que la carga 4 pesa 500 kilogramos.

Permitir$$$x_{i, j}$  es una variable de decisión que toma el valor 1, si el envío$$$i$ asignaron ULD$$$j$ y$$$0$ contrario. Por lo tanto, cuando queremos contar todos los envíos asignados por ULD 3, podemos recorrer todas las variables$$$x_{i, j}$ , donde$$$j=3$ . Si tuviéramos 4 envíos, y los números de envío 1 y 3 se asignaron a ULD 3, se vería así:

$$

$$x_{1,3} + x_{2,3} + x_{3,3} + x_{4,3} = 1 + 0 + 1 + 0 = 2$$

Pero necesitamos peso total, no cantidad. Para obtenerlo, simplemente puede multiplicar cada variable de solución por un parámetro de peso. Como la variable de decisión toma el valor 0, si no se le asigna un peso, este peso se restablece y no se incluye en el total. Suponga que los pesos para las cargas uno a cuatro son 10, 50, 25 y 5. Entonces el peso total en ULD 3 será:

$$

$$g_1x_{1,3} + g_2x_{2,3} + g_3x_{3,3} + g4x_{4,3} = (10)(1) + (50)(0) + (25)(1) + (5)(0) = 10 + 25 = 35$$

Escribamos este cálculo del peso total en general. Determine el peso total de la ULD$$$j$ como $$$y_j$. Entonces$$$y_1=g_1x_{1,1}+g_2x_{2,1}+ … + g_ix_{i, 1}$y $$$y_2=g_1x_{1,2}+g_2x_{2,2} +…+ g_ix_{i, 2}$. Podemos colapsar esto usando la notación de suma$$$y_1 = \sum g_ix_{i, 1}$ y $$$y_2=\sum g_ix_{i, 2}$. Ya que queremos que esto sea cierto para todos los posibles$$$j$, usamos el signo "para todos": $$$\forall$. Esto nos da la forma final de nuestro límite de peso total:

$$

$$y_j=\sum_{i \in I}g_ix_{i,j} \forall j \in J$$

Peso extra

Ahora que tenemos el peso total, podemos aplicar nuestra fórmula para la carga adicional:

$$

$$y_j^E = y_j-U_j^P \quad \forall j \in J$$

Por ejemplo, si $$$y_1=1500$y y $$$U_1^P=1000$luego peso extra $$$y_1^E = 1500 - 1000 = 500$kilogramos Multiplique esto por el factor de costo para obtener el resultado en dólares. A primera vista, esto puede parecer suficiente, pero ¿qué pasa con el caso cuando el peso total de la carga completa para ULD no excede el peso estándar? En este caso, si utilizamos la fórmula "tal cual", entonces el peso de sobrecarga sería un número negativo. Por ejemplo, si el peso estándar es de 1650 kilogramos y el peso total asignado es de 1000 kilogramos, entonces sobrecarga = 1000–1650 = -650. La función objetivo multiplica este número por un factor para sobrecargas y obtenemos un número negativo. Como si el transportista nos pagara por un envío inferior al costo de un peso estándar.

Esto es lo que realmente queremos:$$$\text{max}(y_j^E, 0)$.
Esto es lo mismo que simplemente establecer 0 para una variable, que es tan simple como crear una restricción$$$y_j^E>=0$.

$$$y_j^E >= y_j - U_j^P \quad \forall j \in J$, $$$y_j^E >= 0 \quad \forall j \in J$

Entonces, implementamos la función max () en programación matemática: a = max (b, c), es decir, a> = b && a> = c. Veamos nuestras definiciones.
Función objetiva:$$$\text{min} \sum_{j} y^E_j c^E_j$
$$$c_j^E$: Relación de sobrecarga ULD $$$j$
$$$y_j^E$: Sobrecarga ULD $$$j$; $$$y_j^ = y_j - U_j^P$
$$$U_j^P$: Peso estándar ULD $$$j$
$$$g_i$: Peso bruto de envío $$$i$
$$$x_{i, j}$: decisión variable; $$$x_{i, j}=1$si envío $$$i$asignado por ULD $$$j$, $$$0$de otra manera.
$$$y_j$: peso total de todos los envíos designados por ULD $$$j$; $$$y_j=\sum_{i \in I}g_ix_{i,j} \quad \forall j \in J$

Cada carga debe volar

En este punto, podríamos escribir esto en Python y enviarlo al solucionador. Si hiciéramos esto, encontraríamos que el solucionador asignó cero entregas a cualquier vuelo, y podemos entender rápidamente por qué: la mejor manera de minimizar la función objetivo es no acumular ningún costo. Esto lleva a la siguiente restricción: cada lote debe asignarse a algún ULD. Extendiremos esto a cada carga que debe asignarse a un único ULD, aunque en realidad podemos dividir la carga en varios ULD e incluso en varios vuelos.

Esto significa que$$$x_{i, j}$solo puede ser 1 por un valor único de $ j $. Por ejemplo, si estamos considerando enviar 13, entonces$$$x_{13,1}+x_{13,2}+ x_{13,3}+ … + x_{13, J}=1$. Queremos aplicar esta restricción para cada envío.$$$i$ (que escribimos como $$$\forall i\in I$), y podemos contraer la suma usando el operador de suma ($$$\sum$), por lo que nuestra limitación final es:

$$

$$\sum_{j \in J} x_{i, j}=1\quad\forall i \in I$$

Dada esta limitación, el solucionador realmente comenzará a asignar envíos a vuelos, pero simplemente distribuirá los envíos entre todos los vuelos disponibles hasta que se cumplan los pesos. El solucionador colocaría cada envío restante en un ULD con el menor costo adicional. Excluyendo el volumen o peso de este ULD. Por lo tanto, las siguientes restricciones adicionales son el volumen y el peso.

Limitaciones de volumen y peso

Vamos a decidir $$$U_j^M$como carga máxima en kilogramos de ULD $$$j$y $$$U_j^$como volumen máximo en metros cúbicos ULD $$$j$. Vamos a decidir$$$v_i$y el volumen en metros cúbicos de carga $$$i$. Para limitar el modelo a la capacidad de carga máxima y al volumen máximo, tenemos las condiciones:

$$

$$y_j<=U_j^M \quad \forall j \in J$$

$$

$$\sum_{i \in I} x_{i,j} v_ i <= U_j^V \quad \forall j \in J$$

Un veterano de la industria se dará cuenta de inmediato de que esto no es cierto. ¿Por qué? Debido a que estas restricciones tratan la carga como si pudiera verterse, como agua, en cualquier volumen. En realidad, las cargas son rígidas o tienen otras restricciones, como el apilamiento. No se pueden embalar 10 metros cúbicos de carga en un volumen arbitrario igual a exactamente 10 metros cúbicos. Para hacer frente a estos casos, debe resolver el problema del embalaje en contenedores. Verificamos si ciertos volúmenes caben dentro de otros, pero esto está más allá del alcance de este artículo.

Ahora el solucionador asigna el ULD de envío, respetando el peso y el volumen máximos y minimizando el costo total. Pero hay otro problema: no dijimos nada sobre la cita de los artículos y el cumplimiento de las fechas de entrega. De hecho, hay cuatro marcas de tiempo que debe tener en cuenta al asignar un envío: el

momento en que el envío está realmente listo para consolidarse con otros envíos en el ULD y cargar en el vuelo. Vamos a usar$$$Q_i^-$para representar el momento en que el envío está listo $$$i$.
El tiempo durante el cual las mercancías deben descargarse en el destino se desconsolida y está disponible para su recepción, por regla general, desde la terminal de carga. Usemos $ Q_i ^ + $ para representar la fecha límite de entrega$$$i$.
El momento en que toda la carga debe ser entregada a la terminal de carga para cargarla en el vuelo. Vamos a usar$$$T_j^ -$para representar el tiempo de recorte de la carga ULD $ j $.
Hora de llegada del vuelo: es el momento en que la carga del vuelo está disponible en el almacén de destino. Vamos a usar$$$T_j^+$ para representar la hora de llegada del vuelo ULD $$$j$

Origen y Destino

Introducir un conjunto más $$$J_i$, que definimos como un conjunto de vuelos, cuyo origen y destino coinciden con la salida y recepción de carga $$$i$. En otras palabras, si la salida 85 es desde Hong Kong y el destino en Londres, entonces $ J_ {85} $ es el conjunto de todos los ULD con salida desde Hong Kong y destino en Londres.
Ahora podemos usar$$$j \in J_i$ para obtener un kit ULD que coincida con la ruta comercial de envío $$$i$o podemos usar $$$j \notin J_i$para obtener un conjunto de ULD que no coincida. Para prohibir la vinculación de la carga a ULD, que no corresponde a su origen y destino, simplemente restringimos$$$x_{i,j} = 0$para todos esos vuelos. La restricción se describe completamente como sigue:

$$

$$\sum_{j \notin J_i} x_{i,j}=0 \quad \forall i \in I$$

El tiempo de entrega

Cuando se trabaja con marcas de tiempo en la optimización, es conveniente presentar los momentos necesarios como hora Unix. Ventajas del enfoque:

1. Almacenamiento de fechas como números.
2. No es necesario manejar zonas horarias.
3. El solucionador utiliza comparaciones directas más y menos.

El vuelo debe llegar antes de la hora de entrega:
$$$\sum_{j \in J_i}T_j^+x_{i,j}<=Q_i^+ \quad \forall i \in I \quad$
Tenga en cuenta que, al igual que para la restricción anterior de salida y destino, hemos indicado que esta restricción se aplica solo a la ULD en el conjunto $$$J_i$dónde $$$J_i$ es un conjunto de ULD que coinciden con el envío y la recepción del envío $$$i$. ¡Eso es todo! Veamos todo el modelo.

Modelo completo

Bajo tales restricciones, el solucionador asigna los artículos ULD de la manera menos costosa, y cada carga se entrega desde el lugar de salida correcto al destino correcto. Por supuesto, la carga se entrega a tiempo y sin sobrecargar los artículos por volumen o peso.

Parámetros

$$$I$: Un conjunto de todos los envíos. Un envío enviado$$$i$
$$$J$: Un conjunto de todos los ULD. ULD individual es minúscula$$$j$.
$$$J_i$: Un conjunto de todos los ULD que coinciden con el emisor y el receptor $$$i$.
$$$g_i$: Peso bruto de envío $$$i$en kilogramos
$$$v_i$: Volumen en metros cúbicos de envío $$$i$
$$$c_j^E$: Relación de sobrecarga ULD $$$j$en dólares estadounidenses por kilogramo
$$$U_j^M$: Capacidad máxima de peso ULD $$$j$en kilogramos
$$$U_j^V$: Potencia envolvente máxima ULD $$$j$en metros cúbicos
$$$U_j^P$: Peso estándar ULD $$$j$en kilogramos

$$$T_j^-$: Tiempo de entrega permitido al terminal ULD $$$j$.
$$$T_j^+$: Hora de llegada de ULD $$$j$.
$$$Q_i^-$: Tiempo de envío listo $$$i$. 
$$$Q_i^+$: Período de entrega $$$i$.

Variables de decisión y función objetivo:
$$$y_j$: Peso total ULD $$$j$
$$$y_j^E$: Sobrecarga ULD $$$j$en kilogramos
$$$x_{i,j}$: 1 si envía $$$i$asignado por ULD $$$j$0 de lo contrario.

Función de destino

$$

$$\text{Minimize} \sum y_j^Ec_j^E$$

Limitaciones

$$$y_j$ - peso total de los envíos en ULD $ j $: $$$y_j=\sum_{i \in I} g_ix_{i,j} \quad \forall j \in J$
El peso extra jE es máximo (0, yj-UjP):
$$$y_j^E >=y_j-U_j^P \quad \forall j \in J$
$$$y_j^E >=0 \quad \forall j \in J$
Cada entrega debe asignarse exactamente a 1 ULD: $$$\sum_{j \in J} x_{i,j}=1 \quad \forall i \in I$.
ULD$$$j$ no puede exceder el peso máximo: $$$y_j<=U_j^M \quad \forall j \in J$
ULD $$$j$no puede exceder la capacidad máxima: $$$\sum_{i \in I}x_{i,j}v_i <= U_j^V \quad \forall j \in J$

Pasos adicionales

Este artículo describe la programación matemática que subyace en el propósito de la carga del vuelo. Pero escribir matemáticas no es suficiente. El siguiente paso es implementar el programa, probablemente en AML, como Pyomo, o usando su propia API de solucionador, por ejemplo, Python Gurobi API. Después de eso, el desarrollador escribirá un código para transferir los parámetros de todas las salidas y vuelos disponibles. Luego, la instancia del modelo se envía al solucionador. El solucionador establece los valores de las variables de decisión de manera óptima. Luego, el desarrollador debe hacer algo con los valores de las variables de decisión.