第一作者:董鹏(1977—),男,河北怀安人,高级工程师,博士生.研究方向为物流网络优化布局.email:12114205@bjtu.edu.cn.
针对存在失效风险的设施选址问题,构建了信息缺失下考虑预算约束的物流设施可靠性选址模型.该模型既反映了信息缺失下顾客访问设施方式的变化,又在预算有限的情况下考虑了设施优化布局方案.针对构建模型的特性,基于拉格朗日松弛算法,提出了定制的启发式求解算法.基于京津冀区域的实际数据,构建了一系列的算例,对选址模型的性能和参数进行深入分析研究.研究结果表明:采用拉格朗日松弛算法求解该模型可以获得合理的物流设施选址方案.通过灵敏度分析,探讨了模型参数对物流设施选址成本的影响.
In order to deal with the facility location problem with failure risk, a reliability model for facility location under information shortage and budget constraints is proposed. This proposed model not only reflects the change of customer visiting facility pattern under information shortage, but also reflects how to design the optimal facility layouts with budget constraints. According to the feature of the proposed model, we propose a customized Lagrangian relaxation algorithm to solve the proposed model. Based on the data of Beijing-Tianjin-Hebei area, we conduct a number of examples to study the performance and parameters of the proposed model. The results indicate that the proposed model solved by Lagrangian relaxation algorithm can obtain a reasonable facility location scheme. Sensitivity analysis makes deep insights on the influence of model parameters on the total cost of facility location design.
所谓物流设施选址问题, 是指通过合理选择设施的建设位置, 意图获得最优的物流系统总成本.众所周知, 在选址问题中物流设施的一次性建设成本与物流系统中长期的交通成本之间存在着相互制约的关系, 即, 若物流设施的建设成本减少, 则其建设数量也会减少, 导致顾客到达设施的平均距离增加, 最终增加了系统的运输成本; 反之, 若要减少运输成本, 就需要减少顾客到达设施的平均距离, 也就是要增加设施的建设密度, 最终导致建设成本的增加.可以看出, 物流设施选址问题就是要寻求这两者之间的平衡点, 获得最优的总成本.
经典的物流设施选址研究有一个基本假设, 即, 设施一旦建成将永不失效.但随着自然灾害和人为事故的频发, 实际中的设施常遭破坏而无法正常工作, 人们逐渐意识到, 在运营过程中物流基础设施随时面临着失效风险, 可能因为各种事件而无法正常工作.因此, 在研究物流设施选址问题时不仅要考虑系统的运营效率, 还应该考虑到运营的可靠性和弹性.目前, 针对设施可靠性选址问题, 许多学者提出了不同的数学模型, 并设计了相应的求解算法以在合理的求解时间内获得最优的选址方案[1, 2, 3, 4, 5, 6, 7, 8, 9].SNYDER[1]等针对一般的设施选址问题, 首先提出了可靠性选址模型并设计了相应的求解算法.之后, 针对不同系统网络的特点, 如:交通传感器网络[2]、应急设施网络[4], 不同学者建立了相应的可靠性选址模型[2, 3, 4, 6, 7, 8].这些可靠性选址研究涵盖了大部分的设施失效情景, 包括了设施失效的同质性[1, 2, 4]、差异性[6, 8]以及关联性[3, 7], 并且假设顾客对于设施失效的情景是完全知晓的.但在实际的社会中, 设施的工作状态往往是无法实时获知的, 只有到达设施之后才能获知, 如:ATM, 加油站等设施, 因此Yun[5, 9]等提出了信息缺失下的设施可靠性选址模型, 并分别考虑了设施失效的同质性[5]和差异性[9].但在Yun的研究中缺少了对预算的约束, 有可能无法实现最优设施布局的建设.
本文作者根据现有文献的研究, 提出了信息缺失下考虑预算约束的物流设施可靠性选址模型, 并根据本模型的特性定制了启发式求解算法.基于京津冀区域的实际数据, 构建了一系列的算例对物流设施选址方案的特性进行了深入分析, 为京津冀区域物流一体化发展提供理论依据.
物流设施选址需要考虑很多现实问题, 如:建设设施预算总额受限、设施存在损坏可能性、设施实时信息缺失等问题, 因此本文在考虑这3个问题基础上提出了信息缺失下考虑预算约束的设施可靠性选址模型.在该模型中, 系统的总成本主要由两部分构成, 分别是设施的建设成本及设施建成后的运营成本.设施的建设成本主要受预算约束, 寻求最优的设施布局方案; 运营成本主要是由顾客获得服务的交通成本和拒绝服务的惩罚成本构成.所谓信息缺失是指, 在信息网损坏或者通达性较差情境下, 顾客无法获知设施的实时工作状态, 只知道既有设施的位置信息.在信息缺失的情形下, 顾客寻求服务的模式发生了根本性的变化.当顾客能够获得设施的完全信息时, 寻找服务的模式为, 从自身所在地直接前往处于正常工作状态、且距离最短的设施, 并获得服务, 如图1(a)所示.顾客只需选择一条路径, 无论是路径①或其他路径, 只需要一条到达有效且距离最短的路径即可; 但当顾客面临信息缺失时, 需要逐一访问预先分配的设施, 直到他找到处于正常工作的设施并获得服务或者放弃寻求服务并接受惩罚成本为止, 如图1(b)所示.该模型试图在预算总额受限的前提下, 确定最优的设施建设数量和位置, 以及预先分配给各个顾客的设施访问次序集合, 进而得到最优的期望总成本, 包括设施的建设成本、顾客期望的交通成本和惩罚成本.
在该模型中, 所有顾客的集合用I来表示, 其中元素i∈ I表示集合中的某个顾客(简称顾客i); 所有设施的备选位置集合采用J表示, 其中元素j∈ J表示设施的某个备选位置(简称设施j).对于任意顾客i∈ I, 他的需求采用α i表示.cij表示顾客i从其起始点到设施j的单位需求的交通成本, cijj'表示顾客i从设施j到另外一个设施j'的单位需求的交通成本.单位需求的交通成本与两地之间的距离成正比关系, 其比例系数即单位距离的交通成本为ω .当顾客i未获得服务时, 他的惩罚成本为π .对于任意备选设施j∈ J, 其建设成本为fj, 其损坏概率为q.为了在模型中更加简单的表示顾客未获得服务的情景, 本文引入一个虚拟设施j0, 当任意顾客i从起始点或任意备选设施去往虚拟设施时, 他的单位需求的交通成本均为π .R表示顾客访问设施的最大等级(包括访问虚拟设施).
为了简化公式, 新增集合定义如下:
其中:
决策变量集合Y=
定义设施分配次序的决策变量集合为X=
由此, 可得到信息缺失下考虑预算约束的物流设施可靠性选址为
约束条件:
在该选址模型中, 目标函数(1)表示在不同的设施选址和顾客预先分配设施方案中选取能够使总成本最小的方案.式(2)保证设施选址方案的建设成本不超过预算总额B.式(3)确保分配给每个顾客的第一等级设施必须存在, 无论是分配给实际的设施还是分配给虚拟设施; 式(4)表示分配顾客的设施只能是已经确定要建设的, 而且每个顾客在所有等级中只能访问同一个设施一次.式(5)和式(6)表示顾客必须按照既定的设施访问次序逐一访问设施; 约束条件(7)确保每位顾客可能面临惩罚成本的存在性; 式(8)~(10)表示决策变量为0-1变量.
虽然文献[2-5, 8-9]所研究的具体选址问题各不相同, 但均明确指出可靠性选址的这类问题是NP-hard问题.因此本文所要解决的可靠性选址问题仍是NP-hard问题, 需要基于拉格朗日松弛算法定制相应的启发式算法对所提出的可靠性选址模型进行求解.
从该模型的约束条件中, 可以看出式(4)是决策变量Y与X, X'之间存在联系的纽带.因此选择对式(4)进行松弛, 并带入目标函数(1)中, 其中
约束条件为式(2)~式(3)、式(5)~式(10).
除此之外, 由于松弛了式(4), 为了确保任意顾客i在所有等级中只能访问任意备选设施j一次, 必须新增一个约束条件如下
该约束条件并没有增加决策变量Y与X, X'之间存在的联系.
在LRλ 模型中决策变量Y与X, X'之间不存在相互约束的关系, 因此可以将LRλ 模型分解为两组独立的子问题, 分别为决策变量是Y的子问题和决策变量是X和X' 的子问题.
关于决策变量Y的子问题包括1个子模型如下
约束条件为
根据顾客的数量, 第2组子问题可以分为
所有子模型的约束条件为式(3)、式(5)~式(9)和式(12).
对于给定的λ , 通过对式(13)和式(16)分别进行求解, 得到松弛问题的最优目标值
该目标值可以作为式(1)的下界.
若式(11)得到的最优解是原选址模型式(1)~式(10)的可行解, 且Z
根据式(11)得到的最优解, 最简单获取原选址模型可行解的办法就是将X和X'的值固定, 然后根据式(4)的限制即可获得Y的值, 如下
式(18)的时间复杂度为O
根据决策表变量Y的值, 定义集合J* =
所有子模型的约束条件为式(2)~式(9).
此时, 得到一组可行解{X, X', Y}, 将之带入到式(1)中获得目标函数值, 即可得到式(1)的上界, 采用
对比下界Z
首先设定松弛因子的初始值λ 1.
然后在每一个迭代步k中, 将松弛因子
其中tk为迭代步长
式中:UB表示到第k个迭代步时所获得最小上界; LBk表示第k个迭代步中所求得的下界; 参数uk初始值取值范围为0< uk≤ 2.如果在连续K迭代步中UB都没有得到优化, 那么参数uk将被更新为uk=uk/θ , 其中θ 是一个大于1的收缩系数.
最后, 如果满足下述的任意条件时结束该算法, 否则重新迭代松弛因子.
1)UB-LBk/UB≤ ε , 其中ε 是一个非常小数值;
2)k< kmax, kmax为最大迭代次数;
3)uk≤ umin, umin为参数uk的最小值;
4)算法的求解时间大于T.
该案例以京津冀区域内的所有县级市(204个)作为离散的后备选址点, 见图2, 以人口数量的比例值作为顾客的需求量, 并在此基础上获得设施的建设成本.每个数据点的顾客需求量α i为该点人口数量除以100; 设施的建设成本fj=500000+100α i, 设施的损坏概率q=0.05, 设施建设预算总额B=108.顾客未获得服务的惩罚成本π =10 000.
单位距离的交通成本ω =1.拉格朗日松弛算法的参数设定如下:K=6、θ =1.01、ε =0.01、kmax=100 000、umin=0.001和T=1 800 s.
采用本文提出的物流设施可靠性选址模型和求解算法, 对京津冀区域内的物流设施选址进行优化分析.表 1为不同设施损坏概率下, 京津冀区域物流设施选址的结果, 其中误差为下界与总成本(上界)之间的差值百分比, 即, (上界— 下界)/上界× 100%.从表1中可以看出, 对于所有算例来讲, 本文提出的模型和算法可以很好地获得近似最优解, 其求解时间为1 800 s且误差均小于5%, 满足实际工程的需要.此外, 还可观察到, 损坏概率越大, 无论是设施建设数量还是总成本及其各个成本均越大.这说明在建设设施时, 应尽可能降低设施损坏的风险用以减少不可预测的成本增加.图 3对比了不同损坏概率下京津冀区域物流设施选址方案的特点.从该图中可以很清晰地看出, 损坏概率大的设施选址方案中设施集簇效应更加明显, 如图 3(b)中圆圈所示.这说明设施损坏概率的增大会使设施集中建设用以抵御设施损坏所带来的影响.从图 3(a)中可以看出, 当设施损坏概率很小时, 设施分布较为分散, 主要分布在顾客需求较大的区域, 用以减少顾客的交通成本.这些特点可以清晰地表明本文提出的模型和算法是可以解决京津冀区域物流设施选址问题, 并获得较为合理的设施选址方案.
本文对该设施选址模型中的主要参数进行灵敏度分析, 进一步研究其对系统各项成本以及设施建设数量的影响.
首先分析不同设施访问等级的设定对系统总成本的影响.表 2展示了系统各项成本以及设施数量随着访问等级R的变化而发生的变化规律.从该表可以看出, R的增加会显著的降低顾客所受到的惩罚成本, 直至惩罚几近等于0.这是由于等级R的增加意味着顾客可以访问更多的备用设施用以获得服务, 与此同时访问这些设施的概率会呈指数级降低, 进而造成顾客未获得服务而选择承受惩罚成本的概率急剧减少, 由此使得系统中的惩罚成本迅速减少乃至无限接近于0.当R=2时, 意味着顾客只会访问主要设施, 一旦主要设施发生损坏, 顾客就要承受非常巨大的惩罚成本.如果为顾客安排一个备用设施, 即R=3时, 发现虽然设施的建设数量、建设成本和交通成本有所增加, 但惩罚成本的减少量则非常巨大, 进而使得总成本也发生断崖式的减少, 其减少量达到了88%.这说明在可靠性设施选址中, 设施备用设施是可以极大降低设施选址运营的总成本, 也就是说可以获得巨大的经济效益.随着设置备用设施数量的增加, 其总成本的减少量在逐渐递减.当R=4时, 总成本的减少比例为37%; 当R=5时, 总成本的减少比例为2.8%.这说明增加额外的备用设施的效益在逐步减少.当R> 5时, 可看出无论是设施的数量还是设施的建设成本均不再变化, 而且系统总成本的减少比例几乎可以忽略不计, 小于0.41%.这说明增加更多的备用设施已经毫无意义, 因此本文选取最大的备用设施数量为5, 即R=5.
其次, 分别对设施的损坏概率q、交通费率ω 以及单位需求的惩罚成本π 进行灵敏度分析.在图 4(a)中, 可以看出随着损坏概率q的增加, 建设成本、交通成本、惩罚成本以及总成本均呈现递增的趋势.虽然建设了更多的设施(如图 4(b)所示)用于减少设施损坏的影响, 相应的建设成本和交通成本随之增加, 但其增加速度缓慢.对于惩罚成本来讲, 它的增加速度非常快几乎呈现指数增长的趋势.这说明损坏概率对于惩罚成本的影响非常巨大, 越来越多的顾客面临着无法获得服务进而受到惩罚的境况.当损毁概率q≥ 0.3时, 惩罚成本超过建设成本和交通成本, 成为总成本的主要构成部分, 相应的, 总成本的变化趋势也越来越接近于惩罚成本的增长趋势.因此要严格控制设施的损坏概率, 防止总成本的过快增加.从图 4(b)可以看出随着损坏概率q的增加, 设施建设数量也呈现出增加的趋势.对比图 4(a), 可以看出, 建设成本增加不仅仅改变了设施的建设数量, 也对设施的具体建设位置产生了影响.
从图 4(c)中可以看出, 随着运输费率ω 的增加, 设施的建设成本、顾客的交通成本以及总成本均呈现近似线性增加的趋势.但是顾客的交通成本增速大于设施的建设成本增速.这是由于运输费率的增加会直接影响顾客需求的交通成本, 造成交通成本过快的增加.为了减少交通成本的增加, 可以修建更多的设施(如图 4(d)所示)用以降低顾客的出行距离.这就造成了交通成本和建设成本都会随之增加.这说明交通成本与设施的建设成本两者之间具有相互制约的关系, 即交通成本可以通过增加新的设施进行减少, 但设施的建设成本会相应增加, 反之减少设施的建设数量会造成交通成本的增加.寻求最优的设施选址方案就是为了平衡设施的建设成本和顾客的交通成本.另外, 随着运输费率ω 的增加, 顾客的惩罚成本并未增加.这说明巨大的惩罚成本使得顾客并不会因为交通成本的增加而过早的选择放弃寻求服务.
1)提出了信息缺失下考虑预算约束的物流设施可靠性选址模型, 由于该选址模型研究的选址问题为NP-hard问题, 因此需要设计定制的拉格朗日松弛算法对该模型进行求解.
2)基于京津冀区域的实际数据, 对物流设施选址问题进行了研究.研究结果表明, 该模型和算法可以对京津冀物流设施选址问题进行求解, 并获得合理的设施选址方案.
3)通过灵敏度分析, 反映了模型的参数对京津冀区域物流设施选址成本的影响, 验证了模型的鲁棒性, 为获得最优的京津冀物流设施选址方案提供了理论依据.
The authors have declared that no competing interests exist.