仓储中心是供应链的重要节点, 在物流管理中起着连接供应链上下游的作用, 因此仓储中心的选址直接影响着其他物流决策, 有时候甚至决定着整个物流过程的效率和效益。对仓储中心位置进行合理规划是个传统的物流问题, 国内外学者进行了广泛的研究。文献[1]和文献[2]从定性的角度分析了影响仓储中心选址的多种因素, 文献[3]则从定量角度给出了线性规划、动态规划等9种基本形式的选址模型。结合具体情景, 文献[4]和文献[5]在考虑库存及运输配送的基础上, 建立仓储中心选址模型, 并验证了其合理性。

然而以上研究都是基于市场需求一定的情景进行研究的, 而市场需求受众多因素影响, 往往会发生变化[6,7]。根据需求的这种特性, 文献[8]从随机需求角度将仓储中心选址问题建模为整数线性规划模型并设计求解;文献[9]则在单一中心静态选址的基础上研究了动态选址问题。但是这些文献多是考虑自建仓储中心, 虽然自建仓储中心更能符合企业自身存储物品的特性及要求, 但却需要巨大的投资, 资金占用率高, 风险大[10]。而租赁仓储中心无需固定投资, 降低了仓储成本, 特别是其地点选择具有弹性, 可以随市场迁移, 降低了需求变动所带来的风险[11]。因此, 对于规模小, 产品需求波动大的产品来说, 租用仓储中心可以减少固定投资, 增加资金的流动性, 提高经营灵活性。本文正是从这个角度出发, 在需求波动的背景下, 研究了单一第三方仓储中心的选择问题。文章首先针对需求变化已知的情形给出了最优的仓储中心选择策略, 然后为需求变化不可预知的情形设计了在线选择策略, 并从竞争分析的角度讨论了策略的竞争性能。

本文所研究的问题描述如下:某公司需要把产品从不同的产地运往销售地, 销售地分散着n个需求点, 每个需求点的需求量随时间而变化。同时在销售地的不同区域分散着m个第三方仓储中心, 公司根据不同时期的需求量变化情况, 动态地选择仓储中心, 而仓储中心的更换需要固定的转换成本, 如果限定每阶段只选择一个仓储中心, 那么公司应如何动态地选择仓储中心使得经营成本尽量小?

针对该问题, 给出以下符号定义:

C:仓储中心转换成本;c:单位运输成本;xi:第i个潜在需求点, i=1, 2, …, n;yj:第j个备选仓储中心, j=1, 2, …, m;T:阶段数, 同时也是决策期限;qit:需求点xi的需在第t阶段的需求量, t=1, 2, …, T;dij=d (xi, yj) :需求点xi到仓储中心yj的最短路程, 设为已知。

便于讨论, 本文基于以下假设:

(1) 不同产地到不同仓储中心的距离相同;

(2) 由于资金或其他限制, 每阶段只选一个仓储中心;

(3) 在同一时期内, 不同仓储中心的单位库存成本相同;

(4) 不同中心之间的转换需要固定的转换成本, 且忽略中心转换所需的时间。

需要说明的是, 产地到销售地的距离相对于不同仓储中心间的距离大得多, 因此在选择仓储中心的决策中, 假设⑴认为不同产地到不同仓储中心的距离相同, 可以不考虑产地到销售地的距离影响。假设⑶说明同一时期的总库存成本不会因为仓储中心的不同而不同, 因此只需要考虑从仓储中心到需求点的运输成本, 精简了论证过程。

现在考虑下面两个问题:

P1:所有需求点在不同阶段的需求情况已知时, 如何进行仓储中心的选择?

P2:在任何阶段, 只知道该阶段及以前阶段各个需求点的需求情况, 如何进行仓储中心的选择?

P1问题是信息完全情形下的多阶段动态决策, 属于离线问题, 可以设计相应的动态算法进行求解;P2问题是P1问题对应的在线问题, 该问题的特点是任何时刻, 对以后阶段的情况不可预知, 决策者要在只知道以前需求的情况下做出在线决策, 使得收益 (成本或者利润) 与对应的P1问题的最优解之间的差距尽量小。针对P2问题, 文章采用在线策略与竞争分析的方法进行研究, 这种方法与以往解决此类问题的方法的最大区别在于:它在变化因素的每一个特例中都能给出一个方案, 使得这一方案所得到的解离最优方案给出的解总在一定的比例之内[12,13]。对于费用最小化问题P以及任何有限的输入序列δ, 如果存在一个常数r, 使得在线策略G的费用CostG (δ) 与离线最优策略OPT的费用CostOPT (δ) 满足

CostG (δ) ≤r·CostOPT (δ) (1)

