Hybrid Metaheuristic Vehicle Routing Problem for Security Dispatch Operations
This addresses optimization for security and patrolling operations, but it is incremental as it combines existing metaheuristics for a specific domain problem.
This paper tackled the Vehicle Routing Problem for Security Dispatch (VRPSD) with constraints like precise timing, proposing three hybrid metaheuristic algorithms, and found that a hybrid multiphase ALNS-TS-TA algorithm performed best on a 251-customer instance, showing potential for improvement with more computation time.
This paper investigates the optimization of the Vehicle Routing Problem for Security Dispatch (VRPSD). VRPSD focuses on security and patrolling applications which involve challenging constraints including precise timing and strict time windows. We propose three algorithms based on different metaheuristics, which are Adaptive Large Neighborhood Search (ALNS), Tabu Search (TS), and Threshold Accepting (TA). The first algorithm combines single-phase ALNS with TA, the second employs a multiphase ALNS with TA, and the third integrates multiphase ALNS, TS, and TA. Experiments are conducted on an instance comprising 251 customer requests. The results demonstrate that the third algorithm, the hybrid multiphase ALNS-TS-TA algorithm, delivers the best performance. This approach simultaneously leverages the large-area search capabilities of ALNS for exploration and effectively escapes local optima when the multiphase ALNS is coupled with TS and TA. Furthermore, in our experiments, the hybrid multiphase ALNS-TS-TA algorithm is the only one that shows potential for improving results with increased computation time across all attempts.