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

Farid Morsidi

doi:10.56532/mjsat.v6i4.801

Authors

Farid Morsidi Faculty of Computing and Meta-Technology, Computing Department, Universiti Pendidikan Sultan Idris, Tanjong Malim, Perak, Malaysia, 35900

DOI:

https://doi.org/10.56532/mjsat.v6i4.801

Keywords:

Differential Evolution, Metaheuristics, Ablation Study, Large Neighborhood Search, Multi-Depot Vehicle Routing Problem

Abstract

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.

References

D. Wang, J. Jiang, R. Ma, and G. Shen, “Research on Hybrid Real-Time Picking Routing Optimization Based on Multiple Picking Stations,” Math. Probl. Eng., vol. 2022, no. 1, pp. 1–15, Apr. 2022, doi: https://doi.org/10.1155/2022/5510749

C.-M. Chen, S. Lv, J. Ning, and J. M.-T. Wu, “A Genetic Algorithm for the Waitable Time-Varying Multi-Depot Green Vehicle Routing Problem,” Symmetry (Basel)., vol. 15, no. 1, p. 124, 2023, doi: https://doi.org/10.3390/sym15010124

F. Morsidi, “An Intensification-Enhanced Adaptive Hybrid Memetic Algorithm for the Multi-Depot Vehicle Routing Problem with Time Windows,” Appl. Model. Simul., vol. 10, no. 1, pp. 50–63, 2026, url: https://arqiipubl.com/ojs/index.php/AMS_Journal/article/view/1127

A. Shuib and P. M. Ibrahim, “a Mixed Integer Goal Programming (Migp) Model for Donated Blood Transportation Problem – a Preliminary Study,” Malaysian J. Comput., vol. 6, no. 2, p. 835, 2021, doi: https://doi.org/10.24191/mjoc.v6i2.10751

N. S. Ibrahim, A. Shuib, and Z. A. Zaharudin, “Modified Hungarian Method for Lecturer-To- Course Assignment : a Multi-Objective Mathematical Programming Model for Optimizing Preferences and Competency ( Pc Mo- Mhm ),” Malaysian J. Comput., vol. 10, no. 2, pp. 2308–2321, 2025, doi: https://doi.org/10.24191/mjoc.v10i2.5562

K. Moonsri, K. Sethanan, and K. Worasan, “A Novel Enhanced Differential Evolution Algorithm for Outbound Logistics of the Poultry Industry in Thailand,” J. Open Innov. Technol. Mark. Complex., vol. 8, no. 1, p. 15, 2022, doi: https://doi.org/10.3390/joitmc8010015

J. Sun, X. Liu, T. Back, and Z. Xu, “Learning Adaptive Differential Evolution Algorithm from Optimization Experiences by Policy Gradient,” IEEE Trans. Evol. Comput., vol. 25, no. 4, pp. 666–680, 2021, doi: https://doi.org/10.1109/TEVC.2021.3060811

S. Sankul, N. Supattananon, R. Akararungruangkul, and N. Wichapa, “An adaptive differential evolution algorithm to solve the multi-compartment vehicle routing problem: A case of cold chain transportation problem,” Int. J. Prod. Manag. Eng., vol. 12, no. 1, pp. 91–104, 2024, doi: https://doi.org/10.4995/ijpme.2024.19928

H. Budiman, S. Li Wang, F. Morsidi, T. Foo Ng, and S. Chin Neoh, “Self-Adaptive Ensemble-based Differential Evolution with Enhanced Population Sizing,” in 2020 2nd International Conference on Cybernetics and Intelligent System (ICORIS), IEEE, Oct. 2020, pp. 1–6. doi: https://doi.org/10.1109/ICORIS50180.2020.9320767

F. Morsidi, “Distribution Path Segmentation Using Route Relocation and Savings Heuristics for Multi-Depot Vehicle Routing,” Malaysian J. Sci. Adv. Technol., vol. 3, no. 2, pp. 72–80, May 2023, doi: https://doi.org/10.56532/mjsat.v3i2.154

J. F. Castaneda Londono, R. A. G. Rendon, and E. M. T. Ocampo, “Iterated local search multi-objective methodology for the green vehicle routing problem considering workload equity with a private fleet and a common carrier,” Int. J. Ind. Eng. Comput., vol. 12, no. 1, pp. 115–130, 2020, doi: https://doi.org/10.5267/j.ijiec.2020.8.001

W. Chowmali and S. Sukto, “A novel two-phase approach for solving the multi-compartment vehicle routing problem with a heterogeneous fleet of vehicles: A case study on fuel delivery,” Decis. Sci. Lett., vol. 9, no. 1, pp. 77–90, 2020, doi: https://doi.org/10.5267/j.dsl.2019.7.003

