雅安市网站建设_网站建设公司_云服务器_seo优化-吉林市网站建设公司

原文：towardsdatascience.com/how-we-optimized-the-problem-of-global-containers-distribution-ea6201d4513e?source=collection_archive---------5-----------------------#2024-08-01

使用线性规划优化全球范围内的集装箱供应链操作。

https://willian-fuks.medium.com/?source=post_page---byline--ea6201d4513e--------------------------------https://towardsdatascience.com/?source=post_page---byline--ea6201d4513e-------------------------------- Will Fuks

·发表于Towards Data Science ·阅读时间 18 分钟·2024 年 8 月 1 日

–

最近，我被一位同事邀请加入一个位于巴西的大型公司的项目，该公司在全球范围内销售商品和服务。

该项目涉及运输优化，非常有趣——也很具挑战性——所以我想写一下这个项目，以及我们如何使用cvxpy库解决问题（该库也被像Tesla、Netflix和Two Sigma等公司用来解决优化问题）。

本文具体内容包括：

在多项约束条件下，全球运输集装箱的挑战。
我们如何管理公司的数据，并将其描述为一组线性变换。
我们如何调整变量和约束，以适应线性规划的公式。
用来保证目标函数和约束条件是凸的技术——cvxpy 的主要限制。

事不宜迟，让我们开始吧。

1. 挑战

当项目启动时，公司向我们透露，他们已经在Microsoft Excel Solver上实现了解决方案，以优化如何最好地管理集装箱。该 Solver 旨在减少运输、货运、存储和操作的成本，同时遵循一系列约束条件。

该解决方案运行良好，但随着业务扩展，过程开始停滞，并遭遇一些瓶颈，正如公司所解释的那样。有时，他们需要分配的集装箱太多，以至于 Solver 处理整个数据集并给出答案可能需要几天时间。

他们要求我们开发一种新系统，能够在处理工作负载的同时，还要足够灵活，以便系统能够根据需求接受新的约束条件。

首先，公司在全国各地都有工厂，集装箱根据各工厂的需求进行准备：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/001c29d34f438addc891bce6c9dbdac9.png

分布在全国各地的工厂及其集装箱。图像来自作者。

每个工厂根据自己的需求每周生产集装箱，这意味着某些工厂会生产比其他工厂更多的集装箱。每个集装箱携带自己的货物，因此销售价格也会发生变化（这个变量很快会变得重要）。

每个集装箱的命运也各不相同；有些将被运输到邻近国家，而其他的则需要跨越全球。因此，公司需要将集装箱送到适当的码头，否则将面临无法成功交付的风险（因为各国码头之间缺乏连接）。

在试图将工厂与适当的码头连接时，几个新的变量会出现。首先，每个工厂可以选择如何运输集装箱：要么使用火车——并且在这样做时，可以选择不同类型的合同——要么使用卡车（同样，也有多种合同类型）：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/fdbfee15861f3e4967091c415c6c6177.png

工厂可以根据可用选项选择如何将集装箱运输到码头。图像来自作者。

现在，另一个挑战出现了：每个集装箱都有特定的目的地，而每个码头上也有相应的船只。因此，目的地必须匹配！如果一个应当运往香港的集装箱被运输到一个没有前往亚洲的船只的码头，那么我们就浪费了一个集装箱。

匹配问题意味着，有时工厂可能需要将集装箱运输到更远的码头（并支付更多费用），仅仅因为这是将巴西与世界其他地方连接起来的唯一选项。托运人将是另一个变量，他们需要考虑每艘船上的空间可用性以及船只的目的地。

托运人也可能允许所谓的“超额预定空间”，也就是说，正如这一概念应用于航空航班，它同样适用于船只，但这里的概念稍微宽松些：对于某一周，托运人可以告知一个“超额预定因子”，这会给我们一个关于每艘船可以额外添加多少个集装箱的概念，超过了该船的最大容量——并且按预期，运费会更高。优化器可以利用这个因子来分配剩余的集装箱，并利用更便宜的运输方式，例如。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/d4b2327f58c1a5ca015aaba46d9191ed.png

增加了托运人这一挑战。图像来自作者。

优化器还必须考虑一套需要遵循的规则。以下是一些简要的要求：

船只有最大容量：每艘船通过所谓的“贸易”服务特定区域。每个发货人对于每个贸易有一个最大集装箱容量——这项规则有时可以通过超额预定来打破。
连接工厂和码头：工厂只能将集装箱发送到具有有效且可用运输方式的码头——如果工厂没有与某个码头的火车站连接，则优化器必须选择其他运输方式。
运输限制：公司明确表示，运输合同和可用时段可能会有所不同；他们与火车公司有协议和许可证，可以每月使用特定的时段，这为可运输的集装箱数量设定了上限。
连接出发码头和发货人：优化器必须将集装箱从工厂发送到包含有空间的发货人所在的码头，并且服务该集装箱的贸易目的地。
超额预定：超额预定是可能发生的——就像是我们手中额外的“招数”。每个发货人都有一个可以超过最大上限的预定槽位的系数。超额预定的集装箱成本更高，只有在所有先前可用的空间已经被占用的情况下才应使用。
运输与否：优化器可能会得出结论，认为将某个集装箱存放在工厂中比运输它更为合适，这会影响到总成本的预期。

