? 摘要
合约广告（GD）分为两个不同的阶段，即离线售卖阶段和在线投放阶段。前者进行合约库存分配，主要考虑库存利用率的提升从而提升收入；后者则针对合约进行广告投放展示，考虑履约完成率。现有的研究通常将这两个阶段分开处理，订单在离线售卖阶段时，并不考虑在线投放阶段的实际情况。
本文提出一种用于合约广告的双目标库存分配方法，旨在最大化分配给新广告订单的展示次数（即库存分配）提升库存利用率的同时，优化库存分配的平衡性以实现履约完成率的提升。由于所提出的问题是高维、多目标和多约束的，我们设计了一种高效的局部搜索算法，该算法交替关注这两个目标。实验结果表明，我们的算法优于进化算法和Gurobi。前者常用于多目标优化中，后者是一个知名有竞争力的商业求解器。基于该项工作整理的论文已被KDD 2024接受，欢迎阅读交流。
论文：Bi-Objective Contract Allocation for Guaranteed Delivery Advertising
下载：https://dl.acm.org/doi/10.1145/3637528.3671752
1. 背景介绍
合约广告（GD）对于电子商务营销中的精准投放至关重要，其目的是将广告投放给满足特定且可能复杂要求的目标用户。这些要求涉及用户的特征，如年龄、性别、所使用的设备、地理位置等。
传统的合约广告通常考虑已签约订单需求的情况下估算和分配新订单的最大可售卖量。在实践中，常见的方法基于供应和需求节点的容量，寻找能够最大化新订单可用售卖量的最优分配。然而，在线投放阶段可能因各种潜在问题而无法满足已签约的订单。传统方法仅考虑新订单的最大售卖量，可能会因为忽视在线投放中的问题而导致投放不足违约和高额罚款。因此，我们提出了一种新的双目标广告库存分配问题，该问题同时考虑新订单的最大可用售卖量和投放中的履约完成率。我们在下文中将该问题称为双目标GD问题。
第二个目标，通过平衡已分配展示量的分布提升投中履约完成率。一种常见情况是：投前系统在假设将所有供应节点的展示量都分配给需求订单的情况下，最大化新订单的可用展示量。然而，假设的预测是准确的，部分的展示量可能会在在线投放阶段被分配给另一个订单，导致无法满足订单 。为避免这种情况，我们希望投前系统在确定新订单的展示量时不要超卖供应节点中的库存，且尽量平衡的分配减小履约风险。
本文核心亮点：1) 解决了实际操作中涉及线下投前阶段和在线投放阶段的合约广告库存分配问题，形成了双目标合约广告问题；2) 提出了交替优化的双目标局部搜索算法。实验结果表明，所提出的算法在实际业务场景中优于著名的MOEAs和商业工具Gurobi。
2. 问题建模
2.1 订单广告库存分配
合约广告库存分配可以通过下图所示的二部图来说明。在左侧，每个供应节点表示一组库存 。供应节点可以通过各种属性的组合来标记，如城市、性别、用户等，每个节点可以作为广告订单的一组展示。 是 能够提供的展示数量。在右侧，每个节点表示广告商订单中的需求 。是所需的展示数量。
我们用邻接矩阵 表示供应节点和需求节点之间的连接关系，其中 表示供应的库存可以为需求提供展示，，；否则，。我们用表示可用于需求的供应集，即与相连的供应集，。类似地，我们用 表示可以提供展示的需求订单。
传统的合约广告工作通常致力于最大化可以为新订单需求分配的展示数量。例如，给定一组现有订单的需求 和一个新订单需求 ，常见的目标是最大化可分配给的供应量，同时确保现有需求订单的需求。我们在下文中将现有需求订单集表示为。
合约广告系统通常包含大量的供应和需求，需要在短时间内给出解决方案。通常采用启发式方法在有限时间内搜索高质量的解决方案。然而，仅仅为了最大化新订单的库存分配可能会导致不同供应之间的库存不平衡，进而在在线服务阶段导致潜在的履约风险。为了解决这个问题，我们引入了下列方程（2）目标，该目标旨在平衡不同供应的展示分配。我们希望实现一个分配，使得在总可用供应中的比例与相应供应中的展示分配 的比例之间的偏差最小，这有助于保证供应之间的平衡。对于需求，我们希望为 分配的展示次数由 中的多个供应节点提供，而不是由一个或少数几个特定节点提供。此外，每个供应节点提供的展示次数应与其容量相关。
总体而言，给定一组供应，一组现有需求订单，以及一个新订单 ，我们的双目标 GD 广告库存分配问题是找到一个分配 ，以优化以下两个目标（我们记 为集合，为集合）：
双目标：
多约束：
其中，方程(1) 表示最大化新订单需求的展示次数（我们通过减法将其表示为最小化问题）， 方程(2)旨在保持不同供应的库存平衡，方程(3) 表示分配的展示次数不会超过每个供应节点的库存，方程(4) 约束现有订单的需求必须得到满足，方程(5) 中的表示供应 为需求提供的分配次数。请注意，实际上，是预定义的现有需求订单集合，我们的问题目标是为新需求订单达到适当的分配。
2.2 帕累托解集
多目标整数规划问题可以表述如下：。其中，对于我们提出的问题，目标数 ，表示搜索空间。我们处理的是最小化问题。
我们定义，对于两个解和 ，如果 在两个目标上都好于（我们称支配），记作 。则。如果 并且 ，则两个解 和 是非支配的，记作。
一个解 是帕累托最优的，如果_。所有可行非支配解的集合称为帕累托最优集。帕累托最优集的目标值形成帕累托前沿 。
多目标优化问题的目标是找出帕累托最优集中的解。然而，由于现实问题的搜索空间通常很复杂，多目标优化的实际方法是搜索一组近似的帕累托最优集的非支配解。
3. 双目标局部搜索算法
3.1 算法框架
我们提出了 BOLS 方法如下所示。由于所解决的 GD 问题是高维度且高度约束的，可行解的搜索空间是稀疏的。实际场景需要在有限的时间内获得解决方案，即时间要求相对较短。因此，我们在初始化阶段执行贪婪策略。
在优化循环中，算法分两个阶段进行：寻找可行解（第3-5行）和分别改进可行解（第7-16行）。第一阶段确保为改进阶段找到一个可行解。采用SatisfyingMove迭代操作，直到解 中不存在违反的约束条件。之后，
在改进阶段，应用ImproveMove操作以寻找更好的解决方案。在解决双目标 GD 问题时，BOLS 交替优化其中一个目标。在实践中，当 步后没有改进时，它会切换优化另一个目标（第16行）。在前述步骤中，BOLS 处理一个解，解决二分图中排除的问题。当获得一个可行（且更好）的时，BOLS 将通过为分配展示次数来创建一个完整的分配。并且，我们通过比较新的完整分配（第11行）来维护一组帕累托解。当达到终止条件，即耗尽 cutoff_time 时，BOLS 返回帕累托集。
3.2 初始化
适当的初始化可以提高算法性能并加速收敛。为了获得一个有效的初始解，尽管它不需要是可行的，我们通过最小化 （2）所示的目标来生成它。在实践中，对于每个 和 ，我们通过分配每个分量来计算 的初始化值，同时确保 。通过简单的线性变换，生成的初始解可以证明满足(4)中的约束。请注意，我们在这一步中排除了，并且 的分配将在验证现有订单的分配之后进行。
3.3 满足约束阶段
由于初始解的可行性无法保证，BOLS首先使用SatisfyingMove搜索可行解。SatisfyingMove通过更新解中的一个或两个变量的值来创建新解。SatisfyingMove需要调整以满足(3)的约束，即确保每个供应节点提供的总库存不超过其可用库存。请注意，这里已经满足了(3)中的约束，且尚未考虑新的需求订单。
如Algorithm 2所示，SatisfyingMove旨在减少由供应节点提供的库存，其中每个supply节点提供的库存超过其库存容量。该函数首先检测是否可以通过调整分配给一个需求订单的库存来满足随机选择的的违反约束（第4-7行）。如果无法满足违反的约束，则该函数使用多次选择最佳策略（BMS）调整两个随机选择的需求订单的相应分配，BMS从次独立试验中选择最佳操作（第9-14行）。在本文中，我们根据先前工作的建议将设置为100。当调整两个需求订单的分配时，我们获得最佳得分的操作（第13行），该得分表示由两个供应节点提供的库存的平衡性。评分函数基于操作前后两个节点使用率之间的差异计算。是已分配给需求的总库存数，可以看作的使用率。
3.4 优化阶段
为了获得有效的解决方案来应对（1），（2）两个目标，我们在算法中应用ImproveMove来改进现有订单的分配，，并迭代测试新的完整分配以应对。我们定义：为新需求订单的总剩余库存，为每个供应节点为现有订单提供的库存量的平衡水平。
ImproveMove通过交替优化和来解决这两个目标。在比较现有需求订单的分配和时，我们将和的偏差分别表示为和。我们定义如果。
对于给定的解决方案和当前的非支配解决方案集，ImproveMove首先通过调优随机选择的一个来找到一个新的，，其中。是由约束(3),(4)确定的可行域（第1-7行）。根据优化模式，我们选择最小化或的（第5行）。如果获得了，则ImproveMove终止（第7行）。
如果在调优一个的次试验后未能获得，则它将在调优两个的次试验中进行，直到获得（第8-12行）。在实践中，它随机选择两个和（第9行），并通过更新值（第11行），其中是根据相应的模式计算的（第10行）。如果，则该试验失败。当调优一个和两个变量都失败时，ImproveMove将在调优一个的次试验中通过进行，其中是根据最小化或的相应模式计算的（第13-20行）。函数在获得时终止并返回（第19行）。否则，它通过估算每个，并选择得分最高的一个，其中表示当前关注目标的进展，表示另一个目标的进展（第20行）。
3.5 更新解集
如Algorithm 3所述，在得到一组可行解后，UpdatePareto会用更新Pareto集（第11行）。我们依次检查中的。如果，，则 将从 中删除。如果对于所有 ，，则 将被加入到 中。在实践中，。
4. 实验结果
4.1 评估指标
我们在这里介绍用于算法比较的四个评估指标：(1) 表示与其他测试算法相比，该算法得到最优结果的实例数；(2) 表示在给定时间限制内获得可行解的实例数。解决一个实例表示获得至少一个满足所有现有需求订单所需印象的解决方案；(3) 是被解集支配的目标空间的体积。给定一个具有目标值的解集，其中是搜索空间的维数，以及一个参考点， ， 其中表示勒贝格测度，表示正交体，其角点分别为和；(4)是评估实际广告收入的实用度量标准。
其中。SR的定义是使用实际分配数据调整的。
4.2 与多目标遗传算法对比
由于进化计算在多目标优化问题中得到了广泛应用，本节中我们与四种多目标进化算法（MOEAs）：NSGA-II、NSGA-III、U-NSGA-III 和 C-TAEA，进行比较。
下表展示了五个数据集上测试算法的， 和正则化的结果。为了研究算法在不同截止时间下的性能影响，我们展示了给定截止时间10s、60s和300s的结果。
这些观察结果表明，MOEAs在获取相对较小搜索空间的可行解方面具有优势。与此同时，BOLS在解决大规模问题方面表现出优越性。此外，通过交替专注于每个目标的策略，结果显示BOLS相对于MOEAs能够在所有数据集上给出更好的解决方案。
4.3 与Gurobi的求解数量对比
我们现在将我们提出的 BOLS 与著名的商业优化工具 Gurobi 进行比较。Gurobi 已成功应用于各种现实世界的场景，并在许多混合整数规划问题中表现出显著优势。
虽然 Gurobi 不提供求解帕累托解集的功能，但它可以通过为每个目标值分配权重，将多目标优化问题转换为单目标问题，从而求解问题。因此，我们通过为和 分别分配权重 和来测试 Gurobi 对我们提出的双目标 GD 问题的解决方案。在实践中，我们使用 Gurobi 解决问题 ，同时约束条件保持不变。
我们测试了 Gurobi 的精确方法（Gurobi-E）和启发式方法（Gurobi-H）进行比较。下表展示了各方法的和 。我们可以观察到，在给定为时间10s时，BOLS 在五个数据集中都优于 Gurobi 的两种方法。随着运行时间的增加，Gurobi 在供应节点规模相对较小的数据集 中优于 BOLS。然而，BOLS 在其余数据集中仍显著优于 Gurobi。
4.4 收益对比
如前几节所述，我们在这项工作中解决了合约广告系统的双目标问题，在与其他方法的对比中，而我们提出的 BOLS 显示出其优势。在本节中，我们使用销售收入（SR）指标来评估该工作的实际收益。在本节中，我们仅将 BOLS 与 Gurobi 进行比较，因为 Gurobi 通常应用于商业场景，而 BOLS 显示出相对于 MOEAs 的显著优势。在实践中，我们使用 和的九种设置获得的最佳结果来计算 Gurobi 方法的 SR，并使用获得的 Pareto 解集的最佳结果来计算 BOLS 的 SR。下表展示了60s（商业场景中常用的设置）的结果，这是测试实例中 SR 的总和。结果表明，与 Gurobi 的精确方法和启发式方法相比，的销售收入分别提高了1.4%和 3.7%。对于，这些值分别为23.5%和19.5%。由于没有获得可行解，和的 Gurobi 值缺失，如下表所示。
5. 结论
本文提出一种新的双目标库存分配方法，用于合约广告的离线售卖阶段，这个问题首次考虑了流量供给的均衡分布。该方法可以在实际的在线服务阶段更好地分配订单，避免无法履约。我们提出了一种双目标局部搜索算法来解决这个问题，实验结果表明，它相对于多目标进化算法和 Gurobi 有着显著的优势，证明了我们的方法在解决这种高维度和高度约束的双目标整数规划问题上的优越性。
未来，我们计划深耕该方法的并行版本，以应对更大规模的数据集，从而使提出的问题和方法能够推广到更多实际应用场景。并且可以将双目标局部搜索应用于其他二分分配问题，例如通信中的资源分配、供应链库存分配、库存分配，尤其是具有高维度和众多约束的分配问题。
? 参考文献
[1] Nader Al Theeb, Hazem J Smadi, Tarek H Al-Hawari, and Manar H Aljarrah. 2020. Optimization of vehicle routing with inventory allocation problems in Cold Supply Chain Logistics. Computers & Industrial Engineering 142 (2020), 106341
[2] Peiji Chen, Wenjing Ma, Srinath Mandalapu, Chandrashekhar Nagarjan, Jayavel Shanmugasundaram, Sergei Vassilvitskii, Erik Vee, Manfai Yu, and Jason Zien. 2012. Ad serving using a compact allocation plan. In Proceedings of the 13th ACM Conference on Electronic Commerce. 319–336.
[3] Kalyanmoy Deb. 2011. Multi-objective optimisation using evolutionary algorithms: an introduction. In Multi-objective Evolutionary Optimisation for Product Design and Manufacturing. Springer, 3–34
[4] Andrzej Jaszkiewicz. 2002. Genetic local search for multi-objective combinatorial optimization.European Journal of Operational Research137, 1 (2002), 50–71
[5] Wuyang Mao, Chuanren Liu, Yundu Huang, Zhonglin Zu, M Harshvardhan, Liang Wang, and Bo Zheng. 2023. End-to-End Inventory Prediction and Contract Allocation for Guaranteed Delivery Advertising. InProceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 1677–1686.
[6] Hong Zhang, Lan Zhang, Lan Xu, Xiaoyang Ma, Zhengtao Wu, Cong Tang, Wei Xu, and Yiguo Yang. 2020. A request-level guaranteed delivery advertising planning: Forecasting and allocation. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2980–2988.
作者:容洵
