A Discrete Partial Charging Enabled Dynamic Programming Strategy for Optimal Fixed-Route Electric Vehicle Charging

The rapid adoption of Electric Vehicles (EVs), driven by stringent environmental regulations and rising fuel costs, is reshaping the landscape of Vehicle Routing Problems (VRP). This shift has led to the Electric Vehicle Routing Problem (EVRP), which incorporates EV-specific operational constraints such as limited driving range, energy consumption, recharging strategies, and detour-related charging costs. The challenge becomes even more critical in modern mixed fleets , where Electric and Internal Combustion Engine Vehicles (ICEVs) coexist and must be co-routed efficiently. A widely adopted two-step strategy first uses Capacitated VRP (CVRP) algorithms to generate energy-oblivious routes, then makes EV routes energy-feasible via charging station insertion. While VRP and CVRP are extensively studied, methods for efficiently ensuring energy feasibility for EVs on fixed routes remain limited. This article introduces the Fixed Route Vehicle Charging Problem with Discrete Partial Charging (FRVCP-DPC) , extending FRVCP by allowing partial recharging up to predefined discrete levels. We develop a scalable optimal Dynamic Programming algorithm, Best Energy Feasible Route Generator (BEFRG) , to select detour points, charging stations, and charge levels that minimize total route time while maintaining energy feasibility. To evaluate BEFRG in dynamic traffic conditions, we introduce EFRGen , a traffic-aware EVRP simulator built on Simulation of Urban Mobility (SUMO) and OpenStreetMap (OSM). Experiments on the Montoya benchmark—spanning 120 instances with up to 320 demand points and 38 charging stations—show that BEFRG computes optimal solutions for all cases within one minute.