交货任务

在本文中，我们将了解Flexport如何使用数学和数据科学解决交付问题并以最低的成本准时交付商品。

考虑一个投机性场景：对于任何货运，货运代理都有十个出发点和一个目的地航班。唯一要做出的决定是是否将每个货件分配给该单个航班。如果我们没有为航班分配特定的负载，则可以以其他方式移动它。

每批货物都有数量和成本，并且航班数量有限。您可能将其视为简化的背包问题。因此，有1024-1 = 1023个可能的解决方案（我们不会将飞机发送到完全空的状态）。

我们可以创建一个电子表格以列出整个解决方案，然后选择利润最高的解决方案。但是，如果您有10个相同的出发航班却有2个航班，该怎么办？仅10批出货就提供了59,049个解决方案。

大型货运代理有十多个出发点，当然还有两个以上的航班可供选择，这导致了数万亿到数万亿的可能解决方案。其中只有数百万个可行的解决方案，这意味着传统的电子表格方法可以找到至少一个可行的解决方案。但是，我们并不需要可行的解决方案。我们需要最佳，最佳的解决方案。如何在众多可能性中找到它们？一种答案是使用整数编程。

整数编程是离散优化的一个子部分，是与受约束约束的一些目标函数最小化有关的操作研究领域。我们希望将总成本降到最低，只要将货物以正确的位置按时交付，并以ULD（单位装载设备-一种包装货物的方式）堆叠。我们努力寻求最佳解决方案，但实际上有时我们无法实现。在这种情况下，我们对良好或接近的解决方案感到满意。在这里，我们将自己局限于一个简单的模型，在该模型中可以实现最佳解决方案。

解决此问题的第一步是转向文献。科学界多年来一直在处理货运代理。我们发现了几本让人回想起我们问题的作品。我们从这些作品中采用了以下许多概念和符号，并感谢作者对这一领域的贡献。

我们首先定义目标函数。为了最大程度地降低成本，我们需要了解标准重量的概念。简而言之，标准重量是货运代理同意使用的最小重量，而与实际提供的重量无关。我们有总重量，标准重量以及超载的赔率，反之则是体重不足。标准重量乘以体重不足是一种低估，因此我们可以忽略体重不足，而将注意力放在过载系数乘以过载本身上。

目标功能是使总成本最小化，总成本定义为ULD分配的所有货物的总重量乘以负载系数。例如，如果ULD1拥塞100公斤，而ULD1的拥塞率是每公斤$ 4，那么ULD1的总成本将是$ 400。因此，我们需要一些关于超重及其价值的表示法。

让$$$y_j^E$  -重量ULD j高于标准，并且 $$$c_j^E$ -同一ULD的成本因素。我们需要计算$$$y_j^Ec_j^E$ 对所有人 $$$j$。如果$$$j \in {1, 2, 3}$那么目标函数将是 $$$y_1^Ec_1^E+y_2^Ec_2^E+y_3^Ec_3^E$。它崩溃成$$$\sum y_j^Ec_j^E$。我们希望使价值最小化，因此我们的最终目标是：

$$

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

价值 $$$c_j^E$不是计算值。此参数是从电子表格或数据库获得的。但$$$y_j^E$ 我们定义为ULD的总过载重量 $$$j$，我们可以将其计算为ULD分配的所有耗材的总重量（表示为 $$$y_j$）减去此ULD的标准重量。标准重量特定于ULD类型，并且也是一个参数。让$$$U_j^P$  是ULD的标准重量 $$$j$以千克为单位。然后是超重的额外重量$$$j$ 定义为 $$$y_j^E=y_j-U_j^P$。
当然，ULD的总权重取决于分配给ULD的权重及其权重。因此，我们需要一个表达式来计算它，包括上面提到的细节。

这只是ULD分配的权重之和。如何指示一批货物已分配给特定的ULD？为此，我们不需要参数，而是解决方案变量。决策变量是求解器可以在最小化目标函数的同时进行控制的东西。

让参数$$$g_i$ 代表毛重 $$$i$以千克为单位。
例如，$$$g_4=500$表示4的负载重500公斤。

让$$$x_{i, j}$  -装运时取值为1的决策变量 $$$i$ULD分配 $$$j$和 $$$0$除此以外。因此，当我们要计算ULD 3分配的所有货运时，我们可以遍历所有变量$$$x_{i, j}$哪里 $$$j=3$。如果我们有4个货件，并且货件编号1和3被分配给ULD 3，则如下所示：

$$

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

