BiS4EV: A fast routing algorithm considering charging stations and preferences for electric vehicles

Ying Zhang, Bin Wu, Yao Yi Chiang, Xin Zhang, Yuanchang Chen, Muyang Li, Fanyu Li

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


Electric Vehicles (EVs) have grown in recent years as they have become a promising alternative to traditional fossil fuel-driven vehicles. As a result, new routing algorithms that consider both the locations of charging stations and the charging preferences of users are necessary to maintain urban traffic efficiency. This paper proposes a Constrained Route Planning (CRP) approach, called BiS4EV, to provide efficient route planning for EVs in large urban road networks. CRP is an NP-hard problem. BiS4EV introduces a two-layered structure to solve the CRP problem for EVs. In the first layer, BiS4EV integrates the locations of charging stations and the battery consumption on each road arc into a road network graph and proposes a fast routing algorithm that considers the constraints of battery capacity and charging preferences to find the shortest feasible path for EVs. The second layer incorporates charging policies to the obtained path, which forms a complete route plan for EVs. Such a two-layered method breaks down the complexity of the problem and avoids directly solving the entire NP-hard problem. We have proved the correctness of the proposed approach in theory, and the presented experimental results verified the efficiency and the effectiveness of BiS4EV from the practical aspect.

Original languageEnglish (US)
Article number104378
JournalEngineering Applications of Artificial Intelligence
StatePublished - Sep 2021
Externally publishedYes

Bibliographical note

Funding Information:
This work is jointly supported by the National Natural Science Foundation of China (No. 52078212 ), the State Key Laboratory of Simulation and Regulation of Water Cycle in River Basin , China Institute of Water Resources and Hydropower Research (No. IWHR-SKL-202003 ) and the Jilin Scientific and Technological Development Program (No. 20190303133SF ).

Publisher Copyright:
© 2021 Elsevier Ltd


  • Charging policy
  • Charging station
  • Electric vehicle
  • Road network
  • Route planning


Dive into the research topics of 'BiS4EV: A fast routing algorithm considering charging stations and preferences for electric vehicles'. Together they form a unique fingerprint.

Cite this