技术摘要：基于 k 次装箱的电力分配中的时间与供应公平性

1. 问题定义

本文探讨了发展中国家中公平电力分配的问题，在这些国家中，家庭总需求超过了可用供应容量（$S$）。核心挑战在于如何在需求（$D$）各异的家庭（$n$个）之间分配有限的电力，以最大化公平性。

作者定义了两个不同的优化目标：

1. 连接时间的平等分配：目标是最大化任何家庭连接到电网的最小时间量。代理的效用是二元的：仅当其在某个时间区间内的全部需求得到满足时才能获得效用；部分满足则产生零效用。这模拟了某些活动需要特定功率阈值才能运行的场景。
2. 瓦特（供应量）的平等分配：目标是最大化分配给任何家庭的最小电能数量（以千瓦时 kWh 计）。与基于时间的模型不同，该模型考虑了输送的电力体积，旨在使代理接收的总能量相等，即使它们的连接时间不同。

本文将基于时间的问题形式化为经典装箱问题的一个变体，称为k 次装箱（kBP）。在 kBP 中，给定一组物品（需求）和装箱容量 $S$，目标是将物品装入最少数量的箱子中，使得：

• 每个箱子中物品大小的总和不超过 $S$。
• 每个物品恰好出现在 $k$ 个不同的箱子中。
• 每个箱子不包含同一物品的多个副本。

2. 方法论与理论框架

理论基础

作者建立了电力分配问题与 kBP 之间的理论联系。

• 最优 $k$ 的存在性：他们证明，对于任何包含 $n$ 个家庭的电力分配实例，都存在一个有限整数 $k$，使得最优求解 kBP 问题即可得到连接时间平等分配问题的最优解。
• $k$ 的界限：论文基于家庭数量 $n$ 给出了该 $k$ 的上界，具体为 $k \le a(n)$，其中 $a(n)$ 是 $n \times n$ 二元矩阵的最大行列式（与哈达玛矩阵相关）。同时也为特定实例确立了 $k \ge n-1$ 的下界。
• 瓦特分配的不可行性：相反，对于瓦特的平等分配，作者证明了一个不可行性结果：不存在一个仅依赖于代理数量 $n$ 的有限 $k$ 来保证最优解。这是因为最优解可能需要需求较小的代理连接显著更长的时间，从而需要无界的重复比率。

算法扩展

由于 kBP 是 NP 难的，本文侧重于将现有的装箱近似算法扩展到 kBP 设置中：

1. 快速常数因子近似：

   • $FF_k$（首次适应）：作者扩展了首次适应算法，以处理输入实例的 $k$ 个副本（$D^k$）。他们证明了渐近近似比为 $(1.5 + \frac{1}{5k}) \cdot OPT(D^k) + 3k$。随着 $k$ 的增加，该比率趋近于 1.5，优于标准首次适应算法的 1.7 比率。
   • $FFD_k$（首次适应递减）：作者扩展了首次适应递减算法。虽然未证明紧确上界，但基于模拟数据，他们推测渐近比率为 $11/9$（约 1.22），优于标准 FFD 比率。
   • $NF_k$（下次适应）：下次适应的扩展被证明具有 2 的渐近比率。

2. 多项式时间近似方案（PTAS）：

   • 本文推广了 Fernandez de la Vega-Lueker 和 Karmarkar-Karp 算法。
   • Fernandez de la Vega-Lueker 的扩展实现了 $(1 + 2\epsilon)OPT(D^k) + k$ 个箱子。
   • Karmarkar-Karp 算法 1 和 2 的扩展提供了依赖于 $k$ 和 $\epsilon$ 的加性项的解，并在多项式时间内运行。

3. 瓦特分配的启发式方法：

   • 由于瓦特分配不存在通用的有限 $k$，作者提出了四种启发式算法（HA1–HA4）。
   • 这些启发式方法采用两步过程：
     1. 识别需求最小的一组代理，使其连续（全天候）连接。
     2. 对剩余代理和减少后的供应量应用基于 kBP 的策略（使用 $FF_k$ 或 $FFD_k$），以最大化最小瓦特分配。
   • 这些算法利用三分搜索来确定连续连接子集的最优大小（$g$），以最大化leximin向量（优先考虑处境最差的代理）。

3. 主要结果与实验评估

理论结果

• 近似比率：本文提供了 $FF_k$ 和 $NF_k$ 近似比率的严格证明。对于 $FF_k$，随着 $k$ 的增长，比率得到改善，理论上收敛于 1.5。
• 不可行性：证明没有仅依赖于 $n$ 的有限 $k$ 足以实现瓦特平等分配，这促使针对该特定变体转向启发式方法。

实验结果

作者使用两个数据集评估了他们的算法：

1. 合成数据：生成具有已知最优解的实例，以验证 $FF_k$ 和 $FFD_k$ 的近似比率。结果支持了以下推测：对于 $k > 1$，$FF_k$ 实现的比率为 1.375，$FFD_k$ 实现的比率为 $11/9$。
2. 真实世界数据：来自尼日利亚的 367 个家庭的数据集（来自 Oluwasuji 等人 [34, 35]），涵盖 13 周的每小时需求。

连接时间性能（平等时间）：

• $FF_k$ 和 $FFD_k$ 算法（测试时 $k=100$）在平等连接时间方面显著优于现有的启发式和基于 ILP 的方法（例如 [35] 中的舒适模型和供应模型）。
• 它们实现了代理之间接近零的最大效用差异，表明分配高度公平。
• 算法的运行时间相对于代理数量几乎呈线性。

瓦特分配性能（平等瓦特）：

• 在四种启发式方法中，HA1（使用 $FFD_k$）在向处境最差的代理供应最大电量方面表现最佳。
• HA4（使用 $FF_k$）在总输送瓦特数和总连接时间方面优于其他方法。
• 这些启发式方法成功平衡了将小需求代理连续连接与公平分配剩余供应给大需求代理之间的权衡。

4. 意义与主张

本文声称提供了一个实用、公平且高效的框架，用于资源受限环境中的电力分配。其主要贡献包括：

• 形式化：将 k 次装箱问题定义为公平资源分配的数学抽象，其中物品必须在不相交的集合中进行复制。
• 算法改进：证明了将标准装箱启发式方法扩展到 kBP 设置中，能产生比原始算法更好的近似比率，特别是改善了连接时间的平等结果。
• 实际应用：验证了这些理论扩展能够比之前的最先进方法更有效地解决现实世界的负荷削减问题，特别是在最大化所有家庭的最小连接时间方面。
• 新基准：建立了瓦特平等分配的新基准，表明虽然不存在理论上的最优 $k$，但启发式方法可以产生优于现有方案的公平性指标。

作者得出结论，使用 kBP 为实现公平电力分配提供了一条可行途径，特别是当目标是最大化每个代理的连接时间时；并且，为了最大化输送能量体积（瓦特）的公平性，启发式调整是必要且有效的。