但是我们需要总重量，而不是数量。要获得它，只需将每个解决方案变量乘以权重参数即可。由于决策变量的值为0，因此如果未分配权重，则将重置此权重并且不将其包括在总计中。假设货物1至4的重量分别为10、50、25和5。那么ULD 3中的总重量为：

$$

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

让我们大致写出总重量的计算。确定ULD的总重量$$$j$ 如 $$$y_j$。然后$$$y_1=g_1x_{1,1}+g_2x_{2,1}+ … + g_ix_{i, 1}$和 $$$y_2=g_1x_{1,2}+g_2x_{2,2} +…+ g_ix_{i, 2}$。我们可以使用求和符号来折叠$$$y_1 = \sum g_ix_{i, 1}$ 和 $$$y_2=\sum g_ix_{i, 2}$。因为我们希望所有情况都如此$$$j$，我们使用“所有人”符号： $$$\forall$。这为我们提供了总重量限制的最终形式：

$$

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

超重

现在我们有了总重量，我们可以将公式应用于额外的负载：

$$

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

例如，如果 $$$y_1=1500$和 $$$U_1^P=1000$然后超重 $$$y_1^E = 1500 - 1000 = 500$公斤。将此乘以成本因子即可得出结果。乍一看，这似乎足够了，但是当ULD的整个货物的总重量不超过标准重量时，该怎么办？在这种情况下，如果我们使用“原样”公式，则过载权重将为负数。例如，如果标准重量为1650千克，分配的总重量为1000千克，则过载= 1000–1650 = -650。目标函数将此数字乘以过载的系数，得到负数。好像承运人为我们支付的运费少于标准重量的费用。

这是我们真正想要的：$$$\text{max}(y_j^E, 0)$。
这与为变量设置0相同，就像创建约束一样简单$$$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$

因此，我们在数学编程中实现了max（）函数：a = max（b，c），即a> = b && a> = c。让我们看看我们的定义。
目标功能：$$$\text{min} \sum_{j} y^E_j c^E_j$
$$$c_j^E$：ULD过载率 $$$j$
$$$y_j^E$：ULD超载 $$$j$; $$$y_j^ = y_j - U_j^P$
$$$U_j^P$：标准重量ULD $$$j$
$$$g_i$：总运输重量 $$$i$
$$$x_{i, j}$：决策变量； $$$x_{i, j}=1$如果装运 $$$i$ULD分配 $$$j$， $$$0$除此以外。
$$$y_j$：ULD指定的所有货运的总重量 $$$j$; $$$y_j=\sum_{i \in I}g_ix_{i,j} \quad \forall j \in J$

每个负载都必须飞行

此时，我们可以用Python编写此代码并将其发送到求解器。如果这样做，我们会发现求解器对任何航班都分配了零个交货，并且我们可以快速理解原因：最小化目标函数的最佳方法是不累积任何成本。这导致以下限制：必须将每个批次分配给某些ULD。我们会将其扩展到应分配给一个ULD的每个货物，尽管实际上我们可以将货物分为几个ULD甚至几个航班。

代表着$$$x_{i, j}$对于$ j $的单个值，只能为1。例如，如果我们考虑装运13，则$$$x_{13,1}+x_{13,2}+ x_{13,3}+ … + x_{13, J}=1$。我们想将此限制应用于每批货。$$$i$ （我们写成 $$$\forall i\in I$），我们可以使用求和运算符（（$$$\sum$），因此我们的最终限制是：

$$

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

鉴于此限制，求解器实际上将开始将货物分配给航班，但他将仅在所有可用航班之间分配货物，直到满足重量要求为止。然后，求解器将以最少的额外成本将每个剩余托运货物放置在一个ULD中。不包括此ULD的体积或重量。因此，以下附加限制是体积和重量。

体积和重量限制

让我们决定 $$$U_j^M$作为最大有效载荷（以千克ULD为单位） $$$j$和 $$$U_j^$以立方米为单位的最大体积 $$$j$。让我们决定$$$v_i$，以及以立方米为单位的货物体积 $$$i$。为了将模型限制为最大负载能力和最大体积，我们具有以下条件：

$$

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

行业资深人士将立即意识到这是不正确的。为什么？因为这些限制将货物当作可以像水一样倒入任何体积的货物。实际上，负载是刚性的或具有其他限制，例如堆叠。 10立方米的货物不能以等于10立方米的任意体积包装。为了应对这些情况，您需要解决容器包装的问题。我们检查某些卷是否适合其他卷，但这不在本文讨论范围之内。

