The task of the delivery of goods

In this post, we will see how Flexport uses math and data science to solve delivery problems and deliver goods on time at the lowest possible cost.

Consider a speculative scenario: the forwarder has ten departures and one destination flight for any shipment. The only decision to be made is whether to assign each shipment to this single flight. If we do not assign a specific load to the flight, suppose it is possible to move it in another way.

Each shipment has volume and cost, and the flight is limited in volume. You may think of it as a simplified backpack problem. So, there are 1024-1 = 1023 possible solutions (we would not send the plane completely empty).

We could create a spreadsheet to list the entire solution and choose the most profitable one. But what if you have the same ten departures, but two flights? This is 59,049 solutions in just 10 shipments.

A large forwarder has more than ten departures and, of course, more than two flights to choose from, which leads to trillions to trillions of possible solutions. Among them, only millions are feasible, which means that the traditional spreadsheet method can find at least one feasible solution. But we do not need only feasible solutions. We need the best, optimal solutions. How to find them among countless possibilities? One answer is to use integer programming.

Integer programming is a subsection of discrete optimization, an area of ​​study of operations related to minimizing some objective function subject to constraints. We want to minimize the total costs, provided that the goods are delivered on time to the right places, stacked in ULD (Unit Load Device - a means of packaging goods). We strive for an optimal solution, but in practice sometimes we can’t achieve it. In this case, we are satisfied with a good or close solution. Here we restrict ourselves to a simple model in which the optimal solution is achievable.

The first step in solving this problem is to turn to the literature. The scientific community has been dealing with freight forwarding for many years. We found several works that are very reminiscent of our problem. We took many of the following concepts and notation from these works and thank the authors for their contribution to this area.

We start by defining the objective function. To minimize costs, we need to understand the concept of standard weight. In short, the standard weight is the minimum weight that the forwarder agrees to work with, regardless of what weight is actually offered. We have total weight, standard weight and odds for overloads and, conversely, underweight. The standard weight multiplied by the underweight is an underestimation, so we can ignore the underweight and focus on the overload coefficient multiplied by the overload itself.

The objective function is to minimize the total cost, defined as the total weight of all goods assigned by ULD, multiplied by the load factor. For example, if ULD1 has 100 kilograms of congestion and the congestion rate for ULD1 is $ 4 per kilogram, then the total cost of ULD 1 will be $ 400. So, we need some notation for being overweight and for its value.

Let be$$$y_j^E$  - weight ULD j above standard and $$$c_j^E$ - cost factor for the same ULD. We need to calculate$$$y_j^Ec_j^E$ for all $$$j$. If$$$j \in {1, 2, 3}$then the objective function will be $$$y_1^Ec_1^E+y_2^Ec_2^E+y_3^Ec_3^E$. It collapses to$$$\sum y_j^Ec_j^E$. We want to minimize the value, so our final goal:

$$

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

Value for $$$c_j^E$not a calculated value. This parameter is obtained from a spreadsheet or database. But$$$y_j^E$ we defined as total overload weight for ULD $$$j$, which we can calculate as the total weight of all supplies assigned by ULD (denote it $$$y_j$), minus the standard weight of this ULD. Standard weight is specific to ULD type and is also a parameter. Let be$$$U_j^P$  is the standard weight for ULD $$$j$in kilograms. Then the amount of extra weight for ULD$$$j$ defined as $$$y_j^E=y_j-U_j^P$.
The total weight of the ULD, of course, depends on what weights are assigned to the ULD and their weight. Therefore, we need an expression to calculate it, including the details mentioned above.

This is simply the sum of the weights assigned by ULD. How to indicate that a batch of goods has been assigned to a specific ULD? To do this, we need not a parameter, but a solution variable. A decision variable is something that the solver can control while minimizing the objective function.

Let the parameter$$$g_i$ represents gross weight $$$i$in kilograms.
For instance,$$$g_4=500$means that a load of 4 weighs 500 kilograms.

Let be$$$x_{i, j}$  - a decision variable taking the value 1, if shipment $$$i$assigned by ULD $$$j$, and $$$0$otherwise. Thus, when we want to count all shipments assigned by ULD 3, we can loop through all the variables$$$x_{i, j}$where $$$j=3$. If we had 4 shipments, and shipment numbers 1 and 3 were assigned to ULD 3, it would look like this:

$$

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

But we need total weight, not quantity. To obtain it, you can simply multiply each solution variable by a weight parameter. Since the decision variable takes the value 0, if it is not assigned a weight, then this weight is reset and not included in the total. Suppose the weights for cargoes one through four are 10, 50, 25, and 5. Then the total weight in ULD 3 will be:

