整合供应商选择的多层级选址-库存模型

税文兵，何保红，何 民

昆明理工大学 交通工程学院，昆明 650500

整合供应商选择的多层级选址-库存模型

税文兵，何保红，何 民

昆明理工大学 交通工程学院，昆明 650500

1 引言

传统的“先选址，再库存”的顺序决策方法，从总成本的角度来看，并不是最优的[1]。近年来，将选址分配决策问题和库存控制决策问题进行整合，实现选址成本、运输成本和库存成本的平衡，从而进一步降低总成本，成为了物流系统优化的发展方向之一。基于选址分配决策和库存控制决策的相互影响关系，从系统整体最优的角度，建立同时考虑选址成本、运输成本和库存成本的选址-库存模型，对设施的位置、数量、服务范围和库存控制参数同时进行优化决策，在文献中被称为选址-库存问题（Location-Inventory Problems，LIP）。

早在1958年，Baumol就提出应该在选址模型的目标函数中包含库存成本[2]。文献[1]建立了确定环境下基于经济订货批量（EOQ）的连续选址-库存模型，并采用微分方法求解，但是该模型没有考虑设施的建立成本。文献[3]研究了需求和提前期随机变化下的选址-库存问题，证明了当配送中心采用连续(S-1，S)补货策略时，系统的总安全库存与总配送中心数存在线性关系，并利用这种关系建立了线性的选址-库存模型。然而，由于(S-1，S)库存策略一般用于需求较少、提前期短的情况。对于需求量大的重要产品，往往采用(Q，R)库存策略。因此，(Q，R)库存策略下的选址-库存问题成为了重要的研究方向。

文献[4]针对由一个供应商、多个分销中心和多个零售商的供应链，基于Axsater[5]的库存成本计算方法，建立了第一个(Q，R)库存策略下的选址-库存模型。该模型较好地体现了选址分配决策和库存控制决策之间的相互影响关系，从而成为了这一研究方向的基础模型，得到了很多学者的进一步研究。如文献[6]建立了基于场景规划的模型，文献[7]建立了考虑设施能力限制的模型，文献[8]建立了考虑工厂选址的三层级选址模型等。这些研究从不同的角度完善了Shen的模型，然而，它们都只考虑了一个库存点，没有考虑多级库存的情况。

除(Q，R)库存策略下的LIP模型，其他库存策略下的模型也得到了研究。文献[9]针对连续检查(Q，R)策略下的选址-库存模型，会使每一个配送中心的订货间隔期都不相同，从而导致供应商在供货时不能够协调供货，增加车队的调度使用成本的问题，建立了配送中心采用定期检查(T，S)策略下的选址-库存模型。文献[10]针对单供应商、配送中心和顾客构成的供应链，建立了配送中心采用(s，S)策略、顾客采用(R，S，Q)策略的多级选址-库存模型，然而，模型没有考虑不同库存点之间的相互影响关系。文献[11]基于Roundy[12]的多级库存控制方法，建立了分销中心和顾客都有库存的选址-库存模型，但仍然仅限于一个供应商的三层分销网络。文献[13]基于EOQ模型假设和单点库存控制策略，建立了允许供应商可以直接向顾客供货的多级选址-库存模型，然而，该模型没有明确考虑空间距离对配送中心选址的影响。

上述研究有三个特点：（1）从供应链阶段来看，大部分都只针对由工厂、配送中心和顾客构成的三级分销网络，没有考虑零部件供应商的选择；（2）从选址对象来看，都只对配送中心进行选址分配决策，没有对工厂进行选址决策；（3）从所建立的模型特征来看，都是将选址分配模型和库存控制模型融合为一个模型。前两个特点决定了所建立的模型不能用于由供应商、工厂、配送中心和顾客组成的完整供应链网络设计。最后一个特点使得所建立的模型呈现出高度的非线性，采用传统的精确算法难以在较短时间内求解较大规模的问题。

