A complementarity equilibrium model for electric vehicles with charging

This paper presents a complementarity equilibrium model for electric vehicles (EVs). Under the equilibrium conditions, each EV takes the path that is shortest and does not violate the driving range. When the driving range has to be violated, the EVs are allowed to choose a path with a charging station to extend their driving range. To find the shortest such path, a constrained shortest path problem with replenishment (CSPP with replenishment) is formulated that considers the driving range limit of EVs. The CSPP is solved with a label-correcting algorithm with two additional steps that substantially reduce the computation time and the required memory. The first procedure is a pruning technique that eliminates exploring branches (of an enumeration tree) that can no longer become incumbent and the second procedure is an indexing technique that works as a pointer for navigating the generated (enumeration) tree when it becomes too large. Numerical experiments on a number of networks show a substantially lower computation time compared to existing algorithms and the results provide several insights into the driving patterns of EVs. When charging time is increased, the EVs shift to paths that have a longer travel time but a shorter distance. Hence, the total network distance decreases but the total network travel time increases. We also show that unregulated expansion of the charging infrastructure can actually increase the total network travel time due to the presence of Braess' paradox.