通过二维货架空间分配最大化收益-研究论文

我们考虑优化分配连续矩形展示空间以最大化收入的问题。 在零售货架空间中的产品布置和特色广告展示或网页的设计中会遇到此类问题。 具体来说，我们允许 (i) 产品展示的形状具有垂直和水平组件，以及 (ii) 展示扩展到多个货架以进行店内展示。 由于展示产品的货架的垂直位置会影响其销售额，因此每个垂直位置在创收方面都有其自身的有效性。 最大化显示器的总加权收入的问题是非常 NP-hard 的。 因此，我们将其分解为两个子问题。 第一个包括将产品分配到不同的机柜。 在第二个中，在每个机柜内，每个产品的单元都排列在一个连续的矩形中并分配一个位置。 这些子问题使用一种创新方法来解决，该方法结合了整数规划和最大权重独立集问题的算法。 基于对现实世界和模拟数据的计算研究，我们证明了我们方法的效率和有效性。 具体来说，该方案产生的收益对于实际数据在最优值的 1% 以内，对于模拟数据的最优值在 5% 以内。