库存路径优化的固定分区策略效率分析

第27卷 第10期2010年10月

公 路 交 通 科 技

JournalofHighwayandTransportationResearchandDevelopment

Vol127 No110

Oct.2010

文章编号:1002-0268(2010)10-0143-05

库存路径优化的固定分区策略效率分析

傅成红,符 卓

1,2

2

(1.长沙理工大学 交通运输工程学院,湖南 长沙 410114;2.中南大学 交通运输工程学院,湖南 长沙 410075)摘要:针对最常见的单个物流中心、多个零售商组成的系统,从固定分区策略基本思想入手,对固定分区策略在零售商当地条件有无限制的情况下,单独考虑库存最优或配送最优,分别讨论最理想、最坏及一般情况,导出了固定分区策略的成本边界;分析出固定分区策略的一般情况效率水平,并用算例进行了验证。结合分析,最后给出了提高配送效率的建议:一般情况,零售商单次配送量相对车容量很小时,应该采用分区联合配送以提高效率,同时应通过改善这些零售商的当地条件来提高配送效率;当车容量和零售商当地最大配送频率限制已经确定,提高固定分区策略的效率应更多地关注有效分区及对应配送线路。

关键词:运输经济;效率分析;固定分区策略;库存路径问题;配送中图分类号:F540 文献标识码:A

AnalysisonEffectivenessofFixedPartitionPolicyinOptimizingInventoryRouting

FUChenghong,FUZhuo

(1.

1,2

2

SchoolofTrafficandTransportationEngineering,ChangshaUniversityofScienceandTeleology,ChangshaHunan410114,China)

2.SchoolofTrafficandTransportationEngineering,CentralSouthUniversity,ChangshaHunan410075,China

Abstrac:tForthemostcommondistributionsystemwhichcomposedofone-warehouseandmult-iretailer,startedwithdiscussingthebasicidea,theFixedPartitionPolicy(FPP)underthebes,tthewors,tandgeneralconditionsbasedonthesituationsthatretailerwith/withoutlocallimitofinventory-capacitywasdiscussed,theloweranduppercostlimitsofFPPwerederivedafteroptimizingtheinventoryanddistribution

separately.Thegeneraleffectivenesswasestimatedandverifiedusinganumericalexample.Incombinationwiththeanalysis,someproposalsforimprovingdistributioneffectivenesswereputforward:(1)Ingenera,lwhenanyoneretailerpsdeliveryismuchsmallerthanthetruckcapacity,thejointdistributionpolicyshouldbeusedtogethighefficiency,andthelocalinventory-capacityofretailersshouldbeenlarged.(2)Whenthetruckcapacityandtheultimatedistributingfrequencyofretailerarebeingfixed,moreattentionshouldbepaidtotheeffectivepartitionandfindingoptimizeddistributionroutings.Keywords:transporteconomics;problem;distribution0 引言

库存和运输存在效益背反(trade-off)关系,单方面成本降低通常并不能实现整体控制;为了从整体上降低物流成本,需要对二者进行整合研究。库存路径问题(IRP,InventoryRoutingProblem)

[1]

effectivenessanalysis;fixedpartitionpolicy;inventoryrouting

是整合库存和运输研究的典型问题。文献[2-3]

是最早的IRP研究成果,受当时计算机技术限制,相关研究未能迅速展开。现代启发式算法的发展和计算机技术的进步,极大地推动了IRP研究,目前已经成为物流学、运筹学的研究热点。NHMoin和SSalhi对IRP研究现状进行分析认为,当前IRP研究

收稿日期:2009-09-18

基金项目:国家自然科学基金项目(70671108),湖南省教育厅科研资助项目(07C106)

作者简介:傅成红(1971-),男,重庆丰都人,博士,副教授,研究方向为物流工程,交通运输规划与管理1(fch407@1261Com)

144公路交通科技第27卷

存在的一个不足是缺乏标准测试算例和解的质量评价方法

[4]

。

6]对直接送货效率进行了分析,

FPP)上下边界

[9]

[7,8]

21211 零售商当地无约束

(1)最小库存成本

单独考虑零售商i的库存成本最小可能是:最大频率配送。零售商当地无频率限制,配送频率的上界fi松弛到每单位时间段配送一次,即fi=1,则零售商i最小的单位时间库存成本为:hiri/2。

(2)最小配送成本

如果零售商当地条件足够,应该以整车直接给零售商i单独配送以最小化其配送成本。受到车辆装载容量限制,fi=v/ri,则零售商i的最小单位时间配送成本为:

2d0i+s

。v/ri

D

U

U

文献[5,

ChanL1M1等采用数学推导方法找出了固定分区策略(FixedPartitionPolicy,

,

AnilyS.和BramelJ.做了类似研究

,文献[10]

对直接送货和FPP做了比较分析,文献[11]对求解IRP的3种策略进行了分析。上述文献对FPP研究都很深入,比较偏重理论;本文主要是运用已有理论成果从实践视角探讨不同情况下FPP的边界和效率。1 问题与假设

考虑常见的单个物流中心、多个零售商(one-warehousemult-iretailer,下称1-M)系统,给中心及零售商编号0,1,2,,,n,0代表中心,任意两点距离用dij表示,i,jI

{0,1,2,,,n};中心

供应能力足够,不考虑其库存费用;零售商i的单位时间t的需求为ri,不许缺货,当地库存费率hi,作业、库存能力有限制;同类型车辆从中心出发为零售商实施单种货物配送后返回,零售商的配送量不可拆分,车容量v,vmri,车辆每个行程车发生固定成本s及可变成本(与行程成正比)。

为了后续分析,用fi、fi分别表示允许给零售商i配送的最大、最小频率,并且规定ri/v[f[f[1,用f表示直接为零售商i配送的经济订货量(EconomicOrderQuantity,EOQ)频率;用l表示FPP(FixedPartitionPolicy)的零售商分区编号,lI{1,2,,L}。

应该如何组织库存分配和配送路线,才有利于系统总成本最小化?2 FPP成本边界211 FPP基本思想

FPP是经常被用于解决IRP的有效策略,其基本思想是:把需求量不足整车的多个零售商固定划分成多个分区,每个分区用一辆车为零售商实施配送,同一分区的零售商配送频率相同,不同分区的配送频率相互不影响。可以把整车运输(直接配送)看成是FPP的特例,即每个分区只有一个零售商。212 任意策略下界

考察1-M系统的任意策略,总成本包括两部分:一部分是库存成本,另一部分是配送成本(含固定Ui

Ei

Di

U

D

这种情况下,任意两个零售商的合并配送(受车容量限制)不会节约配送成本。

证明:不失一般性,任意取两个零售商i=1,2,考察单独配送、联合配送的最小成本:

DISsingle=DISjoint=

(2d01+s)r1+(2d02+s)r2

,

v(d01+d02+d12+s)(r1+r2)

,

vDISsingle-DISjoint=

(d01-d02-d12)r1+(d02-d01-d12)r2

,

v其中,d01、d02、d12满足三角不等式,所以,DISsingle-DISjoint[0,即为零售商单独配送时配送成本达到最低。证毕。

(3)总成本下界

综合配送及库存成本最小,可以得到1-M系统任意策略总成本下界(也是FPP的下界):

Zmin=

E

n

i=1

(2d0i+s)ri+hiri。v2

这个总成本下界可以对应到/理想情况0:地理位置相同而需求率不同的多个零售商,它们的单位时间需求量之和正好等于车载容量,对其实施合并运输,每个单位时间给全部零售商配送一次,平均总成本即等于下界值,所以Zmin也是FPP的总成本下界。

现实中,零售商很多货物采用/翌日销售(todayfortomorrow)0的配送计划,同一个中心的某

种货物可能会配送给多家/相邻店铺0,如果他们的每日需求量之和正好等于车容量,可以视为上述情况。

21212 零售商当地有约束

(1)最小库存成本

第10期傅成红,等:库存路径优化的固定分区策略效率分析*

U

n

145

不能过于频繁,此时单独考虑零售商i,fi[1,单位

U

时间库存成本最小值为:hiri/fi。

2

(2)最小配送成本

另一方面,受到当地库存能力等条件限制,每次给零售商配送量不能太大(配送频率不能过小)。因为问题假设vmri,此时f\ri/v,零售商的最大配送量为ri/fi。

假定配送也用分区策略,但分区并不固定,每次配送临时确定分区,并且每次各分区内零售商配送量之和正好等于车容量,即:PlI{1,2,,,L},

D

D

i

Z

fmin

=

E

i=1

(2d0i+s)ri+hiri/fi,v2

FPP

max

Z

其中,

=

EminZ,

i

i=1

n

(2d0i+s)riE

+hiv, fi[ri/v[fi,v2

Zi=

2(2d0i+s)hiri, ri/v[fi[fi,(2d0i+s)fi+

311 最坏情况

(2d0i+s)riZmin1

令minZ=+hiri/fi,定义e=FPP

v2Zmax

f

i

f

E

1E

hiri/fi, fi\fi\ri/v。2

E

iIl

(ri/f)=v。分区零售商与配送中心组成TSP

D

i

回路行程为Ol,把分区单次配送成本为(Ol+s)按照零售商的配送量分摊,则零售商i的单位时间配送成本为:

ri/f(Ol+s)ri(2d0i+s)ri

(Ol+s)f=\

vvv(当Ol=2d0i时取等)。

可见,加入配送频率下限的/理想情况0,配送成本仍有可能达到任意策略下界。

(3)总成本下界

加入零售商当地(频率)约束后,任意策略单位时间总成本下界(也是FPP理想情况的单位时间总成本下界)为:

Z

fmin

D

iDi

=

EE

n

minZi

。文献[5]把e称为直接配送的效率minZi

f

i=1ni=1

(effectiveness),即FPP最坏情况的效率。

不失一般性,任选零售商i单独考察,依照EOQ理论,

(2d0i+s)fi=

E

E

hr/fi,关注以下3个2

E

比值在配送策略中的影响。

EOQ策略的配送批量ri/fi=与车容量之比:

ri/fi

A=v

最小(允许)配送批量与车容量之比:

B=

ri/fi

v

E

2ri(2d0i+s)/hi

=

E

n

i=1

(2d0i+s)riU

+hiri/fi。v2

213 FPP成本上界

FPP的最坏可能是:每个分区只有一个零售商(直接配送)。换句话说,FPP总成本必须不大于各

零售商直接配送的总成本时,FPP才有实际意义。

记FPP成本上界为:Zmax=其中,

(2d0i+s)ri1E

+hiv, fi[ri/v,v2

Zi=

DD

(2d0i+s)fi+hiri/fi,

2

D

E

FPP

配送频率上限与EOQ策略配送频率之比(也是最小配送量与EOQ策略配送量之比):

C=fi/fi=A/B。

令ki=2d0i+s,为了书写简洁,以下(1)~(3)省略符号ki,ri,fi,fi的下标i。

E

E

E

n

i=1

minZi,

ri/v[fi[fi,

U

ED

(1)当f[r/v[f时

此时,配送量受到车容量限制无法达到EOQ批量,需要减少到与车容量相等,则:

hr/f2ei==1A+1kr/v+hv2

kr/v+

把ei对A求偏导数:

5ei=[22因为B=5A(A+1)v

E

2(2d0i+s)hiri, fi[fi[fi,UUE

(2d0i+s)f+hiri/fi, fi[fi。

2

Ui

3 FPP的效率

以上关于Zi分段表达式中,当ri/v[fi[fi时,f对FPP并不起实际限制作用,而f[f时,f对FPP也起不到实际限制作用。所以,定义fi,ri/v[fi,imax:

f

FPP

Ui

Ui

Ei

Di

E

D

E

5ei1,所以\0,ei是关于A=的单调递增函数,

5

146

E

公路交通科技第27卷

E

而f[r/v]A[1,当A=1时ei最小,得:ei\21r/f=+22v

(2)当r/v[f[f时

以EOQ批量直接配送最经济,则:

kr/v+ei=

E

E

E

iIl

(hiri)/Eri表示分区的平均库存费率,fl表示

iIl

Gl

分区的EOQ配送频率,用f表示分区的最大允许

配送频率,用Rl表示分区的总需求率,则一般情况分区l的FPP单位时间总成本表示为:

Zl

其中,

Zl=

G

FPP

=minZl,

E

G

G

hr/f\

2khr

OlRl1

+hlv,v22OlhlRl,

GGOlfl+hlRl/fl,

2

fl<Rl/v[fl,Rl/v[fl[fl,fl>fl\Rl/v。

f

E

GE

G

(3)当f\f\r/v时

受当地收货作业能力等限制,只能以r/f的批量为零售商配送。则:

kr/v+hr/f2

ei==1C+1kf+hr/f2

5ei把ei对A求偏导数:=[因为B=(C+1)v1,所以

E

Zl

考察任意分区l的一般FPP效率:el=其

Zl中Zl=

f

E

iIl

kiri1G

+hiri/fl,作以下定义:EOQv2

E

5eiE

[0,ei是关于C=f/f的单调递减函数,=22

Rl/fl

策略的分区车辆装载率:Al=;最大允许频率

vRl/fl

的FPP分区车辆装载率:Bl=;最大允许频率

v与EOQ策略的分区配送频率之比:Cl=fl/fl=Al/Bl;直接配送与FPP配送行程效率之比:Xl=

G

E

G

而f>f,C[1,C=1时ei最小,得:ei\r/f

+。 2v

综上,FPP最坏情况(直接配送)的效率(还原相应符号的下标i)ei\

ri/(vfi),说明FPP的

E

(kiri)OlRl

,反映两种模式完成相同配送量的(类

[10]

iIl

似)运输周转量差别。

类似311节的分析,可以得到(1)当fl<Rl/v[fl时:el\(2)当fl>fl\Rl/v时:el\(3)当Rl/v[fl[fl时:ei\综上,

E

G

E

G

E

G

效率下界与单个零售商允许的最小配送量与车容量之比(车辆装载率)有关。如果每个零售商的单次配送量都超过车容量的一半,只能直接配送,其效率可达2/2=71%以上;如果经济批量占车容量71%以上时,整车配送效率至少可达94%;只有minri/fi[v/2成立时,才有分区联合配送的可能,这个结论与文献[5]所述是一致的。312 一般情况

/理想情况0分区并不总是存在,至少不会每个分区都/理想0。文献[7-8]的理论假设ny],实质就是假设有足够多的零售商,使得每个微小分区(地理位置相同)零售商需求总量都能够装满车辆。

一般FPP实际情况是:零售商并不在相同地理位置,可以通过组建分区联合配送以节约总成本。通常,分区配送比直送的行程迂回很多,即Ol比2d0i大得多。

把分区l看作一个/大零售商0,PlI,,L},用Rl=

{1,2,

U

:

Xl+Bl

2XlBl+22ll总有

el\

无论什么情况,

G

iIl

(kiri)/(Olvfl)成立。

观察到:车容量确定情况下,分区l的FPP效率下界主要取决于分区配送迂回行程Ol及最大允许频率fl的限制。4 算例

假设1个物流中心和8个零售商组成的系统,采用文献[6]提供的标准测试算例编号vrpnc1数据(前9组)确定坐标X、Y、ri,用欧氏距离作为任意两点距离,单位距离运价取1,零售商配送频率上限取相同值,fi=015,PiI

{1,2,,,n},车

v,G

E

iIl

ri表示分区的总需求率,hl=

第10期傅成红,等:库存路径优化的固定分区策略效率分析*

表1 参数及频率计算结果

Approaches2009,

for

the

Inventory-routing

Problem

147with

Tab11 Parametersandcalculationresultoffrequency

编号(i)坐标X坐标YrihifE

iri/v

030400-0--13752710.170.07

24949300.50.230.30

352641660.540.16

42026950.410.09

540302130.500.21

621471520.350.15

f

Backlogging[J].Computers&IndustrialEngineering,

83162231

71763193

56:1519-1534.

1974,

[2] BELTRAMIE,worksandVehicleRouting

forMunicipalWasteCollection[J].Networks,4:65-94.

[3] RUSSELR,[4] MOINNH,

IGOW.AssignmentRoutingProblem[J].SALHIS.

InventoryRoutingProblems:AJournaloftheOperational

Networks,1979,9:1-17.LogisticalOverview[J].

0.430.280.190.23

FPP

按照前面分析,分别计算出Zmin、Zmin、Zmax;如果采用FPP策略,可以把零售商分成3个分区:l=1:1-7-8,l=2:4-5-6,l=3:2-3,则与

中心组成配送线路对应TSP行程分别为Ol=1=7218,Ol=2=7415,Ol=3=6819分别计算分区的EOQ配送频率:f

E

l=1

ResearchSociety,2007,58:1185-1194.

[5] GALLEGOG,SIMCHI-LEVID.OntheEffectivenessof

DirectShippingStrategyfortheOne-warehouseMult-iretailerR-systems[J].ManagementScience,1990,(2):240-243.

[6] KLEYWEGTAJ,NORIVS,SAVELSBERGHMWP.

TheStochasticInventoryRoutingProblemwithDirectDeliveries[J].TransportationScience,94-118.

[7] CHANLMA,

FEDERGRUENA,

2002,36(1):SIMCHI-LEVID.

for36

=0142,f

E

l=2

=0147,f

El=2

=0151,分区1、

2可以按照EOQ频率配送,而分区3只能以最大配送频率fl=fi=015,实际的FPP效率为8010%。结果对比如表2。

表2 计算结果对比

Tab12 Comparisonofcalculationresultsoftwopolicies

任意策略

结果单位时间总成本

效率/%

Zmin36516-Zfmin53316100

固定分区策略ZFPPmax824186417

Z

FPP

G

ProbabilisticAnalysesandPracticalAlgorithmsInventory-routingModels[J].1998,

46(1):

96-106.

[8] CHANLMA,SIMCHI-LEVID.

OperationResearch,ProbabilisticAnalyses

1562-1576.

5%-effective

666188010

andAlgorithmsforThree-levelDistributionSystems[J].ManagementScience,1998,44(11):

[9] ANILYS,BRAMELJ.AnAsymptotic98.

routingProblem[J].2004,

[10]

145(1):22-39.

CHENHaoxun,CHUFeng.Performance

EuropeanJournalofOperational

(onlinefirst)

LIJianxiang,

5 结论

(1)单个零售商直接配送反映的是FPP最差情

况,实际FPP效率会更好;

(2)一般情况FPP的分区内,联合配送相对整车配送的行程节约越多,效率越高,因而,当配送频率上限限制的零售商单次配送量相对车容量很小时,应该采用分区联合配送以提高效率;

(3)采用FPP时,当某些零售商需求率相对车容量很小时,应该通过改善这些零售商的当地条件(比如增加收货平台作业能力、增大当地库容量等等)来提高配送效率;

(4)当车容量和零售商当地最大配送频率限制已经确定,提高FPP效率应该重点关注寻找最少配送费用的分区及对应每辆车的TSP线路。

参考文献:References:

[1] TAMERF,ABDELMAGUID,MAGEDM,

eta.lHeuristic

LowerBoundonFixedPartitionPoliciesfortheInventory-DiscreteAppliedMathematics,

evaluationofdistributionstrategiesfortheinventoryroutingproblem[J].

[11]

Research,2010,202:412-419.路交通科技,2009,Routing

刘立辉,叶春明.库存路径问题的3种策略[J].公

26(12):137-144.

JournalofHighway

2009,P.

and26The

LIULIHUI,YECHUNMING.ThreePoliciesofInventory

Problem[J].

TransportationResearchandDevelopment,(12):137-144.

[12]CHRISTOFIDESN,MINGOZZIA,

MINGOZZIA,TOTH

VehicleRoutingProblem[C]MCHRISTOFIDESN,

TOTHP,

SANDIC.

Combinatorial

Optimization.London:Wiley,1979:315-338.

本文来源：https://www.bwwdw.com/article/1z91.html