$$

$$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$$

Let's write this calculation of the total weight in general. Determine the total weight of the ULD$$$j$ as $$$y_j$. Then$$$y_1=g_1x_{1,1}+g_2x_{2,1}+ … + g_ix_{i, 1}$, and $$$y_2=g_1x_{1,2}+g_2x_{2,2} +…+ g_ix_{i, 2}$. We can collapse this using summation notation$$$y_1 = \sum g_ix_{i, 1}$ and $$$y_2=\sum g_ix_{i, 2}$. Since we want this to be true for all possible$$$j$, we use the "for all" sign: $$$\forall$. This gives us the final form of our total weight limit:

$$

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

Extra weight

Now that we have the total weight, we can apply our formula for the extra load:

$$

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

For example, if $$$y_1=1500$and and $$$U_1^P=1000$then extra weight $$$y_1^E = 1500 - 1000 = 500$kilograms. Multiply this by the cost factor to get the result in dollars. At first glance this may seem sufficient, but what about the case when the total weight of the entire cargo for ULD does not exceed the standard weight? In this case, if we used the “as is” formula, then the overload weight would be a negative number. For example, if the standard weight is 1650 kilograms and the total weight assigned is 1000 kilograms, then overload = 1000–1650 = -650. The objective function multiplies this number by a factor for overloads and we get a negative number. As if the carrier paid us for shipping less than the cost of a standard weight.

Here is what we really want:$$$\text{max}(y_j^E, 0)$.
This is the same as just setting 0 for a variable, which is as simple as creating a constraint$$$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$

So, we implemented the function max () in mathematical programming: a = max (b, c), that is, a> = b && a> = c. Let's look at our definitions.
Objective function:$$$\text{min} \sum_{j} y^E_j c^E_j$
$$$c_j^E$: ULD Overload Ratio $$$j$
$$$y_j^E$: ULD overload $$$j$; $$$y_j^ = y_j - U_j^P$
$$$U_j^P$: Standard weight ULD $$$j$
$$$g_i$: Gross Shipping Weight $$$i$
$$$x_{i, j}$: decision variable; $$$x_{i, j}=1$if shipment $$$i$assigned by ULD $$$j$, $$$0$otherwise.
$$$y_j$: total weight of all shipments designated by ULD $$$j$; $$$y_j=\sum_{i \in I}g_ix_{i,j} \quad \forall j \in J$

Every load must fly

At this point, we could write this in Python and send it to the solver. If we did this, we would find that the solver assigned zero deliveries to any flight, and we can quickly understand why: the best way to minimize the objective function is to not accumulate any costs. This leads to the following restriction: each batch must be assigned to some ULD. We will extend this to each cargo that should be assigned to one and only one ULD, although in reality we can divide the cargo into several ULD and even several flights.

It means that$$$x_{i, j}$can only be 1 for a single value of $ j $. For example, if we are considering shipping 13, then$$$x_{13,1}+x_{13,2}+ x_{13,3}+ … + x_{13, J}=1$. We want to apply this restriction for each shipment.$$$i$ (which we write as $$$\forall i\in I$), and we can collapse the addition using the summation operator ($$$\sum$), so our final limitation is:

$$

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

Given this limitation, the solver will actually begin to assign shipments to flights, but he will simply distribute shipments between all available flights until the weights are met. The solver would then place each remaining consignment in one ULD with the least additional cost. Excluding the volume or weight of this ULD. So, the following added restrictions are volume and weight.

Volume and Weight Limitations

Let's decide $$$U_j^M$as maximum payload in kilograms of ULD $$$j$and $$$U_j^$as maximum volume in cubic meters ULD $$$j$. Let's decide$$$v_i$, and the volume in cubic meters of cargo $$$i$. To limit the model to the maximum load capacity and maximum volume, we have the conditions:

$$

$$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$$

An industry veteran will immediately realize that this is not true. Why? Because these restrictions treat the cargo as if it could be poured, like water, into any volume. In reality, loads are rigid or have other restrictions, such as stacking. 10 cubic meters of cargo cannot be packed in an arbitrary volume equal to exactly 10 cubic meters. To cope with these cases, you need to solve the problem of packaging in containers. We check whether certain volumes will fit inside others, but this is beyond the scope of this article.

Now the solver assigns the shipment ULD, respecting the maximum weight and volume while minimizing the total cost. But there is another problem: we did not say anything about the appointment of the items and the observance of the delivery dates. In fact, there are four timestamps that you need to consider when assigning a shipment: The

