信息缺失下考虑预算约束的物流设施可靠性选址研究
董鹏, 王喜富, 员丽芬
北京交通大学 交通运输学院,北京 100044
通讯作者:王喜富(1963—),男,内蒙古赤峰人,教授,博士,博士生导师.email: xfwang1@bjtu.edu.cn.

第一作者:董鹏(1977—),男,河北怀安人,高级工程师,博士生.研究方向为物流网络优化布局.email:12114205@bjtu.edu.cn.

摘要

针对存在失效风险的设施选址问题,构建了信息缺失下考虑预算约束的物流设施可靠性选址模型.该模型既反映了信息缺失下顾客访问设施方式的变化,又在预算有限的情况下考虑了设施优化布局方案.针对构建模型的特性,基于拉格朗日松弛算法,提出了定制的启发式求解算法.基于京津冀区域的实际数据,构建了一系列的算例,对选址模型的性能和参数进行深入分析研究.研究结果表明:采用拉格朗日松弛算法求解该模型可以获得合理的物流设施选址方案.通过灵敏度分析,探讨了模型参数对物流设施选址成本的影响.

关键词: 物流工程; 可靠性模型; 拉格朗日松弛算法; 信息缺失; 预算约束
中图分类号:F252 文献标志码:A 文章编号:1673-0291(2018)03-0016-07
Research on reliable logistic facility location under information shortage and budget constraints
DONG Peng, WANG Xifu, YUN Lifen
School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044,China
Abstract

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.

Keyword: logistics engineering; reliability model; Lagrangian relaxation algorithm; information shortage; budget constraints

所谓物流设施选址问题, 是指通过合理选择设施的建设位置, 意图获得最优的物流系统总成本.众所周知, 在选址问题中物流设施的一次性建设成本与物流系统中长期的交通成本之间存在着相互制约的关系, 即, 若物流设施的建设成本减少, 则其建设数量也会减少, 导致顾客到达设施的平均距离增加, 最终增加了系统的运输成本; 反之, 若要减少运输成本, 就需要减少顾客到达设施的平均距离, 也就是要增加设施的建设密度, 最终导致建设成本的增加.可以看出, 物流设施选址问题就是要寻求这两者之间的平衡点, 获得最优的总成本.

经典的物流设施选址研究有一个基本假设, 即, 设施一旦建成将永不失效.但随着自然灾害和人为事故的频发, 实际中的设施常遭破坏而无法正常工作, 人们逐渐意识到, 在运营过程中物流基础设施随时面临着失效风险, 可能因为各种事件而无法正常工作.因此, 在研究物流设施选址问题时不仅要考虑系统的运营效率, 还应该考虑到运营的可靠性和弹性.目前, 针对设施可靠性选址问题, 许多学者提出了不同的数学模型, 并设计了相应的求解算法以在合理的求解时间内获得最优的选址方案[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的研究中缺少了对预算的约束, 有可能无法实现最优设施布局的建设.

本文作者根据现有文献的研究, 提出了信息缺失下考虑预算约束的物流设施可靠性选址模型, 并根据本模型的特性定制了启发式求解算法.基于京津冀区域的实际数据, 构建了一系列的算例对物流设施选址方案的特性进行了深入分析, 为京津冀区域物流一体化发展提供理论依据.

1 预算约束下的可靠性选址模型

物流设施选址需要考虑很多现实问题, 如:建设设施预算总额受限、设施存在损坏可能性、设施实时信息缺失等问题, 因此本文在考虑这3个问题基础上提出了信息缺失下考虑预算约束的设施可靠性选址模型.在该模型中, 系统的总成本主要由两部分构成, 分别是设施的建设成本及设施建成后的运营成本.设施的建设成本主要受预算约束, 寻求最优的设施布局方案; 运营成本主要是由顾客获得服务的交通成本和拒绝服务的惩罚成本构成.所谓信息缺失是指, 在信息网损坏或者通达性较差情境下, 顾客无法获知设施的实时工作状态, 只知道既有设施的位置信息.在信息缺失的情形下, 顾客寻求服务的模式发生了根本性的变化.当顾客能够获得设施的完全信息时, 寻找服务的模式为, 从自身所在地直接前往处于正常工作状态、且距离最短的设施, 并获得服务, 如图1(a)所示.顾客只需选择一条路径, 无论是路径①或其他路径, 只需要一条到达有效且距离最短的路径即可; 但当顾客面临信息缺失时, 需要逐一访问预先分配的设施, 直到他找到处于正常工作的设施并获得服务或者放弃寻求服务并接受惩罚成本为止, 如图1(b)所示.该模型试图在预算总额受限的前提下, 确定最优的设施建设数量和位置, 以及预先分配给各个顾客的设施访问次序集合, 进而得到最优的期望总成本, 包括设施的建设成本、顾客期望的交通成本和惩罚成本.

图1 完全信息和信息缺失下顾客访问设施模式Fig.1 Pattern of customer visiting facility under perfect information and information shortage

在该模型中, 所有顾客的集合用I来表示, 其中元素iI表示集合中的某个顾客(简称顾客i); 所有设施的备选位置集合采用J表示, 其中元素jJ表示设施的某个备选位置(简称设施j).对于任意顾客iI, 他的需求采用α i表示.cij表示顾客i从其起始点到设施j的单位需求的交通成本, cijj'表示顾客i从设施j到另外一个设施j'的单位需求的交通成本.单位需求的交通成本与两地之间的距离成正比关系, 其比例系数即单位距离的交通成本为ω .当顾客i未获得服务时, 他的惩罚成本为π .对于任意备选设施jJ, 其建设成本为fj, 其损坏概率为q.为了在模型中更加简单的表示顾客未获得服务的情景, 本文引入一个虚拟设施j0, 当任意顾客i从起始点或任意备选设施去往虚拟设施时, 他的单位需求的交通成本均为π .R表示顾客访问设施的最大等级(包括访问虚拟设施).

为了简化公式, 新增集合定义如下:

J-=J{j0}, Jj+=J-, J\{j}, j=j0jJ, Jj-={j0}, J-\{j}, j=j0jJ,

其中: Jj+代表在备选设施j之前访问的备选设施集合; Jj-则代表在备选设施j后面可以访问的备选设施集合; jJ̅.

决策变量集合Y= yjjJ表示备选设施是否被选中, 即

yj=1, 在候选位置j上建设一个设施0, 其他.

定义设施分配次序的决策变量集合为X= xijiI, jJ-X'= xijj'riI, jJ-, j'Jj-, r=2, , R.

xij=1, 顾客i1等级的分配设施是j0, 其他, xijj'r=1, 顾客i(r-1)等级的分配设施是j,   并且第r等级分配的设施是j',   r=2, , R0, 其他.

由此, 可得到信息缺失下考虑预算约束的物流设施可靠性选址为

ZX, X', Y=minX, X', YjJfjyj+iIαijJ-cijxij+j'Jj-r=2Rqr-1cijj'xijj'r(1)

约束条件:

jJfjyjB(2)jJ-xij=1, iI(3)xij+r=2Rj'Jj-xij'jryj, iI, jJ(4)xij=j'Jj-xijj'2, iI, jJ-(5)j'Jj+xij'j(r-1)=j'Jj-xijj'r, iI, jJ-, r=3, , R(6)jJj0+xijj0R=1, iI(7)xij{0, 1}, iI, jJ-(8)xijj'r{0, 1}, iI, jJ-, j'Jj-, r=2, , R(9)yj{0, 1}, jJ(10)

在该选址模型中, 目标函数(1)表示在不同的设施选址和顾客预先分配设施方案中选取能够使总成本最小的方案.式(2)保证设施选址方案的建设成本不超过预算总额B.式(3)确保分配给每个顾客的第一等级设施必须存在, 无论是分配给实际的设施还是分配给虚拟设施; 式(4)表示分配顾客的设施只能是已经确定要建设的, 而且每个顾客在所有等级中只能访问同一个设施一次.式(5)和式(6)表示顾客必须按照既定的设施访问次序逐一访问设施; 约束条件(7)确保每位顾客可能面临惩罚成本的存在性; 式(8)~(10)表示决策变量为0-1变量.

2 拉格朗日松弛算法

虽然文献[2-5, 8-9]所研究的具体选址问题各不相同, 但均明确指出可靠性选址的这类问题是NP-hard问题.因此本文所要解决的可靠性选址问题仍是NP-hard问题, 需要基于拉格朗日松弛算法定制相应的启发式算法对所提出的可靠性选址模型进行求解.

2.1 下界

从该模型的约束条件中, 可以看出式(4)是决策变量YX, X'之间存在联系的纽带.因此选择对式(4)进行松弛, 并带入目标函数(1)中, 其中 λ=λijiI, jJ表示非负的拉格朗日松弛因子, 由此得到了拉格朗日松弛后的模型(LRλ ), 如下

Z(λ)=minX, X', YjJfj-iIλijyj+iI[αicij0xij0+jJ(αicij+λij)xij+r=2RjJ[αiqr-1cijj0rxijj0r+j'J\{j}αiqr-1cijj'r+λij'xijj'r]](11)

约束条件为式(2)~式(3)、式(5)~式(10).

除此之外, 由于松弛了式(4), 为了确保任意顾客i在所有等级中只能访问任意备选设施j一次, 必须新增一个约束条件如下

xij+r=2Rj'Jj+xij'jr1, iI, jJ(12)

该约束条件并没有增加决策变量YX, X'之间存在的联系.

在LRλ 模型中决策变量YX, X'之间不存在相互约束的关系, 因此可以将LRλ 模型分解为两组独立的子问题, 分别为决策变量是Y的子问题和决策变量是XX' 的子问题.

关于决策变量Y的子问题包括1个子模型如下

ZY(λ)=minYjJ(fj-iIλij)yj(13)

约束条件为

jJfjyjB(14)yj{0, 1}, jJ(15)

根据顾客的数量, 第2组子问题可以分为 I个子模型.任意子模型的目标函数如下

ZiX, X'(λ)=minX, X'αicij0xij0+jJ(αicij+λij)xij+r=2RjJ[αiqr-1cijj0rxijj0r+j'J\{j}αiqr-1cijj'r+λij'xijj'r], iI(16)

所有子模型的约束条件为式(3)、式(5)~式(9)和式(12).

对于给定的λ , 通过对式(13)和式(16)分别进行求解, 得到松弛问题的最优目标值

Z(λ)=ZY(λ)+iIZiX, X'(λ)(17)

该目标值可以作为式(1)的下界.

2.2 上界

若式(11)得到的最优解是原选址模型式(1)~式(10)的可行解, 且Z λ与式(1)相同; 那么说明该可行解正是原选址模型的最优解.否则, 采用启发式算法在式(11)得到的最优解的基础上构建一个原选址模型的可行解, 进而获得式(1)的上界.

根据式(11)得到的最优解, 最简单获取原选址模型可行解的办法就是将XX'的值固定, 然后根据式(4)的限制即可获得Y的值, 如下

yj=maxxij, j'Jj+xij'jr, iI, r=2, , R, jJ(18)

式(18)的时间复杂度为O I·J·R, 求解效率高.但是由于XX'的取值十分分散, 可能会要求建设更多的设施, 使得式(1)的值过大, 进而导致上下界的差距过大.因此, 本文将设施建设的决策变量Y固定, 然后对设施分配的决策变量XX'进行求解.

根据决策表变量Y的值, 定义集合J* = jyj=1, jJ表示已经建设的所有设施.在此基础上, 通过求解 I个如下所示的子模型获得决策变量XX'的取值

Z-iX, X'λ=minX, X', jJ* jJ-αicijxij+r=2RjJj'J-\{j}αiqr-1cijj'rxijj'r(19)

所有子模型的约束条件为式(2)~式(9).

此时, 得到一组可行解{X, X', Y}, 将之带入到式(1)中获得目标函数值, 即可得到式(1)的上界, 采用 Z-λ表示.

2.3 松弛因子更新

对比下界Z λ和上界 Z-λ的大小, 如果两者相同, 那么 Z-λ的最优解就是原选址模型的最优解; 否则, 采用次梯度法来反复更新拉格朗日松弛因子λ , 用于寻找一个较好的可行解.

首先设定松弛因子的初始值λ 1.

然后在每一个迭代步k中, 将松弛因子 λk= λijk迭代为 λk+1= λijk+1, 迭代公式为

λijk+1=λijk+tijk(xij+r=2Rj'Jj+xij'jr-yj), iI, jJ(20)

其中tk为迭代步长

tk=uk(UB-LBk)iIjJxij+r=2Rj'Jj+xij'jr-yj(21)

式中:UB表示到第k个迭代步时所获得最小上界; LBk表示第k个迭代步中所求得的下界; 参数uk初始值取值范围为0< uk≤ 2.如果在连续K迭代步中UB都没有得到优化, 那么参数uk将被更新为uk=uk, 其中θ 是一个大于1的收缩系数.

最后, 如果满足下述的任意条件时结束该算法, 否则重新迭代松弛因子.

1)UB-LBk/UBε , 其中ε 是一个非常小数值;

2)k< kmax, kmax为最大迭代次数;

