  As a telecom provider, our company has a critical mission to maintain telecom
services even during power outages. To accomplish the mission, it is essential
to maintain the power of the telecom base stations. Here we consider a solution
where electric vehicles (EVs) directly supply power to base stations by
traveling to their locations. The goal is to find EV routes that minimize both
the total travel distance of all EVs and the number of downed base stations. In
this paper, we formulate this routing problem as a new variant of the Electric
Vehicle Routing Problem (EVRP) and propose a solver that combines a rule-based
vehicle selector and a reinforcement learning (RL)-based node selector. The
rule of the vehicle selector ensures the exact environmental states when the
selected EV starts to move. In addition, the node selection by the RL model
enables fast route generation, which is critical in emergencies. We evaluate
our solver on both synthetic datasets and real datasets. The results show that
our solver outperforms baselines in terms of the objective value and
computation time. Moreover, we analyze the generalization and scalability of
our solver, demonstrating the capability toward unseen settings and large-scale
problems. Check also our project page: https://ntt-dkiku.github.io/rl-evrpeps.
