·954· 工程科学学报，第39卷，第6期 急物流等领域具有应用价值] 法的一种，模拟退火算法同样容易陷入局部最优导致 近年来越来越多的学者开始关注到选址-路径问 早熟.Yu与Lin)利用模拟退火算法求解了一种开放 题，然而目前大多数研究集中在一级选址-路径问题 式的选址路径问题(open location routing problem, 上.程赐胜等)把LRP问题的解看作是一个整体，采 OLAP),并用最多318个客户点的标准算例进行了检 用遗传算法求解该问题，对遗传算法的编码进行重新 验.由于2E-LRP属于NP-hard问题较为复杂，标准 设计，对交叉和变异操作做了改进，因而能够更容易得 模拟退火算法求解效果不佳，因此本文针对模拟退火 到问题的最优解.Duhamel等a利用贪婪随机自适应 算法的核心之一邻域构建方式进行改进，提出大规模 搜索过程来解决带容量限制的选址-路径优化问题. 邻域搜索模拟退火算法.大规模邻域搜索(large Marinakist)提出了一种改进的粒子群算法，其适用于 neighborhood search,LNS)最早由Shaw[14)提出的，大规 求解离散优化问题，并将该算法应用于求解带容量限 模邻域搜索通过对初始解进行破坏和重组过程，在初 制的选址-路径优化问题.Ponboon等[]提出了一个分 始解较大规模的邻域解空间范围内进行搜索并不断迭 支定价算法来求解带时间窗的选址-路径问题.Lopes 代，从而最终得到最优解.大规模邻域搜索具有邻域 等]提出了一种混合遗传算法来解决带容量限制的选 搜索范围大，求解效果较好等优点.大规模邻域搜索 址一路径问题，该混合遗传算法遵循标准遗传算法框 与模拟退火算法相结合，能够充分发挥二者优势 架，在变异阶段使用邻域搜索过程. 基于以上，本文建立了二级选址-路径问题模型， 随着人们消费水平的提高，需求逐渐从少品种大 设计了大规模邻域搜索模拟退火算法进行求解.本文 批量向多品种小批量方式进行转变.为了适应这种变 通过2E-LRP的标准算例集来对大规模邻域模拟退火 化，物流配送网络需要在供应点和需求点之间建立中 算法的有效性进行检验，并与标准模拟退火算法和国 转站，从而将供货点运来的商品进行拆包、拼装、配载 际已知最优解进行对比验证 等作业⑧)，因此形成了二级选址-路径问题(wo- 1问题描述及模型 echelon location routing problem,2E-LRP).2E-LRP 早由Jacobsen和Madsen9]提出，该问题要解决三个 1.1问题描述 NP-hard子问题：确定物流网络中设施点的数量和位 2E-LRP定义如下：某二级配送网络是由若干个 置、确定一级车辆配送路线、确定二级车辆配送路线. 备选配送中心、若干备选中转站以及已知需求点组成 配送过程中，货物从配送中心出发，经过中转站后到达 目前对于二级选址-路径问题研究还不是很多，Nguyen 等[提出了一种多起点迭代局部搜索算法，利用禁忌 需求点，其中配送中心与中转站以及相应的配送路径 搜索算法框架，并通过路径重连对解方案进行进一步 构成一级配送网络，中转站和需求点以及相应的配送 优化.陈久梅与曾波[]提出一种变邻域人工蜂群算法 路径构成二级配送网络.2E-LRP需要在已知各级物 求解2E-LRP.邓学平等[]建立了B2C电子商务环境 流设施容量、各级物流配送车辆容量和需求点地理位 置、需求量的条件下，确定各级物流设施的数量和位置 下2E-LRP模型，并提出了一种改进的遗传算法进行 以及车辆形式路径，从而使物流网络整体物流成本最 求解.文献研究表明，目前对于LRP研究主要集中在 低.物流网络总成本包括各级物流设施节点的固定成 一级LRP,随着电子商务以及快递行业的快速发展，越 本、各级车辆的固定成本和行驶成本.图1为2E-LRP 来越多的企业采用多级物流配送网络，因此对于2E- 示意图. LRP的研究更贴近现实也更有意义.此外，目前很多 针对2E-LRP的研究只考虑了二级的车辆巡回配送， Q 被选择配送中心 对于一次车辆配送采用直达的方式. 模拟退火(simulated annealing,SA)算法是由 未被选择配送中心 Steinbrunn等[a]最早提出的，并由Kirkpatrick最早利 被选择中转站 --Q 用模拟退火算法来处理组合优化问题.模拟退火算法 △ 未被选择中转站 是通过对固体物质高温退火的物理过程进行模拟，从 需求点 某一较高初温出发，伴随温度参数的不断下降，结合概 一级配送路线 率突跳特性在解空间中随机寻找目标函数的全局最优 二级配送路线 解，最终趋于系统总体内能最低，是一种通用性很强的 优化算法，求解效果相对于其他启发式算法较好，并具 图1二级选址-路径问题示意图 有对初始参数设置不敏感的优点，然而作为启发式算 Fig.1 Example of 2E-LRP network工程科学学报,第 39 卷,第 6 期 急物流等领域具有应用价值[2] . 近年来越来越多的学者开始关注到选址鄄鄄 路径问 题,然而目前大多数研究集中在一级选址鄄鄄 路径问题 上. 程赐胜等[3]把 LRP 问题的解看作是一个整体,采 用遗传算法求解该问题,对遗传算法的编码进行重新 设计,对交叉和变异操作做了改进,因而能够更容易得 到问题的最优解. Duhamel 等[4] 利用贪婪随机自适应 搜索过程来解决带容量限制的选址鄄鄄 路径优化问题. Marinakis [5]提出了一种改进的粒子群算法,其适用于 求解离散优化问题,并将该算法应用于求解带容量限 制的选址鄄鄄路径优化问题. Ponboon 等[6]提出了一个分 支定价算法来求解带时间窗的选址鄄鄄路径问题. Lopes 等[7]提出了一种混合遗传算法来解决带容量限制的选 址鄄鄄路径问题,该混合遗传算法遵循标准遗传算法框 架,在变异阶段使用邻域搜索过程. 随着人们消费水平的提高,需求逐渐从少品种大 批量向多品种小批量方式进行转变. 为了适应这种变 化,物流配送网络需要在供应点和需求点之间建立中 转站,从而将供货点运来的商品进行拆包、拼装、配载 等作业[8] , 因 此 形 成 了 二 级 选 址鄄鄄 路 径 问 题 ( two鄄 echelon location routing problem,2E鄄鄄LRP). 2E鄄鄄LRP 最 早由 Jacobsen 和 Madsen [9] 提出,该问题要解决三个 NP鄄鄄 hard 子问题:确定物流网络中设施点的数量和位 置、确定一级车辆配送路线、确定二级车辆配送路线. 目前对于二级选址鄄鄄路径问题研究还不是很多,Nguyen 等[10]提出了一种多起点迭代局部搜索算法,利用禁忌 搜索算法框架,并通过路径重连对解方案进行进一步 优化. 陈久梅与曾波[8]提出一种变邻域人工蜂群算法 求解 2E鄄鄄LRP. 邓学平等[11]建立了 B2C 电子商务环境 下 2E鄄鄄LRP 模型,并提出了一种改进的遗传算法进行 求解. 文献研究表明,目前对于 LRP 研究主要集中在 一级 LRP,随着电子商务以及快递行业的快速发展,越 来越多的企业采用多级物流配送网络,因此对于 2E鄄鄄 LRP 的研究更贴近现实也更有意义. 此外,目前很多 针对 2E鄄鄄LRP 的研究只考虑了二级的车辆巡回配送, 对于一次车辆配送采用直达的方式. 模 拟 退 火 ( simulated annealing, SA) 算 法 是 由 Steinbrunn 等[12] 最早提出的,并由 Kirkpatrick 最早利 用模拟退火算法来处理组合优化问题. 模拟退火算法 是通过对固体物质高温退火的物理过程进行模拟,从 某一较高初温出发,伴随温度参数的不断下降,结合概 率突跳特性在解空间中随机寻找目标函数的全局最优 解,最终趋于系统总体内能最低,是一种通用性很强的 优化算法,求解效果相对于其他启发式算法较好,并具 有对初始参数设置不敏感的优点,然而作为启发式算 法的一种,模拟退火算法同样容易陷入局部最优导致 早熟. Yu 与 Lin [13]利用模拟退火算法求解了一种开放 式的 选 址 路 径 问 题 ( open location routing problem, OLAP),并用最多 318 个客户点的标准算例进行了检 验. 由于 2E鄄鄄 LRP 属于 NP鄄鄄 hard 问题较为复杂,标准 模拟退火算法求解效果不佳,因此本文针对模拟退火 算法的核心之一邻域构建方式进行改进,提出大规模 邻域 搜 索 模 拟 退 火 算 法. 大 规 模 邻 域 搜 索 ( large neighborhood search,LNS)最早由 Shaw [14] 提出的,大规 模邻域搜索通过对初始解进行破坏和重组过程,在初 始解较大规模的邻域解空间范围内进行搜索并不断迭 代,从而最终得到最优解. 大规模邻域搜索具有邻域 搜索范围大,求解效果较好等优点. 大规模邻域搜索 与模拟退火算法相结合,能够充分发挥二者优势. 基于以上,本文建立了二级选址鄄鄄路径问题模型, 设计了大规模邻域搜索模拟退火算法进行求解. 本文 通过 2E鄄鄄LRP 的标准算例集来对大规模邻域模拟退火 算法的有效性进行检验,并与标准模拟退火算法和国 际已知最优解进行对比验证. 1 问题描述及模型 1郾 1 问题描述 2E鄄鄄LRP 定义如下:某二级配送网络是由若干个 备选配送中心、若干备选中转站以及已知需求点组成. 配送过程中,货物从配送中心出发,经过中转站后到达 需求点,其中配送中心与中转站以及相应的配送路径 构成一级配送网络,中转站和需求点以及相应的配送 路径构成二级配送网络. 2E鄄鄄 LRP 需要在已知各级物 流设施容量、各级物流配送车辆容量和需求点地理位 置、需求量的条件下,确定各级物流设施的数量和位置 以及车辆形式路径,从而使物流网络整体物流成本最 低. 物流网络总成本包括各级物流设施节点的固定成 本、各级车辆的固定成本和行驶成本. 图 1 为 2E鄄鄄LRP 示意图. 图 1 二级选址鄄鄄路径问题示意图 Fig. 1 Example of 2E鄄鄄LRP network ·954·