·958· 工程科学学报，第39卷，第6期 执行步骤2，否则执行步骤5 2-opt指路径内进行二项交换，即选择某路径的 步骤2：生成一个[0,1]之间的随机数r,如果r< 两个交换节点，将交换节点内路径的节点顺序进行反 R,执行步骤3，否则执行步骤5. 转生成新路径，计算新路径成本，如果成本减少则保留 步骤3：随机选择一个使用中转站，如果剩余开放 当前操作。 中转站能够有能力服务该选择中转站所服务的需求 2-opt*指所属同一中转站的路径进行路径间二 点，则执行步骤4，否则执行步骤5. 项交换，即选择所属某一中转站的两条路径：路径1和 步骤4：将选择的中转站服务的需求点移除，并添 路径2和这两条路径的交换节点，将路径1前段与路 加到nsert数组中. 径2后段相连，路径2前段与路径1后段相连，形成两 步骤5：如果关闭了中转站，则g=0,否则g=g+1. 条新的路径，如果新路径满足配送车辆容量约束，并且 特别的，在步骤3中，当问题规模较大时，例如 新路径成本有所减少，则保留当前操作. Nguyen标准算例集中的100-10-MN算例，可能会出 插入指对于每个需求点，将其插入到距离最近的 现剩余开放中转站服务总能力能够满足所有需求点总 需求点前或后，如果插入后成本减小，则保留当前 需求量，但单独任意一个开放中转站剩余服务能力不 操作. 能满足某一个具有较大需求量的需求点，导致在重组 交换包含两种操作，分别是单点交换和多点交换. 过程中无法生成可行解.因此，在判断是否能够关闭 单点交换指交换两个需求点位置，如果交换后仍满足 某中转站时，应判断剩余开放中转站能力是否能够满 中转站和车辆容量约束，并且交换后成本降低，则保留 足所有需求点总需求量加最小需求点需求量总和，以 当前交换.多点交换指随机选择两组2~3个相邻需 避免出现上述情况. 求点，交换两组需求点位置，如果交换后仍满足中转站 (6)开放中转站. 和车辆容量约束，并且交换后成本降低，则保留当前 步骤1：如果g>g,执行步骤2，否则执行步骤4. 交换. 步骤2：生成一个[0,1]之间的随机数r,如果r< 2.5一级配送网络求解过程 ,执行步骤3，否则执行步骤4. R s 当完成二级配送网络大规模邻域搜索过程后，根 据二级配送网络邻域解，生成一级配送网络初始解，然 步骤3：将所有已关闭的中转站重新开放 后采用上述大规模邻域搜索来对一级配送网络进行优 步骤4：如果开放中转站，则g=0,否则g=g+1. 化，生成邻域解.在生成一级配送网络初始解过程中， 2.4.2重组过程 首先计算各个中转站所服务的需求点需求总量，作为 所有被移除的需求点在重组过程中被重新插入到 该中转站的需求量，然后将所有被选择的中转站随机 二级配送网络解方案中，待插入需求点按照随机顺序， 均匀的分配给可供选择的配送中心.通过大规模邻域 并贪婪随机插入到可供插入的位置.具体重组步骤 搜索过程来找到一级配送网络最优解或近似最优解. 如下 3实验结果与分析 步骤l:将Insert数组中待插入的需求点随机打乱 插入顺序. 3.1实验算例 步骤2：如果不存在待插入点，则结束，否则计算 本文采用2E-LRP标准算例来对大规模邻域搜索 每条路径是否能够满足当前待插入需求点需求量.如 模拟退火算法进行求解验证.算法在Intel(R)Core 果存在可供插入的路径，则执行步骤3，否则执行步骤4. (TM)5-4200HCPU、8 GB RAM、Vindows10操作系统 步骤3：计算所有可供插入路径的所有位置插入 环境下，使用MATLAB编译，对Nguyen标准算例集进 后增加成本，随机选择成本增加最小或第二小的位置， 行求解，并分别与目前已知国际最优解和标准模拟退 返回步骤2. 火算法进行对比. 步骤4：计算待插入点到所有可供使用中转站距 Nguyen算例集算例名称可表示为：n-m- 离，随机选择距离最小或第二小的中转站新增一条路 N(MN)[b],其中n表示需求点数量，m表示中转站数 径，返回步骤2. 量，N表示需求点位置为单变量正态分布，MN表示需 2.4.3局部搜索过程 求点位置为多变量正态分布，需求点需求量为均值 局部搜索过程包含四个局部搜索90)，分别是：μ=15，方差82=25的正态分布，一级配送车辆容量约 2-opt[2m2-opt*、插入、交换.当二级配送网络解经 束为{750,850}，名称中b表示容量约束为850，二级 过破坏、重组过程后，顺序执行四个局部搜索过程，如 配送车辆容量约束为{100,150}. 果出现更优解，则重复当前局部搜索方法，直到没有更 3.2算法参数 优解产生. 模拟退火框架部分所含参数]包括：初始温度：工程科学学报,第 39 卷,第 6 期 执行步骤 2,否则执行步骤 5. 步骤 2:生成一个[0,1]之间的随机数 r,如果 r < Rp5 ,执行步骤 3,否则执行步骤 5. 步骤 3:随机选择一个使用中转站,如果剩余开放 中转站能够有能力服务该选择中转站所服务的需求 点,则执行步骤 4,否则执行步骤 5. 步骤 4:将选择的中转站服务的需求点移除,并添 加到 Insert 数组中. 步骤 5:如果关闭了中转站,则 g =0,否则 g = g +1. 特别的,在步骤 3 中,当问题规模较大时,例如 Nguyen 标准算例集中的 100鄄鄄 10鄄鄄 MN 算例,可能会出 现剩余开放中转站服务总能力能够满足所有需求点总 需求量,但单独任意一个开放中转站剩余服务能力不 能满足某一个具有较大需求量的需求点,导致在重组 过程中无法生成可行解. 因此,在判断是否能够关闭 某中转站时,应判断剩余开放中转站能力是否能够满 足所有需求点总需求量加最小需求点需求量总和,以 避免出现上述情况. (6) 开放中转站. 步骤 1:如果 g > gmax,执行步骤2,否则执行步骤4. 步骤 2:生成一个[0,1]之间的随机数 r,如果 r < Rp5 | NS | ,执行步骤 3,否则执行步骤 4. 步骤 3:将所有已关闭的中转站重新开放. 步骤 4:如果开放中转站,则 g = 0,否则 g = g + 1. 2郾 4郾 2 重组过程 所有被移除的需求点在重组过程中被重新插入到 二级配送网络解方案中,待插入需求点按照随机顺序, 并贪婪随机插入到可供插入的位置. 具体重组步骤 如下. 步骤 1:将 Insert 数组中待插入的需求点随机打乱 插入顺序. 步骤 2:如果不存在待插入点,则结束,否则计算 每条路径是否能够满足当前待插入需求点需求量. 如 果存在可供插入的路径,则执行步骤3,否则执行步骤4. 步骤 3:计算所有可供插入路径的所有位置插入 后增加成本,随机选择成本增加最小或第二小的位置, 返回步骤 2. 步骤 4:计算待插入点到所有可供使用中转站距 离,随机选择距离最小或第二小的中转站新增一条路 径,返回步骤 2. 2郾 4郾 3 局部搜索过程 局部搜索过程包含四个局部搜索[19鄄鄄20] ,分别是: 2鄄鄄 opt [21] 、2鄄鄄 opt*、插入、交换. 当二级配送网络解经 过破坏、重组过程后,顺序执行四个局部搜索过程,如 果出现更优解,则重复当前局部搜索方法,直到没有更 优解产生. 2鄄鄄 opt 指路径内进行二项交换,即选择某路径的 两个交换节点,将交换节点内路径的节点顺序进行反 转生成新路径,计算新路径成本,如果成本减少则保留 当前操作. 2鄄鄄 opt*指所属同一中转站的路径进行路径间二 项交换,即选择所属某一中转站的两条路径:路径 1 和 路径 2 和这两条路径的交换节点,将路径 1 前段与路 径 2 后段相连,路径 2 前段与路径 1 后段相连,形成两 条新的路径,如果新路径满足配送车辆容量约束,并且 新路径成本有所减少,则保留当前操作. 插入指对于每个需求点,将其插入到距离最近的 需求点前或后,如果插入后成本减小,则保留当前 操作. 交换包含两种操作,分别是单点交换和多点交换. 单点交换指交换两个需求点位置,如果交换后仍满足 中转站和车辆容量约束,并且交换后成本降低,则保留 当前交换. 多点交换指随机选择两组 2 ~ 3 个相邻需 求点,交换两组需求点位置,如果交换后仍满足中转站 和车辆容量约束,并且交换后成本降低,则保留当前 交换. 2郾 5 一级配送网络求解过程 当完成二级配送网络大规模邻域搜索过程后,根 据二级配送网络邻域解,生成一级配送网络初始解,然 后采用上述大规模邻域搜索来对一级配送网络进行优 化,生成邻域解. 在生成一级配送网络初始解过程中, 首先计算各个中转站所服务的需求点需求总量,作为 该中转站的需求量,然后将所有被选择的中转站随机 均匀的分配给可供选择的配送中心. 通过大规模邻域 搜索过程来找到一级配送网络最优解或近似最优解. 3 实验结果与分析 3郾 1 实验算例 本文采用 2E鄄鄄LRP 标准算例来对大规模邻域搜索 模拟退火算法进行求解验证. 算法在 Intel(R) Core (TM) i5鄄鄄4200H CPU、8GB RAM、Windows10 操作系统 环境下,使用 MATLAB 编译,对 Nguyen 标准算例集进 行求解,并分别与目前已知国际最优解和标准模拟退 火算法进行对比. Nguyen 算 例 集 算 例 名 称 可 表 示 为: n - m - N(MN)[b],其中 n 表示需求点数量,m 表示中转站数 量,N 表示需求点位置为单变量正态分布,MN 表示需 求点位置为多变量正态分布,需求点需求量为均值 滋 = 15,方差 啄 2 = 25 的正态分布,一级配送车辆容量约 束为{750,850},名称中 b 表示容量约束为 850,二级 配送车辆容量约束为{100,150}. 3郾 2 算法参数 模拟退火框架部分所含参数[17] 包括:初始温度: ·958·