现在，求解器将分配装运ULD，同时考虑最大重量和最大体积，同时使总成本最小化。但是还有另一个问题：我们没有说有关物品的指定和交货日期的遵守情况。实际上，分配货件时需要考虑四个时间戳：

货件实际准备好与ULD中的其他货件合并并加载航班的时间。让我们用$$$Q_i^-$代表发货准备的时间 $$$i$。
通常，必须将必须在目的地卸下货物的时间取消合并，并可以从货运站接收。让我们用$ Q_i ^ + $表示交货期限$$$i$。
所有货物必须交付到货运站才能装载到航班上的时间。让我们用$$$T_j^ -$代表货物ULD $ j $的削波时间。
航班到达时间：这是航班上的货物可在目标仓库中到达的时间。让我们用$$$T_j^+$ 代表ULD航班到达时间 $$$j$

来源和目的地

再介绍一套 $$$J_i$，我们将其定义为一组航班，其出发地和目的地与货物的出发和接收时间一致 $$$i$。换句话说，如果出发地85是从香港出发并到达伦敦的目的地，则$ J_ {85} $是所有从香港出发并到达目的地是伦敦的ULD的集合。
现在我们可以使用$$$j \in J_i$ 获得与运输贸易路线相匹配的ULD套件 $$$i$或者我们可以使用 $$$j \notin J_i$得到一组不匹配的ULD。为了禁止将货物绑定到与原产地和目的地不符的ULD，我们仅限制$$$x_{i,j} = 0$对于所有此类航班。该限制的详细说明如下：

$$

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

交货时间

在优化中使用时间戳时，将必要的时刻显示为Unix时间很方便。该方法的优点：

1. 将日期存储为数字。
2. 无需处理时区。
3. 求解器使用直接较少的比较。

航班必须在交货时间之前到达：
$$$\sum_{j \in J_i}T_j^+x_{i,j}<=Q_i^+ \quad \forall i \in I \quad$
请注意，就像上述对出发地和目的地的限制一样，我们已经表明此限制仅适用于集合中的ULD $$$J_i$哪里 $$$J_i$ 是一组与发送和接收货件相匹配的ULD $$$i$。就这样！让我们看一下整个模型。

完整模型

在这种限制下，求解器以成本最低的方式分配ULD项目，每批货物都从正确的出发地交付到正确的目的地。当然，货物可以按时交付，而不会因体积或重量而超载。

参量

$$$I$：一组所有货件。提交了一批货$$$i$
$$$J$：一组所有ULD。个别ULD为小写$$$j$。
$$$J_i$：一组匹配发送方和接收方的所有ULD $$$i$。
$$$g_i$：运输毛重 $$$i$以千克为单位。
$$$v_i$：装运量（立方米） $$$i$
$$$c_j^E$：ULD过载率 $$$j$美元/千克
$$$U_j^M$：最大承重ULD $$$j$公斤
$$$U_j^V$：ULD最大环绕声功率 $$$j$立方米
$$$U_j^P$：标准重量ULD $$$j$公斤

$$$T_j^-$：允许到ULD终端的交货时间 $$$j$。
$$$T_j^+$：ULD到达时间 $$$j$。
$$$Q_i^-$：发货准备时间 $$$i$。 
$$$Q_i^+$：交货期 $$$i$。

决策变量和目标函数：
$$$y_j$：ULD总重量 $$$j$
$$$y_j^E$：ULD超载 $$$j$以千克为单位。
$$$x_{i,j}$：1如果发送 $$$i$ULD分配 $$$j$否则为0。

目标功能

$$

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

局限性

$$$y_j$ -ULD $ j $上的货物总重量： $$$y_j=\sum_{i \in I} g_ix_{i,j} \quad \forall j \in J$
额外权重jE为最大值（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$
必须将每个交货准确分配给1个ULD： $$$\sum_{j \in J} x_{i,j}=1 \quad \forall i \in I$。
超低密度脂蛋白$$$j$ 不能超过最大重量： $$$y_j<=U_j^M \quad \forall j \in J$
超低密度脂蛋白 $$$j$不能超过最大容量： $$$\sum_{i \in I}x_{i,j}v_i <= U_j^V \quad \forall j \in J$

进一步的步骤

本文介绍了飞行负荷目的背后的数学编程。但是仅仅写数学是不够的。下一步是使用Pyomo之类的AML或使用自己的求解器API（例如Python Gurobi API）来实现该程序。之后，开发人员将编写代码以传输所有可用出发和飞行的参数。然后将模型实例发送到求解器。求解器以最佳方式设置决策变量的值。然后开发人员必须对决策变量的值做一些事情。