3)ukumin, umin为参数uk的最小值;

4)算法的求解时间大于T.

3 京津冀区域物流设施选址实例
3.1 数据来源与处理

该案例以京津冀区域内的所有县级市(204个)作为离散的后备选址点, 见图2, 以人口数量的比例值作为顾客的需求量, 并在此基础上获得设施的建设成本.每个数据点的顾客需求量α i为该点人口数量除以100; 设施的建设成本fj=500000+100α i, 设施的损坏概率q=0.05, 设施建设预算总额B=108.顾客未获得服务的惩罚成本π =10 000.

图2 京津冀区域以及离散选址点分布Fig. 2 Beijing-Tianjin-Hebei area and its discrete location nodes distribution

单位距离的交通成本ω =1.拉格朗日松弛算法的参数设定如下:K=6、θ =1.01、ε =0.01、kmax=100 000、umin=0.001和T=1 800 s.

3.2 结果分析

采用本文提出的物流设施可靠性选址模型和求解算法, 对京津冀区域内的物流设施选址进行优化分析.表 1为不同设施损坏概率下, 京津冀区域物流设施选址的结果, 其中误差为下界与总成本(上界)之间的差值百分比, 即, (上界— 下界)/上界× 100%.从表1中可以看出, 对于所有算例来讲, 本文提出的模型和算法可以很好地获得近似最优解, 其求解时间为1 800 s且误差均小于5%, 满足实际工程的需要.此外, 还可观察到, 损坏概率越大, 无论是设施建设数量还是总成本及其各个成本均越大.这说明在建设设施时, 应尽可能降低设施损坏的风险用以减少不可预测的成本增加.图 3对比了不同损坏概率下京津冀区域物流设施选址方案的特点.从该图中可以很清晰地看出, 损坏概率大的设施选址方案中设施集簇效应更加明显, 如图 3(b)中圆圈所示.这说明设施损坏概率的增大会使设施集中建设用以抵御设施损坏所带来的影响.从图 3(a)中可以看出, 当设施损坏概率很小时, 设施分布较为分散, 主要分布在顾客需求较大的区域, 用以减少顾客的交通成本.这些特点可以清晰地表明本文提出的模型和算法是可以解决京津冀区域物流设施选址问题, 并获得较为合理的设施选址方案.

