Resource Constraint Evacuation Route Planning: A Capacity-Aware Charge-Encoded State-Space Approach

Electric-vehicle evacuation planning requires evacuation routes that are both road-capacity feasible and driving-range feasible. Existing evacuation routing methods typically account for road capacity but do not explicitly enforce electric-vehicle range constraints, whereas electric-vehicle routing models usually focus on individual vehicle routing and do not address large-scale evacuation scheduling under shared road-capacity limits. This paper studies the Resource Constraint Evacuation Route Planning (RC-ERP) problem, in which evacuees must be routed from source locations to safe destinations while satisfying road-capacity constraints and a maximum travel-distance constraint between consecutive charging-station visits. We propose the Time-Expanded Charge-Encoded Routing Algorithm (TE-CERA), a scalable constructive heuristic that combines charge-encoded route generation with time-expanded capacity-aware scheduling. The proposed Node-Encoded Shortest Path (NESP) procedure computes charging-feasible spatial routes by tracking the accumulated travel distance since the most recent charging-station visit, while the scheduling stage assigns feasible departure times using a time-indexed edge-occupancy table. Under the stated modeling assumptions, the framework guarantees charging-feasible and capacity-feasible evacuation schedules. Experiments on real-world transportation networks show that TE-CERA eliminates charging-constraint violations while maintaining comparable evacuation times to a capacity-constrained evacuation routing baseline. The results demonstrate the feasibility and scalability of integrating electric-vehicle range constraints into evacuation routing, while also highlighting future extensions involving charging duration, charger capacity, and station-level queueing.