Shortest path navigation algorithm for driverless plug-in electric vehicles

Abstract

Driverless plug-in electric vehicles (DPEVs) have attracted a growing attention in transport engineering due to their low environmental impact and increased level of automation. When compared to regular internal combustion engine vehicles, DPEVs have two characteristics: 1) DPEVs require a higher frequency of recharge operations; 2) DPEVs are controlled by predetermined intelligent algorithms, rather than drivers' experience and judgement. Hence, a critical question is how DPEVs can navigate while minimising travel costs subject to recharge requests. Considering potential delays induced by recharge operations, traditional shortest path algorithms, such as Dijkstra’s algorithm, are not completely suitable. In this paper, two predominant recharge modes are considered. One is traditional charging stations, where vehicles must stop and wait to recharge. The other is modern charging lanes, which automatically recharge traversing vehicles. In this case, vehicles might make a detour to catch charging lanes. This study proposes a shortest path navigation algorithm for DPEVs in traffic systems with recharge facilities. First, a transport network is converted into a fictitious network wherein both charging stations and charging lanes are represented as charging stations with appropriate delay nodes. Second, we introduce a novel mathematical optimisation model for the shortest path navigation problem for DPEVs accounting for recharge delay. Third, we develop a refined label-correcting algorithm accounting for en-route recharge modes and recharge delay for this routing problem. Finally, systematic experiments are conducted to validate the performance of the proposed approach. The results demonstrate that the algorithm can generate route decisions with high computational efficiency. Moreover, we report that the navigation results can be significantly influenced by the number and the location of recharge facilities, recharge time and the distance limits of DPEVs. Show more