提出混合元启发式算法优化安保调度路径，提升效率与可行性。
Hybrid Metaheuristic Vehicle Routing Problem for Security Dispatch Operations
- 融合多阶段ALNS、TS与TA，增强全局搜索与跳出局部最优能力。
- 在251个请求实例上，混合算法表现最佳，且计算时间增加时仍可持续优化。
- 适合需要高精度时间窗口的安保巡逻、应急调度等场景使用。
本文研究安保调度车辆路径问题（VRPSD）的优化，该问题涉及精确时间要求与严格时间窗等挑战性约束。提出三种基于不同元启发式算法的方案：第一种结合单阶段ALNS与TA，第二种采用多阶段ALNS与TA，第三种集成多阶段ALNS、TS与TA。实验基于包含251个客户请求的实例进行。结果表明，第三种混合多阶段ALNS-TS-TA算法性能最优。该方法同时利用ALNS的大范围搜索能力进行探索，并在多阶段ALNS与TS、TA结合时有效避免陷入局部最优。此外，实验中该算法是唯一在所有尝试中随计算时间增加而持续改善结果的方案。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。