php - 订单履行优化算法

Question

我正在 Magento 中开发一个模块，我需要在其中进行 100% 订单履行优化，例如:

有现货，我们有以下产品:

Product1    - 2 (Qty in stock)
Product2    - 2
Product3    - 3
Product4    - 5

在商店中，我们有以下需要准备发货的订单:

Order1      -   Product1    - 1 (Ordered Qty)
                Product2    - 2
                Product3    - 1
                Product4    - 4

Order2      -   Product2    - 2
                Product4    - 1

Order3      -   Product1    - 1 
                Product3    - 2
                Product4    - 4

如果我将开始从上到下为订单挑选产品，如下所示:

Case 1 for assignment of Products to Orders

Order1      -   Product1    - 1 (Ordered Qty)   -  1 (Assigned Qty from Stock)
                Product2    - 2                 -  2
                Product3    - 1                 -  1
                Product4    - 4                 -  4

Order2      -   Product2    - 2 (Ordered Qty)   -  0 (No Stock Remain)
                Product4    - 1                 -  1 

Order3      -   Product1    - 1 (Ordered Qty)   -  1 
                Product3    - 2                 -  2 
                Product4    - 4                 -  0 (No Stock Remain)

但是，如果我开始从底部挑选产品，如下所示:

Case 2 for assignment of Products to Orders

Order1      -   Product1    - 1 (Ordered Qty)   -  1 (Assigned Qty from Stock)
                Product2    - 2                 -  0 (No Stock Remain)
                Product3    - 1                 -  1 (Short Picked) 
                Product4    - 4                 -  0 (No Stock Remain)

Order2      -   Product2    - 2 (Ordered Qty)   -  2 (Assigned Qty from Stock) 
                Product4    - 1                 -  1 

Order3      -   Product1    - 1 (Ordered Qty)   -  1 (Assigned Qty from Stock)
                Product3    - 2                 -  2 
                Product4    - 4                 -  4        

如您所见，在案例 1 中，我们仅完成了 33% 的订单履行，其余 66% 的订单未完全完成。但在案例 2 中，我们仅完成了 66% 的订单履行，其余 33% 的订单未完全完成。

例如，我们采用了自上而下和自下而上的方法，但它可以以任何方式处理以获得最大的订单完成百分比。

如果有人以前处理过此类问题，我们将不胜感激。

Answer 1

好消息 您的问题可以建模为 Integer Programming problem很容易:

输入:让 S(j)产品库存j让o(i,j)即产品数量j按顺序i .

变量: 让x(i)等于1如果订单完成并且0否则。

公式:你要解决以下问题:

max sum x(i)

s.t. sum ( o(i,j) x(i) ) <= s(j)对于任何 j

坏消息是解决这类问题是NP-hard因此，没有已知的多项式算法可以最优地解决这个问题。因此，您必须使用启发式方法以近似的方式解决它，例如，按订单所需的商品数量对订单进行排序。