·956· 工程科学学报，第39卷，第6期 部粒子趋于稳定，并且在每个温度下都能够达到平衡 步骤8：T=αT.如果当前温度最优解值与上一温 态.当物体温度下降到某一基态温度时，内能减为最 度最优解值相同，则F=F+1. 小.模拟退火算法利用组合优化与物理退火过程中的 步骤9：如果T<T,或F=Np,终止算法，输出 相似性，基于蒙特卡罗(Monte--Carlo)法进行迭代，在 最优解B,最优总成本Ba,否则返回步骤3. 解空间内结合概率突跳特性寻找全局最优解 (开始 大规模邻域搜索模拟退火算法采用自下向上的求 解过程，在每一次迭代过程中首先对二级配送网络中 初始化参数 中转站的选择和配送路径进行求解，然后根据二级配 随机生成初始解，计算 送网络求解结果，求解一级配送网铬中配送中心的选 初始解成本 择和配送路径.针对二级选址-路径问题，本文利用模 拟退火算法框架，在算法迭代中的关键步骤之一构建 TeT,且F<Npw 邻域过程中，设计利用大规模邻域搜索方法来替代原 是 始邻域构建方法，该方法已经被用于多种不同的车辆 K<M 否 路径优化问题)]，通过对当前解进行破坏重组过程和 上是 局部搜索过程来形成新解. 对二级配送网络进行大 输出当前最优解 2.1算法步骤 规模邻域搜索生成邻域解 算法采用模拟退火算法框架来求解2E-LRP.首 结束 计算中转站需求量，随机生成 先生成算法参数，并初始化第二级配送网络初始解，算 邻域解的一级配送网络解 法求解过程中生成新解部分包含两个阶段.第一阶段 对一级配送网络进行大规模 利用大规模邻域搜索构造第二级配送网络邻域解方 邻域搜索生成邻域解 案，第二阶段根据上一阶段生成的第二级配送网络邻 域解方案，采用相同的大规模邻域搜索构造第一级配 计算邻域解，总成本，按照Metropolis 准则更新当前解，/=+1 送网络解方案.算法通过计算二级配送网络邻域解方 案成本，采用Metropolis准则接受邻域解，直到满足算 更新最优解 法终止条件，返回最终二级配送网络解方案 算法具体步骤如下，算法流程图如图2所示 T=aT 步骤1：初始化算法初始温度T=T。,算法终止温 度T,降温系数α，内循环次数M,不更新代数F=0, 否 当前温度 最优解与上一温度 I=0,最大不更新代数Vp,随机生成初始解. 最优解相同 步骤2：利用大规模邻域搜索构造初始解第一级 是 配送网络解方案，并计算当前初始解X总成本Xa· F=F+1 令最优解B=X,最优解成本B。a=Xm 图2大规模邻域搜索模拟退火算法流程图 步骤3：如果1<M。,执行步骤4，否则令I=0,执 Fig.2 General flowchart of SA-LNS 行步骤8. 步骤4：二级配送网络大规模邻域搜索.对X的二 2.2编码 级配送网络解依次进行破坏、重组、局部搜索操作，生 由于2E-LRP包含多个子问题，并且本文提出的 成邻域解X'的二级配送网络解.根据X'二级配送网 大规模邻域搜索模拟退火算法采用自下向上的求解过 络解所选择的中转站，计算每个中转站所服务的需求 程，因此在解编码方式选择上，本文将一级配送网络与 点配送总量作为中转站需求量，随机生成X'的一级配 二级配送网络分别用相同的方式进行编码来表示解 送网络解 方案 步骤5：一级配送网络大规模邻域搜索.对X'的 本文采用的是实数编码方式，以二级配送网络为 一级配送网络解依次进行破坏、重组、局部搜索操作， 例.二级物流配送网络解编码包含有编号为{1,2，…， 生成邻域解X'的一级配送网络解 c}的c个需求点、编号为{c+1,c+2,…,c+s}的s个 步骤6：计算邻域解X'的总成本X,按照Metrop- 备选中转站，以及若干个0表示路径分割.图3为10 olis准则接受邻域解，I=I+1. 个需求点、5个备选中转站的二级配送网络编码示意 步骤7：如果Xa<Boa,则令B=X',Bm=Xa, 图，其中11、12表示中转站1、2被选择使用，未出现的 F=0,返回步骤3. 13、14、15表示中转站3、4、5未被选择使用：0表示路工程科学学报,第 39 卷,第 6 期 部粒子趋于稳定,并且在每个温度下都能够达到平衡 态. 当物体温度下降到某一基态温度时,内能减为最 小. 模拟退火算法利用组合优化与物理退火过程中的 相似性,基于蒙特卡罗(Monte鄄鄄 Carlo)法进行迭代,在 解空间内结合概率突跳特性寻找全局最优解. 大规模邻域搜索模拟退火算法采用自下向上的求 解过程,在每一次迭代过程中首先对二级配送网络中 中转站的选择和配送路径进行求解,然后根据二级配 送网络求解结果,求解一级配送网络中配送中心的选 择和配送路径. 针对二级选址鄄鄄路径问题,本文利用模 拟退火算法框架,在算法迭代中的关键步骤之一构建 邻域过程中,设计利用大规模邻域搜索方法来替代原 始邻域构建方法,该方法已经被用于多种不同的车辆 路径优化问题[15] ,通过对当前解进行破坏重组过程和 局部搜索过程来形成新解. 2郾 1 算法步骤 算法采用模拟退火算法框架来求解 2E鄄鄄 LRP. 首 先生成算法参数,并初始化第二级配送网络初始解,算 法求解过程中生成新解部分包含两个阶段. 第一阶段 利用大规模邻域搜索构造第二级配送网络邻域解方 案,第二阶段根据上一阶段生成的第二级配送网络邻 域解方案,采用相同的大规模邻域搜索构造第一级配 送网络解方案. 算法通过计算二级配送网络邻域解方 案成本,采用 Metropolis 准则接受邻域解,直到满足算 法终止条件,返回最终二级配送网络解方案. 算法具体步骤如下,算法流程图如图 2 所示. 步骤 1:初始化算法初始温度 T = T0 ,算法终止温 度 Tf,降温系数 琢,内循环次数 Mit,不更新代数 F = 0, I = 0,最大不更新代数 Nnotimp ,随机生成初始解. 步骤 2:利用大规模邻域搜索构造初始解第一级 配送网络解方案,并计算当前初始解 X 总成本 XCost . 令最优解 B = X,最优解成本 BCost = XCost . 步骤 3:如果 I < Mit,执行步骤 4,否则令 I = 0,执 行步骤 8. 步骤4:二级配送网络大规模邻域搜索. 对 X 的二 级配送网络解依次进行破坏、重组、局部搜索操作,生 成邻域解 X忆的二级配送网络解. 根据 X忆二级配送网 络解所选择的中转站,计算每个中转站所服务的需求 点配送总量作为中转站需求量,随机生成 X忆的一级配 送网络解. 步骤 5:一级配送网络大规模邻域搜索. 对 X忆的 一级配送网络解依次进行破坏、重组、局部搜索操作, 生成邻域解 X忆的一级配送网络解. 步骤 6:计算邻域解 X忆的总成本 X忆Cost,按照 Metrop鄄 olis 准则接受邻域解,I = I + 1. 步骤 7:如果 X忆Cost < BCost,则令 B = X忆,BCost = X忆Cost, F = 0,返回步骤 3. 步骤 8:T = 琢T. 如果当前温度最优解值与上一温 度最优解值相同,则 F = F + 1. 步骤 9:如果 T < Tf 或 F = Nnotimp ,终止算法,输出 最优解 B,最优总成本 BCost,否则返回步骤 3. 图 2 大规模邻域搜索模拟退火算法流程图 Fig. 2 General flowchart of SA鄄鄄LNS 2郾 2 编码 由于 2E鄄鄄LRP 包含多个子问题,并且本文提出的 大规模邻域搜索模拟退火算法采用自下向上的求解过 程,因此在解编码方式选择上,本文将一级配送网络与 二级配送网络分别用相同的方式进行编码来表示解 方案. 本文采用的是实数编码方式,以二级配送网络为 例. 二级物流配送网络解编码包含有编号为{1,2,…, c}的 c 个需求点、编号为{ c + 1,c + 2,…,c + s}的 s 个 备选中转站,以及若干个 0 表示路径分割. 图 3 为 10 个需求点、5 个备选中转站的二级配送网络编码示意 图,其中 11、12 表示中转站 1、2 被选择使用,未出现的 13、14、15 表示中转站 3、4、5 未被选择使用;0 表示路 ·956·