🕵🏽 😻 👩🏽‍💻 我们如何选择承运人的货物 🌹 🎓 👊🏽

下午好。我们的名字叫Ilya Bashtanov（Tochka-Tochka开发人员）和Tatyana Voronova（2M中心数据分析师）。我们想谈谈选择运输货物的任务的技术实施。

问题的实质如下。仓库中有一些货物需要从城市A运到城市B。我们可以假设仅考虑了货物的重量，其大小或多或少是标准的（欧洲货盘）。想要收取中转货物的承运人希望尽可能多地携带，但受到包裹重量和数量的限制。有必要为他从仓库中的可用货物中形成一些批次的变体。

在这种情况下解决的业务任务：

尽可能高效地装载车辆，从而增加运输收入。
在用户可接受的时间内解决交付问题（包括FIFO原则）。

该项目立即看起来很有吸引力。首先，从数学的角度来看：提出了一种解决经典组合优化问题的算法。其次，PostgreSQL是作为DBMS提出的，由于具有许多功能，可靠性和良好的性能特征，近年来它的流行一直在不断增长。当然，涉及许多不同参与者的实际任务的重要性和项目规模也成为了很大的动力。

算法

该任务是经典背包包装问题的一种变体。背包问题是NP-complete的。尽管在数学上尚未证明，但这些问题无法在多项式时间内解决。这意味着精确算法（例如穷举搜索变体或其优化的变体）在实践中不起作用，因为它们具有复杂性

。近似方法可提供最佳时间的解决方案。例如，贪心算法假定最大重量尽可能长地放在背包中。它的复杂度不超过排序的复杂度

O (2^{n})

$O(2^n)$

，但结果可能并非最佳。还有一类遗传算法可以在有限的时间内给出良好的结果，但是它们是不确定的，在我们的情况下，这将导致在重复呼叫期间发出不同的发行选项，很难向客户和运营商解释。结果，该选择落在近似方法上，该近似方法在多项式时间内保证了结果的准确性。因此，我们有：

(O (n * l o g n))

$(O(n * log n))$

配重 $w_1,w_2,... , w_n$
货物总重量的限制 $W_\max$
货运限额 $Q_\max$

需要找到最大总重量满足约束条件的商品子集。

这个想法是通过增加商品的权重并应用贪婪算法来减少商品的种类。在这种情况下，近似解是在完全多项式时间内找到的，即具有保证精度的解

1 - ε

$1- \varepsilon$ 获得的复杂度是的多项式

n

$n$ 和

ε

$\varepsilon$ 。

在算法的输入处，我们有一个盘子，其中包含商品的四舍五入重量以及每个重量的座位数。使用贪婪算法，我们尝试获取总权重的样式选项

W_{max},

$W_\max,$

W_{max} - 1,

$W_\max-1,$

W_{max} - 2,

$W_\max-2,$

\dots,

$…,$

0

$0$ 。为此，在设置目标总重量后，在周期中，我们从剩余负载中选择最大重量的货物，以不超过目标总重量。如果达到最大允许量

Q_{max}

$Q_\max$ ，循环结束。结果组合存储在临时数组中。

可能的组合数量可能很大，并且方便用户从少量选项中进行选择，但是同时仍然应该有一个选择。选择优选的组合产生了另外的任务。为了不复杂，我们决定尽可能给出两个选择。对于仓库，建议首先发送最重的货物，因此我们将组合按货物最大重量的降序排列。如果最大最大重量的组合超过两个，我们给出两个：最大和最小数量的货物。

测验

为了进行测试，我们选择了所考虑算法的两种实现，它们的细节无关紧要：一种在Java中，另一种在PL / pgSQL（PostgreSQL DBMS的过程语言）中。应当立即指出，最终的选择不仅受测试结果的影响，而且还受体系结构考虑，可用性和其他因素的影响。但是首先，任务是选择两个实现之一。

使用了两个测试环境：一个用于测试开发的桌面和一个用于在与真实环境相似的条件下进行测试的服务器。

