Algorithms for Battery Utilization in Electric Vehicles

作者：Adany Ron; Tamir Tami^*

来源：Applied Artificial Intelligence, 2014, 28(3): 272-291.

DOI：10.1080/08839514.2014.883906

We consider the problem of utilizing a pack of m batteries serving n current demands in electric vehicles. When serving a demand, the current allocation might be split among the batteries in the pack. A battery%26apos;s life depends on the discharge current used for supplying the requests. Any deviation from the optimal discharge-current is associated with a penalty. Thus, the problem is to serve an online sequence of current requests in a way that minimizes the total penalty associated with the service. %26lt;br%26gt;We show that the offline problem, for which the sequence of current demands is known in advance, is strongly NP-hard and hard to approximate within an additive gap of omega(m) from the optimum. For the online problem, we present a competitive algorithm associated with the redundant penalty at most m. Finally, we provide a lower bound of 1.5 for the multiplicative competitive ratio of any online algorithm.

• 出版日期2014-3-16