我们到了吗？嗯，还没有。实际上，挑战要复杂一些，因为它应当包括工厂运输每个集装箱所需的时间，并与发货人何时能在码头可用进行连接。如果我们选择了一个太慢的运输方式，可能会错过船只，随后可能要等待并希望有另一艘船前往相同的目的地，或者我们可能会直接失去这个集装箱。本文没有考虑时间变量，因为这会使得开发过程更为复杂。

现在我们已经有了挑战，让我们看看我们是如何解决它的 🥷！

3. 线性规划

线性规划（LP）是一种优化技术，也接受作为线性变换表示的一组约束。

在数学上，我们有如下的内容：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/70d4a1a86c13c0f4e06e37a43132f0a3.png

f是目标函数（或成本函数），在我们的挑战中，它表示与每个运输、船只相关的成本，以及集装箱是否处于超额预定状态以及将集装箱留在工厂与否的权衡。

值得注意的是，x代表优化器必须操作的变量，以便最小化目标函数。在我们的案例中，它将决定选择哪种运输、船只、码头和超额预定状态。

为了让这个概念更具实用性，并与本文的主要挑战关联起来，让我们从一个非常简单的 cvxpy 实现开始。

3.1 简单示例

假设以下设定：

公司在某一周生产了 4 个集装箱，所有集装箱都来自同一个工厂。它们的价值为：[$200, $300, $400, $500]。
工厂只能使用一种类型的运输方式。
工厂仅连接到一个码头。
在这一假设的周内，两个发货人将在码头上有船可用。发货人分别收取每个集装箱$100 和$130 的费用。
第一个发货人有 2 个剩余空位；第二个发货人只有 1 个。

优化器的主要目标是将 4 个集装箱分配到可用的船只空间上，同时最小化运输的总成本。

我们如何在 cvxpy 中实现这个呢？其实很简单。首先我们需要一个变量x，表示优化器可以做出的选择。在这种情况下，表示x的最佳方式是使用形状为(4, 2)的布尔数组——每行对应一个集装箱，2 列表示有两个发货人可供选择：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/4684be83ca2133aa3fc0f31123427229.png

x的一个可能值的示例，表示优化器可以做出的选择以最小化成本。图片来自作者。

行中“1”的值表示优化器将对应的集装箱分配给该列的相应发货人。在此示例中，第一个和第二个集装箱分配给第一个发货人，第三个和第四个集装箱分配给第二个发货人。请注意，每行只能包含一个“1”的值，其他必须是“0”，否则就意味着某个集装箱被同时分配给了两个发货人，这是无效的。

因此，优化器的挑战将是不断调整这个数组，直到找到总成本的最小值，同时仍然满足要求。

至于代码实现，这是一个可能的实现方式：

需要考虑的关键点：

cvxpy 需要变量、约束条件和最终的成本表达式。
代码行constraint0 = cx.sum(x_shippers, axis=1) <= 1是一个cvxpy必须遵守的约束条件，用于优化x。作为一般规则，约束条件必须保持优化过程的凸性（这保证了收敛性），并且可以是等式表达式或上界等式。在此案例中，sum运算符作用于axis=1，意味着“按列求和”。
该规则意味着每行x_shippers的和最多等于 1，这保证了某个集装箱不会同时分配给多个发货人。
由于求和约束遵循<=规则，因此某行可以全是 0，这意味着某个集装箱可能完全没有被分配给任何船只（例如，可能由于船只上没有空余空间）。
constraint1 = cx.sum(x_shippers, axis=0) <= shippers_spaces的作用与constraint0相似。它基本上表达的是每个船只分配的所有容器不能超过其最大容量。
然后，我们来到了问题的核心：成本函数，定义为：cost = cx.sum(x_shippers @ shippers_cost.T) + container_costs @ (1 — cx.sum(x_shippers, axis=1))。第一个部分cx.sum(x_shippers @ shippers_cost.T)基本上表达了为每个船只分配每个容器的所有成本。 “@” 表示点积，因此该操作的结果已经是与每个容器相关的成本，必须对其进行求和得到总成本。
第二部分container_costs @ (1 — cx.sum(x_shippers, axis=1))可以说更有趣，因为在这里我们开始看到可以用来在cvxpy中表达问题的策略。通过使用1矩阵减去按行求和的cx.sum(x_shippers, axis=1)，我们实际上得到了一个 (4, 1) 矩阵，其中每行表示容器是否曾经被分配给某个船只。
点积container_costs @ 未选择的容器跟踪哪些容器没有被分配，并求和它们的成本值。