dev： HP Probook 4740s客户端工作站+ 32位2 xPentium®双核CPU E5300 @ 2.60GHz和4 GB RAM，Ubuntu Linux 16.04，PostgreSQL 10.3。
test: 64-bit 2 x Intel Xeon CPU E5-2673 v4 @ 2.30GHz 14 , CentOS Linux 7.4, PostgreSQL 10.3

在PostgreSQL数据库中准备了一个测试表，其中包含7000个负载，随机权重为20到800 kg。为了进行测试，我们使用了PostgreSQL的标准pgBench实用程序，该实用程序在测试过程中执行了500个事务（10个连接，每个50个事务）。每笔交易都使用随机参数（重量限制在10到1000公斤，货物数量限制在1到50件）调用算法。所有随机变量平均分配。

对于第一个算法，每个事务都启动一台Java机器，并将JAR存档及其算法代码传递给它以供执行。主Java类通过JDBC驱动程序连接到数据库，从表中接收测试数据并将算法应用于它们。

对于第二种算法，每个事务都调用PostgreSQL数据库的存储函数，该函数从表中读取测试数据并应用该算法。

表1.

主要测试的结果除了主要测试的结果显示在表1中之外，还进行了算法2的另一项测试，其中比较了用于获取初始数据的不同选项：从数据库，文件，随机数组生成。事实证明，对于7000个负载，将数据从DBMS传输到本地阵列所需的时间比实际的堆栈算法要多。

发现。

在我们的任务中，性能更多地取决于系统的体系结构以及与数据库的交互速度，而不是所使用的算法。算法1的另一项测试证实了这一点，其中从数据库中选择数据花费了大部分时间。
选项2的扩展性稍好一些，这显然是由于对RAM的要求较低（临时数据库表用于存储中间结果）。

结果，选择了第二种算法，该算法在第二年中进行了较小的改动。结果，寻求一种具有可接受的精度且平均交易时间少于1秒的解决方案。

开发

与往常一样，生活进行了调整，因此我不得不调整实施方式。

实际上，承运人在洋基拍卖中以浮动价格保留托运货物。严格来说，不是通过拍卖出售的选项，但这是在另一个站点进行单独对话的主题。除了最大货物重量和最大数量之外，承运人还设置了两个城市（路线的起点和终点）和所需的装载时间。之后，每对仓库（在出发城市和目的地城市）的选择程序会根据几个标准过滤货物，特别是考虑到仓库的工作时间和最大运输成本（这些成本仍由发件人支付，并将其权重转移到包装算法中）。在算法的输出处，获得了权重列表，根据这些权重列表，选择了一组特定商品，这些特定商品将作为拍卖要约发布。

最初，重量被四舍五入为10千克的倍数的值。在运行过程中，很明显精度会受到明显影响，结果开始与常识相矛盾，例如，当存在重量为12和19千克的货物时，系统可以选择第一个。仓库秤提供的数据精度为1千克，对于当前的体积和负载，秤的整数值算法的性能被证明是可以接受的，因此他们拒绝了四舍五入。将来，随着发货数量的增加，计划将舍入取整为5千克的倍数的值。

使用当前数据量和查询强度进行堆栈算法的操作开销并不重要。在货物选择阶段以及其他系统操作过程中，需要大量资源。

业务发现

Point-Point的任务是一个有效的物流流程，尤其是在交通拥堵方面实现车辆的最佳使用：运输最少的空隙时。

解决货运优化问题的全球目标：节省资源有助于经济增长，为中小型企业创造更多机会，并改善环境。

Center 2M和Tochka-Tochki的专家发现了一种适合所有运输过程参与者的软件数学解决方案。它可以用于联邦网络，在每个点上，由500个运输商要求提供7千个托盘（对应于足球场的大小），并且在不到1秒的时间内获得了结果。

文章的作者：Ilya Bashtanov（i-bash），塔蒂亚娜·沃罗诺娃（Tatyana Voronova）特沃罗诺娃）

我们如何选择承运人的货物

算法

测验

开发

业务发现

More articles: