2017, Vol. 32
2. 集美大学 工商管理学院，福建 厦门 361021;
3. 中钢矿业开发有限公司，北京 100080
2. School of Business Administration, Jimei University, Xiamen 361021, China;
3. Sinosteel Mining Co Ltd, Beijing 100080, China
选址-路径问题(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]针对灾后应急物资保障的四层设施选址-运输模型, 采用商业软件进行了小规模算例精确求解研究, 但没有考虑车辆路径规划; 杨恩缘等[15]针对震后多品种应急物资多级配送中的选址-路径问题, 采用商业软件LINGO进行了求解, 研究中对于运输部分采用按距离估算成本方式, 没有考虑车辆路径规划.
综合分析, 目前在LRP研究方面, 国内外虽然取得了一定的成果, 但针对三层级及以上的ME-LRP的研究文献较少, 缺乏针对ME-LRP的通用研究理论和求解方法.为此, 本文探索通用的ME-LRP数学建模及智能求解算法, 并以3E-LRP进行实例测试和验证.
1 ME-LRP模型建立 1.1 问题描述N层级的ME-LRP中, 在工厂和客户之间存在N-1层中间仓储设施.物流网络可用有向图G(V, E)描述, V表示节点集, E表示路径集; D ={D1, D2,…, DN+1}表示N+1层对象节点集, D1表示第1层即工厂的节点集, DN+1表示第N+1层即用户的节点集, Di(i ∈ [2, N])表示中间的N-1层候选设施节点集, 且D ⊆ eq V; Ve = {ve1, ve2,…, veN}表示运输车辆类型集合, 第i层级运输采用车型为vei, i ∈ [1, N].
参数di(i ∈ [1, N+1])表示第i层的对象节点(工厂、候选设施或用户)的数量; cod_Dij(i ∈ [2, N], j ∈ [1, di])表示第i层候选设施j的建设费用; cap_Dij (i ∈ [1, N], j ∈ [1, di])表示第i层设施j的容量, i=1指工厂的生产能力; dem_Dij(i ∈ [1, N+1], j ∈ [1, di])表示第i层设施j的需求量, i=1表示工厂的实际产量, i=N+1表示第N+1层即用户的需求, i ∈ [2, N]表示入选设施实际对应的下级对象的需求总和. {vci, vtli, vtfi, vtci, γi}(i ∈ [1, N])为第i层级运输车辆参数:装载容量、最大行程、行车固定费用、单位运输费率及车辆空载成本系数; λ为周期参数, 以选址费用与一个周期的运输费用之和作为LRP总费用.
变量Zijk = {1, 0}(i ∈ [1, N], j ∈ Di, k ∈ Di+1)描述第i层级中设施分配关系:当上级设施j与下级对象k构成设施分配关系时取值为1, 否则为0; Sijk ={1, 0}(i ∈ [1, N], j ∈ Di∪Di+1, k ∈ Di∪Di+1)表示第i层级中设施节点在车辆路径规划中的顺序关系:当节点j的下一站为节点k时取值为1(即节点j和节点k为同一车辆路径规划中的顺序相邻节点), 否则取值为0.
给定: 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建立如下混合整数规划模型:
|
(1) |
|
(2) |
|
(3) |
|
(4) |
约束条件
|
(5) |
|
(6) |
|
(7) |
|
(8) |
|
(9) |
|
(10) |
|
(11) |
|
(12) |
|
(13) |
|
(14) |
|
(15) |
|
(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为
|
若不考虑VRP, 仅考虑设施选址和设施分配, 则其可能的求解空间排列组合数NLA为
|
可能的VRP子决策数量NV为
|
ME-LRP模型复杂度主要与层级数N和各层设施对象数量di相关.以N=3, {di}={1, 3, 7, 35}为例, 变量Zijk和Sijk个数分别为
|
仅FLP和FAP的求解空间大小为
|
最多存在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优化, 并将优化结果反馈给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 ∈ [1, N], 则第i+1层每个节点对象编码时, 为同时考虑FLP和FAP的需要, 可以用bi+1位量子位编码表示每个对象节点. bi+1需满足以下条件:
|
(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={D1, D2, D3, D4}, D1为工厂P的节点集, D1={34}; D2为一级仓库CD的候选节点集, D2={24, 40, 50}; D3为二级仓库RD的候选节点集, D3={6, 12, 19, 39, 46, 54, 62}; D4为用户即零售商RC的节点集, 设定图中35个节点为RC(黑色实心圆节点).图中还有17个其他节点.设定P的产能、各RC的需求、CD和RD的容量与建设费用, 以及各层级车辆参数等指标, 取λ=365, 进行3E-LRP优化运算. QEA-GA搜索到的3E-LRP优化方案如图 2所示.
|
图 2 LRP优化方案 |
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 ∈ [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用户数量∈[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策略优化结果表 |
|
|
表 2 路径权重FAP策略优化结果表 |
|
图 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费用演化对照图 |
图 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算子以提高寻优效率, 探索采用并行计算或云计算平台提高运算速度是下一步的研究方向.
| [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. DOI:10.1016/0377-2217(89)90188-4 |
| [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. DOI:10.1016/j.ejor.2006.04.004 |
| [4] |
Prodhon C, Prins C. A survey of recent research on location-routing problems[J]. European J of Operational Research, 2014, 238(1): 1-17. DOI:10.1016/j.ejor.2014.01.005 |
| [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. DOI:10.1016/j.ejor.2014.08.030 |
| [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. DOI:10.1016/j.ejor.2003.04.009 |
| [7] |
Jeong-hun L, Il-kyeong M, Jong-heung P. Multi-level supply chain network design with routing[J]. Int J of Production Research, 2010, 48(13): 3957-3976. DOI:10.1080/00207540902922851 |
| [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. DOI:10.11896/j.issn.1002-137X.2015.05.049) |
| [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] |
陈刚, 张锦. 灾后应急物资保障的多目标定位-联运模型[J]. 计算机应用研究, 2014, 31(3): 804-807. (Chen G, Zhang J. Multi-objective location-transportation model in post-disaster relief operations[J]. Application Research of Computers, 2014, 31(3): 804-807.) |
| [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.) |