这是结果的一个示例：

print(x_shippers.value)array([[0.,0.],[0.,1.],[1.,0.],[1.,0.]])

容器 0 没有被分配给任何船只（因为它是最便宜的，所以没有被优先考虑）。

在我们继续之前，给出一些提示：

你可以通过 Colab 运行 cvxpy 的实验。只需运行!pip install cvxpy，然后你就可以开始了。
在实现模型时，你可以运行一些检查来确认你走在正确的道路上。我喜欢使用的一种技巧是，例如，先给变量设置一个初始值，比如x_shippers = cx.Variable((2, 2), value=[[1, 0], [0, 1]])。然后，运行操作（例如r=A @ x_shippers）后，你可以打印结果的r.value属性，以检查一切是否按预期工作。
在使用 cvxpy 时，有时你会在运行优化时遇到一些错误。一个常见的问题是错误信息：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/495c23a75b2347bb0018533dd00b4ab7.png

这是臭名昭著的规范凸优化问题（简称DCP），它由一组规则组成，这些规则必须遵守，以保证约束和目标是凸的。例如，如果我们用max操作符代替sum，我们仍然会得到相同的结果，但在尝试运行时，我们会遇到DCPError。因此，DCP 意味着所有用于表达成本和约束的操作必须遵循凸性的规则。

上面的示例对于温和地介绍cvxpyAPI 很有帮助。现在让我们考虑一个主题相同但稍微复杂的例子。

3.2 中等示例

让我们再次考虑相同的 4 个容器，费用和条件相同。这次，第一和第三个容器将运往目的地 “0”，而第二和第四个容器必须运往目的地 “1”，并且可用空间与之前相同（[2, 1]）。我们为此问题得到的输入大致如下：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/0f2cdb29fbc489646b636f49b2111817.png

行中的容器，列中的成本和目的地。图片由作者提供。

所有容器都是在同一家工厂生产的，但这次有 2 种运输方式可供选择：火车和卡车，分别对应的费用是 [$50, $70]。对于这一周，我们最多只能将 2 个容器分配到火车上。

在继续之前，思考一下你将如何解决这个问题。记住，使用线性规划时推荐的基本步骤：

描述这个问题需要哪些变量？x_shippers = ...
如何表达成本函数？cost = ...
如何使用通过矩阵和数学运算（符合 DCP）的约束来构建整个问题？destines <= x_shippers...

（你也可以使用 Colab 进行尝试）

…

这是一个可能的解决方案：

总体上，它遵循与之前相同的结构。关于代码的一些说明：

现在我们正在优化两个变量，x_shippers和x_transport。
我们使用映射器来处理火车和将承运人链接到其目的地。根据我们的约定，映射器变量的名称通常从行空间中的变量名开始，然后是列空间。例如，destine_shippers表示行代表目的地，列代表承运人。
具体来说，dest_ships_arr = destine_shippers_map[containers[:, 1]]这一行的结果是一个包含 4 行的矩阵，每一行包含负责运送相应容器目的地的船只。为了更清楚地说明：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/21da9318f47e715e0fee80b97c4aff47.png

destine_shippers_map矩阵将输入容器转换为一个数组，表示每个容器适合的承运人。图片由作者提供。

映射器允许将输入数据应用于约束和成本函数。在前面的例子中，优化器被限制只能将承运人 0 分配给第一个容器，将承运人 1 分配给第二个容器，例如。这是通过以下代码实现的：constraint02 = x_shippers <= dest_ships_arr。

使用类似技术的地方有：constraint11 = cx.sum(x_transports @ train_map.T) <= 2)，矩阵点积操作跟踪所有与火车相关的运输。最终的总和等同于分配给火车的所有容器，必须小于或等于 2。
约束条件会接收两个数字（例如：“00” 或 “10”）。这是为了将所有约束按特定主题进行分组。在这个示例中，第一个 0 代表所有关于船只的约束，1 代表运输。我们这样做是因为，如果以后需要增加约束的数量，只需在“0”后添加新数字，并扩展最终的数组。

最终解是：x_shippers = [[1, 0], [0, 0], [1, 0], [0, 1]]和x_transport = [[1, 0], [0, 0], [1, 0], [0, 1]]（两个结果巧合相等）。优化器没有为第二个集装箱分配航运商，因为船上总共只有 3 个位置。第一个集装箱通过火车运送到航运商 0，第三个集装箱也是如此，最后一个集装箱通过卡车运送到航运商 1。

现在让我们稍微提升难度，增加一些挑战。

3.3 完整示例