则称该在线策略G为r竞争策略, 或者该在线策略具有竞争比r, 如果某一个在线策略的竞争比满足r*=lnf(r)G‚则称r*为该在线问题的最优竞争比[14]。

文章第三部分针对P1问题给出了线性时间的动态规划算法, 论证了结论的最优性;第四部分针对P2问题给出了一种简单贪婪策略, 并讨论了该策略在一般情形和特殊情形下的竞争性能;第五部分分别用DPA算法和简单贪婪策略对算例进行分析求解;第六部分对文章进行了总结及展望。

当所有需求点在不同阶段的需求情况已知时, 本文给出了线性时间的动态规划算法, 在给出算法之前, 首先讨论最优解的有关性质。假设决策期包含T个阶段, 如果不考虑转换成本, 则在任意阶段t, 选择第j个备选仓储中心的运输成本为:

Cjt=n∑i=1cdijqit, j=1,2,⋯,m (2)

在已知Cjt的情况下, P1问题可以转化为特殊的最短路问题, 该最短路问题具有以下三个特点: (1) 具有T个阶段, 每阶段均包含m个结点, 其中第t阶段的第j个结点记为yjt, 对应于第t阶段的备选仓储中心yj; (2) 上一阶段的任一结点都可以到达下一阶段的所有结点, 其中只有一条弧长为0, 其它均为C, 在P1问题中的实际意义是, 如果前后两相邻阶段的仓储中心位置不变, 则弧长为0, 如果改变则弧长为C; (3) 第t阶段的每个结点也有权重, 权重值为Cjt。

我们可以通过以下两个辅助操作, 把该特殊最短路问题转化为一般的分阶段最短路问题: (1) 增加两个虚拟结点:一个初始结点O和一个终止结点D, 同时连接结点O和第一阶段的m个结点, 以及结点D和最后阶段的m个结点, 令增加的虚拟结点和虚拟弧的权重均为0; (2) 把第t阶段的结点yjt的权重变为0, 把结点yji所有入弧的权重都增加Cjt。则可以用图1描述该特殊最短路问题, 其中最短路径对应的结点就是最优的仓储中心选择序列。

因为该最短路问题具有 (Tm+2) 个结点, 所以直接利用Dijkstra算法对该最短路问题进行求解的时间复杂性为O ( (Tm) 2) 。为了寻找更加快捷的算法, 对问题的最优解结构进行分析:设Ctit为第t阶段选择中心yi时, 前t阶段的最小总成本, 且定义Yit为实现Ctit时从第1阶段到第t阶段的仓储中心序列, 则下面的引理是显然的:

引理1 若最优策略在第t阶段选择了中心yi, 则第t阶段以前的中心序列为Yit。

图1 P1问题的最短路模型示意图  下载原图

结合前文对Cjt的定义, 有以下递推关系:

Ctit=min{Ct-1i(t-1)+Cit,minj≠i{Ct-1j(t-1)+C+Cit}}, i=1,2,3,⋯,m (3)

根据引理1和关系式 (3) , 给出离线问题的动态规划算法 (DPA) 如下:

Step 1 计算Cjt=n∑i=1cdijqit, j=1, 2, …, m;t=1, 2, …, T, 令C1j1=Cj1, j=1, 2, …, m, 得到向量X1= (C111, C121, …, C1m1) T。

Step 2 , For (t=2;t=T;t++) , 计算Ctit=min{Ct-1i(t-1)+Cit,minj≠i{Ct-1j(t-1)+C+Cit}},i=1,2,3,⋯,m, 若Ct-1i(t-1)+Cit≤minj≠i{Ct-1j(t-1)+C+Cit}, 则标记ji (t-1) =i, 否则标记ji(t-1)=j=argminj≠i{Ct-1j(t-1)+C+Cit}, 同时得到向量Xt= (Ct1t, Ct2t, …, Ctmt) T。

Step 3 令Csummin=min1≤j≤mCΤjΤ, 标记j*Τ=j=argminjCΤjΤ。

Step 4 标记j*T-1=jj*T (T-1) , 令T=T-1, 当T=1时结束, 否则返回Step 4, 并记录Csummin以及序列 (j*1, j*2, …j*T) 。

其中序列 (j*1, j*2, …j*T) 对应的仓储中心序列即为最优的选择序列, 最优成本为Csummin。

关于算法时间复杂性的分析:Step 1需要计算 (Tm) 个值, 每个值需要n次加法运算, 所以Step 1的时间复杂性为O (Tm) ;Step 2共需循环T次, 每次循环需要确定m个值, 而每个值需要进行m次比较, 所以时间复杂性为O (Tm2logm) ;Step 3和Step 4的时间复杂性分别为O (1) 和O (T) , 所以总的时间复杂性为O (Tm2logm) , 如下面定理所示:

定理1 对于P1问题, 存在时间复杂性为O (Tm2logm) 的线性算法 (DPA) 。

从定理1可知, 当T>logm时, DPA算法的复杂性 (O (Tm2logm) ) 小于Dijkstra算法的复杂性 (O (Tm) 2) ) , 因此面对实际问题时, 可以先判断是否满足T>logm, 如果满足则利用本文的DPA算法进行求解, 否则直接采用Dijkstra算法进行求解。

上一节给出了离线情形的最优解及算法, 而在实际商业活动中, 尤其是需求波动大的产品, 未来的需求情况往往难以预测, 因此在只知道当前阶段及以前阶段的需求情况时, 对仓储中心的选择做出在线决策就显得更为重要。面临不确定问题时, 人们对未来缺乏充足的认识, 通常追求“眼前利益”, 这正是贪婪策略产生的根源, 本节针对具有在线决策特点的P2问题给出一种简单贪婪策略, 并分别在一般情形和特殊情形下, 讨论了策略的竞争性能。

简单贪婪策略 (SGS) :设t-1阶段的仓储中心为yi, 则在t阶段进行判断:若Cit≤C+minj≠iCjt, 则不改变仓储中心, 仍然为yi, 否则选择仓储中心yj, 满足j=argminj≠iCjt。

简单贪婪策略是人们在处理类似P2问题时经常做出的选择, 但是从竞争分析的角度而言, 在一般情形下简单贪婪策略不是竞争的。要证明该策略不是竞争的, 只需构造一个序列, 使得贪婪策略在该序列下没有常数竞争比, 或者竞争比无界, 因此构造下面特例:

设只有三个备选仓储中心, 即y1、y2、y3, 同时构造T个阶段的需求序列使得对应的各仓储中心的运输成本向量分别为:C1= (x, M, …, x, M) , C2= (M, x…, M, x) , C3= (x+ε, x+ε, …, x+ε) , 其中M>x+C, ε→0+。在这里向量Ci中的分量表示仓储中心yi在某一阶段的运输成本Cit。

根据定义, 简单贪婪策略的仓储中心选择序列为 (y1, y2, …, y1, y2) , 对应成本为Tx+ (T-1) C;而最优策略的选择序列为 (y3, y3, …, y3) , 对应成本为Tx+Tε。因此一般情形下, 简单贪婪策略的竞争比不小于r1=Τx+(Τ-1)CΤx+Τε=1+(Τ+1)CΤx, 而当C>>x时, r1是无界的, 因此有下面定理:

定理2 一般情形下, 简单贪婪策略 (SGS) 不是竞争的。

上一小节论证了简单贪婪策略在一般情形下不是竞争的。本节结合实际情况, 研究了经济生活中经常存在的一种特殊情形下的简单贪婪策略的竞争性能。特殊情形:任何阶段中, 各仓储中心的运输成本都至少是改变仓储中心所需转化成本的α倍, 即存在关系:Cjt≥αC。在该特殊情形下, 当α是确定常数时, 简单贪婪策略具有常数竞争比, 如定理3所示:

定理3 当Cjt≥αC时, 简单贪婪策略 (SGS) 的竞争比为r2=1+1α。

证明 首先对于简单贪婪策略而言, 如果在第t-1阶段选择的仓储中心为yi, 则在第阶段会出现两种可能的情形:Cit≤C+minj≠iCjt或者Cit>C+minj≠iCjt。若Cit≤C+minj≠iCjt, 则不改变仓储中心位置;若Cit>C+minj≠iCjt, 则仓储中心位置变更为yj, 其中j=argminj≠iCjt。无论哪种情形, 简单贪婪策略在每阶段的成本 (Cont) 都满足关系式:Cont≤C+minjCjt。对于离线最优策略而言, 每阶段的成本 (Coptt) 不小于该阶段的最小运输成本, 即Coptt。≥minjCjt。

所以该情形下的策略竞争比为

r2=ConCopt=Τ∑t=1ContΤ∑t=1Coptt≤Τ∑t=1(minjCjt)+ΤCΤ∑t=1(minjCjt)=1+ΤCΤ∑t=1(minjCjt)≤1+1α (4)

证毕。

特殊情形下, 简单贪婪策略的竞争性能给决策者的启示是:当α较大时, 贪婪策略与离线最优策略的差距较小, 因此这种情况下简单贪婪策略是合理的在线策略。值得注意的是, 很多决策者具有不同程度的成本敏感度, 即当成本差异在一定范围之内可以接受, 超出该范围就明显感受到差异, 结合敏感度的启示是, 当决策者的敏感度s≥α时, 对于决策者而言, 简单贪婪策略和离线最优策略没有区别;当决策者的敏感度s<α时, 能够比较明显地感受简单贪婪策略和离线最优策略的差异。