本文对该设施选址模型中的主要参数进行灵敏度分析, 进一步研究其对系统各项成本以及设施建设数量的影响.

表1 不同损坏概率下京津冀区域物流设施选址结果 Tab. 1 Solutions of Beijing-Tianjin-Hebei logistic facility under various disruption probabilities

图3 不同损坏概率下的京津冀区域设施选址方案Fig.3 Facility location scheme with various disruption probabilities in Jing-Jin-Ji area

首先分析不同设施访问等级的设定对系统总成本的影响.表 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)所示)用以降低顾客的出行距离.这就造成了交通成本和建设成本都会随之增加.这说明交通成本与设施的建设成本两者之间具有相互制约的关系, 即交通成本可以通过增加新的设施进行减少, 但设施的建设成本会相应增加, 反之减少设施的建设数量会造成交通成本的增加.寻求最优的设施选址方案就是为了平衡设施的建设成本和顾客的交通成本.另外, 随着运输费率ω 的增加, 顾客的惩罚成本并未增加.这说明巨大的惩罚成本使得顾客并不会因为交通成本的增加而过早的选择放弃寻求服务.

表2 R灵敏度分析 Tab.2 Sensitivity to R

图4 灵敏度分析Fig.4 Sensitivity analysis

4 结论

1)提出了信息缺失下考虑预算约束的物流设施可靠性选址模型, 由于该选址模型研究的选址问题为NP-hard问题, 因此需要设计定制的拉格朗日松弛算法对该模型进行求解.

