Feasibility-Repair Adaptive Large Neighborhood Search for EVRPTW-SPD with Time Windows and Full Recharge

Optimizing electric vehicle route planning with time windows and simultaneous pick-up and delivery (EVRPTW-SPD) remains challenging due to the complex interactions among routing, dynamic cargo loads, charging behavior, and time windows. Under a full-recharge policy in which vehicles are fully recharged whenever they visit a charging station, a hybrid heuristic framework is proposed. We first build a complete customer assignment by inserting unrouted customers one by one. Energy infeasibility is handled by a hierarchical charging-station repair module (CRM), which combines a greedy algorithm with a parallel evolutionary algorithm to identify the best repair plan while minimizing total detour cost. The repaired solution is then further improved through adaptive large neighborhood search (ALNS) with dynamic operator selection and simulated annealing (SA) acceptance. Load, time-window, and battery violations are penalized adaptively during the search, and a restart rule is used when the search stays trapped for too long. Experiments on the Akbay benchmark indicate that the method consistently finds feasible solutions and converges within acceptable computing time, demonstrating the effectiveness of feasibility-oriented repair and adaptive exploration of infeasible solutions for the full-recharge EVRPTW-SPD problem.