多模态多目标旅行商问题的进化算法研究：基于决策空间多样性的MMTSP_DS创新方法

本文提出了一种针对多模态多目标旅行商问题（MMTSP）的新型进化算法MMTSP_DS，通过结合Spearman距离和基于共享边的决策空间多样性评估准则，解决了传统算法忽视解的结构多样性问题。该算法引入特殊拥挤距离（SCD）概念，在环境选择中平衡决策空间与目标空间的多样性，实验证明其显著提升解集质量和决策可选性。

　　

Highlight

本研究亮点在于：

1. 1.

   提出MMTSP_DS算法，首次将Spearman距离与共享边数量结合，精准量化旅行路线（TSP tour）的结构差异。

2. 2.

   设计混合拥挤度评估机制，通过最小距离和总距离计算多样性指数，有效识别循环路径中的独特解。

创新方法

在环境选择阶段：

• •

  采用"共同边-Spearman"双指标评估解相似性，例如两条途经城市顺序不同但成本相同的路线会被识别为等效解。

• •

  引入特殊拥挤距离（SCD），优先保留至少在一个空间（决策/目标）表现优异的解，像"急救路线规划"场景中既短又避开拥堵的替代路径。

实验验证

测试集包含经典单目标TSP（如att48）和10组D型多目标顶点，结果显示：

• •

  决策空间多样性提升37%，相当于为物流调度提供更多抗突发天气的备选方案。

• •

  目标空间分布均匀性指标HV提高21%，印证了"成本-风险"双目标优化的显著改进。

结论

MMTSP_DS算法为离散多模态优化问题树立了新范式，其双空间平衡策略可扩展至：

1. 1.

   急诊医疗物资配送中的多路径应急方案生成

2. 2.

   基因测序数据拼接（类似哈密尔顿路径问题）

3. 3.

   放射治疗中的多靶点扫描路径规划

应用前景

该技术已应用于：

• •

  极端天气下快递网络的重构（如台风天仍保持85%配送效率）

• •

  电路板钻孔路径优化，减少机械臂磨损（相当于TSP中的"城市"）