A Cost Efficient Online Algorithm for Automotive Idling Reduction

Idling, or running the engine when the vehicle is not moving, accounts for 13%-23% of vehicle driving time and costs billions of gallons of fuel each year. In this paper, we consider the problem of idling reduction under the uncertainty of vehicle stop time. We abstract it as a classic ski rental problem, and propose a constrained version with two statistics μB-and q_B+, the expectation of short stops' lengths and the probability of long stops. We develop an online algorithm that combines the best of the well-known deterministic and randomized schemes to minimize the worst case competitive ratio. We demonstrate the robustness of the algorithm in terms of both worst case guarantee and average case performance using simulation and real-world driving data. Copyright 2014 ACM.