混合蛇优化算法求解带时间窗的车辆路径问题

Hybrid Snake Optimization Algorithm for Solving Vehicle Routing Problem with Time Windows

摘要:

针对带时间窗的车辆路径问题（VRPTW）约束条件复杂、求解难度高，以及蛇优化算法（SO）在求解过程存在局部搜索能力弱、求解质量低等问题，提出了一种混合蛇优化算法（HSO），采用最小位置匹配值法进行离散化解码，有效提升了求解效率。通过引入随机插入与基于密度带有噪声的空间聚类（DBSCAN）算法相结合的混合初始化策略，增强了初始种群多样性，拓展了解空间覆盖范围;融合蛇群探索食物、靠近食物、战斗与交配等行为，并结合局部邻域搜索机制，有效提升了算法局部搜索能力。利用Solomon数据集开展仿真试验，并采用Wilcoxon秩和检验及Friedman检验对结果进行统计分析。试验结果表明，HSO算法在求解VRPTW中表现出优异的求解精度与稳定性。最后，通过实际城市农产品配送问题的应用，验证了该算法在复杂组合优化问题中适应性与实际应用价值。

Abstract:

Aiming to address the complex constraints and high computational complexity of the vehicle routing problem with time windows (VRPTW), as well as the weak local search capability and limited solution quality of the snake optimization algorithm (SO), a hybrid snake optimization algorithm (HSO) was proposed. The minimum position matching value method was employed for discrete decoding, thereby improving computational efficiency. A hybrid initialization strategy combining random insertion and the density-based spatial clustering of applications with noise (DBSCAN) algorithm was introduced to enhance the diversity of the initial population and broaden the coverage of the search space. Furthermore, snake behaviors, including searching for food, approaching food, fighting, and mating, were integrated with a local neighborhood search mechanism to strengthen the local search capability. Simulation experiments were conducted on the Solomon dataset, and the results were statistically analyzed by using the Wilcoxon rank-sum test and Friedman test. The experimental results demonstrated that the proposed HSO algorithm exhibited superior solution accuracy and stability for solving the VRPTW. Finally, application of the proposed HSO algorithm to a real-world urban agricultural product distribution problem further demonstrated its adaptability and practical value for solving complex combinatorial optimization problems.