Online Algorithms for Automotive Idling Reduction With Effective Statistics

作     者：Dong, Chuansheng Zeng, Haibo Chen, Minghua 

作者机构：McGill Univ Dept Elect & Comp Engn Montreal PQ H3A 0E9 Canada Virginia Tech Dept Elect & Comp Engn Blacksburg VA 24061 USA Chinese Univ Hong Kong Dept Informat Engn Hong Kong Hong Kong Peoples R China 

出 版 物：《IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS》 (IEEE Trans Comput Aided Des Integr Circuits Syst)

年 卷 期：2015年第34卷第11期

页      面：1742-1755页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Basic Research Program of China [2013CB336700] University Grants Committee of the Hong Kong Special Administrative Region, China, under Theme-Based Research Scheme Project [T23-407/13-N] General Research Fund 

主　　题：Automotive idling reduction competitive analysis online algorithm ski rental problem 

摘      要：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 mu(B)- and q(B+), the expected length of short stops and the probability of long stops. We develop two online algorithms, a suboptimal closed-form algorithm and an optimal numerical solution, that combine the best of the well-known deterministic and randomized schemes to minimize the worst case competitive ratio. We demonstrate the algorithms perform better than existing solutions in terms of both worst case guarantee and average case performance using simulation and real-world driving data.