An Ablation Study of Constraint-Handling Mechanisms in Differential Evolution for Multi-Depot Vehicle Routing with Time Windows

Classical Differential Evolution (DE) solves the Multi-Depot Vehicle Routing Problem with Time Windows (MDVRPTW) efficiently but struggles to maintain time-window feasibility. This study investigates whether DE can be systematically hybridized with three constraint-handling mechanisms: adaptive penalty control, Large Neighborhood Search (LNS), and Tabu memory, implemented as independently toggleable components in a Java/JavaFX solver, enabling a controlled ablation across four MDVRPTW instances from Vidal et al. (2013): pr11a, pr11b, pr12a, and pr12b, with 30 independent repetitions per configuration per instance. LNS was the dominant contributor to cost reduction, cutting mean route distance by 35–45% relative to baseline DE (Friedman χ² = 14.80, df = 4, p = 0.0051). Tabu memory's individual contribution was not statistically significant, and contrary to the initial hypothesis, adaptive penalty substantially increased both route distance and time-window violations when combined with LNS and Tabu, raising mean fitness by 74–91% across instances while simultaneously reducing on-time service rate. No configuration achieved full feasibility on any instance. These results clarify which mechanisms meaningfully improve DE's behavior on MDVRPTW.