让我们使用之前的示例，但现在增加一个新变量：码头。现在，工厂可以将集装箱运输到两个可用的码头。火车和卡车可以到达码头 0，费用分别为[$50, $70]，而码头 1只能通过卡车到达，费用为$60。两个航运商都能以相同费用到达两个码头。

你会如何解决这个问题？

你可能会意识到，添加码头变量使得问题变得更加复杂。许多连接码头和运输的尝试会导致DCPErrors。看看你是否能找到策略，确保它们的建模按预期进行。

…

….

你成功了吗？这是一个可能的解决方案：

这在大多数情况下与之前的示例相等。但请注意，现在我们引入了 AND 变量，它将码头和运输变量连接起来。

关键点是：当优化器为x_transport选择一个值时，最终会影响x_docks的选择。然而，当它选择了码头它也会反过来影响运输！为了解决这个问题，我们引入了 AND 变量，使优化器能够同时辨别其决策的影响。

这一实现首先通过 y 变量完成：y_docks_and_transp = cx.Variable((4, 4), boolean=True, name="docks AND transportations")。这个变量也会被优化器更新，但我们将强制它成为两个其他数据源的AND组合，正如我们接下来会看到的那样。我们使用的技术通过列模板作为参考，将码头和运输相结合：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/b69fc16b735bed79ebcd1dddbc187c46.png

使用的 AND 变量将两个变量结合起来，在本例中是码头和运输。图像由作者提供。

这些列将呈现树形结构。正如变量名称"y_docks_and_transp"所示，首先出现的名称是"docks"，这意味着码头将是第一个参考，然后运输会随之跟进，如上所示。以第二行为例，第二列的值是“1”。这意味着它选择了码头 0 和运输方式 1（卡车）。

使用这个模板，我们可以创建其他同时作用于码头和运输变量的数据和约束。例如，这里是我们如何指定费用的：transport_and_dock_costs = np.array([[50, 70, 0, 60]])，这意味着码头 0 和运输工具 0（火车）的费用为 $50。

优化器可以使用模板将每个x变量转置到码头和运输设置中。为此，我们使用了如下的映射器：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/8874df58b7448fd7c66dc8a8cc12d71e.png

左图是将x_transport变量映射到dock_AND_transp映射的过程。右图则是将x_docks映射到docks_AND_transp。图片由作者提供。

如果优化器选择运输方式 0，那么它会映射到左图的第一行。请记住，火车不会前往码头 1，这就是为什么在第三列中是“0”的原因。此外，注意变量的名称也遵循一种模式：transp_dock_transp_map表示行代表运输工具，并且它映射到码头和运输工具之间的 AND 连接，其中码头排在前面。

这是我们使用y_docks_and_transp的地方。当优化器更改x变量时，我们将其映射到码头和运输领域。但随后，我们需要将两个映射结合起来，以准确知道哪个点对应码头和运输变量的 AND：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/df1fd6f7697ef3aa218d18c7eb98f17d.png

这张图看起来可能很吓人，但其实相当简单。首先，我们有x变量和点操作符（“@”），它将x映射到码头和运输领域。然后，我们强制执行 AND 操作来找出y_docks_and_transps。图片由作者提供。

如上图所示，首先我们将x变量转置到码头和运输领域。然后，我们获取结果并应用 AND 操作，专门找出每个容器的码头和运输工具选择：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/daa3a7baecd3d0d7526eeac54c141b83.png

AND 操作的结果。图片由作者提供。

第一行意味着优化器选择了码头 0 和火车。第二行意味着它选择了码头 1 和卡车。请注意，由于码头 1 不与火车连接，因此第三列永远不会是“1”，这也解决了有效连接的问题。

但是，实际上这并不像看起来那么简单，因为大多数尝试实现这个 AND 操作都会引发DCPError。为了解决这个问题，我们使用了辅助约束：

x1=x_transports @ transp_dock_transp_map x2=x_docks @ dock_dock_transp_mapconstraint12=y_docks_and_transp>=x1+x2 –1constraint13=y_docks_and_transp<=x1 constraint14=y_docks_and_transp<=x2 constraint15=(cx.sum(y_docks_and_transp,axis=1)==cx.sum(x_shippers,axis=1))

通过这样做，y_docks_and_transp被强制在x1和x2都是“1”的时候才是“1”。当需要进行 AND 操作时，可以使用此技术。

constraint15是一个安全条款，保证只有已路由的容器会被保留。

这是x和y的最终值：

x_ships=[[1,0],[0,0],[1,0],[0,1]]x_transports=[[1,0],[0,0],[1,0],[0,1]]x_docks=[[1,0],[0,0],[1,0],[0,1]]y_docks_and_transp=[[1,0,0,0],[0,0,0,0],[1,0,0,0],[0,0,0,1]].