  The integration of electric vehicles (EVs) with the energy grid has become an
important area of research due to the increasing EV penetration in today's
transportation systems. Under appropriate management of EV charging and
discharging, the grid can currently satisfy the energy requirements of a
considerable number of EVs. Furthermore, EVs can help enhance the reliability
and stability of the energy grid through ancillary services such as energy
storage. This paper proposes the EV routing problem with time windows under
time-variant electricity prices (EVRPTW-TP) which optimizes the routing of an
EV fleet that are delivering products to customers, jointly with the scheduling
of the charging and discharging of the EVs from/to the grid. The proposed model
is a multiperiod vehicle routing problem where EVs can stop at charging
stations to either recharge their batteries or inject stored energy to the
grid. Given the energy costs that vary based on time-of-use, the charging and
discharging schedules of the EVs are optimized to benefit from the capability
of storing energy by shifting energy demands from peak hours to off-peak hours
when the energy price is lower. The vehicles can recover the energy costs and
potentially realize profits by injecting energy back to the grid at high price
periods. EVRPTW-TP is formulated as an optimization problem. A Lagrangian
relaxation approach and a hybrid variable neighborhood search/tabu search
heuristic are proposed to obtain high quality lower bounds and feasible
solutions, respectively. Numerical experiments on instances from the literature
are provided. The proposed heuristic is also evaluated on a case study of an EV
fleet providing grocery delivery at the region of Kitchener-Waterloo in
Ontario, Canada. Insights on the impacts of energy pricing, service time slots,
range reduction in winter as well as fleet size are presented.
