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

工程科学学报，第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：如果rg)

李 想等: 两级选址鄄鄄路径问题的大规模邻域搜索模拟退火算法 径分割符,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 gmax), ·957·

·958· 工程科学学报，第39卷，第6期 执行步骤2，否则执行步骤5 2-opt指路径内进行二项交换，即选择某路径的 步骤2：生成一个[0,1]之间的随机数r,如果rg,执行步骤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 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·

李想等：两级选址一路径问题的大规模邻域搜索模拟退火算法 ·959· T。=10000,终止温度：T=0.1,降温系数：a=0.96,内 前已知国际最优解和标准模拟退火算法进行对比.本 循环次数：M.=1500,最大不更新代数：Np=300. 文算法在中小规模(25~50个需求点)算例中求解效 大规模邻域搜索部分所含参数包括：相邻点移除概率： 果十分优秀，均能够找到与已知国际最优解相同的解， R。=0.14、最大节约点移除概率：R。=0.50、随机路径 在大规模(100个需求点)算例中，本文算法求解效果 移除概率：R=0.28、单点路径移除概率：R=0.37、 较好.具体求解结果如表1所示. 关闭、开放中转站概率：R。=0.21、不允许更改中转站 上述实验结果表明，在中小规模算例中，大规模邻 状态代数：g=50. 域搜索模拟退火算法能够找到最优解，在大规模算例 3.3实验结果对比分析 中，相对于标准模拟退火算法，SA-LNS求解质量较 将本文的大规模邻域搜索模拟退火算法分别与目 高，总体表现求解效果优秀 表1 Nguyen算例集求解结果 Table 1 Results for Nguyen 2E-LRP instances set 算例 BKS· SA SA-LNS 算例 BKS* SA SA-LNS 25-5-N 80.370 80.370 80,370 50-10-MN 135,519 137,562 135,519 25-5-Nb 64,562 64,562 64.562 50-10-MNh 110,613 110.763 110.613 25-5-MN 78.947 78.947 78.947 100-5-N 193.228 201.866 193,229 25-5-MNb 64,438 64,438 64,438 100-5-Nh 158.927 160,217 159.989 50-5-N 137,815 141,563 137,815 100-5-MN 204.682 211,470 205,862 50-5-Nb 110.094 112,409 110,094 100-5-MNh 165,744 174,740 166,173 50-5-MN 123.484 125,554 123.484 100-10-N 209,952 216.620 210.799 50-5-MNb 105,401 106,313 105.401 100-10-Nb 155,451 157.682 156,401 50-10-N 115,725 119,797 115,725 100-10-MN 201,275 207.795 202.084 50-10-Nb 87,315 88.903 87,315 100-10-MNh 170.625 172,276 170.625 注：◆表示目前国际已知最优解 在小规模问题中(25个需求点)，SA-LNS与SA 图4为SA和SA-LNS算法分别求解算例50-5- 均能够找到最优解：在中等规模问题中(50个需求 MN的迭代曲线对比图.从图中可以看出LNS-SA在 点)，SA不能够找到最优解，但是SA-LNS均能够找到 收敛速度上远优于SA,图中第一代的求解结果显示， 最优解：在大规模问题中(100个需求点)，SA-LNS与 LNS-SA经过一次迭代的优化效果要明显优于SA,并 SA均没能找到最优解，但是SA求解效果较差，SA- 且LNS-SA在第34代完成收敛，而SA在第83代完成 LNS优化效果明显. 收敛.此外LNS-SA在收敛效果也要优于SA,LNS-SA 将大规模邻域搜索嵌入到模拟退火算法中，构造 能够最终收敛到算例国际已知最优解，而A并不能 邻域解时在更大的解空间内进行搜索，从而进一步提 .91 高了算法求解效果，能够在较大规模问题中找到比较 —SA 好的解方案.大规模邻域搜索中的破坏过程包含6种 ---SA-LNS 破坏方法，其中前4种破坏方法是对路径进行优化，后 1.7 2种破坏方法是对设施节点选址进行优化.该方法能 1.6 够将选址与路径问题统一考虑，从而相对于标准模拟 退火算法，能够在选址-路径问题中取得更好的求解 1.5 在求解大规模问题中，标准模拟退火算法不能够很好 14f 地兼顾选址和路径问题，往往导致选择了较差的中转 站节点，这也是在中大规模问题中标准模拟退火算法 求解效果不佳的原因之一 20 50100150200250300350400 由于一级配送网络所含中转站节点总数较少，标 迭代次数 准算例集Nguyen最多只包含有10个中转站，因此采 图4SA与SA-LNS求解算例50-5-MN收敛曲线对比 用大规模邻域搜索能够有效的找到一级配送网络最优 Fig.4 Comparison of SA and SA-LNS convergence trend graphs for 解或者近似最优解 50-5-MN instance