在一个完整的供应链中，供应商的选择、工厂和配送中心的选址、供应商与工厂以及工厂与配送中心之间的运输量以及工厂和配送中心的库存量都存在相互影响的关系。在进行这类供应链网络设计和优化时，如果忽视了其中某个影响因素，所得到的设计方案从系统的角度看并不是最优的。本文针对由供应商、工厂、配送中心和顾客构成的四层级供应链网络，构建同时对供应商的选择、工厂和配送中心的选址和库存控制参数进行决策的LIP模型。其中，利用梯级库存概念，处理供应链中上下游库存点之间的相互影响关系，建立工厂和配送中心的库存成本计算模型。考虑到所建模型的复杂性，设计了基于部分编码的粒子群优化算法求解，并通过多个算例验证模型的有效性和算法的可行性。

2 模型建立

本文所研究的供应链网络由供应商、工厂、配送中心和顾客组成，供应商向工厂提供原材料，工厂根据配送中心的订单进行生产，产品生产出来之后通过配送中心运往顾客。配送中心通过成品库存满足若干顾客的确定需求，工厂分别通过原材料库存和成品库存满足生产和配送中心的需要。在已知顾客的需求、单位运输成本、候选的供应商、工厂和配送中心位置等参数下，对供应商的选择、工厂和配送中心的选址、节点之间的运输量，以及设施的库存量进行决策。

2.1 模型参数和变量

基本参数：I为顾客的集合，某一个顾客用i表示；J为配送中心的集合，某一个配送中心用 j表示；P为工厂的集合，某一个工厂用 p表示；S为供应商的集合，某一个配送中心用s表示。di为顾客的需求（单位/年）；DDj为配送中心的需求（单位/年）；DPp为工厂成品仓库的需求（单位/年）；DMp为工厂原材料仓库的需求（单位/年）；FDj为配送中心的打开成本（元/年）；FPp为工厂的打开成本（元/年）；FSs为供应商的选择成本（元/年）；ODj为配送中心订货成本（元/次）；OPp为工厂成品订货成本（元/次）；OMp为工厂原材料订货成本（元/次）；HDj为配送中心单位产品每年的库存持有成本（元/单位）；HPp为工厂单位产品每年的库存持有成本（元/单位）；HMp为工厂单位原材料每年的库存持有成本（元/单位）；EDj为配送中心单位产品每年的梯级库存持有成本（元/单位）；EPp为工厂单位产品每年的梯级库存持有成本（元/单位）；EMp为工厂单位原材每年的料梯级库存持有成本（元/单位）；MPp为工厂单位产品生产成本（元/单位）；MHp为工厂单位原材料处理成本（元/单位）；PHp为工厂单位成品处理成本（元/单位）；DHj为配送中心单位成品处理成本（元/单位）；PSs为供应商的单位原材料售价（元/单位）；TDji为从配送中心到顾客的单位运输成本（元/单位）；TPpj为从工厂到配送中心的单位运输成本（元/单位）；TSsp为从供应商到工厂的单位运输成本（元/单位）；BOM为成品和原材料之间的数量关系；B为大的正数。

决策变量：XDj为如果配送中心打开取1，否则取0；XPp为如果工厂打开取1，否则取0；XSs为如果供应商被选用取1，否则取0；YDji为如果配送中心和顾客之间建立服务关系取1，否则取0；YPpj为如果工厂和配送中心之间建立服务关系取1，否则取0；YSsp为如果供应商和工厂之间建立服务关系取1，否则取0；QPpj为工厂到配送中心的运输量（单位/年）；QSsp为供应商到工厂的运输量（单位/年）；OQDj为配送中心订货批量（单位/次）；OQMp为工厂原材料订货批量（单位/次）；OQPp为工厂成品订货批量（单位/次）。

2.2 模型数学描述

整合供应商选择的多层级LIP模型，以设施的打开成本、原材料和成品库存成本、原材料采购和运输成本、成品的生产和运输成本之和最小为目标，同时对供应商的选择、工厂和配送中心的选址、配送中心和顾客之间的分配关系、层级之间的运输量以及工厂和配送中心的订货批量进行决策，模型如下：

其中，式（1）是模型的目标函数，前三项分别是供应商的选择成本、工厂和配送中心的打开成本；第四项是原材料的采购和运输成本，第五项是产品的生产和从工厂到供应商的运输成本；第六项是从配送中心到顾客的运输成本；第七项是配送中心的库存持有成本；第八和第九项是工厂的库存持有成本。式（2）表示只有当配送中心打开后，才能为顾客提供服务；式（3）和（4）表示只有当供应商、工厂和配送中心都打开后，它们之间才能建立服务关系；式（5）表示一个配送中心就能完全满足一个顾客的需求；式（6）和（7）分别是进出配送中心和工厂的产品数量相等；式（8）和（9）表示供应商、工厂和配送中心之间运输量的取值限制；式（10）是配送中心的梯级库存持有成本；式（11）和（12）分别是工厂成品和原材料的梯级库存持有成本；式（13）和式（14）是厂和配送中心订货批量关系限制；式（15）～式（23）是决策变量的取值限制。

