两级选址-路径问题的大规模邻域搜索模拟退火算法

工程科学学报，第39卷.第6期：953-961,2017年6月 Chinese Journal of Engineering,Vol.39,No.6:953-961,June 2017 D0L:10.13374/j.issn2095-9389.2017.06.019;htp:/journals.ustb.edu.cn 两级选址-路径问题的大规模邻域搜索模拟退火算法 李想，李苏剑⑧，李宏 北京科技大学机械工程学院，北京100083 ☒通信作者，E-mail:lisujian@mc.usth.cdu.cm 摘要针对目前越来越普遍的多级配送模式，建立以总成本最小为目标函数的两级选址-路径问题模型，并提出了大规模 邻域搜索模拟退火算法进行求解.在模拟退火算法框架中，嵌入大规模邻域搜索过程，包含破坏、重组和局部搜索方法，从而 进一步提高算法在解空间中构建邻域的范围.采用两级选址-路径问题标准算例对算法求解效果进行验证，并与标准模拟退 火算法和国际已知最优解进行对比.结果显示，所建模型和算法正确有效，并且在求解大规模问题时算法能够取得相对更好 的优化结果 关键词模拟退火算法；大规模邻域搜索：两级选址一路径问题：破坏重组 分类号224.3 Simulated annealing with large-neighborhood search for two-echelon location routing problem LI Xiang,LI Su-jian,LI Hong School of Mechanical Engineering,University of Science and Technology Beijing,Beijing 100083,China Corresponding author,E-mail:lisujian@me.ustb.edu.cn ABSTRACT Considering the multi-level distribution network has becoming more and more common,a two-echelon location routing problem (2E-LRP)model was established based on minimum total cost objective function.To solve the 2E-LRP model,a simulated annealing with large neighborhood search algorithm was developed.In the framework of the simulated annealing algorithm,a large neighborhood search process was embedded,which includes destroy-and-repair principles as well as some local search methods to further improve the range of the neighborhood search in the solution space.The proposed model and algorithm were tested by two-echelon benchmark instances and compared with the standard simulated annealing algorithm solutions and the internationally best known solutions.The results show the proposed model and algorithm to be correct and that the algorithm can obtain better solutions than standard simulated annealing when solving large-scale problems. KEY WORDS simulated annealing algorithm;large-neighborhood search;two-echelon location routing problem;destroy-and-repair 物流配送企业关注的核心问题之一是如何能够降routing problem,LRP)就是基于此提出的.LRP是物流 低物流配送网络成本，包括配送中心选址建设成本和配送网络规划中设施选址(location allocation problem, 配送运输路径成本，然而如果单独从选址或路径方面 LAP)和车辆路径规划(vehicle routing problem,VRP) 进行优化，往往只能达到局部最优而不能够获得配送 两个问题的集成，通过合理的对配送服务点进行选址、 网络总成本最优口，因此，需要将网络中的设施选址和 安排配送运力、规划配送路径，降低配送网络总成本 路径优化进行综合考虑，选址-路径问题(location 在生鲜配送、药品配送、包裹配送、废弃物回收以及应 收稿日期：2016-11-02

工程科学学报,第 39 卷,第 6 期:953鄄鄄961,2017 年 6 月 Chinese Journal of Engineering, Vol. 39, No. 6: 953鄄鄄961, June 2017 DOI: 10. 13374 / j. issn2095鄄鄄9389. 2017. 06. 019; http: / / journals. ustb. edu. cn 两级选址鄄鄄路径问题的大规模邻域搜索模拟退火算法 李 想, 李苏剑苣 , 李 宏 北京科技大学机械工程学院, 北京 100083 苣通信作者, E鄄mail: lisujian@ me. ustb. edu. cn 摘 要 针对目前越来越普遍的多级配送模式,建立以总成本最小为目标函数的两级选址鄄鄄路径问题模型,并提出了大规模 邻域搜索模拟退火算法进行求解. 在模拟退火算法框架中,嵌入大规模邻域搜索过程,包含破坏、重组和局部搜索方法,从而 进一步提高算法在解空间中构建邻域的范围. 采用两级选址鄄鄄路径问题标准算例对算法求解效果进行验证,并与标准模拟退 火算法和国际已知最优解进行对比. 结果显示,所建模型和算法正确有效,并且在求解大规模问题时算法能够取得相对更好 的优化结果. 关键词 模拟退火算法; 大规模邻域搜索; 两级选址鄄鄄路径问题; 破坏重组 分类号 F224郾 3 Simulated annealing with large鄄neighborhood search for two鄄echelon location routing problem LI Xiang, LI Su鄄jian 苣 , LI Hong School of Mechanical Engineering, University of Science and Technology Beijing, Beijing 100083, China 苣Corresponding author, E鄄mail: lisujian@ me. ustb. edu. cn ABSTRACT Considering the multi鄄level distribution network has becoming more and more common, a two鄄echelon location routing problem (2E鄄鄄LRP) model was established based on minimum total cost objective function. To solve the 2E鄄鄄LRP model, a simulated annealing with large neighborhood search algorithm was developed. In the framework of the simulated annealing algorithm, a large neighborhood search process was embedded, which includes destroy鄄and鄄repair principles as well as some local search methods to further improve the range of the neighborhood search in the solution space. The proposed model and algorithm were tested by two鄄echelon benchmark instances and compared with the standard simulated annealing algorithm solutions and the internationally best known solutions. The results show the proposed model and algorithm to be correct and that the algorithm can obtain better solutions than standard simulated annealing when solving large鄄scale problems. KEY WORDS simulated annealing algorithm; large鄄neighborhood search; two鄄echelon location routing problem; destroy鄄and鄄repair 收稿日期: 2016鄄鄄11鄄鄄02 物流配送企业关注的核心问题之一是如何能够降 低物流配送网络成本,包括配送中心选址建设成本和 配送运输路径成本,然而如果单独从选址或路径方面 进行优化,往往只能达到局部最优而不能够获得配送 网络总成本最优[1] ,因此,需要将网络中的设施选址和 路径优化进行综合考 虑, 选 址鄄鄄 路 径 问 题 ( location routing problem,LRP)就是基于此提出的. LRP 是物流 配送网络规划中设施选址( location allocation problem, LAP)和车辆路径规划( vehicle routing problem,VRP) 两个问题的集成,通过合理的对配送服务点进行选址、 安排配送运力、规划配送路径,降低配送网络总成本. 在生鲜配送、药品配送、包裹配送、废弃物回收以及应

·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·

李想等：两级选址-路径问题的大规模邻域搜索模拟退火算法 ·955· 1.2模型假设 ∑mu≥0a,HseN, (20) (1)候选配送中心、中转站和需求点的数量、地理 位置、固定成本已知，各级配送车辆固定成本已知，需 ma≤oa,Hs∈Ns,Hd∈Nn, (21) 求点的配送需求量已知 An≥，ce, (22) (2)各级物流设施容量已知，分配给各级物流设 n。≤a,VcENc,VsENs. (23) 施的总需求量不能超过设施的容量限制. 式(1)为目标函数.为了降低物流配送网络总体 (3)各级配送车辆容量已知，各配送路径上车辆 成本，目标函数为二级物流配送网络总成本最小化，物 载重不能超过容量限制. 流总成本包括：选择的配送中心固定成本、选择的中转 (4)各节点间距离按照欧氏距离计算，各级配送 站固定成本、一级配送车辆固定成本、二级配送车辆固 车辆单位长度配送成本已知. 定成本、一级配送路径运输成本、二级配送路径运输 (5)每个需求点只能被一辆车服务一次，各级配 成本. 送车辆从物流设施节点出发并返回相同物流设施 式(2)~(23)为约束条件.式(2)保证每个被选 节点 择的中转站只能被一辆一级配送车辆服务一次，未被 1.3数学模型 选择的中转站不能被服务：式(3)保证每个需求点只 Mn2=ACm+￡6s+ 能被一辆二级配送车辆服务一次：式(4)保证一级配 EN. 送网络中每个节点的进出车辆相同：式(5)保证二级 且A三c+Cuya+ E 配送网络中每个节点的进出车辆相同：式(6)保证一 AA名+AAA Cymc (1) 级配送网络中各节点之间不存在回路：式(7)保证二 级配送网络中各节点之间不存在回路；式(8)限制了 s.t. 盆名听e (2) 一级配送网络中各个配送中心之间不允许存在路径； A点g=l.ieN (3) 式(9)限制了二级配送网络中各个中转站之间不允许 存在路径：式(10)表示每个中转站只能被一个配送中 三y三=0，VeN.Ve (4) 心完成服务；式(11)保证每个需求点只能被一个中转 三-三=0，ie水keK. (5) 站完成服务；式(12)保证任意一级配送车辆只能完成 一条服务路径，并且出发点必须是配送中心；式(13) xi=0,VieN,Vvev, (6) 保证任意二级配送车辆只能完成一条服务路径，并且 ym=0,Hi∈N2,HkeK, (7) 出发点必须是中转站：式(14)保证每条一级配送路径 -0.Veev. (8) 上的所有中转站被该条路径上的配送中心服务：式 点Aa=0,eK, (9) (15)保证每条二级配送路径上的所有需求点被该条 路径上的中转站服务；式(16)保证一级配送路径中车 三=l.e, (10) 辆容量不会超过一级配送车辆容量限制：式(17)保证 是=1，ee 二级配送路径中车辆容量不会超过二级配送车辆容量 (11) 限制：式(18)保证配送中心所服务的中转站配送总量 .1.Veev. (12) 不会超过该配送中心容量限制：式(19)保证中转站所 名An≤l,VeK, 服务的需求点配送总量不会超过该中转站容量限制： (13) 式(20)和(21)保证中转站只能够通过被选择的配送 三，+三1+m, 中心完成服务：式(22)和(23)保证需求点只能够通过 VsENs,Hd∈Np,HueV, 被选择的中转站完成服务. (14) 是+点a≤1+： 2求解算法 VcENc,VsENs,VkeK, (15) 本文提出了大规模邻域搜索模拟退火算法(simu- AAg4≤0keK, (16) lated annealing-large neighborhood search,SA-LNS) nd≤0，VueK 较大规模的二级选址-路径问题进行求解.模拟退火 (17) 算法是通过对固体物质高温退火的物理过程进行模 名n≤0.eN. (18) 拟，物理中将某一固体物质加热到以足够高的温度后， dn.m.QVdeN. 再令其逐步降温，在升温过程时，固体物质内能较大， (19) 内部粒子变为无序状，随着温度的下降，内能减少，内

李 想等: 两级选址鄄鄄路径问题的大规模邻域搜索模拟退火算法 1郾 2 模型假设 (1) 候选配送中心、中转站和需求点的数量、地理 位置、固定成本已知,各级配送车辆固定成本已知,需 求点的配送需求量已知. (2) 各级物流设施容量已知,分配给各级物流设 施的总需求量不能超过设施的容量限制. (3) 各级配送车辆容量已知,各配送路径上车辆 载重不能超过容量限制. (4) 各节点间距离按照欧氏距离计算,各级配送 车辆单位长度配送成本已知. (5) 每个需求点只能被一辆车服务一次,各级配 送车辆从物流设施节点出发并返回相同物流设施 节点. 1郾 3 数学模型 MinZ = 移d沂ND CDdwd + 移s沂NS CSs zs + 移i沂ND 移 j沂NS 移v沂V CVv xijv + 移i沂NS 移 j沂NC 移k沂K CKk yijk + 移i沂ND 移 j沂NS 移v沂V cv xijv cfij + 移i沂NS 移 j沂NC 移k沂K ck yijk csij . (1) s. t. 移i沂N1 移v沂V xijv = zj,坌j沂NS , (2) 移i沂N2 移k沂K yijk = 1,坌j沂NC , (3) 移i沂N1 xijv - 移i沂N1 xjiv = 0,坌j沂N1 ,坌v沂V, (4) 移i沂N2 yijk - 移i沂N2 yjik = 0,坌j沂N2 ,坌k沂K, (5) xiiv = 0,坌i沂N1 ,坌v沂V, (6) yiik = 0,坌i沂N2 ,坌k沂K, (7) 移i沂ND 移 j沂ND xijv = 0,坌v沂V, (8) 移i沂NS 移 j沂NS yijk = 0,坌k沂K, (9) 移d沂ND msd = 1,坌s沂NS , (10) 移s沂NS ncs = 1,坌c沂NC , (11) 移i沂ND 移 j沂NS xijv臆1,坌v沂V, (12) 移i沂NS 移 j沂NC yijk臆1,坌k沂K, (13) 移g沂N1 xsgv + 移h沂N1 xdhv臆1 + msd , 坌s沂NS ,坌d沂ND ,坌v沂V, (14) 移g沂N2 ycgk + 移h沂N2 yshk臆1 + ncs, 坌c沂NC ,坌s沂NS ,坌k沂K, (15) 移i沂NC 移 j沂N2 yijkdi臆QK ,坌k沂K, (16) 移i沂ND 移 j沂N1 移c沂NC xijvncjdc臆QV ,坌v沂V, (17) 移c沂NC dcncs臆QS ,坌s沂NS , (18) 移s沂NS 移c沂NC dcncsmsd臆QD ,坌d沂ND , (19) 移d沂ND msd逸wd ,坌s沂NS , (20) msd臆wd ,坌s沂NS ,坌d沂ND , (21) 移s沂NS ncs逸zs,坌c沂NC , (22) ncs臆zs,坌c沂NC ,坌s沂NS . (23) 式(1)为目标函数. 为了降低物流配送网络总体 成本,目标函数为二级物流配送网络总成本最小化,物 流总成本包括:选择的配送中心固定成本、选择的中转 站固定成本、一级配送车辆固定成本、二级配送车辆固 定成本、一级配送路径运输成本、二级配送路径运输 成本. 式(2) ~ (23)为约束条件. 式(2)保证每个被选 择的中转站只能被一辆一级配送车辆服务一次,未被 选择的中转站不能被服务;式(3) 保证每个需求点只 能被一辆二级配送车辆服务一次;式(4) 保证一级配 送网络中每个节点的进出车辆相同;式(5) 保证二级 配送网络中每个节点的进出车辆相同;式(6) 保证一 级配送网络中各节点之间不存在回路;式(7) 保证二 级配送网络中各节点之间不存在回路;式(8) 限制了 一级配送网络中各个配送中心之间不允许存在路径; 式(9)限制了二级配送网络中各个中转站之间不允许 存在路径;式(10)表示每个中转站只能被一个配送中 心完成服务;式(11)保证每个需求点只能被一个中转 站完成服务;式(12)保证任意一级配送车辆只能完成 一条服务路径,并且出发点必须是配送中心;式(13) 保证任意二级配送车辆只能完成一条服务路径,并且 出发点必须是中转站;式(14)保证每条一级配送路径 上的所有中转站被该条路径上的配送中心服务;式 (15)保证每条二级配送路径上的所有需求点被该条 路径上的中转站服务;式(16)保证一级配送路径中车 辆容量不会超过一级配送车辆容量限制;式(17)保证 二级配送路径中车辆容量不会超过二级配送车辆容量 限制;式(18)保证配送中心所服务的中转站配送总量 不会超过该配送中心容量限制;式(19)保证中转站所 服务的需求点配送总量不会超过该中转站容量限制; 式(20)和(21)保证中转站只能够通过被选择的配送 中心完成服务;式(22)和(23)保证需求点只能够通过 被选择的中转站完成服务. 2 求解算法 本文提出了大规模邻域搜索模拟退火算法( simu鄄 lated annealing鄄large neighborhood search, SA鄄鄄 LNS) 对 较大规模的二级选址鄄鄄 路径问题进行求解. 模拟退火 算法是通过对固体物质高温退火的物理过程进行模 拟,物理中将某一固体物质加热到以足够高的温度后, 再令其逐步降温,在升温过程时,固体物质内能较大, 内部粒子变为无序状,随着温度的下降,内能减少,内 ·955·

·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·

李想等：两级选址~路径问题的大规模邻域搜索模拟退火算法 ·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·