Solving the Multivariant EV Routing Problem Incorporating V2G and G2V Options

In the near future, gasoline-fueled vehicles are expected to be replaced by electrical vehicles (EVs) to save energy and reduce carbon emissions. A large penetration of EVs threatens the stability of the electric grid but also provides a potential for grid ancillary services, which strengthens the grid, if well managed. This paper incorporates grid-to-vehicle (G2V) and vehicle-to-grid (V2G) options in the travel path of logistics sector EVs. The paper offers a complete solution methodology to the multivariant EV routing problem rather than considering only one or two variants of the problem like in previous research. The variants considered include a stochastic environment, multiple dispatchers, time window constraints, simultaneous and nonsimultaneous pickup and delivery, and G2V and V2G service options. Stochastic demand forecasts of the G2V and V2G services at charging stations are modeled using hidden Markov model. The developed solver is based on a modified custom genetic algorithm incorporated with embedded Markov decision process and trust region optimization methods. An agent-based communication architecture is adopted to ensure peer-to-peer correspondence capability of the EV, customer, charging station, and dispatcher entities. The results indicate that optimal route for EVs can be achieved while satisfying all constraints and providing V2G ancillary grid service.