logo资料库

多层级设施选址-路径规划问题建模及算法.pdf

发布时间：2022-05-30 发布人：admin 分类：说明书 资料大小：0.24M 资料格式：pdf 举报 版权申诉
第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
资料共7页，全文预览结束
    第 32 卷 第 10 期 2017 年 10月 控 制 与 决 策 and Decision Control Vol.32 No.10 Oct. 2017 文章编号: 1001-0920(2017)10-1803-07 DOI: 10.13195/j.kzyjc.2016.1306 多层级设施选址-路径规划问题建模及算法 黄凯明1;2y, 卢才武1, 连民杰3 (1. 西安建筑科技大学 管理学院，西安 710055；2. 集美大学 工商管理学院，福建 厦门 361021； 3. 中钢矿业开发有限公司，北京 100080) 文献标志码: A 摘 要: 基于有向图对物流网络多层级设施选址-路径规划问题, 建立混合整数规划数学模型, 提出量子进化算法 与遗传算法协同的双智能算法集成求解方案. 量子进化算法解决设施选址和设施分配, 遗传算法进行路径规划, 并提出可达配送区域的搜索策略和路径长度为权重的设施分配优化策略以提高算法效率. 实例测试表明, 所提出 的数学模型和组合智能算法是可行而有效的, 可为多层级设施选址-路径规划问题提供理论与方法指导. 关键词: 多层级设施选址-路径规划问题；建模；量子进化算法；遗传算法 中图分类号: TP18；C934 Modeling and algorithm for multi-echelon location-routing problem HUANG Kai-ming1;2y, LU Cai-wu1, LIAN Min-jie3 (1. School of Management，Xi’an University of Architecture and Technology，Xi’an 710055，China；2. School of Business Administration，Jimei University，Xiamen 361021，China；3. Sinosteel Mining Co Ltd，Beijing 100080， China) Abstract: Aiming at the multi-echelon location-routing problem(ME-LRP) based on the directed graph theory, a systematic model is built up, and a combination intelligent algorithm of the quantum-inspired evolutionary algorithm(QEA) and genetic algorithm(GA) is applied to solve it. The QEA is applied to solve the facility location problem(FLP) and facility allocation problem(FAP), and the GA is applied to solve the vehicle routing problem(VRP). In order to improve the efficiency of the algorithm, the searching strategy based on the reachable distribution region and the facility allocation strategy based on path length are proposed. The results from the testing example shows that, the proposed ME-LRP mathematical model and the combined intelligent algorithm are feasible and effective, which provide the oretical and methodical guidance for the ME-LRP. Keywords: multi-echelon location-routing problem；modeling；quantum-inspired evolutionary algorithm；genetic algorithm 0 选址-路径问题 (LRP) 是由设施选址问题 (FLP) 和车辆路径规划问题(VRP) 组成的复杂系统问题, 且 FLP和VRP存在依赖关系[1]. 根据物流网络的层次结 构, LRP 可分为单层级LRP、两层级LRP(2E-LRP) 和 多层级 LRP(ME-LRP). 目前 LRP 的相关研究主要为 2E-LRP[2-5]. Ambrosino 等[6] 首 次 基 于 工 厂-配 送 中 心-转 运 点-客户的 4 层结构研究 3E-LRP, 进行了配送中心和 转运点两层设施选址, 以及配送中心-转运点和转运 点-用户两层路径规划, 并采用商业软件进行了线性 规划模型求解, 需要数十小时的计算量. Jeogn-hun 等[7] 在进行多层次供应链网络设计时也进行了路径 规划, 属于 3E-LRP, 但仅考虑了第 1 层级和第 3 层级 的路径规划, 研究中所提出的算法仅针对的是小规 模的测试算例, 不适用于实际问题. Hamidi 等[8] 研究 了 3E-LRP, 研究中假定不同层次的设施均可向用户 配送, 只进行面向用户级的VRP 规划, 不同层次的设 施间直接配送而不进行路径规划. 文献[9-13] 进行了 2E-LRP 的相关研究; 陈刚等[14] 针对灾后应急物资保 障的四层设施选址-运输模型, 采用商业软件进行了 小规模算例精确求解研究, 但没有考虑车辆路径规 收稿日期: 2016-10-17；修回日期: 2017-01-22. 基金项目: 陕西省重点学科建设专项基金项目(E08001)；陕西省自然科学基金项目(2011JQ7016)；陕西省社会科学 作者简介: 黄凯明 (1973), 男, 副教授, 博士生, 从事管理系统工程及智能算法的研究；卢才武 (1965), 男, 教授, 博 基金项目(2016R014). 士生导师, 从事计算智能及系统工程等研究. 通讯作者. E-mail: kmhuang@jmu.edu.cn y
    1804 控 制 与 决 策 第32卷 划; 杨恩缘等[15] 针对震后多品种应急物资多级配送 中的选址-路径问题, 采用商业软件LINGO 进行了求 解, 研究中对于运输部分采用按距离估算成本方式, 没有考虑车辆路径规划. 综合分析, 目前在 LRP 研究方面, 国内外虽然取 得了一定的成果, 但针对三层级及以上的ME-LRP 的 研究文献较少, 缺乏针对ME-LRP 的通用研究理论和 求解方法. 为此, 本文探索通用的 ME-LRP 数学建模 及智能求解算法,并以3E-LRP进行实例测试和验证. 1 ME-LRP 模型建立 1.1 问题描述 N 层级的 ME-LRP 中, 在工厂和客户之间存在 N1层中间仓储设施. 物流网络可用有向图G(V; E) 描述, V 表示节点集, E 表示路径集; D = fD1; D2; ; DN +1g表示N + 1层对象节点集, D1 表示第1层 即工厂的节点集, DN +1 表示第 N + 1 层即用户的节 点集, Di(i 2 [2; N ]) 表示中间的 N 1 层候选设施 节点集, 且 D V ; Ve= fve1; ve2; ; veNg 表示运 输车辆类型集合, 第 i 层级运输采用车型为 vei; i 2 [1; N ]. 参数di(i 2 [1; N + 1])表示第i层的对象节点(工 厂、候选设施或用户) 的数量; cod_Dij(i 2 [2; N ]; j 2 [1; di]) 表示第 i 层候选设施 j 的建设费用; cap_Dij (i 2 [1; N ]; j 2 [1; di]) 表示第 i 层设施 j 的容量, i = 1 指工厂的生产能力; dem_Dij(i 2 [1; N + 1]; j 2 [1; di]) 表示第 i 层设施 j 的需求量, i = 1 表示工厂的 实际产量, i = N + 1 表示第 N + 1 层即用户的需求, i 2 [2; N ] 表示入选设施实际对应的下级对象的需 求总和. fvci; vtli; vtfi; vtci; ig(i 2 [1; N ]) 为第 i 层 级运输车辆参数: 装载容量、最大行程、行车固定费 用、单位运输费率及车辆空载成本系数; 为周期参 数, 以选址费用与一个周期的运输费用之和作为LRP 总费用. 变量 Zijk = f1; 0g(i 2 [1; N ]; j 2 Di; k 2 Di+1) ∪ 描述第 i 层级中设施分配关系: 当上级设施 j 与下 级对象 k 构成设施分配关系时取值为 1, 否则为 0; Sijk = f1; 0g(i 2 [1; N ]; j 2 Di Di+1) 表示第 i 层级中设施节点在车辆路径规划中的 顺序关系: 当节点 j 的下一站为节点 k 时取值为 1(即 节点 j 和节点 k 为同一车辆路径规划中的顺序相邻 节点),否则取值为0. Di+1; k 2 Di ∪ 给定: G(V; E), D, Ve; 已知参数: di, cod_Dij, cap_Dij, dem_DN +1;j, vci, vtli, vtfi, vtci, i, ; 假定: 第 N + 1 层用户必须得到服务且需求不可 拆分, 车辆从各层级的上级设施点出发, 最后都回到 起点; 求解: Zijk 和Sijk,使得LRP总费用最少. 1.2 ME-LRP数学模型 基于以上假定, 对ME-LRP 建立如下混合整数规 划模型: minf = f1 + f2 + f3; i=1 j=1 k=1 { di+1∑ di∑ N1∑ di+1∑ di∑ N∑ { di∑ di+1∑ di∑ k=1 j=1 j=1 i=1 f1 = f2 = f3 = N∑ N∑ i=1 i(vci)(vtci) (vtfi)Sijk; i=1 j=1 k=1 约束条件 cod_D(i+1)kZijk } ; (1) (2) (3) ∑ line2Route_Pij } dist(line) + (1 i)Zijkdem_D(i+1)k(vtci)Lijk: (4) dem_D(N +1)j ⩽ vcN ; dN +1∑ dem_Dij ⩽ cap_Dij; i 2 [1; N ]; j 2 [1; di]; dem_D(N +1)j ⩽ d1∑ cap_D1j; j=1 j=1 di+1∑ Zijkdem_D(i+1)k; i 2 [1; N ]; S(i=N )jk 1; 8k 2 [1; dN +1]; j=1 j=1 k=1 dem_Dij = dN∑ Z(i=N )jk 1; 8k 2 [1; dN +1]; dN +dN +1∑ 8Z(i+1)jk = 1; 9 di∑ 8Z(i+1)jk = 1; 9 di+di+1∑ Z(i+1)jk = 0; 9 di∑ ∑ Z(i+1)jk = 0; 9 di+di+1∑ ∑ m=1 m=1 m=1 8 8 k k m=1 i 2 [1; N 1]; Simj = 0; Zimj = 1; i 2 [1; N 1]; (11) Simj ⩾ 1; i 2 [1; N 1]; (12) Zimj = 0; i 2 [1; N 1]; (5) (6) (7) (8) (9) (10) (13) (14)
    第10期 黄凯明 等: 多层级设施选址-路径规划问题建模及算法 1805 di∑ j=1 (15) Zijk ⩽ 1; 8i 2 [1; N 1]; dem_Dij > 0; i 2 [1; N + 1]; distijk ⩾ 0; i 2 [1; N ]; Lijk + Likj ⩽ vtli; i 2 [1; N ]: (16) (17) (18) 其中: distijk 为第 i 层级设施点 j 与设施点 k 在有向图 G 中的最短距离; Lijk 为第 i 层级配送路径中, 从上级 设施点 j 出发至配送点 k 的行车里程, j 和 k 为上下不 同层的设施节点; Route_Pij 为第 i 层级上级设施 j 的 车辆路径规划路径序列(集合), 集合为空表示设施 j 未被启用, 否则, 路径序列至少构成一个闭环, 即从设 施j 出发到返回设施j. 式 (1) 为 LRP 费用函数, 求极小值, 由选址费用、 车辆配送固定费用和运输费用3 部分组成; 式(2) 计 算 N 1 层中间设施选址费用; 式(3) 计算 N 层级车 辆配送固定费用; 式(4) 根据 N 层级路径规划方案, 考 虑空车返场费用, 计算 N 层级运输费用; 式 (5) 为第 N + 1 层对象即用户的需求必须小于车载容量, 需求 不可拆分约束之一; 式(6) 为第1 层 第 N 层设施容 量约束; 式(7) 为第 1 层设施即工厂产能必须满足用 户需求约束; 式(8) 为第1 层 第 N 层各设施节点供 需平衡约束; 式(9) 为用户必须且只能分配一个上级 设施约束; 式 (10) 为用户需求不可拆分约束; 式 (11) 为中间层设施点若分配有下级服务节点, 则必须为 其指派上级设施节点约束; 式(12) 为中间层设施点若 分配有下级服务节点, 则其必须且至少存在于1 个上 级设施点的路径规划序列中(需求可以拆分) 约束; 式 (13) 为中间层设施点若未分配有下级服务节点(未被 选址), 则不能为其指派任何上层设施约束; 式(14) 为 中间层设施点若未分配有下级服务节点, 则其不能 存在于任何车辆路径规划序列中约束; 式(15) 为除第 N + 1 层外, 每个下级对象最多只能指派一个上级设 施约束; 式 (16) 为非负需求约束; 式 (17) 为有向图路 径(距离)非负约束;式(18)为车辆运距约束. ME-LRP 模型复杂度分析: 模型中变量 Zijk 和 Sijk 的数量NZ、NS 为 N∑ N∑ i=1 NZ = di di+1; NS = i=1 (di + di+1)2: NLA = dN +1∏ dN∏ d2∏ C 1 dN1+1 C 1 dN (dN1 + 1)dN (d1 + 1)d2; C 1 1 1 d1+1 = 1 ddN +1 N 可能的VRP子决策数量NV 为 N∑ NV = di: i=1 ME-LRP 模型复杂度主要与层级数 N 和各层设施对 象数量di 相关. 以N = 3,fdig = f1; 3; 7; 35g为例,变 量Zijk 和Sijk 个数分别为 NZ = 269; NS = 1 880: 仅FLP和FAP的求解空间大小为 NLA = 735 (3 + 1)7 (1 + 1)3 = 4:965 1034; 最多存在 NV = 11 个VRP 子决策. 因此, ME-LRP 是 求解空间巨大且非常复杂的组合优化问题. 2 ME-LRP 算法设计 组成LRP 的FLP 和VRP 都是NP-Hard 问题, 因此 LRP 更加复杂, 单一的启发式智能算法难以同时解 决其两个子问题. 有些研究人员针对2E-LRP 提出采 用两阶段法来解决 LRP 中的 FLP 和 VRP 两个子问 题[16], 分阶段法实质上是将 LRP 拆分成 FLP 和 VRP 两个独立子问题, 分别予以解决. 如先求解 FLP 子问 题, 在求解 FLP 时对 VRP 的相关费用采用预估方法; 得到FLP的优化解后,再针对FLP优化解进行VRP优 化. 由于LRP 中的FLP 和VRP 存在依赖关系, 分阶段 法难以保证LRP全局最优. 对于N-echelon LRP(N ⩾ 3), 即使不考虑分阶段法的全局寻优理论合理性, 由 于涉及 N 1 层设施选址及 N 层级路径规划, 分阶段 的处理方式也难以实现. LRP 优化包含FLP、设施分配(FAP) 和VRP 三个 决策问题. 其中: FLP 决策哪些候选设施启用, 是典型 的0-1 型决策问题; FAP 确定上下层设施间的分配关 系, 是一个指派问题; VRP 在给定上下层设施的分配 关系后, 确定车辆配送的先后顺序, 属于顺序决策. 由 于VRP决策必须依据FLP和FAP的结果,而FAP决策 又必须与 FLP 决策保持协同, 且 VRP 决策结果又关 系到FLP 和FAP 的决策评价, 因此LRP 的3 个子决策 问题FLP、FAP和VRP是相互关联和相互制约的. 2.1 QEA-GA算法 基于 ME-LRP 特征, 设计 QEA-GA 双智能算法: 采用量子进化算法(QEA)[17-18] 负责FLP 和FAP 优化; 采用遗传算法(GA)将QEA 寻优过程中的FLP 和FAP 若不考虑VRP, 仅考虑设施选址和设施分配, 则其可 能的求解空间排列组合数NLA 为
    1806 控 制 与 决 策 第32卷 中间结果作为输入, 同步进行VRP 优化, 并将优化结 果反馈给 QEA. QEA 和 GA 分工合作, 协同完成 ME- LRP优化. QEA-GA双智能算法模型如图1所示. 图 1 QEA-GA 双智能算法模型 QEA-GA 双算法求解方案中, 纵向的 QEA 解决 跨层间的FLP 和FAP 子问题, 横向的GA 负责解决各 层级 VRP 问题. 因此, 在 ME-LRP 优化过程中, QEA 只执行一次, 而GA 则要根据层级数和各层级内部的 设施节点数量执行多次. QEA 编码由 N 个部分组成: 第2 层 第 N 层的 候选设施编码段和第N + 1层的用户编码段. 在设计 各层节点对象编码时,依据上级设施点的数量确定本 层每个设施点的量子位编码位数. 设上级设施点位 于第i层, i 2 [1; N ],则第i+1层每个节点对象编码时, 为同时考虑FLP 和FAP 的需要, 可以用 bi+1 位量子位 编码表示每个对象节点. bi+1 需满足以下条件: 2bi+1 ⩾ di + 1; i 2 [1; N 1]; 2bi+1 ⩾ di; i = N: (19) 依据式(19) 可计算出第 i + 1 层节点量子编码位 长度的最小整数值bi+1. 根据 bi+1 位量子位观测得到的二进制编码串对 应的十进制值, 用取值为零和非零来表示设施选址, 即: bi+1 位二进制编码串对应的十进制值 = 0, 对应的 设施点设施选址未选中; bi+1 位二进制编码串对应的 十进制值 > 0, 对应的设施点设施选址被选中; 当 bi+1 位二进制编码串对应的十进制值 > 0 时, 其对应的十 进制值还表示与某个上级 (即第 i 层) 设施点的设施 分配关系. 因此, 该编码方案既能满足FLP 需要, 也包 含了FAP的关系描述. GA 采用整数编码. 根据 QEA 的 FLP 和 FAP 输 出, GA 将按FAP 方案中对应的下级设施点数 m 生成 m 位基因编码. m 位基因编码表达了整数 1 m 之间 的排列组合. 上级设施点是车辆路径的出发点和终 点, 不列入GA 基因编码中,但在适应度计算时作为有 向图 G(V; E) 的出发点, 计算车辆行驶里程; 此外, 还 要根据车载容量和最大行程判断是否需要返场. 所 以针对 m 个下级设施点采用 m 位整数基因编码, 对 应的 VRP 路径方案是包含起点和终点 (即上级设施 节点)在内的车辆服务顺序序列. 2.2 基于可达配送区域的搜索策略 从设施点向下级对象节点配送时,任何下级对象 节点必须符合从设施点出发到返回设施点的行车路 径不能超出车辆的最大行程 (式 (18)). 用 Dijkstra 算 法计算出有向图 G(V; E) 中任意两节点的最短路径, 结合不同层级车辆参数,确定每一设施节点对应的可 达配送区域对象节点集合. QEA 在进行FAP 优化时, 结合可达配送区域进行搜索, 可以解决运距约束, 提 高搜索效率和速度. 2.3 基于最短路径长度为权重的FAP优化策略 各层级侯选设施均有容量限制 (式 (6)). 设计如 下 FAP 优化策略: 当设施容量超限时, 按设施到下级 服务对象最短路径长度正相关的概率选择被剔除服 务对象, 即路径越长, 被选择剔除的概率越大; 为下级 服务对象指派上级设施时,按对象节点到可达的上级 设施最短路径长度反相关的概率指派上级设施,即路 径越短, 被指派的概率越大. 基于最短路径长度为权 重的FAP优化策略与惩罚值措施联合作用, 可有效解 决FAP优化过程中的多层级设施容量超限问题. 3 运算测试及结果分析 为测试 N-echelon LRP 模型和 QEA-GA 算法性 能, 以某省主要县市作为有向图节点 (63 节点), 连接 县市的公路作为边 (296 条边), 形成有向图 G(V; E), 并基于 G 构建 3E-LRP 算例: 设定 D = fD1; D2; D3; D4g, D1 为工厂 P 的节点集, D1 = f34g; D2 为一级 仓库 CD 的候选节点集, D2 = f24; 40; 50g; D3 为二 级仓库RD 的候选节点集, D3 = f6; 12; 19; 39; 46; 54; 62g; D4 为用户即零售商RC的节点集,设定图中35个 节点为 RC(黑色实心圆节点). 图中还有 17 个其他节 点. 设定 P 的产能、各RC 的需求、CD 和RD 的容量与 建设费用, 以及各层级车辆参数等指标, 取 = 365, 进行3E-LRP优化运算. QEA-GA搜索到的3E-LRP优 化方案如图2所示. VRPVRPVRPVRPVRPVRPPPDCPlantCandidatedepotCustomerVehicleroutingDDDCCCCCCLayer+1NEchelon:GAforVRPNLayerNLayeriEchelon:GAforVRPiLayer 1Layer 2Echelon 1:GAforVRPDDDDDDQEAfor FLP& FAP
    第10期 黄凯明 等: 多层级设施选址-路径规划问题建模及算法 1807 图 2 LRP 优化方案 3.1 计算环境与算法参数设置 QEA-GA采用ANSI C++设计, Red Hat Enterprise Linux AS 4.0 系统运行, 计算机配置为 IBM xSeries 346 服务器, 3.2 GHz 双 Xeon 处理器, 8 G EEC 内存. QEA 的量子位长度 LQ 体现了寻优空间大小, 应考虑 LQ 值来设置QEA 参数. 结合实验测试, 参考设置为: 当 LQ ⩽ 50 时, 量子种群大小取1, 观测次数取5, 最大 进化运算代数取500; 当 LQ 2 [50; 100] 时, 量子种群 大小取 2, 观测次数取 5, 最大进化运算代数取 1 000; 当LQ ⩾ 100时,如本测试算例LQ = 122,量子种群大 小取2, 观测次数取10, 最大进化运算代数取4 000. 设 定GA 复制概率为0.25, 交换概率为0.60, 突变概率为 0.15, GA 群体大小 GN 和最大运算代数 GT 与VRP 的 用户数量有关, 参考设置为: 当VRP 用户数量⩽ 5 时 (如测试算例的第 1 和第 2 层级), 取 GN = 50; GT = 50; 当VRP 用户数量2 [5; 10] 时(如测试算例的第 3 层 级), 取 GN = 100; GT = 100; 当VRP 用户数量⩾ 10 时, 取 GN = 200; GT = 200 或者更大值. GN 和 GT 取值过小, 容易导致VRP 优化结果为非最优解; 反之, 若 GN 和 GT 取值太大, 则会增加 QEA-GA 的整体运 算时间. 3.2 结果分析 以 25 次 QEA-GA 优化运算为一组, 对测试算例 分别采用常规的随机 FAP 策略和基于路径权重的 FAP 策略, 各进行 4 组测试. 算例 QEA-GA 优化运算 结果见表1和表2,两种策略的结果对比见图3. 表 1 随机FAP 策略优化结果表 No Item LRP Cost FLP Cost FAP Cost VRP Cost 1 2 3 4 Total Avg Opt Avg Opt Avg Opt Avg Opt Avg Opt 143 453 263.2 137 112 622.1 3 780 000 3 600 000 143 801 471.3 3 840 000 138 255 802.1 3 600 000 800 000 0 0 0 380 474.7 365 788.0 383 456.0 368 920.0 143 059 512.5 3 804 000 400 000 380 426.0 138 255 802.1 3 600 000 0 369 660.4 143 714 060.4 3 768 000 400 000 382 317.9 139 044 390.9 3 900 000 0 370 258.6 143 507 076.8 3 798 000 400 000 381 668.7 137 112 622.1 3 600 000 0 365 788.0 表 2 路径权重FAP 策略优化结果表 No Item LRP Cost FLP Cost FAP Cost VRP Cost 1 2 3 4 Total Avg Opt Avg Opt Avg Opt Avg Opt Avg Opt 132 487 252.9 3 876 000 130 132 112.8 3 900 000 132 315 275.4 3 888 000 128 476 764.8 3 900 000 132 051 510.1 126 913 718.8 3 876 000 3 600 000 132 114 569.2 3 888 000 128 173 376.8 3 900 000 132 242 151.9 3 882 000 126 913 718.8 3 600 000 0 0 0 0 0 0 0 0 0 0 352 359.6 345 841.4 351 855.5 341 306.2 351 165.7 337 845.8 351 305.6 340 475.0 351 671.6 337 845.8 373634388352323130267242322251920211817161056272829504933394053541055565751414243441314154124546479606261523584811PlantCDRDRCARC
    1808 控 制 与 决 策 第32卷 图 4 中: LRP 费用曲线随着QEA-GA 进化次数增 加逐步向最优解逼近, 表明算法是有效可行的; LRP 费用曲线和VRP 费用曲线形态基本一致, 表明 取值 大小直接关系到FLP 和VRP 费用在LRP 成本中的权 重. 图 5 中: FLP 费用演化曲线和VRP 费用演化曲线 表明, LRP 中的FLP 与VRP 之间不是相互独立的, 研 究LRP 必须将FLP 与VRP 作为有关联的系统进行同 步优化. QEA-GA 智能算法不是精确算法, 在LRP 寻 优上存在概率不确定性, 通过增加运算次数, 可以增 大寻优概率,或者通过选择多次优化运算的最佳解作 为最优解是可行的. 4 结 论 本文基于有向图对带容量限制的多层级设施选 址-路径规划问题(ME-LRP) 建立了通用数学模型, 并 结合低碳物流[19] 发展趋势, 在模型中纳入了车辆空 载返程费用. 针对提出的ME-LRP 模型, 设计了QEA- GA 双智能算法, 实现了FLP 与VRP 的整合与同步优 化,并提出了基于可达配送区域的搜索策略和基于最 短路径为权重的FAP 优化策略. 3E-LRP 实例仿真运 算表明,所提出的模型和智能算法求解方案是有效可 行的, 适合于较大规模的ME-LRP 问题. 探索新的寻 优策略、改进QEA 或者GA 算子以提高寻优效率, 探 索采用并行计算或云计算平台提高运算速度是下一 步的研究方向. 参考文献(References) [1] Salhi S, Rand G K. The effect of ignoring routes when locating depots[J]. European J of Operational Research, 1989, 39(2): 150-156. [2] Cuda R, Guastaroba G, Speranza M G. A survey on two-echelon routing problems[J]. Computers & Operations Research, 2015, 55: 185-199. [3] Nagy G, Salhi S. Location-routing: Issues, models and methods[J]. European J of Operational Research, 2007, 177(2): 649-672. Prodhon C, Prins C. A survey of recent research on location-routing problems[J]. European J of Operational Research, 2014, 238(1): 1-17. [4] [5] Drexl M, Schneider M. A survey of variants and extensions of the location-routing problem[J]. European J of Operational Research, 2015, 241(2): 283-308. [6] Ambrosino D, Grazia Scutell M. Distribution network design: New problems and related models[J]. European J of Operational Research, 2005, 165(3): 610-624. Jeong-hun L, Il-kyeong M, Jong-heung P. Multi-level [7] 图 3 权重策略与常规搜索寻优对比图 对 100 次优化运算结果统计分析, 平均每次运 算耗时约 59 958 s(约 16.65 小时). 表 1 和表 2 中: FLP Cost 为式 (1) 中的 f1 项, 即入选设施建设费用总和; VRP Cost 为式(1) 中的 f2 与 f3 项之和; FAP Cost 为设 施容量超限费用即容量超限惩罚值. 如 图 3 所 示, 基 于 路 径 权 重 的 FAP 策 略 改 善 QEA-GA 算法性能显著, 采用该策略后的寻优解普 遍优于常规随机搜索解 (FLP Cost 的平均值和最佳 寻优值分别下降7:8 %和7:4 %). 表1和表2数据表明, 路径权重FAP 策略能很好地处理设施容量约束, 100 次优化结果中, 均没有出现设施容量超限情况, 而 常规的随机FAP 处理方式中, 即使采用惩罚值措施, 仍 存 在 设 施 容 量 超 限 解; 最 优 方 案 LRP 总 费 用 为 126 913 718.8(见表 2), 其对应的方案如图 2 所示. 最 优解QEA-GA 迭代过程中的LRP、FLP 和VRP 费用 演化关系如图4和图5所示. 图 4 LRP 总费用与VRP 费用演化对照图 图 5 FLP 费用与VRP 费用演化对照图 125130135140145150LRPCost/106020406080100testing serialsᩗ[ʁψʡʁ01234QEA-GAevolution/103LRPVRP1213141516cost/10701234QEA-GAevolution/103VRPFLP253035404550cost/105
    第10期 黄凯明 等: 多层级设施选址-路径规划问题建模及算法 1809 supply chain network design with routing[J]. Int J of Production Research, 2010, 48(13): 3957-3976. [8] Hamidi M, Farahmand K, Sajjadi S R, et al. A heuristic algorithm for a multi-product four-layer capacitated location-routing problem[J]. Int J of Industrial Engineering Computations, 2014, 5(1): 87-100. [9] 金莉, 朱云龙, 申海. 三级物流网络选址-路径问题 建模与求解算法研究 [J]. 控制与决策, 2010, 25(8): 1195-1200. (Jin L, Zhu Y L, Shen H. Research on modeling and algorithm for three-layer distribution network location-routing problem[J]. Control and Decision, 2010, 25(8): 1195-1200.) [10] 石兆, 符卓. 配送选址-多车型运输路径优化问题及求 解算法[J]. 计算机科学, 2015, 42(5): 245-250. (Shi Z, Fu Z. Distribution location-routing problem of heterotypic vehicles and its algorithms[J]. Computer Science, 2015, 42(5): 245-250.) [11] 戢守峰, 唐金环, 蓝海燕, 等. 考虑选址-路径-库存联合 优化的碳排放多目标模型与算法[J]. 管理工程学报, 2016, 30(3): 224-231. (Ji S F, Tang J H, Lan H Y, et al. Considering the location-routing-inventory joint optimization of carbon emissions multi objective model and algorithm[J]. J of Industrial Engineering/Engineering Management, 2016, 30(3): 224-231.) [12] 周林, 林云, 王旭, 等. 网购城市配送多容量终端选 址与多车型路径集成优化[J]. 计算机集成制造系统, 2016, 22(4): 1139-1147. (Zhou L, Lin Y, Wang X, et al. Integrated optimization for multiclass terminal location-heterogeneout vehicle routing of urban distribution under online shopping[J]. Computer Integrated Manufacturing Systems, 2016, 22(4): 1139-1147.) [13] 戴卓. 三层物流网络选址-路径优化及混合启发式算 法研究[J]. 计算机应用研究, 2017, 34(8): 1-8. (Dai Z. Study on optimization and hybrid heuristic algorithm for location-routing of three-layer logistics network [J]. Application Research of Computers, 2017, 34(8): 1-8.) [14] 陈刚, 张锦. 灾后应急物资保障的多目标定位-联运模 Zhang 型[J]. 计算机应用研究, 2014, 31(3): 804-807. (Chen G, location- transportation model in post-disaster relief operations[J]. Application Research of Computers, 2014, 31(3): 804- 807.) J. Multi-objective [15] 杨恩缘, 李进, 严翌娴, 等. 震后多品种应急物资多 级配送中的选址-路径模型 [J]. 灾害学, 2016, 31(2): 200-205. (Yang E Y, Li J, Yan Y X, et al. Location-routing model for post-earthquake multi-stage distribution with multi-type emergency supplies[J]. J of Catastrophology, 2016, 31(2): 200-205.) [16] Escobar J W, Linfati R, Toth P. A two-phase hybrid heuristic algorithm for the capacitated location-routing problem[J]. Computers & Operations Research, 2013, 40(1): 70-79. [17] 张磊, 方洋旺, 毛东辉, 等. 一种新的相位角编码量子 进化算法[J]. 控制与决策, 2015, 30(4): 739-744. (Zhang L, Fang Y W, Mao D H, et al. A new phase angle encoded quantum evolutionary algorithm[J]. Control and Decision, 2015, 30(4): 739-744.) [18] 高辉, 徐光辉, 王哲人. 改进量子进化算法及其在物 流配送路径优化问题中的应用[J]. 控制理论与应用, 2007, 24(6): 969-972. (Gao H, Xu G H, Wang Z R. An improved quantum evolutionary algorithm and its application to a real distribution routing problem[J]. Control Theory & Applications, 2007, 24(6): 969-972.) [19] 唐金环, 戢守峰, 朱宝琳. 考虑碳配额差值的选址-路 径-库存集成问题优化模型与算法[J]. 中国管理科学, 2014, 22(9): 114-122. (Tang J H, Ji S F, Zhu B L. Optimization model and algorithm considers carbon-capped difference in the collaboration of location-routing-inventory problem[J]. Chinese J of Management Science, 2014, 22(9): 114- 122.) （责任编辑：郑晓蕾）
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料