PEGA-EV: A Data-Driven Policy Learning Method for Energy-Efficient Electric Vehicle Routing with Time Windows

Constructive heuristics are widely used for the Electric Vehicle Routing Problem with Time Windows (EVRPTW) due to their low computational cost and transparent decision logic. Under hard customer time windows and battery-limited operation, however, manually designed priority rules often fail to generalise across heterogeneous instance structures. We propose a Policy--Evolving Genetic Algorithm for Electric Vehicle Routing (PEGA--EV) that learns a deterministic linear routing policy embedded within a greedy route-construction procedure. Candidate moves are ranked using a compact set of instance-normalised features capturing spatial proximity, time-window urgency, customer demand, and distance to the depot. An extended variant, PEGA--6, augments this representation with an explicit energy-risk feature that penalises moves leaving limited post-move reachability to the depot or charging stations. Feasibility is enforced by construction through strict time-window compliance and conservative safe-haven reachability to charging infrastructure throughout route building. Experiments on the full 92-instance Schneider benchmark show that PEGA--EV consistently constructs fully feasible solutions with competitive fleet size and total distance at millisecond-scale construction times. Reductions in fleet size and travelled distance also indicate improved operational efficiency, which is relevant for energy-aware and sustainable electric vehicle logistics systems. These results indicate that PEGA--EV provides a fast and reliable constructive baseline for EVRPTW, delivering competitive solution quality under strict energy and time-window feasibility, with consistent zero-shot transferability across heterogeneous instance families.