假设某公司需要将产品运往5个需求点, 其可选择的仓储中心有3个, 仓储中心与需求点以及需求点之间的距离如图2所示。设定单位运输成本c=1, 仓储中心转换成本C=800, T=4, Dt={q1, q2t, q3t, q4t, q5t}表示第t阶段5个需求点的需求的集合, 其中D1={239, 179, 25, 19, 33}, D2={37, 29, 62, 158, 277}, D3={185, 166, 33, 28, 35}, D4={64, 75, 450, 224, 150}。

图2 仓储各心及需求点运输路线示意图  下载原图

离线情景下, 公司对4个阶段中需求点的需求状况完全了解。由于可选仓储中心只有3个, 因此无论采用DPA算法还是Dijkstra算法进行计算都不复杂, 本算例中采用本文设计的DPA算法进行求解:

Step 1 对第1阶段各个仓储中心的运输成本进行计算, 如:C11=5∑i=1cdi1qi1=742, 并令C111=C11, 得到向量X1= (742, 1509, 2252) 。

Step 2 先对第2阶段的第一个仓储中心进行分析, 计算C212=min{C111+C12, min{C121+C+C12, C131+C+C12}}=C111+C12=3226, 同理可得C222=3201, C232=2439, 最终得到向量X2= (3226, 3201, 2439) ;以此类推, 再进行第3阶段, 第4阶段的计算, 得到X3= (3965, 4502, 4342) , X4= (6800, 6406, 6300) 。

Step 3 根据X4可知, 令Csummin=C434=6300, 标记j*T=3。

Step 4 根据第三步的结果进行逆推, 可知仓储中心选择的最优序列为 (1, 3, 3, 3) , 最低成本Copt=6300。

然而现实中, 公司往往对未来的需求信息并不能做到完全掌握。在线情境下, 假设公司仅知道当前阶段的需求信息, 即在第t阶段时, 公司仅知道Dt及t阶段以前的信息。针对此情景, 采用文中设计的简单贪婪策略进行求解, 具体如下:

Step 1 第1阶段选择成本最小的仓储中心, 由C1i1=min{C11, C21, C31}=742可知为仓储中心1, 即i=1。

Step 2 在选定仓储中心1的基础上进行第2阶段选择, 由C2i2=min{C111+C12, min{C111+C+C22, C111+C+C32}}=C111+C32=2439知选择仓储中心3;以此类推, 第3阶段选择仓储中心1, C313=3978;第4阶段选择仓储中心2, C424=6682。

Step 3 根据第二步的结果, 可知仓储中心选择序列为 (1, 3, 1, 2) , 最低成本Con=6682。

由以上两部分计算可知, 此算例中在线与离线的比值r=ConCopt=1.1。结合定理3可知, 当仓储中心转换成本足够小的情境下, 即满足Cjt≥αC, 采用简单贪婪策略可以有效的控制成本, 使得简单贪婪策略的运输成本与最优策略的成本比值总在一定的比例之内。

在物流管理中, 物流中心选址是一个经典问题, 以往的研究多是考虑自建设施。但在中国当前的经济情境下, 城市地价飞涨, 自建仓储中心的成本会远远超过租赁成本, 占用企业大量的资金。同时 , 如果只建单一仓储中心, 当需求变动时, 无疑会大幅增加运输成本;而建造多个仓储中心, 不仅会增加投入, 同时还会面临空置的风险, 增加了管理成本。因此, 当决策者资金有限, 或者销售产品具有需求波动大的特点时, 往往会采取租用第三方仓储中心的策略。

假设仓储成本不变的条件下, 决策者出于运输费用最小化考虑, 往往租用临近消费者的仓储中心, 但是消费者消费趋向的转变往往导致以前的仓储中心不再适合, 因此根据消费趋向的变化动态地选择仓储中心显得尤为重要。本文首先针对未来需求变化完全预知的情形, 给出了时间复杂性为O (Tm2logn) 的离线算法;其次, 对于未来需求变化无法预知的情形, 分析了一般情形下, 简单贪婪策略 (SGS) 的竞争性能, 指出一般情形下SGS不具有竞争性;并结合实际, 分析了特殊情形下 (Cjt≥αC) 的SGS, 证明了该情形下的竞争比为1+1α。而结合城市的交通状况以及最新的经济形势, 设计合理的动态选址策略正是以后的研究方向。