利用模拟退火算法解决NEARP问题的实用方案

### 利用模拟退火算法解决NEARP问题的实用方案 在物流配送、资源调度等领域，网络边弧需求问题（NEARP）是一个常见且重要的问题。传统解决方法虽然有一定效果，但过程复杂，尤其是局部搜索程序，在处理大规模实例时会消耗大量时间。本文提出了一种基于模拟退火算法的简单有效解决方案。 #### 1. 现有方法与全局 - 局部搜索流程 在解决NEARP问题的现有方法中，存在全局和局部两个搜索阶段。全局阶段，会将一组行程转换为字符串，当作染色体处理。具体步骤如下： 1. **染色体选择**：随机选取两条染色体，从中选出成本最低的作为父染色体，再以同样方式选另一条父染色体。 2. **交叉操作**：对这对父染色体应用扩展顺序交叉，生成一对子染色体。 3. **行程划分**：随机选取一个子染色体，通过最优分割程序将字符串划分为对应各车辆的行程，然后进入局部阶段。 局部阶段，会对行程内部或两个行程之间应用局部搜索程序，包含以下子程序： - **翻转任务**：将任务a替换为其反向任务inv(a)。 - **移动单个任务**：把任务a移到另一个任务或仓库之后。 - **移动连续任务**：将连续的两个任务a和b移到另一个任务或仓库之后。 - **交换任务**：交换两个任务a和b。 - **2 - opt移动**：对行程进行优化调整。 每个子程序会在检测到首次改进移动或检查完所有移动后结束，不断重复该过程，直到无法再节省成本。局部优化完成后，将所有行程连接成无分隔符的字符串，替换种群中的一条染色体，进入下一代全局阶段。 #### 2. 提出的新方法 由于现有方法复杂，尤其是局部搜索耗时严重，本文提出了一种更简单的数据模型和单阶段算法来解决NEARP问题。 ##### 2.1 数据建模 新方法基于内部网络编码，所有实体（节点、边、弧）以三维数组形式存储。数组第一个元素表示实体的头节点，第二个表示尾节点，第三个是布尔值，若实体为弧则值为1，若头尾节点相同则表示单个节点。 NEARP问题的解决方案用整数序列（字符串）表示。字符串中数字的位置不仅表明哪个车辆执行任务，还表示任务的路由顺序。具体规则如下： - 所需弧或节点用正数表示。 - 所需边根据遍历方向用正数或负数表示。 - 特殊数字‘0’既代表仓库，也是划分行程的分隔符。若有m辆车，字符串中会有(m - 1)个‘0’，若‘0’之间无数字，则对应车辆未使用。 评估解决方案成本时，会参考字符串中任务对应的内部编码。 ##### 2.2 转换规则 通过以下三种转换规则从当前状态生成新的解决方案状态： 1. **一对一交换**：交换字符串中的两个数字。若在子字符串内执行，仅改变一辆车的路线；若在不同子字符串的组件间执行，会在两辆车之间交换任务；若在非零数字和‘0’之间执行，会将一辆车的部分路线移动并嵌入另一辆车的路线。 2. **删除并插入**：删除任意数字并插入到字符串的其他位置。若删除非零数字并跨‘0’插入，会将任务移到另一辆车的路线；若删除‘0’并插入到其他位置，会大幅改变路线。 3. **方向反转**：反转无向边的遍历方向，但此规则不适用于有向弧。 这些规则同样适用于特殊数字‘0’。 ##### 2.3 目标函数 NEARP问题的目标是在满足各车辆负载容量等约束条件下，最小化总成本。目标函数公式为： \[E = \sum_{i=1}^{n} c_{s_i} + \sum_{i=1}^{n - 1} p_{s_i, s_{i + 1}}\] 其中，\(s = (s_1, s_2, \cdots, s_n)\)是包含任务和仓库的字符串，\(c_k\)是处理任务\(k\)的成本（\(k = 0\)时，\(c_k = 0\)），\(p_{k, l}\)是从任务\(k\)的尾节点到任务\(l\)的头节点的最小遍历成本。 所有\(p_{k, l}\)的值会基于内部网络编码，使用Warshall - Floyd算法预先计算优化。若\(k\)和\(l\)都是边任务，需根据它们的遍历方向计算四个不同的\(p_{k, l}\)值。 ##### 2.4 优化算法 采用模拟退火算法（SA）进行优化，因其具有简单随机过程和全局搜索范围的特点。整个算法步骤如下： 1. **准备阶段**：读取网络数据，计算两个任务之间的最小路径成本\(p_{k, l}\)。 2. **初始化阶段**： - 生成随机初始可行解\(x_0\)。 - 令\(x := x_0\)，\(x^* := x\)。 - 通过探索性SA执行计算初始温度INITTEMP，令\(T := INITTEMP\)。 3. **模拟退火优化阶段**：在SA框架下，对字符串模型\(x\)应用三种转换规则，最小化目标函数\(E\)。具体步骤如下： - 初始化尝试次数\(trials = 0\)和更改次数\(changes = 0\)。 - 重复以下操作： - \(trials := trials + 1\)。 - 随机应用一种转换规则生成新状态\(x'\)。 - 若\(x'\)可行，计算\(\Delta E = E(x') - E(x)\)。 - 若\(\Delta E < 0\)，接受\(x'\)为新状态，若\(E(x') < E(x^*)\)，则\(x^* := x'\)。 - 否则，以概率\(\exp(-\Delta E / T)\)接受\(x'\)。 - 若接受\(x'\)，则\(changes := changes + 1\)，\(x := x'\)。 - 直到\(trials \geq SIZEFACTOR \cdot N\)或\(changes \geq CUTOFF \cdot N\)。 - \(T := T \cdot TEMPFACTOR\)。 - 直到\(T \leq INITTEMP / FIN_DIVISOR\)。 4. **输出阶段**：输出最佳解决方案\(x^*\)。 生成的新状态\(x'\)的可行性通过检查各车辆总负载是否不超过其负载容量来确定。 #### 3. 实验评估 为验证新方法的有效性，进行了一系列实验。 ##### 3.1 实验实例 使用Prins等人提供的23个NEARP实例，这些实例由他们的原始生成器随机生成，包含不同数量的节点、边和弧，且尚未找到这些实例的下界。由于VRP和CARP是NEARP的特殊情况，他们曾将解决方案应用于基准VRP和CARP问题，取得了良好效果。 ##### 3.2 随机初始可行解生成 初始可行解会影响计算结果质量，按以下步骤生成： 1. 按任务需求量降序排序。 2. 在不超过车辆负载容量的前提下，将排序后的任务分配给车辆。 3. 根据分配结果形