W. Chowmali and S. Sukto, “A hybrid fja-alns algorithm for solving the multi-compartment vehicle routing problem with a heterogeneous fleet of vehicles for the fuel delivery problem,” Decis. Sci. Lett., vol. 10, no. 4, pp. 497–510, 2021, doi: https://doi.org/10.5267/j.dsl.2021.6.001

T. Vidal, T. G. Crainic, M. Gendreau, and C. Prins, “A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows,” Comput. Oper. Res., vol. 40, no. 1, pp. 475–489, Jan. 2013, doi: https://doi.org/10.1016/j.cor.2012.07.018

F. Morsidi, “Multi-depot dispatch deployment analysis on classifying preparedness phase for flood-prone coastal demography in Sarawak,” J. ICT Educ., vol. 9, no. 2, pp. 175–190, Dec. 2022, doi: https://doi.org/10.37134/jictie.vol9.2.13.2022

M. Alweshah et al., “Vehicle routing problems based on Harris Hawks optimization,” J. Big Data, vol. 9, no. 1, 2022, doi: https://doi.org/10.1186/s40537-022-00593-4

Y. Shi, L. Lv, F. Hu, and Q. Han, “A heuristic solution method for multi-depot vehicle routing-based waste collection problems,” Appl. Sci., vol. 10, no. 7, 2020, doi: https://doi.org/10.3390/app10072403

J. Sidorova and S. C. Kaja, “A New Approach for Solving the Disruption in Vehicle Routing Problem during Delivery,” Международный Научный Журнал “Современные Информационные Технологии И Ит-Образование,” vol. 16, no. 2, pp. 371–378, 2020, doi: https://doi.org/10.25559/sitito.16.202002.371-378

Y. Christopher, S. Wahyuningsih, and D. Satyananda, “Study of variable neighborhood descent and tabu search algorithm in VRPSDP,” J. Phys. Conf. Ser., vol. 1872, no. 1, 2021, doi: https://doi.org/10.1088/1742-6596/1872/1/012002

Y. Shen, M. Liu, J. Yang, Y. Shi, and M. Middendorf, “A hybrid swarm intelligence algorithm for vehicle routing problem with time windows,” IEEE Access, vol. 8, pp. 93882–93893, 2020, doi: https://doi.org/10.1109/ACCESS.2020.2984660

S. Wahyuningsih, D. Satyananda, and L. T. Oktoviana, “Implementation of the ACS-RVND algorithm on the VRP variant and its application to distribution optimization,” J. Phys. Conf. Ser., vol. 2157, no. 1, 2022, doi: https://doi.org/10.1088/1742-6596/2157/1/012025

S. Zhu, H. Fu, and Y. Li, “Optimization research on vehicle routing for fresh agricultural products based on the investment of freshness-keeping cost in the distribution process,” Sustain., vol. 13, no. 14, 2021, doi: https://doi.org/10.3390/su13148110

N. D. Lagaros, M. Kournoutos, N. A. Kallioras, and A. N. Nordas, “Constraint handling techniques for metaheuristics: a state-of-the-art review and new variants,” Optim. Eng., vol. 24, no. 4, pp. 2251–2298, 2023, doi: https://doi.org/10.1007/s11081-022-09782-9

H. Bae and I. Moon, “Multi-depot vehicle routing problem with time windows considering delivery and installation vehicles,” Appl. Math. Model., vol. 40, no. 13–14, pp. 6536–6549, 2016, doi: https://doi.org/10.1016/j.apm.2016.01.059

G. S. Kashyap, A. E. I. Brownlee, O. C. Phukan, K. Malik, and S. Wazir, “Roulette-Wheel Selection-Based PSO Algorithm for Solving the Vehicle Routing Problem with Time Windows,” 2023, doi: https://doi.org/10.48550/arXiv.2306.02308

V. V. de Melo, A. M. Nascimento, and G. Iacca, “A co-evolutionary algorithm with adaptive penalty function for constrained optimization,” Soft Comput., 2024, doi: https://doi.org/10.1007/s00500-024-09896-5

S. Suwannarongsri, “Optimal Solving Multi-Depot Vehicle Routing Problem By Modern Metaheuristic Algorithm,” Int. J. Innov. Comput. Inf. Control, vol. 19, no. 6, pp. 1753–1767, 2023, doi: https://doi.org/10.24507/ijicic.19.06.1753

F. Morsidi, “Scalable Metaheuristic Optimization of Asymmetric and Clustered TSP Variants using Iterated Local Search,” J. Telecommun. Electron. Comput. Eng., vol. 18, no. 1, pp. 35–44, 2026, doi: https://doi.org/10.54554/jtec.2026.18.01.005

N. A. Wouda, L. Lan, and W. Kool, “PyVRP: a high-performance VRP solver package,” INFORMS J. Comput., vol. 36, no. 4, pp. 943–955, Mar. 2024, doi: https://doi.org/10.1287/ijoc.2023.0055