Modeling and Optimization of Material Supply in the Power Grid Considering Capacity Reservation Contracts with Uncertain Demand
-
摘要:
如何综合挖掘既有仓储网络和协议供应商资源,实现彼此互补和协同、按需备货和分配,是电网企业供应链管理降本增效的难点,其中优化模型的选择是关键。本文采用集成管理的思想,考虑需求的不确定性,基于电网现有物资供应模式,在构建确定性模型的基础上,提出两类物资供应的鲁棒优化模型,利用Bender分解方法设计模型的求解算法。基于国网案例,收集数据,设计实验,对模型和算法的性能进行分析;并针对不同的物资供应模式,探讨需求未满足偏差的惩罚成本参数和预算不确定参数的变化对总成本的影响。研究发现如下。1) Bender分解算法对于求解大规模问题效率更高。2)基于期望需求的确定性模型虽然总成本最低,但抵御不确定需求风险方面不如两类鲁棒模型;基于随机情景的鲁棒模型可以平衡总成本和需求未满足偏差的惩罚成本;考虑预算不确定集的鲁棒模型可以将需求不确定性控制在特定范围内。3)考虑实物库存优先分配与配送的物资供应模式在总成本控制方面更好。4)考虑预算不确定集的鲁棒模型具有很好的需求满足能力,但成本更大;基于随机情景的鲁棒模型在成本上优于考虑预算不确定集的鲁棒模型,但可能部分需求无法满足。
Abstract:Comprehensively exploring resources from the existing warehouse network and contractual suppliers to achieve mutual complementarity and collaboration, coordinated inventory and allocation, is a challenge faced by power grid enterprises to reduce cost and increase efficiency in supply chain management, where the selection of optimization models is critical. From the perspective of integrated management, this paper considers demand uncertainty based on current material supply modes in the power grid. It proposes robust optimization models for two types of material supplies based on a deterministic model. A solution algorithm based on the Bender decomposition method is designed to solve the above models. Using data collected from a State Grid case, experiments are designed to analyze the performance of the models and the algorithm. Additionally, the impacts of changes in the penalty cost parameter of unmet demand deviation and the budget uncertainty parameter on total cost are explored under different material supply modes. Results show that 1) the Bender decomposition algorithm in this paper is more efficient in solving large-scale problems. 2) The deterministic model based on expected demand has the lowest total cost but is less effective in addressing uncertain demand risks compared to the two robust models: the robust model based on stochastic scenarios can balance the total cost and the penalty cost of unmet demand deviation, while the robust model based on budget uncertainty can control demand uncertainty within a specific range. 3) Material supply modes considering physical inventory prioritization for allocation and distribution offer better total cost control. 4) The robust model based on budget uncertain sets possesses a good demand satisfaction capability but reveals a greater cost; the robust model based on stochastic scenarios is better than that based on budget uncertain sets in terms of cost, but may cause some unmet demand.
-
Keywords:
- power grid /
- capacity reservation contracts /
- material supply /
- robust model /
- Bender decomposition
-
物资供应是保证电网建设和运营的必要前提,高效的保供方案是企业降本增效、减少运营风险的重要保证。随着数字化供应链和智慧供应链的发展,电网构建了中心库+周转库+终端库+专业仓的多级库存仓储网络,建立了实物储备、协议库存、寄存代储、现货采购的多种物资供应(自储+协同)模式,搭建了ERP (enterprise resource planning,企业资源规划) +WMS (warehouse management system,仓库管理系统) +VMI (vendor managed inventory,供应商管理库存) +调配系统的信息系统。基于此,物资供应的及时性和经济性有了显著的提升。
然而,实际运营发现,既有的物资供应模式还存在着诸多不足。多级库存仓储网络虽然需求响应及时,但常因自储不合理,以及仓库间周转、调拨与积压,导致管理成本高。协议库存虽是一种创造性的库存采购方法,将库存保留在供应商处,采用“定厂、定价、定量”框架,通过在招标采购时明确未来一段时间物资需求总量来保障物资的供应,但由于基于项目群的方式进行需求预测的精度有限,不确定情形多,常需后期进行库存消减。因此,在需求存在不确定性的情况下,如何合理地启用仓储网络,在各个仓储点科学自储备货,实现区域互补协同;如何规划协议库存供应商,确定有效的协议库存量;如何实现各类库存量的合理分配等都是企业需要解决的问题,即采用集成管理的思想,将原来分散的仓库自储备货、调拨分配,以及协议库存供应商的决策、协议库存量的决策与分配统一进行考虑。通过集成调配决策,应对需求的不确定性和分散决策方案的高风险性和脆弱性,增强供应链的系统性,提升物资供应能力,实现电网企业与物资供应商的“双赢”。
选址问题(facility location problem,FLP)是与本研究相关的问题之一,主要确定所要分配的设施的数量、位置以及分配方案,以满足特定的需求。这些设施主要指物流系统中的节点,如制造商、供应商、仓库、配送中心、零售网点等。它是运筹优化领域非常经典且应用广泛的问题[1],如选址分配问题(location allocation problem,LAP)、选址运输问题(facility location-transportation problem,FTP)、动态选址问题(dynamic location problem,DLP)、竞争选址问题(competitive location problem,CLP)等。特别地,随着运营环境的变化,经典选址问题中的成本、需求、旅行时间及其他输入参数可能是高度不确定的,建立不确定条件下的选址模型已经成了物流和随机优化、鲁棒优化等领域的热门问题[2-4]。Cheung等[4]构建两阶段和多阶段随机规划模型解决了预期客户需求的情况下,经由一个仓库集合,从一个或多个工厂配送商品的问题。Ardestani-Jaafari等[5]使用预算不确定性集的鲁棒优化模型研究了一个有容量约束的固定费率的多周期选址−运输问题,确定每个设施的位置和容量,以及如何生产和配送。本文同样针对不确定需求,但结合协议库存供应商的安排,来探索如何将需求有效地分配给合适的仓库和协议库存供应商,以实现系统总成本最小。
供应商选择与订单分配问题(supplier selection & order allocation,SS&OA)是与本研究相关的另一问题,这是一个复杂的决策问题,包括许多有形和无形的标准。目标在于选择最好的供应商组合,并在选择的供应商间实现订单需求的最优分配,满足不同的采购标准以及供应商的容量限制,使得QCD测度(成本、数量、配送时间等)最优[6-7]。结合情境和决策范式展开应用研究成为近年来的趋势。Torabi等[6]在运作和中断风险存在的情境下提出了一个双目标概率和两阶段随机混合的模型研究SS&OA问题,以建立可靠的供应基地。Ahmad等[7]研究了带式输送机行业中两级按订单供应链中的供应商选择和订单分配问题,将田口公差设计方法 (Taguchi method of tolerance design,TMTD) 与混合整数非线性规划(mixed integer nonlinear programming,MINLP)模型结合,寻找保持最优的供应商选择和订单分配决策的鲁棒解,最大限度地减小供应链网络总成本的可变性。Feng等[8]针对华为手机制造商的案例,在风险发生概率不确定的中断情境中,建立两阶段分布鲁棒模型,研究供应商选择和订单分配问题,平衡平均成本和风险水平,提高供应链弹性。
然而,本文虽然要将供应商的协议库存分配并配送到需求点,但不讨论额外的标准。假定参与物资供应的协议库存供应商都符合既定标准,仅需结合供应商的成本和配送距离等因素综合确定供应商的选择和订单分配。协议库存事实上是一种容量保留合同(capacity reservation contracts)[9],即一种长期供应或补货合同。对于下游企业而言,它具有成本低、货源有保障、不占企业自身仓储空间等许多优点,因此实践应用非常多[9-11]。如何设置容量和价格,以及如何与既有仓储相互补充、满足物资供应需求是研究的重点。Park等[10]研究了一个向终端消费者提供单一类型产品的采购商与多个异质的供应商利用数学模型确定容量和价格的问题。Alvarez等[11]在供应和需求均为不确定的情境下,利用两阶段随机规划模型研究库存路径问题(inventory routing problem,IRP),采用容量保留合同作为一种补偿机制。本文的关注点是协议库存匹配策略的效率和效益,试图通过集成优化模型中将协议库存结合进来,与仓储备货一起集中决策,以解决单纯协议库存应用时的匹配订单区域分散、物流运输成本高的问题。
物流网络规划问题(logistics network planning,LNP)也是与本文研究相关的问题。Jalal等[12]认为物流网络规划涉及设施(工厂、仓库和配送中心)启用,选择供应商、将产品分配到工厂、选择配送渠道和运输方式,以及通过网络确定原材料、半成品和成品的流量。它是跨战略、策略和运营等层次的复杂决策问题。这些决策层次之间存在相互依赖关系,面对不断变化的商业情景,集成对于减少成本和增强网络响应性非常重要。姚冠新等[13]构建了一种同时满足农产品与非农产品物流需要,并允许直达运输的混合轴辐式城乡一体化物流网络规划模型,以降低城乡物流成本和提高城乡物流效率。李珍萍等[14]针对顾客需求量不确定情况下末端配送中心选址及提前备货问题,建立了两阶段连续型随机规划模型,研究基于“自营+外包”配送模式的配送中心选址−配送问题。Mohammed等[15]认为供应商选择和订单分配是供应链管理中两个最重要的阶段,针对肉制品供应链,考虑经济、环境和社会标准,设计了一个包含4个阶段的集成方法,解决可持续的两阶段供应商选择和订单分配问题。Badri等[16]考虑设施、公共仓库和建立私人仓库的潜在地点的最小和最大利用率等特点,将具有不同时间分辨率的战术和战略决策进行了有机集成,提出了一个新的多层次、多商品供应链网络设计数学模型,用于寻找公司收入对主要发展来源、公司活动扩展和服务扩展的最佳分配。本文也采用集成管理的思想,将仓库的备货、供应商的选择、协议库存和实物库存的分配与配送等供应链多个环节集成起来,建立有效的模型解决企业面临的实际问题。
上述文献从不同的视角研究了不同情境下,各类设施 (物流) 网络为满足特定物资需求,如何协调网络(供应商、仓库等)和各种流(物流、资金流等)保障物资供应效益和效率的问题。本文针对国网现有的物资供应模式和数据集,采用集成管理的思想,以总成本最小为目标,构建确定性物资供应模型;在此基础上,基于情景方法和区间支集方法描述不确定需求,分别利用Mulvey等[17]和Bertsimas等[18]提出的鲁棒优化方法建立鲁棒优化模型;设计基于Bender分解方法[19]的求解算法。通过计算实验,研究模型和算法的性能,分析需求未满足偏差的惩罚成本参数和预算不确定参数的变化,以及物资供应模式对总成本的影响,从而为企业在不确定需求的情况下优化带有协议库存的物资供应模式和模型选择提供启示和参考。
1. 问题描述与建模
本文所探讨的模型是一个综合性的集成模型,用于解决战略层次的仓库位置的选择、协议库存供应商的选择和协议库存量的决策,以及运营层次每个周期的协议库存的分配、仓库的备货、周转及分配问题。通过对既有的选址库存问题、选址路径问题进行适当改进,可以更好地反映现实的电网物资供应模式。首先给出需求确定性条件下的优化模型。与以往模型不同,本模型具有如下明显的特征:1)模型集成了仓库选址、协议库存供应商选择和库存的分配等现实的管理功能;2)模型考虑了仓库之间的货物周转和调拨,以更好地管理仓库的库存,协调不同仓库的物资资源,实现库存成本的优化;3)模型考虑了企业现实的管理策略,在物资分配时能够差异化地对待库存,确保自有仓库的物资优先分配。
下面的多周期混合整数规划公式给出了针对如上现实问题特征的确定性的模型。假设需求是确定已知的,由于信息系统的存在,库存信息是共享和透明的,因此本文不区分仓库类型,每期的需求必须当期得到满足。
1.1 符号说明
1)集合。
I :备选的签订协议库存的供应商的集合;J :备选的仓库(周转库或终端库)集合;T :规划期集合(包含|T| 个周期);K :需求点集合。2)索引。
i :供应商索引;j :仓库索引;t :周期索引;k :需求点索引。3)参数。
αi :与供应商i合作的固定成本;ati :在t期供应商i备货的单位可变成本;atj :在t期仓库j备货的单位可变成本;ctjj′ :t期末从仓库j到仓库j′ 的单位转移成本(当j≠j′ 时),或仓库j在t期末时的库存持有成本(当j=j′ 时);otik :在t期从供应商i到需求点k的单位运输成本;otjk :在t期从仓库j到需求点k的单位运输成本;htj :在t期仓库j的单位库存持有成本;I0i :供应商i在规划期开始时的初始库存;I0j :仓库j在规划期开始时的初始库存;mi :供应商i的最大可签订的协议库存量;βj :仓库j的最大库存量;dtk :在t期需求点k的需求(假设是随机且离散的)。4)决策变量。
xti : 供应商i在t期的协议库存的备货量;xtj : 仓库j在t期的备货量;zi :与供应商i签订的最大协议库存合同量;Iti : 供应商i在t期末的库存量;Itj : 仓库j在t期末的库存量;utik : 供应商i在t期分配给需求点k的需求dtk 的比例;vtjk : 仓库j在t期满足需求点k的需求dtk 的比例;ftjj′ : 在t期结束时从仓库j转移到仓库j′ 的数量。1.2 确定性物资供应模型 (deterministic model, DM)
ZD=min{∑i∈Iαizi+∑t∈T∑i∈I(atixti+∑k∈Kotikutik)+∑t∈T∑j∈J(atjxtj+htjItj+∑j′∈Jctjj′ftjj′+∑k∈Kotjkvtjk)}。 s.t. It−1i+xti−∑k∈Kutik=Iti,∀i,t; (1) zi⩽mi,∀i; (2) |T|∑τ=1xτi⩽zi,∀i; (3) It−1j+xtj+∑j′∈Jft−1j′j−∑k∈Kvtjk−∑j′∈Jftjj′=Itj,∀j,t; (4) Itj⩽βj,∀j,t; (5) ∑i∈Iutik+∑j∈Jvtjk⩾dtk,∀k,t; (6) xti,xtj,zi,utik,ftjj′,vtjk,Iti,Itj⩾0,∀i,j,j′,k,t。 (7) 目标函数
ZD 以总成本最小化为目标,集成了供应商端的成本和仓库端的成本。第1项为备选的协议库存供应商的协议库存签订的固定成本(体现为招投标的成本);第2项为每期供应商协议库存的备货成本 (体现为采购单价) 与每期供应商的协议库存备货量分配给需求点的成本(体现为配送成本)之和;第3项为仓库每期的自储备货成本、库存持有成本、库存物资周转调拨成本以及库存物资分配给需求点的成本(体现为配送成本)之和。约束(1)为供应商协议库存的期末库存量。在每个时间周期内,可供分配的量应不超过上期的协议库存的期末库存量加上当期的备货量。约束(2)为合作供应商可签订的协议库存合同的上限,且所签的协议库存合同量不能超过合作供应商的能力限制。约束(3)确保协议库存供应商所有周期的备货量不超过所签协议库存合同量的限制。约束(4)为仓库在周期
t 的期末库存约束,期末库存量等于上期的期末库存量加上本期的自储备货量和其他仓库调拨周转进来的量,再减去本仓库调拨周转出去的量和分配给各个需求点的量。约束(5)为每个周期仓库的期末库存量的最大上界约束。约束(6)确保每个周期每个需求点的需求均能得到满足,它们由仓库的自储备货量和协议库存量共同供应。约束(7)为所有决策变量的非负和0-1整数约束。现实中,企业为了更好地降低自身的仓储成本,往往会制定相应的管理制度,优先保障实物库存先进行需求匹配和分配。因此,仓库储备的物资与储存在供应商处的协议库存物资使用优先级是不同的。协议库存的使用级别低于仓库中实物物资。于是,在库存物资使用时,存在逻辑关系:
如果 ∑k∈Kvtjk⩾0 且 ∑k∈Kutik⩾0,则Itj=0,∀i,j,t。 (8) 这个逻辑关系意味着,如果某个周期仓库和协议库存供应商同时为需求点提供物资需求,则该周期期末库存必定为0。如果期末库存不为0,应优先分配实物库存,因此也就无需动用协议库存的备货物资。
由于
∑k∈Kvtjk⩾ 0和∑k∈Kutik⩾ 0是自动满足的,因此式(8)可等价地表示为如果 ∑i∈I∑k∈Kutik⩾0,则 Itj=0,∀j,t。 (9) 考虑到
Itj 的非负性,可以将式(9)进一步改进为如果 ∑i∈l∑k∈KutiK⩾0,则∑j∈JItj=0,∀t。 (10) 为了将式(10)表示成优化模型的约束,这里引入
|T| 个辅助0-1变量ϑt ,构造|T| 组优化约束,其中M 为一充分大的常数。∑j∈JItj⩽Mϑt,∀t; (11) ∑i∈I∑k∈Kutik⩽M(1−ϑt),∀t。 (12) 1.3 鲁棒模型1
现实需求预测通常不精确,可将其视为不确定的。考虑不确定情况下的决策问题越来越受到各行各业的重视。首先采用Mulvey等[17]提出的鲁棒优化框架对上面的确定性模型进行改进。令
Ω={1,2,⋯,S} 为未来可能的情景集,每个情景出现的概率为ps ,满足∑s∈Ωps =1。假定与供应商的最大协议库存合同量zi 、供应商每个周期的协议库存的备货量xti 、仓库的自储备货量xtj 为设计变量,它们在需求实现之前进行决策,对所有的情景保持一致。由于需求因情景而异,因此假定供应商的期末库存量Iti 、仓库的期末库存量Itj 、仓库间的库存调拨周转量ftjj′ 、供应商在每个周期协议库存向每个需求点的分配比例utik ,以及仓库在每个周期向每个需求点的分配比例vtjk 是设计变量。它们在每个情景需求实现后进行决策,随情景的变化而变化。因此需要增加一个特别的情景s ,即Itsi、Itsj、ftsjj′ 、utik 和vtsjk 。为了更好地描述刻画模型的情景适应性,还需要引入一个特别的符号etsk ,表示供应商和仓库共同满足需求的偏差。用dtsk 表示随情景变化的需求,假定除了需求以外的其他所有参数在每个情景中均保持不变。用ϕs 表示情景给定时的最小总成本。此外,再引入一个额外的参数ω 表示对需求未满足偏差的惩罚成本。于是得到鲁棒模型RM1(RobustModel1) 。RM1 ZR_1=min∑s∈Ωps(φs+ω∑t∈T∑k∈Ketsk)。 s.t. φs=min{∑i∈Iαizi+∑t∈T∑i∈I(atixti+∑k∈Kotikutsik)+∑t∈T∑j∈J(atjxtj+htjItsj+∑j′∈Jctjj′ftsjj′+∑k∈Kotjkvtsjk)}; (13) It−1,si+xti−∑k∈Kutsik=Itsi,∀i,t,s; (14) 约束(2) ~ (3);
It−1,sj+xtj+∑j′∈Jft−1,sj′j−∑k∈Kvtsjk−∑j′∈Jftsjj′=Itsj,∀j,t,s; (15) Itsj−βj⩽0,∀j,t,s; (16) ∑i∈Iutsik+∑j∈Jvtsjk+etsk=dtsk,∀k,t,s; (17) ∑j∈JItsj⩽Mϑst,∀t,s; (18) ∑i∈I∑k∈Kutsik⩽M(1−ϑst),∀t,s; (19) xti,xtj,zi,utsik,ftsjj′,vtsjk,Itsi,Itsj,etsk⩾0,ϑst∈{0,1},∀i,j,j′,k,t,s。 (20) 考虑需求随情景变化,许多作者利用随机优化的方法对此类问题进行建模。对于战略性决策,采用“Here and Now”的决策方式;对于战术和运营类决策,采用“Wait and See”的补偿决策的方式,即一旦战略决策确定后,需求变成现实,随着时间的推移,实现战术和运营的决策。然而针对本文的现实物资供应模式,补偿决策显然不是最佳的。结合随机需求情景实现的鲁棒模型可以更好地面对企业未来的需求不确定,保持决策模式的稳定。
1.4 鲁棒模型2
除了上面Mulvey形式的鲁棒模型外,还有几种类型的鲁棒模型,如Soyster的鲁棒形式、Ben-Tal和Nemirovski的鲁棒形式,这些形式的模型保守程度存在着差异。本文采用Bertsimas等[18]的预算限制约束的鲁棒形式,以便更好地控制需求背离均值的程度。假定需求
dtk 在区间中取值,即dtk∈[¯dtk−^dtk,¯dtk+^dtk]。 其中,
¯dtk 为dtk 的均值,^dtk 为dtk 的方差。定义需求dtk 的标量偏差 (scaled deviation)δtk 为δtk=(dtk−¯dtk)/^dtk。 于是有
|δtk|⩽1 。在时期t的所有节点k的需求关于均值(名义值)的累积背离由预算参数γt 限制,即∑k∈Kδtk⩽γt 。在时期t的预算不确定集为Ut={δt=(δt1,δt2,⋯,δt|K|):|δtk|⩽1∀k,∑k∈Kδtk⩽γt}; t=1,⋯,|T|。 (21) 同样地,定义整个规划期内的预算不确定集为
U={(U1,U2,⋯,U|T|):∑t∈Tγt⩽γ}。 (22) 观察确定性模型,只有约束(6)包含需求
dtk 。由于约束(6)是不等式约束,因此约束(6)对于上述盒式不确定集中的所有参数均成立,意味着如下约束必须得到满足:∑i∈Iutik+∑j∈Jvtjk⩾maxδt∈Utdtk,∀k,t。 (23) 即需要首先求解如下线性规划问题。
maxδt^dtkδtk。 s.t. δtk⩽1,k=1,⋯,|K|(ρtk); ∑k∈Kδtk⩽γt(πt); δtk⩾0,k=1,⋯,|K|。 这里
ρtk 和πt 为相应约束的对偶乘子。其对偶形式优化模型如下。minπ,ργtπt+∑k∈Kρtk。 s.t. πt+ρtk⩾^dtk,k=1,⋯,|K|; πt,ρtk⩾0,k=1,⋯,|K|。 当需求采用盒式不确定集(21)的形式时,可以得到鲁棒模型的等价形式
RM2(RobustModel2) 。RM2 ZR_2=min{∑i∈Iαizi+∑t∈T∑i∈I(atixti+∑k∈Kotikutik)+∑t∈T∑j∈J(atjxtj+htjItj+∑j′∈Jctjj′ftjj′+∑k∈Kotjkvtjk)}。 s.t. 约束(1) ~ (5);约束(11) ~ (12);
∑i∈Iutik+∑j∈Jvtjk⩾¯dtk+γtπt+∑k∈Kρtk,∀k,t; (24) πt+ρtk⩾^dtk,k=1,⋯,|K|,∀t; (25) xti,xtj,zi,utik,ftjj′,vtjk,Iti,Itj,πt,ρtk⩾0,ϑt∈{0,1}∀i,j,j′,k,t。 (26) 类似地,当在整个规划期内限制需求的不确定性,即不确定性集用式(22)来表示时,也可以写出相应的鲁棒优化模型的等价形式。限于篇幅,这里省略具体形式。
2. 求解算法
上文提出了解决企业仓库自储备货、供应商协作备货、货物在仓库间周转调拨以及货物与需求的匹配和配送的综合集成优化的模型。其中模型
DM 和RM2 都是确定性模型。模型RM1 是一个两阶段随机优化模型。模型RM1 的目标可以进一步重新组合成如下形式。ZR_1=min⟨∑i∈Iαizi+∑t∈T∑i∈Iatixti+∑t∈T∑j∈Jatjxtj+∑s∈Ωps{∑t∈T∑i∈I∑k∈Kotikutsik+∑t∈T∑j∈J(htjItsj+∑j′∈Jctjj′ftsjj′+∑k∈Kotjkvtsjk)+ω∑t∈T∑k∈Ketsk}⟩。 其中,第1部分为与设计变量相关的3个成本项之和,第2部分为与情景相关的控制变量和需求偏差变量相关的成本项之和。利用Bender分解方法[19]对此模型求解,将仅包含设计变量的目标函数和约束纳入主问题,将控制变量、偏差变量和辅助变量作为子问题的决策变量,将包含控制变量和需求偏差变量的目标项组合成子问题的目标函数,将包含控制变量、需求偏差变量和辅助变量的约束作为子问题的约束函数。采用单割模式的Bender分解算法求解模型
RM1 ,具体求解步骤如算法1所示。算法1:采用单割模式的Bender分解算法 1:设置计数器 τ=0 。2:设 θ 为二阶段补偿目标函数值的期望。如果τ=0 ,忽视θ ,否则,将θ 加入到主问题的目标函数之中,于是主问题的目标函数变成min 。3:求解主问题,设 \left ({{\textit{z}}}_{i}^{*},{x}_{i}^{t*},{x}_{j}^{t*},{\theta }^{*}\right) 为主问题的最优解。4:将 {{\textit{z}}}_{i}^{*}、{x}_{i}^{t*}、{x}_{j}^{t*} 代入到各个子问题,针对情景s\in \varOmega ,求解子问题相应的松弛,计算该子问题二阶段补偿目标函数值的期望\overline {{\theta }_{{\mathrm{r}}}} ,以及最优的对偶变量值{\pi }_{s} 。5:如果 \theta^* \geqslant \overline{{\theta }_{{\mathrm{r}}}} ,则停止,报告最优主问题的解,否则,进入步骤6迭代。6:生成Bender割,并将其加入到主问题中。令 \tau =\tau +1 ,执行步骤3。为表达简便,假设子问题形式为
\qquad \mathrm{m}\mathrm{i}\mathrm{n}\;\left\langle{Q\mathit{U}}\right\rangle 。 \qquad \mathrm{s}.\mathrm{ }\mathrm{t}. \qquad {{\boldsymbol{WU}}}\geqslant h-TZ \text{;} \qquad {{\boldsymbol{U}}}\geqslant 0 。 其中,
\mathit{U} 为二阶段补偿决策向量,Q 为价值系数,\mathit{W} 为固定补偿矩阵,Z 为一阶段传递进来的变量值。该问题的对偶形式为\qquad \mathrm{m}\mathrm{a}\mathrm{x}\left\langle{\pi (h-TZ) }\right\rangle 。 \qquad \mathrm{s}.\mathrm{t}. \qquad {{\boldsymbol{W}}}\pi \leqslant Q \text{;} \qquad \pi \geqslant 0\mathrm{。} 由于每个情景
s\in S 都有一个子问题,因此采用式 (27) 的单割模式,并将其加入主问题迭代求解。这里没有采用多割模式主要是因变量较多,单割模式能够减少约束,增加收敛速度。\qquad \theta \geqslant \sum _{s\in {\varOmega }}{p}_{s}{\pi }_{s} ({h}_{s}-{T}_{s}Z) 。 (27) 事实上,无论是
\mathrm{D}\mathrm{M} 模型还是\mathrm{R}{\mathrm{M}}_{2} 模型,都是确定性模型,可以用确定性模型的Bender分解方法进行求解,这也可以看成随机模型的一个特例,只是情景数为1。因此,这里不再重述相应的算法。3. 计算实验
3.1 案例
随着电网建设规模逐年增大,物资保障需求也不断增加,供需矛盾日益突出,仓储和配送成为物流运作的关键环节。在“物力集约化、服务专业化”的总体要求下,国网江苏电力公司全面启动了以省中心库为枢纽、第三方物流为支撑的现代仓储配送体系建设工作。依托省、市两级物资调配平台,构建物资集中存储、集中配送、集中调配的集约化仓储配送网络,进一步优化了资源配置,提高了运营效率。目前仓储配送网络由原来的“省中心库—市周转库—县终端库”三级仓储网络调整为“省中心库—地(市)周转库—县终端库+专业仓”新型仓储网络体系。目前,江苏范围内各类仓库合计达75个之多,效率和效益的提升显得格外重要。
协议库存是约定协议期内暂存相应供应商处的库存,适用于标准化高、通用性强、使用频繁的物资,它在保障供应、规范采购、降低成本与提高效率等方面有效创新了传统物资采购模式。近年来,国网江苏电力协议库存实施范围稳步扩大,采购品类和协议供应商逐年增多。协议库存采用集中批量采购,执行时存在着多维度、多层级约束条件,因此,尽管本着公平与效率相统一的目标,但预测精度参差不齐,许多类别执行率差,甚至出现不到10%的现象,严重浪费了资源,影响着运营效率。如国网江苏电力公司的一项最新统计表明,2022年7月 ~ 2023年6月,配网协议执行263个物资小类,预测执行偏差超过50%的物资小类有192个;项目单位总体执行率为85.93%,其中,地市公司总体执行率为77.14%,共5家公司执行偏差在20%以内。
鉴于此,本文利用集成建模思想,在多周期情形下,提出进行仓库自储和备货、协议库存安排与备货,以及库存统一分配的模型,旨在实现物资资源的集中规划和管理,实现系统效率的提升。
3.2 参数设置和数据准备
考虑到江苏境内有75个仓库,为了减少计算量,在每个地级市选择两个仓库,其中一个为周转库,另一个为终端库。另外保留省中心库,因此参与模型计算的仓库合计有
|J| =27个。选择绝缘子作为物资来考虑其需求与供应问题,因为它可以用在各种不同的输电线路上,且易受环境的影响导致性能下降,更新频率高,需求不确定性大。如,2022年7月 ~ 2023年6月绝缘子的配网协议库存被用在非业扩需求和业扩需求两种场合,非业扩需求协议库存的执行率为69.91%,而业扩需求协议库存的执行率为128.71%。两类需求总金额为1.58亿元,总协议库存执行率为79.18%。关于绝缘子的协议库存供应商目前系统中有4家,分别居于扬州、镇江、无锡和苏州,因此参与模型计算的备选协议库存供应商数为| I |=4。本文以年为单位来进行规划设计,将整个规划期划分为12个周期,即
|T| =12。假定协议库存供应商在年初确定。在年初还需决定所有设计变量的值。在每个周期,需求发生后,根据需求确定由各个仓库和供应商向每个需求点分配与配送的绝缘子数量,以及各仓库间的周转量。以区县为加总单元,从信息系统中统计出每个单元2018年 ~ 2023年6年共72个月每个周期(月)的绝缘子需求量,用这组数据来刻画不确定需求,即每个单元在每个周期(月)的需求总共有6个数据值和相应的统计值,如最大值、最小值和均值。假定这6个数据值代表的是6个不同情景下的需求,也即假设2018年 ~ 2023年的每一年作为一个情景,于是情景数|S| =6。将每个地市的区县进行编码,随机选择4个区县作为各个地市的需求点,于是需求点总数|K| =13\times 4=52。用供应商参与招投标时每次需要付出的平均差旅费作为与供应商合作的固定成本
{\alpha }_{i} ,用供应商备货的准备成本和合同单价之和作为供应商备货的单位可变成本{a}_{i}^{t} ,用备货时的平均管理成本和单位采购价格之和作为仓库备货的单位可变成本{a}_{j}^{t} ,用两点间距离乘上单位运价来计算运输成本{\mathrm{s}}_{ik}^{t} 、{w}_{jk}^{t} 和单位转移成本{c}_{j{j\,}{\mathrm{{'}}}}^{t} 。用仓库发生的直接成本和间接成本之和除以库存总量作为单位库存持有成本{h}_{j}^{t} 。主要参数的设置值如表1、表2所示。表 1 仓库主要参数设置值Table 1. Main parameter settings for warehouses仓库编号 {\mathit{a}}_{\mathit{j}}^{\mathit{t}} /元 {\mathit{h}}_{\mathit{j}}^{\mathit{t}} /元 {\mathit{I}}_{\mathit{j}}^{0} /个 {\mathit{k}}_{\mathit{j}} /个 #1 25.0 1.20 190 200 #2 24.8 1.20 120 150 #3 24.8 1.19 115 150 #4 25.0 1.20 100 150 #5 24.9 1.19 120 150 #6 24.8 1.18 118 150 #7 24.9 1.19 113 150 #8 24.7 1.17 90 150 #9 24.7 1.18 106 150 #10 25.0 1.20 80 150 #11 24.8 1.19 97 150 #12 24.8 1.18 117 150 #13 25.0 1.19 122 150 #14 24.9 1.19 75 150 #15 24.5 1.15 53 80 #16 24.5 1.15 49 80 #17 24.5 1.15 26 80 #18 24.4 1.15 59 80 #19 24.5 1.15 61 80 #20 24.4 1.15 66 80 #21 24.4 1.15 56 80 #22 24.6 1.16 42 80 #23 24.6 1.16 47 80 #24 24.5 1.16 35 80 #25 24.5 1.15 52 80 #26 24.5 1.15 57 80 #27 24.4 1.15 48 80 表 2 协议库存供应商主要参数设置值Table 2. Main parameter settings for suppliers with capacity reservation contracts供应商编号 {\mathit{\alpha }}_{\mathit{i}} /元 {\mathit{a}}_{\mathit{i}}^{\mathit{t}} /元 {\mathit{I}}_{\mathit{j}}^{0} /个 {\mathit{m}}_{\mathit{i}} /个 #1 2000 21 100 1 500 #2 1800 21 100 1 500 #3 1600 21 100 1 500 #4 2000 21 100 1 500 需求未满足偏差的惩罚成本参数
\omega 和预算不确定参数{\gamma }_{t},t=1,2,\cdots,\left|T\right| 的设置值对后面的计算实验的结果影响也很重要。由Mulvey等[17]的工作可知,参数\omega 平衡\mathrm{R}{\mathrm{M}}_{1} 模型的解鲁棒性和模型鲁棒性,越大则表示解鲁棒性越弱,模型鲁棒性越强。将其设置在解鲁棒性和模型鲁棒性的均衡点处。由文献[18]可知,预算限制参数{\gamma }_{t} 反映了约束的背离程度,也即需求偏离均值的程度,{\gamma }_{t} 越大表示可容许的需求偏差也大。将所有的预算限制参数{\gamma }_{t} 设置为相同的值,都等于1,即在每个周期中最多容许某个特定需求点的需求达到最大的偏差值。3.3 实验设计与实验结果
实验设计包括如下内容:1)针对上述案例的数据和参数,寻找前面提出的三类模型的最优解;2)研究本文采用的Bender分解算法的计算效率,并将其与Gurobi求解器语言直接得到的结果进行对比;3)不同库存分配与配送模式下,需求未满足偏差的惩罚成本参数
\omega 对总成本的影响与对比;4)不同库存分配与配送模式下,预算不确定参数\gamma 对总成本的影响与对比。1)最优解与算法效率。
基于前面的模型、求解算法和参数及数据,在IBM (Lenovo) Intel (R) Core (TM) i5-7200U CPU、8 GB RAM、Windows10的笔记本电脑上,在Python 3.10、Gurobi10.0环境下分别用Gurobi求解器语言和Bender分解算法1编程对3类模型(
\mathrm{D}\mathrm{M}\mathrm{、} \mathrm{R}{\mathrm{M}}_{1}、 \mathrm{R}{\mathrm{M}}_{2} )进行求解。其中,在确定性\mathrm{D}\mathrm{M} 模型中,需求采用的是各个情景的均值;在鲁棒\mathrm{R}{\mathrm{M}}_{1}\mathrm{模}\mathrm{型} 中,采用6个情景(6年)72个周期的实际需求数据;在鲁棒\mathrm{R}{\mathrm{M}}_{2}\mathrm{模}\mathrm{型} 中,采用6个情景每个周期的最大值和最小值作为鲁棒区间支集的上下界。计算实验结果如表3所示。比较而言,确定性
\mathrm{D}\mathrm{M} 模型的目标值最好,成本最低,用Gurobi求解器语言编程直接计算为3960587 元,用Bender分解算法计算为3851169 元;鲁棒\mathrm{R}{\mathrm{M}}_{2} 模型的目标值最差,成本最高,用Gurobi求解器语言编程直接计算为4869152 元,用Bender分解算法计算为4660252 元。这主要是因为鲁棒\mathrm{R}{\mathrm{M}}_{2} 模型容许不确定性的存在,所以需要承担更多的成本,而确定性\mathrm{D}\mathrm{M} 模型仅能满足特定的需求(均值点),模型缺乏弹性。同样考虑到各种情景鲁棒性的\mathrm{R}{\mathrm{M}}_{1} 模型由于均衡了解鲁棒性和模型鲁棒性,因此其目标值居中。它不同于\mathrm{R}{\mathrm{M}}_{2} 模型,需要考虑不确定需求的100%满足率。它关注的重点是如何平衡成本和需求的满足率。总体上,采用Bender分解算法获得的最优值要好于采用Gurobi求解器语言编程获得的最优值。表 3 模型和算法的最优值与计算时间Table 3. Optimal solutions and computational time of models and algorithms模型 Gurobi Bender分解 最优值/元 计算时间/s 最优值/元 计算时间/s DM 3960587 89 3851169 86 RM1 4472139 517 4323651 403 RM2 4869152 91 4660252 87 关于两种不同的求解方法的效率可从表3中直接得到。确定性
\mathrm{D}\mathrm{M} 模型和鲁棒\mathrm{R}{\mathrm{M}}_{2} 模型的求解所用时间差不多;而鲁棒\mathrm{R}{\mathrm{M}}_{1} 模型由于包含了6类情景,因此计算时间相对较多;但整体看来,在上述案例规模中,采用Bender分解算法进行求解其计算时间均要好于采用Gurobi求解器语言编程计算的时间。2)参数对总成本的影响。
为了进一步分析需求未满足偏差的惩罚成本参数
\omega 和预算不确定参数{\gamma }_{t},t=\mathrm{1,2},\cdots, \left|T\right| 对系统总成本的影响,本文结合现实中的库存优先权的考量来进行探讨。对于库存的分配和配送,企业通常优先考虑自己仓库中存储的实物物资,其次才会考虑供应商的协议库存。本文分别在考虑实物库存优先分配和取消实物库存优先分配两种情形下,研究总成本对需求未满足偏差的惩罚成本参数\omega 和预算不确定参数\gamma 的敏感性分析,结果如图1和图2所示。由图1可见,无论是否考虑实物库存优先分配,总成本总会随着需求未满足偏差的惩罚成本参数
\omega 呈现出一致的变化趋势,随着系统越来越关注于未满足需求的惩罚,即惩罚越来越大,总成本会出现先下降后上升的变化,大约在45 ~ 50之间达到最小值。这是因为当\omega 较小时,系统可以通过忽略一些需求来降低成本;而当\omega 较大时,由于惩罚成本过高,即使有一些需求未满足,但仍会导致总成本的上升。图1中一个不变的规律是,不论需求未满足偏差的惩罚成本参数\omega 如何变化,考虑实物库存优先分配总会带来总成本的降低,这是因为系统目标函数中考虑了实物库存的库存持有成本,且系统中的协议库存供应商分布不均匀等因素会导致总成本存在着明显的差异。由图2可见,无论是否考虑实物库存优先分配,总成本总会随着预算不确定参数
\gamma 呈现出一致的变化趋势,随着系统越来越关注于预算不确定参数\gamma ,即系统的不确定性越大,总成本也会逐步增大,呈上升趋势。这是因为不确定性增大时,系统需求变动范围增大,为了满足所有需求的鲁棒策略带来的总成本自然就会增大。图2中一个不变的规律是,不论预算不确定参数\gamma 如何变化,考虑实物库存优先分配总会带来总成本的降低,这是因为系统目标函数中考虑了实物库存的库存持有成本,且系统中的协议库存供应商分布不均匀等因素会导致总成本存在着明显的差异。4. 结论
物资供应是电网建设和运营的重要保障,科学有效的保供方案是企业降本增效、减少运营风险的重要保证。本文针对国网现有的物资供应模式和数据集,采用集成管理的思想,以总成本最小为目标,构建确定性物资供应模型;在此基础上,基于情景方法和区间支集方法描述不确定需求建立鲁棒优化模型;基于Bender分解方法设计模型的求解算法。围绕案例收集数据并设计实验,分析模型和算法的性能;针对实物库存是否优先于协议库存的物资供应模式,探讨需求未满足偏差的惩罚成本参数和预算不确定参数的变化对总成本的影响。
研究发现:1)相较于直接用Gurobi求解器编程求解,单割模式的Bender分解算法对于大规模优化问题效率更高;2)基于期望需求的确定性模型
\mathrm{D}\mathrm{M} 虽然总成本最低,但抵御不确定需求风险方面不如两类鲁棒模型;3)基于随机情景的鲁棒模型\mathrm{R}{\mathrm{M}}_{1} 总成本是需求未满足偏差的惩罚成本参数的先减后增的凸函数,可以平衡总成本和需求未满足偏差的惩罚成本;4)考虑预算不确定模型\mathrm{R}{\mathrm{M}}_{2} 的总成本是预算不确定参数的单增函数,可以将需求的不确定性控制在特定范围内;5)考虑实物库存优先于协议库存进行分配与配送的物资供应模式在总成本控制方面更好;6)模型\mathrm{R}{\mathrm{M}}_{2} 具有很好的需求满足能力,但成本更大;7)模型\mathrm{R}{\mathrm{M}}_{1} 在成本上优于模型\mathrm{R}{\mathrm{M}}_{2} ,但可能部分需求无法满足。本研究可以得到如下管理启示。1)采用集成管理的方法,对实物库存和协议库存进行统一建模与管理,可以避免分割库存管理造成的各种弊端,更好地实现系统的降本增效。2)不同的模型立足于不同的情境假设,较之于确定性模型,鲁棒模型可以降低需求在遇到不确定性时的缺货成本,提高物资供应系统的敏捷性和整体响应速度。3)考虑实物库存优先于协议库存进行分配与配送的物资供应模式在总成本控制方面更具优势,企业可以结合鲁棒模型和现实管理控制需要,针对不同的物资,将未满足的需求控制在合适的范围内,从而更好地服务于工程建设需要。
本研究可为企业在不确定需求的情况下考虑协议库存的物资供应模式和模型选择提供启示和参考。今后结合决策者的风险偏好和目标导向,考虑资金流的影响,考虑多周期多物资的集成库存协同管理都是值得进一步研究的问题。
-
表 1 仓库主要参数设置值
Table 1 Main parameter settings for warehouses
仓库编号 {\mathit{a}}_{\mathit{j}}^{\mathit{t}} /元 {\mathit{h}}_{\mathit{j}}^{\mathit{t}} /元 {\mathit{I}}_{\mathit{j}}^{0} /个 {\mathit{k}}_{\mathit{j}} /个 #1 25.0 1.20 190 200 #2 24.8 1.20 120 150 #3 24.8 1.19 115 150 #4 25.0 1.20 100 150 #5 24.9 1.19 120 150 #6 24.8 1.18 118 150 #7 24.9 1.19 113 150 #8 24.7 1.17 90 150 #9 24.7 1.18 106 150 #10 25.0 1.20 80 150 #11 24.8 1.19 97 150 #12 24.8 1.18 117 150 #13 25.0 1.19 122 150 #14 24.9 1.19 75 150 #15 24.5 1.15 53 80 #16 24.5 1.15 49 80 #17 24.5 1.15 26 80 #18 24.4 1.15 59 80 #19 24.5 1.15 61 80 #20 24.4 1.15 66 80 #21 24.4 1.15 56 80 #22 24.6 1.16 42 80 #23 24.6 1.16 47 80 #24 24.5 1.16 35 80 #25 24.5 1.15 52 80 #26 24.5 1.15 57 80 #27 24.4 1.15 48 80 表 2 协议库存供应商主要参数设置值
Table 2 Main parameter settings for suppliers with capacity reservation contracts
供应商编号 {\mathit{\alpha }}_{\mathit{i}} /元 {\mathit{a}}_{\mathit{i}}^{\mathit{t}} /元 {\mathit{I}}_{\mathit{j}}^{0} /个 {\mathit{m}}_{\mathit{i}} /个 #1 2000 21 100 1 500 #2 1800 21 100 1 500 #3 1600 21 100 1 500 #4 2000 21 100 1 500 表 3 模型和算法的最优值与计算时间
Table 3 Optimal solutions and computational time of models and algorithms
模型 Gurobi Bender分解 最优值/元 计算时间/s 最优值/元 计算时间/s DM 3960587 89 3851169 86 RM1 4472139 517 4323651 403 RM2 4869152 91 4660252 87 -
[1] CORREIA I, MELO T. Integrated facility location and capacity planning under uncertainty[J]. Computational and Applied Mathematics, 2021, 40(5): 1-36.
[2] XU J, Sen S. Ensemble variance reduction methods for stochastic mixed-integer programming and their application to the stochastic facility location problem[J]. INFORMS Journal on Computing, 2024, 36(2): 587-599. DOI: 10.1287/ijoc.2021.0324
[3] BASCIFTCI B, AHMED S, SHEN S Q. Distributionally robust facility location under decision-dependent stochastic demand[J]. European Journal of Operational Research, 2021, 292(2): 548-561. DOI: 10.1016/j.ejor.2020.11.002
[4] CHEUNG R K M, POWELL W B. Models and algorithms for distribution problems with uncertain demands[J]. Transportation Science, 1996, 30(1): 43-59. DOI: 10.1287/trsc.30.1.43
[5] ARDESTANI-JAAFARI A, DELAGE E. The value of flexibility in robust location-transportation problems[J]. Transportation Science, 2018, 52(1): 189-209. DOI: 10.1287/trsc.2016.0728
[6] TORABI S A, BAGHERSAD M, MANSOURI S A. Resilient supplier selection and order allocation under operational and disruption risks[J]. Transportation Research Part E, 2015, 79: 22-48. DOI: 10.1016/j.tre.2015.03.005
[7] AHMAD M T, FIROUZ M, MONDAL S. Robust supplier-selection and order-allocation in two-echelon supply networks: a parametric tolerance design approach[J]. Computers & Industrial Engineering, 2022, 171: 108394.
[8] FENG Y, CHEN Y, LIU Y. Optimising two-stage robust supplier selection and order allocation problem under risk-averse criterion[J]. International Journal of Production Research, 2023, 61(19): 6356-6380. DOI: 10.1080/00207543.2022.2127963
[9] SCHIFFELS S, VOIGT G, Capacity reservation and wholesale price contracts under forecast sharing: a behavioral assessment[J]. Production and Operations Management, 2021, 30(10): 3579–3598.
[10] PARK S, KIM J S. A mathematical model for a capacity reservation contract[J]. Applied Mathematical Modelling, 2014, 38(5): 1866-1880.
[11] ALVAREZ A, CORDEAU J-F, JANS R, et al. Inventory routing under stochastic supply and demand[J]. Omega, 2021, 102: 102304. DOI: 10.1016/j.omega.2020.102304
[12] JALAL A M, TOSO E A, MORABITO R. Integrated approaches for logistics network planning: a systematic literature review[J]. International Journal of Production Research, 2021, 60(18): 1963875.
[13] 姚冠新, 朱晨俊, 戴盼倩. 混合轴辐式城乡一体化物流网络构建研究[J]. 工业工程, 2019, 22(6): 1-7. YAO Guanxin, ZHU Chenjun, DAI Panqian. A research on the construction of hybrid hub-and-spoke logistics network of urban-rural integration[J]. Industrial Engineering Journal, 2019, 22(6): 1-7.
[14] 李珍萍, 仪明超. 随机需求下基于“自营+外包”模式的配送中心选址−配送问题研究[J]. 中国管理科学, 2022, 30(8): 143-154. LI Zhenping, YI Mingchao. Research on the location-distribution problem of distribution centers based on “self operating-outsourcing” mode under uncertain demands[J]. Chinese Journal of Management Science, 2022, 30(8): 143-154.
[15] MOHAMMED A, SETCHI R, FILIP M, et al. An integrated methodology for a sustainable two-stage supplier selection and order allocation problem[J]. Journal of Cleaner Production, 2018, 192: 99-114. DOI: 10.1016/j.jclepro.2018.04.131
[16] BADRI H, BASHIRI M , HEJAZI T H. Integrated strategic and tactical planning in a supply chain network design with a heuristic solution method[J]. Computers & Operations Research, 2013, 40: 1143-1154.
[17] MULVEY J M, VANDERBEI R J, ZENIOS S A. Robust optimization of large-scale systems[J]. Operations Research, 1995, 43: 264-281. DOI: 10.1287/opre.43.2.264
[18] BERTSIMAS D, SIM M. The price of robustness[J]. Operations Research, 2004, 52(1): 35-53. DOI: 10.1287/opre.1030.0065
[19] Crainic T G, Hewitt M, et al. Partial Benders decomposition: general methodology and application to stochastic network design[J]. Transportation Science, 2021, 52(2): 414-435.