MILP-Based Charging and Route Selection of Electric Vehicles in Smart Grid

Widely accepted as an eco-friendly alternative to conventional vehicles, electric vehicles (EVs), however, have a limitation, such as a charging schedule is necessary for its journey since overloading at a charging station may cause grid failure. Also, despite the current advancement in technology, the battery capacity of EVs is still limited, which affects the cruise range of the vehicles, and it can be solved by en route charging of EVs. However, the charging rate may vary across different public charging stations. This may motivate electric vehicle owners to follow a route that is different from the traditional shortest route. In this paper, we consider a joint charging and route optimization problem, where a transport operator has a number of EVs at a warehouse, and he/she is supposed to deliver certain goods or services to different delivery locations. We have proposed two mixed-integer linear programming (MILP) models, where the delivery locations are first distributed among the EVs, and second, routes for the EVs are determined that minimizes the total travel time, while charging on the route. We prove that the problem is NP-complete. Detailed simulation has been carried out on a realistic dataset 419, and solved using the commercial solver CPLEX, and IBM’s drop-solved platform. The results show that an even distribution of delivery locations among EVs along with their partial charging at different charging stations en route proves to be a useful model for fast delivery of services/goods while minimizing their total travel time.