减少销售损失的关键：利用高速代理辅助 MCTS 优化企业设施网络

21/06/2024

三个要点

✔️ 的侧重于企业在开设或关闭地区分支机构以及调整设施网络时如何最大限度地减少销售损失。然而，准确估算销售额既费时又费钱。为解决这一问题，蒙特卡洛树搜索（MCTS）被用来支持代用模型，从而加快评估速度。
✔️ 代用函数速度快，但准确性较低，已被证明能高效解决优化问题。具体来说，我们研究了关闭零售店以尽量减少销售损失的问题。
✔️ 未来的工作将研究更好的代用函数的实现及其在其他数据集和领域的应用，并将概率论考虑在内。

Surrogate Assisted Monte Carlo Tree Search in Combinatorial Optimization
written by Saeid Amiri, Parisa Zehtabi, Danial Dervovic, Michael Cashmore
(Submitted on 14 Mar 2024)
Comments: Accepted to the ICAPS Planning and Scheduling for Financial Services (FINPLAN) 2023 workshop
Subjects: Artificial Intelligence (cs.AI)

code：

本文所使用的图片要么来自论文、介绍性幻灯片，要么是参考这些图片制作的。

概述

本文重点探讨企业在开设或关闭地区分支机构以及调整设施网络时，如何最大限度地减少销售损失。然而，准确估算销售额既费时又费钱。为了解决这个问题，本文支持使用蒙特卡洛树搜索（MCTS）的代用模型，以加快评估速度。结果表明，与普通 MCTS 相比，由快速代用函数支持的 MCTS 有可能提供更快、更一致的解决方案。

介绍

本文重点讨论服务和零售企业需要根据人口变化和不断变化的市场趋势决定其设施选址的情况。该问题属于组合优化，通常在计算上难以解决。因此，本文提出了一种称为蒙特卡洛树搜索（MCTS）的技术，该技术用于游戏和其他领域，通过搜索可能的行动并评估每个行动的价值来解决问题。

MCTS 也被应用于设施选址问题，并提出了代用辅助 MCTS（SMCTS），它结合了快速代用评估函数和慢速默认评估函数。主要评估函数是评估盈利能力的回归模型，但由于其计算成本较高，因此引入了代用函数。该方法适用于关闭酒类销售网络的问题，目的是最大限度地减少销售损失。结果表明，MCTS 和替代函数的结合减少了计算时间。

建议方法

这是一个设施选址问题，目的是尽量减少因零售店关闭而造成的销售损失。我们的目标是通过关闭该网络中的 M 家店铺，将最终的销售损失降至最低。为此，我们需要优化代表每家店铺开张和关闭的向量 X。具体来说，X 是通过最小化某个评估函数来最小化店铺关闭造成的损失。该评价函数不仅取决于店铺关闭造成的损失，还取决于店铺的销售额和其他店铺的情况。

该解决方案框架采用了代理辅助 MCTS（SMCTS）。在树状结构中确定节点，通过选择、评估、扩展、备份和重新评估等步骤找到解决方案。

下图显示了在代理辅助蒙特卡洛树搜索（SMCTS）中，节点值是如何通过不定时的重新评估步骤来完善的。

它使用替代函数进行评估，并包括一个重新评估步骤，以调整误差。这就确保了节点值的准确更新，并保证了寻找最佳解决方案的搜索效率。

试验

通过实验评估，分析了 SMCTS（代理辅助 MCTS）在不同问题设置下的性能。

首先，使用爱荷华州酒类数据集进行了实验。其中包括商店销售额和位置信息。主评估函数 Fm 是使用 XGBoost 回归模型估算的，该模型评估每家店铺的销售额。代用函数 Fs 则是一个计算速度比 Fm 更快但准确度较低的模型。

左图：显示在 SMCTS（代用辅助蒙特卡洛树搜索）中，偶尔的重新评估步骤如何提高节点的价值。横轴表示需要删除的存储空间数量。
中心图：显示 SMCTS 的各种代用误差。纵轴表示代用函数 Fs 的评估与总评估的比率，横轴表示 RMSE 越大的代用函数。
右图：评估 SMCTS 和 MCTS 所选商店的一致性。纵轴显示了 SMCTS 和 MCTS 所选商店的数量，结果是随机抽取的 10 个县的平均值。

具体结果表明，代用功能的使用频率随着要删除的店铺数量的增加而增加，从而减轻了总体评估负担。随着代用误差的增加，重新评估的次数也会增加，但只要 SMCTS 与 MCTS 相匹配，这种增加是可以接受的。

最后，比较了两种删除不同存储空间方法的一致性。在大多数情况下，SMCTS 的输出与 MCTS 的输出相匹配，表明两者是一致的。然而，由于代用函数估计不足，在一些离群县发现了不一致的情况。

这些结果表明，SMCTS 对设施选址问题非常有效，尤其适用于大规模问题和代用函数质量较低的情况。