time when the shipment is actually ready to consolidate with other shipments in the ULD and load on the flight. Let's use$$$Q_i^-$to represent the time the shipment is ready $$$i$.
The time by which the goods must be unloaded at the destination is deconsolidated and available for receipt, as a rule, from the cargo terminal. Let's use $ Q_i ^ + $ to represent the delivery deadline$$$i$.
The time by which all cargo must be delivered to the cargo terminal for loading onto the flight. Let's use$$$T_j^ -$to represent the clipping time of the cargo ULD $ j $.
Flight arrival time: this is the time by which the cargo on the flight becomes available at the destination warehouse. Let's use$$$T_j^+$ to represent ULD flight arrival time $$$j$

Source and Destination

Introduce one more set $$$J_i$, which we define as a set of flights, whose source and destination coincides with the departure and receipt of cargo $$$i$. In other words, if departure 85 is from Hong Kong and destination in London, then $ J_ {85} $ is the set of all ULDs with departure from Hong Kong and destination in London.
Now we can use$$$j \in J_i$ to obtain a ULD kit that matches the shipping trade route $$$i$or we can use $$$j \notin J_i$to get a set of ULD that does not match. To prohibit the binding of cargo to ULD, which does not correspond to its source and destination, we simply restrict$$$x_{i,j} = 0$for all such flights. The restriction is fully described as follows:

$$

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

Delivery time

When working with timestamps in optimization, it’s convenient to present the necessary moments as Unix time. Advantages of the approach:

1. Storing dates as numbers.
2. No need to handle time zones.
3. The solver uses direct more-less comparisons.

The flight must arrive before the delivery time:
$$$\sum_{j \in J_i}T_j^+x_{i,j}<=Q_i^+ \quad \forall i \in I \quad$
Please note that, just as for the above restriction on departure and destination, we have indicated that this restriction applies only to the ULD in the set $$$J_i$where $$$J_i$ is a set of ULDs that match sending and receiving shipment $$$i$. That's all! Let's look at the whole model.

Full model

Under such restrictions, the solver assigns the ULD items in the least costly manner, with each cargo being delivered from the right place of departure to the right destination. Of course, the cargo is delivered on time and without overloading the items by volume or weight.

Parameters

$$$I$: A set of all shipments. One shipment submitted$$$i$
$$$J$: A set of all ULD. Individual ULD is lowercase$$$j$.
$$$J_i$: A set of all ULDs that match the sender and receiver $$$i$.
$$$g_i$: Shipping gross weight $$$i$in kilograms.
$$$v_i$: Volume in cubic meters of shipment $$$i$
$$$c_j^E$: ULD Overload Ratio $$$j$in US dollars per kilogram
$$$U_j^M$: Maximum weight capacity ULD $$$j$in kilograms
$$$U_j^V$: ULD Maximum Surround Power $$$j$in cubic meters
$$$U_j^P$: Standard weight ULD $$$j$in kilograms

$$$T_j^-$: Allowed delivery time to ULD terminal $$$j$.
$$$T_j^+$: ULD Arrival Time $$$j$.
$$$Q_i^-$: Shipment Ready Time $$$i$. 
$$$Q_i^+$: Delivery period $$$i$.

Decision variables and objective function:
$$$y_j$: ULD total weight $$$j$
$$$y_j^E$: ULD overload $$$j$in kilograms.
$$$x_{i,j}$: 1 if sending $$$i$assigned by ULD $$$j$0 otherwise.

Target function

$$

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

Limitations

$$$y_j$ - total weight of shipments on ULD $ j $: $$$y_j=\sum_{i \in I} g_ix_{i,j} \quad \forall j \in J$
Extra weight jE is max (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$
Each delivery must be assigned exactly to 1 ULD: $$$\sum_{j \in J} x_{i,j}=1 \quad \forall i \in I$.
ULD$$$j$ cannot exceed maximum weight: $$$y_j<=U_j^M \quad \forall j \in J$
ULD $$$j$cannot exceed maximum capacity: $$$\sum_{i \in I}x_{i,j}v_i <= U_j^V \quad \forall j \in J$

Further steps

This article describes the mathematical programming underlying the purpose of the load of the flight. But just writing math is not enough. The next step is to implement the program, probably in AML, like Pyomo, or using its own solver API, for example, Python Gurobi API. After that, the developer will write a code to transfer the parameters of all available departures and flights. Then the model instance is sent to the solver. The solver sets the values ​​of the decision variables in an optimal way. Then the developer must do something with the values ​​of the decision variables.