3 算法设计

所建立的四层级LIP模型属于混合整数非线性规划模型，同时也是典型的NP困难问题，传统的精确算法难以在有限时间内求解较大规模的问题，常用启发式算法获得在可接受时间花费下的可行解[14]。启发式算法总体上可以分为个体搜索算法和群体搜索算法。个体搜索算法从单个个体开始，逐步往最优解靠拢，如贪心算法、松弛算法等。群体搜索算法从解的集合开始，采用并行搜索机制，接近最优解，如遗传算法、粒子群优化算法（Particle Swarm Optimization，PSO）等。实践证明，采用并行机制的群体搜索算法在效率上优于个体搜索算法。相对于遗传算法，粒子群优化算法没有交叉和变异操作，只是通过内部速度进行更新，因此原理更简单、参数更少、实现更容易。因此，PSO被广泛应用于各个领域，是求解非线性连续优化、混合整数非线性优化、组合优化问题的有力工具[15]。所以，本文采用PSO算法求解所建立的模型。同时，为了对PSO算法的求解能力进行评价，将PSO算法的求解结果与基于分支定界算法的Lingo软件求解结果进行比较。

3.1 粒子群初始化

粒子群初始化包括粒子的编码和粒子群的生成。上述LIP模型的决策变量包含0-1整数变量和连续非负变量两大类，经过试验发现，由于模型过于复杂，无论是全部采用二进制编码，还是采用混合编码，都很难得到满足所有约束条件的可行解。因此，本文采用部分编码的策略，仅对其中的选址变量进行编码（二进制编码）。一旦选址变量确定后，运输量通过求解最小成本网络流问题得到。由于运输量的有无反映了节点之间的网络拓扑关系，因此不需要对其进行专门的编码。订货批量通过求解EOQ模型得到，进而得到总的运输成本和总的库存成本。

在上述编码规则下，每一个粒子的长度为候选供应商、工厂和配送中心数量之和，粒子群采用随机的方法生成。

3.2 适应度函数的确定

在选址变量确定后，可以得到总的选址成本LocaC。通过求解如下的最小成本网络流问题得到总的运输成本TraficC。

模型中，QDj是配送中心到顾客的运输量，其他变量含义同前。采用最小费用增广路径算法求解上述网络流问题[16]，从而得到层级之间的运输量和TraficC。在确定选址变量和运输量的结果后，通过EOQ模型计算最初订货批量，再结合约束条件进行调整，进而得到满足约束的订货批量和总的库存成本InvetC。

通过上述分布求解的方式，有效地消除了所有的约束。因此，适应度函数为：

3.3 速度和位置的更新

适应度函数确定后，计算各个粒子的适应度值，并对个体极值和群体极值更新。然后，对粒子速度和位置进行更新。在离散空间下，速度和位置的更新公式如下[17]：

其中，ω称作惯性权重，c1、c2为常数，称作学习因子（也叫加速系数），r1、r2是两个0到1之间的随机数。

4 算例仿真

粒子群算法程序用Matlab 7.10中的M语言编写，测试用的计算机处理器为Intel®CoreTMi5-2410 CPU，单核频率为2.30 GHz，2.0 GB的内存，操作系统为Windows 7家庭普通版。为了对PSO进行评估，同时用优化求解软件Lingo 9.0求解每一个算例。

4.1 算例数据

根据问题规模随机生成20个算例，每一个算例有不同的节点数量，总的节点数量从50变化到170个。例如，算例“5-10-15-20”表示该算例中候选的供应商有5个，工厂有10个，配送中心有15个，顾客有20个。

