李想等：两级选址~路径问题的大规模邻域搜索模拟退火算法 ·957· 径分割符，0前节点为上一路径结束需求点，0后节点 找到最优解或者近似最优解 为下一路径开始需求点.图3所示二级配送网络编码 由于一级配送网络与二级配送网络采用相同的大 可转换为3条路径. 规模邻域搜索，下文均以二级配送网络为例 路径1：11→1→2→3→11 2.4.1破坏过程 路径2：11→4→56→11 破坏过程包含两类破坏方法，分别是小规模破坏 路径3：12→7→89→10→12 和大规模破坏)].小规模破坏包含四种破坏方法：相 邻点移除、最大节约点移除、随机路径移除、单点路径 1112304561278910 移除.大规模破坏包含两种破坏方法：关闭中转站、开 图310个需求点，5个备选中转站编码示意图 放中转站[).在执行破坏过程时，依次对二级配送网 Fig.3 Example of a solution representation with ten customers and five 络解执行上述六种破坏方法，将删除的节点存储在 satellites Insert数组中，以供重组过程使用.其中关闭中转站和 2.3初始化 开放中转站操作只有在迭代到一定代数后才能够有机 算法分为两个阶段，在初始化过程中需要生成两 会进行，即如果中转站状态被改变后的一段时期内，不 级配送网络初始解，考虑到两级配送网络解结构的相 允许进行任何关闭或开放中转站操作 似性，本文采用相同的初始化方法生成初始解.由于 各个破坏方法具体步骤如下 本文提出的大规模邻域搜索方法在求解过程中的效率 (1)相邻点移除. 很高，因此在初始化过程中，采用较为简单的贪婪随机 步骤1：随机选择一个需求点作为移除根节点 初始化方法来保证初始解的多样性，并且降低了初始 步骤2：计算最大移除点数量Mu,M=「RINI门 化复杂度，在算法第二阶段求解时提高了算法效率. 步骤3：随机选择移除点数量，N为[0，Ma]之间 以二级配送网络为例，贪婪随机初始化具体步骤 的随机数. 如下. 步骤4：将根节点和距离根节点最近的N!-1个 步骤1：将需求点随机均匀的分配给所有备选中 需求点从原路径中移除，并添加到Insert数组中. 转站. (2)最大节约点移除 步骤2：根据步骤1需求点分配结果，对每个中转 步骤1：计算每个需求点j移除后的节约成本4， 站进行贪婪路径优化.以中转站节点作为路径初始节 A=cg+ca-ca 点，选择分配给该中转站距离最近的需求点作为路径 步骤2：计算最大移除点数量Me,Me=「R2lNc门. 下一节点. 步骤3：随机选择移除点数量N2,N2为[0，M] 步骤3：将分配给该中转站距离路径上一节点最 之间的随机数. 近的未安排需求点作为路径下一节点，重复执行直到 步骤4：按照轮盘赌的方法随机选择？个需求 分配给该中转站的需求点全部安排后，设置路径终止 点，其中△越大的需求点越有机会被选择移除，将选 节点为该中转站节点. 择的需求点从原路径中移除，并添加到Insert数组中. 步骤4：根据上述生成的路径，按照二级配送车辆 (3)随机路径移除 容量约束，将超出车辆容量约束的路径部分重新另起 步骤1：计算最大移除路径数量Me,Ms= 一条路径，起止节点为当前中转站节点 2.4大规模邻域搜索 是1 大规模邻域搜索[]主要包括三个过程：破坏过 步骤2：随机选择移除路径数量N,N为[0， 程、重组过程和局部搜索过程，在构造邻域解时，分别 Me]之间的随机数. 依次对当前解实施上述三个过程.破坏过程和重组过 步骤3：随机选择Ve条路径，移除选择的路径内 程能够在较大的解空间邻域结构内进行搜索，从而相 所有需求点，并添加到Insert数组中. 对于其余传统邻域构造方法具有更大的可能性找到最 (4)单点路径移除 优解.此外，由于在重组过程中采用较为简单的贪婪 步骤1：生成一个[0,1]之间的随机数r. 随机插人方法，降低了算法的复杂度，平衡了大规模邻 步骤2：如果r<R,则移除二级配送网络解方案 域搜索过程的效率和效果 中所有只包含一个需求点的路径，将所有移除的需求 在得到二级配送网络解方案后，按照贪婪随机算 点添加到Insert数组中 法生成一级配送网络初始解后，算法采用相同的大规 (5)关闭中转站. 模邻域搜索进行求解.因为一级配送网络相对于二级 步骤1：如果中转站进行开放或关闭操作后算法 来讲，节点数量较少，采用大规模邻域搜索能够有效的 迭代代数大于不允许更改中转站状态代数(g>g),李 想等: 两级选址鄄鄄路径问题的大规模邻域搜索模拟退火算法 径分割符,0 前节点为上一路径结束需求点,0 后节点 为下一路径开始需求点. 图 3 所示二级配送网络编码 可转换为3 条路径. 路径 1:11寅1寅2寅3寅11 路径 2:11寅4寅5寅6寅11 路径 3:12寅7寅8寅9寅10寅12 11 1 2 3 0 4 5 6 12 7 8 9 10 图 3 10 个需求点、5 个备选中转站编码示意图 Fig. 3 Example of a solution representation with ten customers and five satellites 2郾 3 初始化 算法分为两个阶段,在初始化过程中需要生成两 级配送网络初始解,考虑到两级配送网络解结构的相 似性,本文采用相同的初始化方法生成初始解. 由于 本文提出的大规模邻域搜索方法在求解过程中的效率 很高,因此在初始化过程中,采用较为简单的贪婪随机 初始化方法来保证初始解的多样性,并且降低了初始 化复杂度,在算法第二阶段求解时提高了算法效率. 以二级配送网络为例,贪婪随机初始化具体步骤 如下. 步骤 1:将需求点随机均匀的分配给所有备选中 转站. 步骤 2:根据步骤 1 需求点分配结果,对每个中转 站进行贪婪路径优化. 以中转站节点作为路径初始节 点,选择分配给该中转站距离最近的需求点作为路径 下一节点. 步骤 3:将分配给该中转站距离路径上一节点最 近的未安排需求点作为路径下一节点,重复执行直到 分配给该中转站的需求点全部安排后,设置路径终止 节点为该中转站节点. 步骤 4:根据上述生成的路径,按照二级配送车辆 容量约束,将超出车辆容量约束的路径部分重新另起 一条路径,起止节点为当前中转站节点. 2郾 4 大规模邻域搜索 大规模邻域搜索[16] 主要包括三个过程:破坏过 程、重组过程和局部搜索过程,在构造邻域解时,分别 依次对当前解实施上述三个过程. 破坏过程和重组过 程能够在较大的解空间邻域结构内进行搜索,从而相 对于其余传统邻域构造方法具有更大的可能性找到最 优解. 此外,由于在重组过程中采用较为简单的贪婪 随机插入方法,降低了算法的复杂度,平衡了大规模邻 域搜索过程的效率和效果. 在得到二级配送网络解方案后,按照贪婪随机算 法生成一级配送网络初始解后,算法采用相同的大规 模邻域搜索进行求解. 因为一级配送网络相对于二级 来讲,节点数量较少,采用大规模邻域搜索能够有效的 找到最优解或者近似最优解. 由于一级配送网络与二级配送网络采用相同的大 规模邻域搜索,下文均以二级配送网络为例. 2郾 4郾 1 破坏过程 破坏过程包含两类破坏方法,分别是小规模破坏 和大规模破坏[17] . 小规模破坏包含四种破坏方法:相 邻点移除、最大节约点移除、随机路径移除、单点路径 移除. 大规模破坏包含两种破坏方法:关闭中转站、开 放中转站[18] . 在执行破坏过程时,依次对二级配送网 络解执行上述六种破坏方法,将删除的节点存储在 Insert数组中,以供重组过程使用. 其中关闭中转站和 开放中转站操作只有在迭代到一定代数后才能够有机 会进行,即如果中转站状态被改变后的一段时期内,不 允许进行任何关闭或开放中转站操作. 各个破坏方法具体步骤如下. (1) 相邻点移除. 步骤 1:随机选择一个需求点作为移除根节点. 步骤 2:计算最大移除点数量 MR1 ,MR1 = 腋Rp1 |NC |骎. 步骤 3:随机选择移除点数量,NR1为[0,MR1 ]之间 的随机数. 步骤 4:将根节点和距离根节点最近的 NR1 - 1 个 需求点从原路径中移除,并添加到 Insert 数组中. (2) 最大节约点移除. 步骤 1:计算每个需求点 j 移除后的节约成本 驻j, 驻j = cij + cjk - cik . 步骤 2:计算最大移除点数量 MR2 ,MR2 = 腋Rp2 |NC |骎. 步骤 3:随机选择移除点数量 NR2 ,NR2为[0,MR2 ] 之间的随机数. 步骤 4:按照轮盘赌的方法随机选择 NR2 个需求 点,其中 驻 越大的需求点越有机会被选择移除,将选 择的需求点从原路径中移除,并添加到 Insert 数组中. (3) 随机路径移除. 步骤 1: 计 算 最 大 移 除 路 径 数 量 MR3 , MR3 = Rp3 移i沂C di QK . 步骤 2:随机选择移除路径数量 NR3 ,NR3 为[0, MR3 ]之间的随机数. 步骤 3:随机选择 NR3 条路径,移除选择的路径内 所有需求点,并添加到 Insert 数组中. (4) 单点路径移除. 步骤 1:生成一个[0,1]之间的随机数 r. 步骤 2:如果 r < Rp4 ,则移除二级配送网络解方案 中所有只包含一个需求点的路径,将所有移除的需求 点添加到 Insert 数组中. (5) 关闭中转站. 步骤 1:如果中转站进行开放或关闭操作后算法 迭代代数大于不允许更改中转站状态代数( g > gmax), ·957·