Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle Charging
Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle Charging
复制标题
DOI：
10.1145/3428336
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Bo Sun;Ali Zeynali;Tongxin Li;M. Hajiesmaili;A. Wierman;D. Tsang
中科院分区：
文献类型：
--
作者：
Bo Sun;Ali Zeynali;Tongxin Li;M. Hajiesmaili;A. Wierman;D. Tsang
我们引入并研究了多背包分数在线背包问题的一个通用版本，该问题包含物品可分配到哪个背包的异构约束，以及物品分配到背包的速率限制约束。这个问题概括了先前分别处理的背包问题和单向交易问题的变体，并且还应用于电动汽车（EV）充电的实时控制。我们引入了一种新算法，该算法在通用问题可达到的最佳竞争比的一个加法因子范围内实现了竞争比，并且在背包和单向交易文献中的特殊情况下达到或改进了已知的最佳竞争比。此外，我们的分析提供了一种基于实例相关的原始 - 对偶分析的在线算法设计新方法，这种方法将最坏情况实例的识别与算法设计联系起来。最后，我们通过基于电动汽车充电轨迹的实验来说明所提出的算法。
We introduce and study a general version of the fractional online knapsack problem with multiple knapsacks, heterogeneous constraints on which items can be assigned to which knapsack, and rate-limiting constraints on the assignment of items to knapsacks. This problem generalizes variations of the knapsack problem and of the one-way trading problem that have previously been treated separately, and additionally finds application to the real-time control of electric vehicle (EV) charging. We introduce a new algorithm that achieves a competitive ratio within an additive factor of one of the best achievable competitive ratios for the general problem and matches or improves upon the best-known competitive ratio for special cases in the knapsack and one-way trading literatures. Moreover, our analysis provides a novel approach to online algorithm design based on an instance-dependent primal-dual analysis that connects the identification of worst-case instances to the design of algorithms. Finally, we illustrate the proposed algorithm via trace-based experiments of EV charging.