各算例的数据产生规则如下：供应商的固定选择成本，工厂和配送中心的打开成本和服从[5 000，15 000]之间的均匀分布；供应商到工厂的单位运输成本服从[5，15]之间的均匀分布，工厂到配送中心的单位运输成本服从[20，50]之间的均匀分布，配送中心到顾客的单位运输成本服从[100，200]之间的均匀分布，供应商的原材料采购成本服从[200，300]之间的均匀分布，工厂的单位生产成本服从[1 000，1 500]之间的均匀分布；工厂成品一次订货成本服从[1 500，2 000]之间的均匀分布，工厂原材料一次订货成本服从[2 000，2 500]之间的均匀分布，工厂成品的单位库存持有成本服从[150，200]之间的均匀分布，工厂单位原材料库存持有成本服从[50，100]之间的均匀分布，配送中心一次订货成本服从[3 000，4 000]之间的均匀分布，配送中心的单位库存持有成本服从[500，800]之间的均匀分布；顾客的需求服从[1 000，3 000]之间的均匀分布。对于所有的算例，BOM都取2。

另外，设定3 600 s的时间限制作为Lingo算法的终止条件，粒子群算法的终止条件为连续10次迭代，适应度函数没有明显的改进。

4.2 算法比较

上述20个算例分别用Lingo 9.0和PSO算法求解，结果如表1所示。第一列“测试算例”表明了每一个算例中候选供应商、工厂、配送中心和顾客的数量；第二列和第三列是Lingo 9.0求解后得到的结果，分别是目标函数最小值（“cost”单位是元）和运算所用时间（“T”单位是s）；第四列和第五列是PSO算法求解后的结果，同样包含目标函数最小值和运算所用时间。从表1可以看出：有55%的算例lingo9.0不能在3 600 s内得到求解结果，尤其是当总节点数超过110个以后，全部都不能得到最小成本，而PSO算法对于所有的算例在较短时间内都能得到最小成本。这表明PSO的求解能力优于优化软件。

表1 算例求解结果

从两种算法都能得到最小成本的算例来看（图1），Lingo 9.0所得到的解都要大于PSO。这说明基于分支定界算法的Lingo 9.0在有限的时间内只能获得局部最优解，而且这种局部最优解比PSO的解质量差。

图1 PSO和Lingo的求解结果比较

从两种算法的求解时间来看（图2），在节点数小于70个的时候，Lingo 9.0的获得最小成本的时间要少于PSO；当节点数超过70个时，情况刚好相反。而且，随着节点数的增加，Lingo 9.0的求解时间增加速度非常快，超过了PSO求解时间的增加速度。

图2 PSO和Lingo的求解时间比较

5 结论

供应链网络设计是供应链管理的战略决策问题，对供应链的绩效有重要的影响。合理设计供应链网络，要求建立选址和库存的集成决策模型。本文针对由供应商、工厂、配送中心和顾客构成的供应链，考虑工厂和配送中心库存决策的相互影响，运用梯级库存的概念，建立了整合供应商选择的多层级的LIP模型。针对模型的特点，设计了PSO算法；通过对20个算例的求解，可以看出本文所设计的PSO算法无论是在得到的最小总成本，还是运算速度上都明显优于数学规划求解软件Lingo，尤其是当总节点数较大时。算例也表明，本文所建立的模型是有效的，设计的算法是可行的，可以用于多层级的一体化供应链网络设计。在未来的研究中，可以考虑需求的不确定性和更为复杂的多级库存控制模型。

[1]Mccann P.The logistics cost location-production problem[J]. Journal of Regional Science，1993，33（4）：503-516.

[2]Baumol W J，Wolfe P.A warehouse-location problem[J].Operations Research，1958，6（2）：252-263.

[3]Nozick L K，Turnquist M A.Integrating inventory impacts into a fixed-charge model for locating distribution centers[J]. Transportation Research Part E，1998，34（3）：173-186.

[4]Shen Z J M.Efficient algorithms for various supply chain problems[D].Evanston，IL：Northwestern University，2000.

[5]Axsater S.Using the deterministic EOQ formula in stochastic inventory control[J].Management Science，1996，42（6）：830-834.

[6]Snyder L V，Daskin M S，Teo C P.The stochastic location model with risk pooling[J].European Journal of Operational Research，2007，3（179）：1221-1238.

[7]Miranda P A，Garrido R A.Incorporating inventory control decisions into a strategic distribution network design model with stochastic demand[J].Transportation Research Part E，2004，40：183-207.

