Solving large-scale highly constrained vehicle routing problems for security dispatch operations

This article introduces and investigates the optimization of the Vehicle Routing Problem for Security Dispatch (VRPSD). VRPSD focuses on security and patrolling applications, which involve precise timing and strict time-window constraints. When the number of sites to visit is large, the problem becomes extremely difficult. In this work, three algorithms are proposed to tackle this problem. The first algorithm combines single-phase adaptive large neighbourhood search (ALNS) with threshold accepting (TA). The second employs a multiphase ALNS with TA, and the third integrates multiphase ALNS, TA and tabu search (TS). Experiments are conducted on a real-world instance comprising 251 customer requests, followed by a structured hyperparameter sensitivity analysis and expanded scope of experiments through synthetic instance generation with varying sizes and constraints for robustness and scalability study. The results demonstrate that the hybrid multiphase ALNS-TS-TA algorithm solves large-scale VRPSD problems effectively with promising scalability and shows potential for continuous improvement with increased computation time.