智能优化算法在物流问题中的应用与比较

### 智能优化算法在物流问题中的应用与比较 在物流领域，高效的规划和优化对于降低成本、提高服务质量至关重要。本文将介绍两种重要的优化算法——禁忌搜索（Tabu Search，TS）和二维带切分约束的快速启发式算法，并对它们在不同规模实例上的性能进行分析。 #### 禁忌搜索算法解决两级定位路由问题 两级定位路由问题（2E - LRP）在物流规划中十分关键，它涉及到多个层面的决策，如设施选址和路径规划。为了解决这个问题，提出了一种禁忌搜索启发式算法。 ##### 算法步骤 该算法将问题分解为四个子问题，分别是一个容量设施定位问题（CFLP）和每个层级的一个多配送中心车辆路径问题（MDVRP）。这些子问题会被依次迭代求解，并将它们的解进行适当组合，以得到一个较好的全局解。具体步骤如下： 1. **步骤 1 - 4**：根据特定规则确定最佳解，若未达到停止条件则重复步骤 4。 2. **步骤 5**：使用 C&W、2 - opt 和 3 - opt 算法定义并优化第二层级的多站路由，然后进入步骤 6。 3. **步骤 6**：对单个开放卫星依次执行插入和交换操作。若达到最大非改进移动次数，则用最佳确定解更新解并进入步骤 7；否则重复步骤 6。 4. **步骤 7**：对多个卫星依次执行插入和交换操作。若满足 Imp - CR2 或 Violated - cap 标准之一，则返回步骤 1；否则重复步骤 7。若达到最大非改进移动次数，则用最佳确定解更新解并进入步骤 8。 5. **步骤 8**：对第二层级依次执行交换和添加位置操作，然后返回步骤 1。若达到最大非改进移动次数，则用最佳确定解更新解并停止；否则返回步骤 1。 下面是该算法步骤的 mermaid 流程图： ```mermaid graph LR classDef startend fill:#F5EBFF,stroke:#BE8FED,stroke-width:2px; classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px; classDef decision fill:#FFF6CC,stroke:#FFBC52,stroke-width:2px; A([开始]):::startend --> B(步骤 1 - 4):::process B --> C{是否达到停止条件?}:::decision C -- 否 --> B C -- 是 --> D(步骤 5):::process D --> E(步骤 6):::process E --> F{达到最大非改进移动次数?}:::decision F -- 否 --> E F -- 是 --> G(步骤 7):::process G --> H{满足 Imp - CR2 或 Violated - cap?}:::decision H -- 是 --> B H -- 否 --> I{达到最大非改进移动次数?}:::decision I -- 否 --> G I -- 是 --> J(步骤 8):::process J --> K{达到最大非改进移动次数?}:::decision K -- 否 --> B K -- 是 --> L([结束]):::startend ``` ##### 实验结果 为了评估禁忌搜索算法的性能，在三组不同规模（小、中、大）的实例上进行了实验，并将结果与精确模型得出的边界进行了比较。实验中主要关注两种参数设置，即 TS1 和 TS2，它们的区别在于探索邻域的大小。 - **小实例**：将 TS 结果与 Sterle 提出的公式在 2 小时计算时间内得到的结果进行比较。从表 2、3、4 可以看出，在已知最优解的情况下（标记为 ∗），TS 至少在一种设置下能够确定最优解。TS1 的差距在 +0.206 和 -0.208 之间，计算时间始终低于 45 秒；TS2 的差距在大多数情况下为正，在 +0.256 和 -0.051 之间，计算时间相对于 TS1 有所增加，但明显低于求解器的时间（少于 360 秒）。 | 实例集 | TS1 最差差距 | TS2 差距范围 | TS1 最大计算时间 | TS2 最大计算时间 | | ---- | ---- | ---- | ---- | ---- | | I1 | -0.208 | +0.256 到 -0.051 | 45 秒 | 360 秒 | | I2 | -0.158 | | | | | I3 | -0.189 | | | | - **中大型实例**：将 TS 解的值与分解方法（DA）的结果进行比较。TS1 的结果与分解方法非常接近，但在计算时间上有显著节省，差距在 +0.283 和 -0.094 之间，计算时间除了实例 I2 - 41025 外始终低于 600 秒；TS