[8]Park S，Lee T T，Sung C S.A three-level supply chain network design modelwith risk-pooling and lead times[J]. Transportation Research Part E，2010，46：563-581.

[9]Berman O，Krass D，Tajbakhsh M M.A coordinated locationinventory model[J].European Journal of Operational Research，2012，217：500-508.

[10]谭凌，高峻峻，王迎军.基于库存成本优化的配送中心选址问题研究[J].系统工程学报，2004，19（l）：59-66.

[11]Romeijn H E，Shu J，Teo C P.Designing two-echelon supply networks[J].European Journal of Operational Research，2007，178：449-462.

[12]Roundy R O.98%effective integer-ratio lot-sizing for one warehouse multi-retailer systems[J].ManagementScience，1985，31：1416-1430.

[13]Tancrez J S，Lange J C，Semal P.A location-inventory model for large three-level supply chains[J].Transportation Research Part E，2012，48：485-502.

[14]邢文训，谢金星.现代优化计算方法[M].北京：清华大学出版社，2003：13-23.

[15]杨维，李歧强.粒子群优化算法综述[J].中国工程科学，2004，6（5）：87-94.

[16]Ahuja R，Magnanti T，Orlin J.Network flows：theory，algorithms，and applications[M].New York：Prentice Hall，1993.

[17]Kennedy J，Eberhart R C.Discrete binary version of the particle swarm algorithms[C]//Proceedings of the IEEE InternationalConferenceon Systems，Man，Cybernetics. Orlando：IEEE Press，1997：4104-4108.

SHUI Wenbing,HE Baohong,HE Min

Faculty of Transportation Engineering,Kunming University of Science&Technology,Kunming 650500,China

To deal with the integrated decisions of location and inventory for the supply chain network design with multi-echelons, a new location-inventory model based on echelon stock policy is developed in which the selection of suppliers is considered. The objective of the model is to determine the number and locations of suppliers,plants and Distribution Centers（DCs）,the assignment of each customer to a DC,the transportation quantity between suppliers,plants and distribution centers,and the optimal order quantity in the opening plants and DCs,which minimizes the system-wide location,production,purchase,transportation,and inventory costs.The particle swarm optimization algorithm based on partial encoding is designed to solve the proposed model.The results of 20 numerical examples of different scale show that the model is effective and can be used to design some four echelons supply chain network,and the PSO algorithm designed performs better than mathematic optimization software of Lingo 9.0 whatever the precision or the speed,especially when there are many nodes in the supply chain.

location-inventory model;selection of suppliers;particle swarm optimization algorithm;partial encoding

针对多级供应链网络设计中选址和库存一体化决策问题，基于梯级库存策略，建立了整合供应商选择的多层级选址-库存模型。模型以网络中供应商的选择成本、工厂和配送中心的打开成本、层级之间的运输成本、库存成本、采购成本和生产成本之和最小为目标，同时对供应商的选择、工厂和配送中心的选址、配送中心对顾客的分配、层级之间的运输量、工厂和配送中心的订货批量进行决策。为了求解所建立的模型，设计了基于部分编码的粒子群优化算法。20个不同规模的算例测试表明：所建立的模型是有效的，能用于多层级供应链网络的设计；所设计的算法无论是在求解精度，还是在运算速度上都明显优于数学优化软件Lingo 9.0，尤其是当供应链网络中总节点数较大时。

选址-库存模型；供应商选择；粒子群优化算法；部分编码

A

F252

10.3778/j.issn.1002-8331.1305-0245

SHUI Wenbing,HE Baohong,HE Min.Multi-echelons location-inventory model with selection of suppliers.Computer Engineering and Applications,2013,49（23）：1-5.

国家自然科学基金项目（No.51068013）；云南省科技厅应用基础研究计划项目（No.2011FZ054）。

税文兵（1982—），男，博士，讲师，研究领域为物流系统设计与优化；何保红（1973—），女，博士，副教授，研究领域为交通运输规划与管理；何民（1972—），男，博士，教授，研究领域为交通运输规划与管理。E-mail:swbzzq@126.com

2013-05-20

2013-07-18

1002-8331（2013）23-0001-05

CNKI出版日期：2013-07-29 http://www.cnki.net/kcms/detail/11.2127.TP.20130729.1105.005.html