Optimal Routing for Plug-In Hybrid Electric Vehicles
针对插电式混合动力汽车，提出考虑不同驾驶模式能效差异的路径规划算法，以最小化油耗，并证明问题为NP完全，给出精确算法和近似方案。
We propose routing algorithms for plug-in hybrid electric vehicles (PHEVs) that account for the significant energy efficiency differences of vehicle operating modes and recommend the predominant mode of operation for each road segment during route planning. This is to enhance fuel economy and reduce emissions. We introduce the energy-efficient routing problem (EERP) for PHEVs and formulate this problem as a new class of the shortest path problem. The objective of the EERP is to not only find a path to any given destination but also to identify the predominant operating mode for each segment of the path to minimize fuel consumption. EERP can be generalized to a new class of problems in the context of network optimization, where for each arc we need to choose which resources to use to minimize the consumption of one of the resources subject to a constraint on the other resource. In this problem, the resource selection is mutually exclusive, which means we cannot choose both resources together for an arc. We prove that the EERP is NP-complete. We then propose two exact algorithms, and a fully polynomial time approximation scheme (FPTAS) to solve the EERP. We demonstrate the performance of our proposed exact and FPTAS algorithms using road network data from Southeast Michigan. The results show that incorporating our proposed algorithms during route planning leads to significant energy savings for PHEVs over simplistic routing algorithms and current practice.