Energy efficient navigation management for hybrid electric vehicles on highways

Plug-in Hybrid Electric Vehicles (PHEVs) are gaining popularity due to their economical efficiency as well as their contribution to environmental preservation. PHEVs allow the driver to use exclusively electric power for 30-50 miles of driving, and switch to gasoline for longer trips. The more gasoline a vehicle uses, the higher cost is required for the trip. However, a PHEV cannot go long with its stored electricity without being recharged. Thus, it needs frequent recharging as compared to traditional engine vehicles powered by gasoline. Moreover, the battery recharging time is usually long, which leads to longer delays on a trip. Therefore, for the deployment of the PHEV technology it is necessary to provide a flexible navigation management scheme considering an efficient recharging scheduling, which allows choosing an optimal route based on the fuel-cost and time-to-destination constraints. In this paper, we show that this PHEV navigation management problem is NP-Complete and present a formal model to solve the problem using Satisfiability Modulo Theories (SMT) that provides a vehicle driver a routing plan, as well as the potential charging points that satisfy the requirements (e.g., the maximum fuel cost and the maximum waiting time). We also present a price-based navigation control technique to achieve better load balance for the system. Our evaluations show that the formalization can be efficiently solved even with large sizes of highway topologies and large number of charging stations.