李 想等: 两级选址鄄鄄路径问题的大规模邻域搜索模拟退火算法 T0 = 10000,终止温度:Tf = 0郾 1,降温系数:琢 = 0郾 96,内 循环次数:Mit = 1500,最大不更新代数:Nnotimp = 300. 大规模邻域搜索部分所含参数包括:相邻点移除概率: Rp1 = 0郾 14、最大节约点移除概率:Rp2 = 0郾 50、随机路径 移除概率:Rp3 = 0郾 28、单点路径移除概率:Rp4 = 0郾 37、 关闭、开放中转站概率:Rp5 = 0郾 21、不允许更改中转站 状态代数:gmax = 50. 3郾 3 实验结果对比分析 将本文的大规模邻域搜索模拟退火算法分别与目 前已知国际最优解和标准模拟退火算法进行对比. 本 文算法在中小规模(25 ~ 50 个需求点)算例中求解效 果十分优秀,均能够找到与已知国际最优解相同的解, 在大规模(100 个需求点)算例中,本文算法求解效果 较好. 具体求解结果如表 1 所示. 上述实验结果表明,在中小规模算例中,大规模邻 域搜索模拟退火算法能够找到最优解,在大规模算例 中,相对于标准模拟退火算法,SA鄄鄄 LNS 求解质量较 高,总体表现求解效果优秀. 表 1 Nguyen 算例集求解结果 Table 1 Results for Nguyen 2E鄄鄄LRP instances set 算例 BKS * SA SA鄄鄄LNS 算例 BKS * SA SA鄄鄄LNS 25鄄鄄5鄄鄄N 80,370 80,370 80,370 50鄄鄄10鄄鄄MN 135,519 137,562 135,519 25鄄鄄5鄄鄄Nb 64,562 64,562 64,562 50鄄鄄10鄄鄄MNb 110,613 110,763 110,613 25鄄鄄5鄄鄄MN 78,947 78,947 78,947 100鄄鄄5鄄鄄N 193,228 201,866 193,229 25鄄鄄5鄄鄄MNb 64,438 64,438 64,438 100鄄鄄5鄄鄄Nb 158,927 160,217 159,989 50鄄鄄5鄄鄄N 137,815 141,563 137,815 100鄄鄄5鄄鄄MN 204,682 211,470 205,862 50鄄鄄5鄄鄄Nb 110,094 112,409 110,094 100鄄鄄5鄄鄄MNb 165,744 174,740 166,173 50鄄鄄5鄄鄄MN 123,484 125,554 123,484 100鄄鄄10鄄鄄N 209,952 216,620 210,799 50鄄鄄5鄄鄄MNb 105,401 106,313 105,401 100鄄鄄10鄄鄄Nb 155,451 157,682 156,401 50鄄鄄10鄄鄄N 115,725 119,797 115,725 100鄄鄄10鄄鄄MN 201,275 207,795 202,084 50鄄鄄10鄄鄄Nb 87,315 88,903 87,315 100鄄鄄10鄄鄄MNb 170,625 172,276 170,625 注:*表示目前国际已知最优解 在小规模问题中(25 个需求点),SA鄄鄄 LNS 与 SA 均能够找到最优解;在中等规模问题中(50 个需求 点),SA 不能够找到最优解,但是 SA鄄鄄LNS 均能够找到 最优解;在大规模问题中(100 个需求点),SA鄄鄄 LNS 与 SA 均没能找到最优解,但是 SA 求解效果较差,SA鄄鄄 LNS 优化效果明显. 将大规模邻域搜索嵌入到模拟退火算法中,构造 邻域解时在更大的解空间内进行搜索,从而进一步提 高了算法求解效果,能够在较大规模问题中找到比较 好的解方案. 大规模邻域搜索中的破坏过程包含 6 种 破坏方法,其中前 4 种破坏方法是对路径进行优化,后 2 种破坏方法是对设施节点选址进行优化. 该方法能 够将选址与路径问题统一考虑,从而相对于标准模拟 退火算法,能够在选址鄄鄄路径问题中取得更好的求解. 在求解大规模问题中,标准模拟退火算法不能够很好 地兼顾选址和路径问题,往往导致选择了较差的中转 站节点,这也是在中大规模问题中标准模拟退火算法 求解效果不佳的原因之一. 由于一级配送网络所含中转站节点总数较少,标 准算例集 Nguyen 最多只包含有 10 个中转站,因此采 用大规模邻域搜索能够有效的找到一级配送网络最优 解或者近似最优解. 图 4 为 SA 和 SA鄄鄄 LNS 算法分别求解算例 50鄄鄄5鄄鄄 图 4 SA 与 SA鄄鄄LNS 求解算例 50鄄鄄5鄄鄄MN 收敛曲线对比 Fig. 4 Comparison of SA and SA鄄鄄LNS convergence trend graphs for 50鄄鄄5鄄鄄MN instance MN 的迭代曲线对比图. 从图中可以看出 LNS鄄鄄 SA 在 收敛速度上远优于 SA,图中第一代的求解结果显示, LNS鄄鄄 SA 经过一次迭代的优化效果要明显优于 SA,并 且 LNS鄄鄄 SA 在第 34 代完成收敛,而 SA 在第 83 代完成 收敛. 此外 LNS鄄鄄SA 在收敛效果也要优于 SA,LNS鄄鄄SA 能够最终收敛到算例国际已知最优解,而 SA 并不能 ·959·