2)基于京津冀区域的实际数据, 对物流设施选址问题进行了研究.研究结果表明, 该模型和算法可以对京津冀物流设施选址问题进行求解, 并获得合理的设施选址方案.

3)通过灵敏度分析, 反映了模型的参数对京津冀区域物流设施选址成本的影响, 验证了模型的鲁棒性, 为获得最优的京津冀物流设施选址方案提供了理论依据.

The authors have declared that no competing interests exist.

参考文献
[1] SNYDER L V, DASKIN M S. Reliability models for facility location: the expected failure cost case[J]. Transportation Science, 2005, 39(3): 400-416. [本文引用:3]
[2] LI X, OUYANG Y. Reliable traffic sensor deployment under probabilistic disruptions and generalized surveillance effectiveness measures[J]. Operation Research, 2012, 60(5): 1183-1198. [本文引用:4]
[3] LI X, OUYANG Y, PENG F. A supporting station model for reliable infrastructure location design under interdependent disruptions[J]. Transportation Research Part E, 2013, 60: 80-93. [本文引用:3]
[4] AN S, CUI N, BAI Y, et al. Reliable emergency service facility location under facility disruption, en-route congestion and in-facility queuing[J]. Transportation Research Part E, 2015, 82: 199-216. [本文引用:4]
[5] YUN L, QIN Y, FAN H, et al. A reliability model for facility location design under imperfect information[J]. Transportation Research Part B, 2015, 81: 596-615. [本文引用:3]
[6] WANG X, LIM M K, OUYANG Y. Infrastructure deployment under uncertainties and competition: the biofuel industry case[J]. Transportation Research Part B, 2015, 78: 1-15. [本文引用:3]
[7] XIE S, LI X, OUYANG Y. Decomposition of general facility disruption correlations via augmentation of virtual supporting stations[J]. Transportation Research Part B, 2015, 80: 64-81. [本文引用:3]
[8] ZHANG Y, SNYDER L V, QI M, et al. A heterogeneous reliable location model with risk pooling under supply disruptions[J]. Transportation Research Part B, 2016, 83: 151-178. [本文引用:3]
[9] YUN L, WANG X, FAN H, et al. A reliable facility location design model with site-dependent disruption in the imperfect information context[J]. PLOS ONE, 2017, 12(5): e0177104. [本文引用:3]