·960· 工程科学学报，第39卷，第6期 收敛到已知最优解 Ne={1,2,…,c,…},需求点集合； 图5为LNS-SA求解算例50-5MN的求解结果路 N。={1,2,…,d,…},备选配送中心集合； 径图 N。={1,2,…,s,…},备选中转站集合； 1000 N,=N。UN,一级配送网络节点集合； 900 N,=NsUNc, 二级配送网络节点集合； 800 V={1,2,…,,…},一级配送车辆集合 (2)参数 C倒' 一级配送网络中节点i与节点j之间距离，i,j∈ 500 N: 400 Ck, 二级配送车辆k单位距离行驶成本： 300 ca, 二级配送网络中节点i与节点j之间距离，i,j∈ 200 N2; 100 Cus 一级配送车辆，单位距离行驶成本； 01002003004005006007008009001000 Cn, 配送中心d固定成本； 算例中各节点所在地理位置横坐标 二级配送车k辆固定成本： ▲已使用配送中心口未使用中转站■已使用中转站 Cu’ ·一级配送路径一一一一·二级配送路径·需求点 Cs, 中转站s固定成本； 图5算例50-5-MN求解结果路径 Cxe 一级配送车v辆固定成本； 需求点配送需求量： Fig.5 Optimal solution for 50-5-MN instance di, Qp, 配送中心容量限制： 4结论 Qx, 二级配送车辆容量限制： Qs, 中转站容量限制： (1)针对两级选址-路径问题，建立了以一级、二 Qv. 一级配送车辆容量限制. 级配送网络总成本最小为目标函数的混合整数规划数 (3)决策变量 学模型，考虑了一级配送中心、二级中转站容量约束 1,如果中转站s由配送中心d完成服务 一级、二级配送车辆容量约束.提出了大规模邻域搜 mu=0,否则 其 索模拟退火算法，该算法以模拟退火为框架，在模拟退 中s∈Ns,deNn; 火算法的关键步骤之一邻域构造部分，采用大规模邻 1,如果需求点c由中转站s完成服务 其中 域搜索方法，包含破坏过程、重组过程和局部搜索过 0,否则 程.破坏过程包含6种破坏方式，能够同时对物流设 c∈Nc,s∈Ns; 施选址以及配送路径进行优化，完成重组后的局部搜 1, 如果选择使用配送中心d 10= 其中deNn; 索过程进一步提高搜索效果 Γ0， 否则 (2)采用国际通用的2E-LRP标准算例对算法求 1,如果一级配送车辆v从节点i驶向节点j 解效果进行验证，并与标准模拟退火算法进行对比， 0.否则 SA-LNS能够在中小规模问题中能够得到最优解，在 其中i,jeN,weV,i≠j: 大规模问题中求解效果优秀，并且求解效果均不低于 (1,如果二级配送车辆k从节点i驶向节点j yn= 0,否则 标准模拟退火算法，在中大规模问题上，SA-LNS相对 其中i,jeN2,k∈K,i≠j: 于SA求解效果更优秀，优化效果明显.本文对2E- LRP求解提供了新思路，具有一定的理论和现实意义. 1,如果选择使用中转站5，其中5EN. 3,=0,香则 (3)未来将针对两级选址-路径问题的求解算法 (4)破坏过程符号 组合进行进一步研究，尝试将模拟退火算法与变邻域 R,相邻点移除概率： 搜索和大规模邻域搜索进行组合，改进邻域结构.此 Re,最大节约点移除概率： 外还将针对两级选址-路径问题进行拓展，引入模糊 R,随机路径移除概率； 因素，并考虑时间窗、集配一体化等问题. R 单点路径移除概率； 附录：符号说明 R6,关闭、开放中转站概率； (1)集合. g,中转站进行开放或关闭操作后算法迭代代数； K={1,2,…,k,…},二级配送车辆集合： &,不允许更改中转站状态代数；

工程科学学报,第 39 卷,第 6 期 收敛到已知最优解. 图 5 为 LNS鄄鄄 SA 求解算例 50鄄鄄5MN 的求解结果路 径图. 图 5 算例 50鄄鄄5鄄鄄MN 求解结果路径 Fig. 5 Optimal solution for 50鄄鄄5鄄鄄MN instance 4 结论 (1) 针对两级选址鄄鄄路径问题,建立了以一级、二 级配送网络总成本最小为目标函数的混合整数规划数 学模型,考虑了一级配送中心、二级中转站容量约束, 一级、二级配送车辆容量约束. 提出了大规模邻域搜 索模拟退火算法,该算法以模拟退火为框架,在模拟退 火算法的关键步骤之一邻域构造部分,采用大规模邻 域搜索方法,包含破坏过程、重组过程和局部搜索过 程. 破坏过程包含 6 种破坏方式,能够同时对物流设 施选址以及配送路径进行优化,完成重组后的局部搜 索过程进一步提高搜索效果. (2) 采用国际通用的 2E鄄鄄LRP 标准算例对算法求 解效果进行验证,并与标准模拟退火算法进行对比, SA鄄鄄LNS 能够在中小规模问题中能够得到最优解,在 大规模问题中求解效果优秀,并且求解效果均不低于 标准模拟退火算法,在中大规模问题上,SA鄄鄄 LNS 相对 于 SA 求解效果更优秀,优化效果明显. 本文对 2E鄄鄄 LRP 求解提供了新思路,具有一定的理论和现实意义. (3) 未来将针对两级选址鄄鄄 路径问题的求解算法 组合进行进一步研究,尝试将模拟退火算法与变邻域 搜索和大规模邻域搜索进行组合,改进邻域结构. 此 外还将针对两级选址鄄鄄 路径问题进行拓展,引入模糊 因素,并考虑时间窗、集配一体化等问题. 附录:符号说明 (1) 集合. K = {1,2,…,k,…}, 二级配送车辆集合; NC = {1,2,…,c,…}, 需求点集合; ND = {1,2,…,d,…}, 备选配送中心集合; NS = {1,2,…,s,…}, 备选中转站集合; N1 = ND胰NS , 一级配送网络节点集合; N2 = NS胰NC , 二级配送网络节点集合; V = {1,2,…,v,…}, 一级配送车辆集合. (2) 参数. cfij, 一级配送网络中节点 i 与节点 j 之间距离,i,j沂 N1 ; ck, 二级配送车辆 k 单位距离行驶成本; csij, 二级配送网络中节点 i 与节点 j 之间距离,i,j沂 N2 ; cv, 一级配送车辆 v 单位距离行驶成本; CDd , 配送中心 d 固定成本; CKk, 二级配送车 k 辆固定成本; CSs, 中转站 s 固定成本; CVv, 一级配送车 v 辆固定成本; di, 需求点配送需求量; QD , 配送中心容量限制; QK , 二级配送车辆容量限制; QS , 中转站容量限制; QV , 一级配送车辆容量限制. (3) 决策变量. msd = 1, 如果中转站 s 由配送中心 d 完成服务 0, { 否则 , 其 中 s沂NS ,d沂ND ; ncs = 1, 如果需求点 c 由中转站 s 完成服务 0, { 否则 , 其 中 c沂NC ,s沂NS ; wd = 1, 如果选择使用配送中心 d 0, { 否则 ,其中 d沂ND ; xijv = 1, 如果一级配送车辆 v 从节点 i 驶向节点 j 0, { 否则 , 其中 i,j沂N1 ,v沂V,i屹j; yijk = 1, 如果二级配送车辆 k 从节点 i 驶向节点 j 0, { 否则 , 其中 i,j沂N2 ,k沂K,i屹j; zs = 1, 如果选择使用中转站 s 0, { 否则 ,其中 s沂NS . (4)破坏过程符号. Rp1 , 相邻点移除概率; Rp2 , 最大节约点移除概率; Rp3 , 随机路径移除概率; Rp4 , 单点路径移除概率; Rp5 , 关闭、开放中转站概率; g, 中转站进行开放或关闭操作后算法迭代代数; gmax, 不允许更改中转站状态代数; ·960·

李想等：两级选址~路径问题的大规模邻域搜索模拟退火算法 ·961· INI,需求点总数； [10]Nguyen V P,Prins C.Prodhon C.A multi-start iterated local IN,中转站总数； search with tabu list and path relinking for the two-echelon loca- 「*1，向上取整 tion-routing problem.Eng Appl Artif Intelligence,2012.25(1): 56 [11]Deng X P,Zhou X M,Tian S H.Research on integrated optimi- 参考文献 zation of location and routing for B2C E-commerce logistics cen- ter.J Chongging Unie Posts Telecommunications Nat Sci Ed, [1]Karaoglan I,Altiparmak F,Kara I,et al.A branch and cut algo- 2016,28(4):593 rithm for the location-routing problem with simultaneous pickup (邓学平，周昔敏，田帅辉.B2C电子商务物流中心选址-路 and delivery.Eur J Operational Res,2011,211(2):318 径综合优化研究.重庆邮电大学学报：自然科学版，2016， [2]Zhang X N,Fan H M,LiJ F.Chance-constrained model and al- 28(4):593) gorithm for LRP with multiple fuzzy variables under change-re- [12]Steinbrunn M,Moerkotte G,Kemper A.Heuristic and random- ward.Syst Eng Theory Practice,2016,36(2):442 ized optimization for the join ordering problem.VIDB1997,6 (张晓梢，范厚明，李创锋.变动补偿的多模糊选址-路径机 (3):191 会约束模型及算法.系统工程理论与实践，2016,36(2)： [13]Yu V F,Lin S Y.A simulated annealing heuristic for the open 442) location-routing problem.Comput Operations Res,2015,62: [3]Cheng C S,Pu Y H,Wu Y.Single-stage algorithm of location- 184 routing problem optimization model for integrated logistics.Cen- [14]Shaw P.Using constraint programming and local search methods ral S Univ Forestry Technol,2008,28(5):113 to solve vehicle routing problems /International Conference on (程赐胜，蒲云虎，吴颖.集成化物流选址-路径问题优化模 Principles and Practice of Constraint Programming-CP98. 型的算法研究.中南林业科技大学学报，2008,28(5)：113) Heidelberg:Springer.1998:417 [4]Duhamel C,Lacomme P,Prins C,et al.A GRASP x ELS ap- [15]Schrimpf G,Schneider J,Stamm-Wilbrandt H,et al.Record proach for the capacitated location-routing problem.Comput Oper- breaking optimization results using the ruin and recreate princi- ations Res,2010,37(11):1912 ple.J Comput Phys,2000,159(2)139 [5]Marinakis Y.An improved particle swarm optimization algorithm [16]Pisinger D,Ropke S.Large neighborhood search /Handbook of for the capacitated location routing problem and for the location Metaheuristics.New York:Springer US,2010:399 routing problem with stochastic demands.Appl Soft Computing, [17]Wei Z Y,Wu L,Zhang J W,et al.An adaptive large neighbor- 2015,37:680 hood search for two-echelon vehicle routing problem.Logistics [6]Ponboon S,Qureshi A G,Taniguchi E.Branch-and-price algo- Sci-Tech,2015,38(8):4 rithm for the location-routing problem with time windows.Trans- (魏占阳，邬炼，张佳伟，等基于自适应大规模邻域搜索算 portation Res Part E Logistics Transportation Rev,2016,86:1 法的两级车辆路径问题.物流科技.2015,38(8)：4) [7]Lopes R B.Ferreira C.Santos B S.A simple and effective evolu- [18]Breunig U,Schmid V,Hartl R F,et al.A large neighborhood tionary algorithm for the capacitated location-routing problem. based heuristic for two-echelon routing problems.Comput Opera- Comput Operations Res,2016,70:155 tions Res,2016,76:208 [8]Chen J M,Zeng B.Artificial bee colony algorithm with variable [19]Toth P.Vigo D.The granular tabu search and its application to neighborhood search and path relinking for two-echelon location- the vehicle-routing problem.Informs Computing,2003,15 routing problem.Comput Integr Manuf Syst,2014,20(5):1228 (4):333 (陈久梅，曾波.两级定位一路径问题的路径重连变邻域搜索 [20]Vidal T,Crainic T G,Gendreau M,et al.Heuristics for multi- 人工蜂群算法.计算机集成制造系统，2014,20(5)：1228) attribute vehicle routing problems:a survey and synthesis.Eur/ [9]Jacobsen S K,Madsen O B G.A comparative study of heuristics Operational Res,2013,231(1):1 for a two-level routing-location problem.Eur J Operational Res, [21]Croes G A.A method for solving traveling-salesman problems. 1980,5(6):378 Operations Res,1958,6(6):791

李 想等: 两级选址鄄鄄路径问题的大规模邻域搜索模拟退火算法 | NC | , 需求点总数; | NS | , 中转站总数; 腋*骎, 向上取整. 参 考 文 献 [1] Karaoglan I, Altiparmak F, Kara I, et al. A branch and cut algo鄄 rithm for the location鄄routing problem with simultaneous pickup and delivery. Eur J Operational Res, 2011, 211(2): 318 [2] Zhang X N, Fan H M, Li J F. Chance鄄constrained model and al鄄 gorithm for LRP with multiple fuzzy variables under change鄄re鄄 ward. Syst Eng Theory Practice, 2016, 36(2): 442 (张晓楠, 范厚明, 李剑锋. 变动补偿的多模糊选址鄄鄄 路径机 会约束模型及算法. 系统工程理论与实践, 2016, 36 (2 ): 442) [3] Cheng C S, Pu Y H, Wu Y. Single鄄stage algorithm of location鄄 routing problem optimization model for integrated logistics. J Cen鄄 tral S Univ Forestry Technol, 2008, 28(5): 113 (程赐胜, 蒲云虎, 吴颖. 集成化物流选址鄄鄄 路径问题优化模 型的算法研究. 中南林业科技大学学报, 2008, 28(5): 113) [4] Duhamel C, Lacomme P, Prins C, et al. A GRASP 伊 ELS ap鄄 proach for the capacitated location鄄routing problem. Comput Oper鄄 ations Res, 2010, 37(11): 1912 [5] Marinakis Y. An improved particle swarm optimization algorithm for the capacitated location routing problem and for the location routing problem with stochastic demands. Appl Soft Computing, 2015, 37: 680 [6] Ponboon S, Qureshi A G, Taniguchi E. Branch鄄and鄄price algo鄄 rithm for the location鄄routing problem with time windows. Trans鄄 portation Res Part E Logistics Transportation Rev, 2016, 86: 1 [7] Lopes R B, Ferreira C, Santos B S. A simple and effective evolu鄄 tionary algorithm for the capacitated location鄄routing problem. Comput Operations Res, 2016, 70: 155 [8] Chen J M, Zeng B. Artificial bee colony algorithm with variable neighborhood search and path relinking for two鄄echelon location鄄 routing problem. Comput Integr Manuf Syst, 2014, 20(5): 1228 (陈久梅, 曾波. 两级定位—路径问题的路径重连变邻域搜索 人工蜂群算法. 计算机集成制造系统, 2014, 20(5): 1228) [9] Jacobsen S K, Madsen O B G. A comparative study of heuristics for a two鄄level routing鄄location problem. Eur J Operational Res, 1980, 5(6): 378 [10] Nguyen V P, Prins C, Prodhon C. A multi鄄start iterated local search with tabu list and path relinking for the two鄄echelon loca鄄 tion鄄routing problem. Eng Appl Artif Intelligence, 2012, 25(1): 56 [11] Deng X P, Zhou X M, Tian S H. Research on integrated optimi鄄 zation of location and routing for B2C E鄄commerce logistics cen鄄 ter. J Chongqing Univ Posts Telecommunications Nat Sci Ed, 2016, 28(4): 593 (邓学平, 周昔敏, 田帅辉. B2C 电子商务物流中心选址鄄鄄路 径综合优化研究. 重庆邮电大学学报: 自然科学版, 2016, 28(4): 593) [12] Steinbrunn M, Moerkotte G, Kemper A. Heuristic and random鄄 ized optimization for the join ordering problem. VLDB J, 1997, 6 (3): 191 [13] Yu V F, Lin S Y. A simulated annealing heuristic for the open location鄄routing problem. Comput Operations Res, 2015, 62: 184 [14] Shaw P. Using constraint programming and local search methods to solve vehicle routing problems / / International Conference on Principles and Practice of Constraint Programming — CP98. Heidelberg: Springer, 1998: 417 [15] Schrimpf G, Schneider J, Stamm鄄Wilbrandt H, et al. Record breaking optimization results using the ruin and recreate princi鄄 ple. J Comput Phys, 2000, 159(2): 139 [16] Pisinger D, Ropke S. Large neighborhood search / / Handbook of Metaheuristics. New York: Springer US, 2010: 399 [17] Wei Z Y, Wu L, Zhang J W, et al. An adaptive large neighbor鄄 hood search for two鄄echelon vehicle routing problem. Logistics Sci鄄Tech, 2015, 38(8): 4 (魏占阳, 邬炼, 张佳伟, 等. 基于自适应大规模邻域搜索算 法的两级车辆路径问题. 物流科技, 2015, 38(8): 4) [18] Breunig U, Schmid V, Hartl R F, et al. A large neighborhood based heuristic for two鄄echelon routing problems. Comput Opera鄄 tions Res, 2016, 76: 208 [19] Toth P, Vigo D. The granular tabu search and its application to the vehicle鄄routing problem. Informs J Computing, 2003, 15 (4): 333 [20] Vidal T, Crainic T G, Gendreau M, et al. Heuristics for multi鄄 attribute vehicle routing problems: a survey and synthesis. Eur J Operational Res, 2013, 231(1): 1 [21] Croes G A. A method for solving traveling鄄salesman problems. Operations Res, 1958, 6(6): 791 ·961·