物流配送中心动态选址问题的探讨

JOURNALOFLIUZHOUVOCATIONAL&TECHNICAlCOLLEGEVo.l5No.4

Dec.2005

物流配送中心动态选址问题的探讨

覃运梅

(广西工学院󰀁汽车工程系,广西󰀁柳州󰀁545006)

摘󰀁要:针对物流配送中心选址时需求和成本会随时间的变化而变化的情况,本文考虑了动态选址模式,把问题转换为网络的最短路问题,并用Dijkstra算法求解。方法简单实用,特别是对于小规模的物流企业具有较大的实用价值。

关键词:物流;配送中心;动态选址

中图分类号:F252󰀁󰀁文献标识码:A󰀁󰀁文章编号:1671-1084(2005)04-0024-03󰀁󰀁0󰀁引󰀁言

物流配送中心是利用现代物流设施和管理技术与手段,以尽可能低的成本,为客户提供优质、高效的配送服务的物流机构

[1]

据。

第三,可以找到一个随时间变化的最优布局变化轨迹,精确地反映什么时候需要转换成新布局。本文探讨的是第三种情况,针对小规模的单设施动态选址问题,建立一个简单实用、易于实施的优化模型。

2󰀁优化模型

2.1󰀁问题描述

对于采用单个配送中心的小规模物流企业,已知备选地址的现有及未来(预测)的需求和成本数据,如何确定在规划期内每一年的选址方案变化轨迹,使决策者确切地知道什么时候需要把配送中心转换到什么地方,从而达到整个规划周期内的总费用最小。

2.2󰀁转化为网络问题

把规划期内各年的选址方案表示为有向连通图G=(V,E),V为顶点vij的集合,E为边ek的集合。设规划期为n年,用vij表示第i年年初选用j地址,虚设点vs和vt,vs表示规划期起点,vt表示规划期终点,即第n年年末。边(vi-1,,fvij)上的数字dk表示从第i年年初从上一年选用的f地址转换到j地址的成本(包括搬迁成本和j地

。配送中心的合

[2]

理选址是物流系统优化的重要组成部分。选

址模型可以分为静态模型和动态模型。静态模型在一开始就实施最优设计,无法提供随时间而变化的最优选址模式。实际上,需求和成本会随时间变化,选址模型根据现有数据得出的解在未来的经济环境下使用不一定是最优的,因此,建立随时间而变化的动态选址模型就非常重要。

1󰀁动态选址方法

通过几种方法可以找到随时间变化的最优选址布局:

第一,可以使用现期条件和未来某年的预期情况来找出配送中心的最佳位置,根据现年与未来年份之间的平均条件进行布局。

第二,找出当前最优布局,并进行实施。随后,在每一年到来,且该年的数据可得时,找出新的布局。如果新旧布局转换带来的成本节约大于搬迁成本,就应该考虑改变布局。该方法的好处是总在使用实际数据󰀂󰀂󰀂不是那些需要预测的数

[收稿日期]2005-10-11

[3]

[作者简介]覃运梅(1976-),女,广西贵港人,合肥工业大学硕士研究生,主要从事交通规划与管理教学和研究。

第5卷󰀁第4期覃运梅:物流配送中心动态选址问题的探讨

25

第i年的使用成本)。网络图如图1。上最小者时,可同时改为P标号。若全部点均为P标号则停止。否则用vi代vi转回(2)。

4󰀁算例

设某企业进行为期5年的配送中心选址规划,第一年年初已经选定在A点,以后各年的备

选地点为A、B,已知各地每年使用成本现值,见表1;搬迁费用是50万元,投资收益率是20%,计算

图1󰀁基本网络图

这样动态选址问题就变为:求从vs到vt的最短路问题。

3󰀁最短路算法

求解最短路问题的有效算法有Dijkstra算法,逐次逼近算法和Floyd算法。其中Dijkstra算法适合于求某一点到其它各点的最短路问题,目

前被认为是求无负权网络最短路问题的最好方法;逐次逼近法适合于网络中有负权的问题;而Floyd算法适用于整个网络中任意两点间的最短路问题,随着网络的增大该方法的复杂性急剧增加。本文涉及到的是规划期起终点之间无负权的最短路问题,因此,文中采用Dijkstra算法求解,

[4]

其原理及步骤如下:

算法原理:若序列{vs,v1,v2,󰀁vn}是从vs到vn的最短路,则序列{vs,v1,v2,󰀁vn-1}必为vs到vn-1的最短路。该算法一般采用标号法:T标号为试探性标号,P为永久性标号,给vi一个P标号时,表示从vs到vi的最短路权,vi点的标号不再改变。给vi一个T标号时,表示从vs到vi的估计最短路权的上界,是一种临时标号。算法每一步都把某一点的T标号改为P标号,当终点vn得到P标号时,全部计算结束。

步骤:

(1)给vs以P标号,P(vs)=0,其余各点均给T标号T(vi)=+ 。

(2)若vi点为刚得到P标号的点,考虑这样的点vj:(vi,vj)属于E,且vj为T标号。对vj的T标号进行如下的更改:

T(vj)=min[T(Vj),P(Vi)+lij]。

(3)比较所有具有T标号的点,把最小者改为P标号,即P(vi=min[T(vi)]。当存在两个以第i年搬迁费用的现值为:50万元/(1+20%),计算结果在表1中。要求做出动态的选址方案,确定在哪一年应搬迁到哪一个选址点,使5年内的总费用最小。

表1󰀁

项目A地使用成本B地使用成本搬迁成本

i

各选址点每年的预期成本现值(万元)

第1年第2年第3年第4年440

43045042

42040035

41038029

第5年40036024

󰀁󰀁4.1󰀁把选址规划转化为网络问题

把上述选址问题用网络图表示,如图2:

图2󰀁动态选址网络图

图中,起点vs的值440表示在第一年年初选定A的使用成本,各条边上的数字表示各年选用相应点的使用成本和搬迁成本之和(可由表1计算得到)。例如,边(v2A,v3B)上的数字表示第三年年初从A搬到B的总成本:400+35=435(万元);(v2A,v3A)上的数字为:420+0=420(万元),该方案没有搬迁,所以搬迁成本为0。

4.2󰀁求解最短路

用Dijkstra算法求解图2中vs点到vt点的最短路,步骤如下:

(1)首先给vs以P标号,P(vs)=440,其余各点均给T标号T(vij)=+ (i=2,!5;j=A,B)。(2)由于(vs,v2A),(vs,v2B)属于E,且v2A、v2B

为T标号,所以修改这两个点的标号:T(v2A)=

26

min[T(v2A),P(vs)+ls,

2A

柳州职业技术学院学报2005年12月

]=min[+ ,440+

2B

按逆向过程找出vs到vt的最短路为:Vs∀V2A∀V3B∀V4B∀V5B∀Vt,路长P(vt)=2045。即最优决策为在第1年年初选定A后,第2年不变,直到

第3年年初搬迁到B,往后年份不变。这时5年的总费用为2045万元。

5󰀁结论

进行物流配送中心选址时,由于不同选址地点的需求和成本会随时间的变化而变化,故用静态方法求出的最优解在未来年份有可能变成次优解。针对这种情况,本文考虑了动态选址模式,并把问题转换为求解网络的最短路问题,方法简单实用,特别是对于小规模的物流企业具有较大的实用价值。

[参考文献]

[1]俞仲文,晨代芬.物流配送技术与实务[M].北京:人民交通出版社,2001.

[2]禤文怡,汪波,袁建强.基于遗传算法和指标满意度求解的第三方物流企业物流中心选址方法[J].运筹与管理,2004,13(2):139-144.

[3]罗纳德.H.巴罗(美)王晓东等译.企业物流管理

430]=870;T(v2B)=min[T(v2B),P(vs)+ls,]

=min[+ ,440+492]=932。

(3)比较所有T标号,T(v2A)最小,所以令P(v2A)=870。

(4)v2A为刚得到P标号的点,考察与之相连的边(v2A,v3A),(v2A,v3B)的端点v3A、v3B。T(v3A)=min[T(v3A),P(v2A)+l2A,3A]=min[+ ,870+420]=1290;T(v3B)=min[T(v3B),P(v2A)+l2A,

3B

]=min[+ ,870+435]=1305。

(5)比较所有T标号,T(v2B)最小,所以令P类似地,修改其它各点的标号,直到终点vt

(v2B)=932。!!

获得P标号,计算结束。全部计算结果见图3。

图3󰀁󰀁计算结果图

-供应链的规划、组织和控制[M].北京:机械工业出版社,2002:409-411.

[4]胡运权.运筹学教程[M].北京:清华大学出版社,1998:236-242.

[5]石欣,程代杰.区域配送中心物流调度模型[J].重庆大学学报.2004,27(1):76-80.

图中括号内的数字为各个顶点的P标号。

ResearchonDynamicSiteSelection

ofLogisticDistributionCenter

QINYun-mei

(AutomobileEngineeringDepartmentofGuangxiUniversityofTechnology,Liuzhou545006,China)Abstract:Forthedemandandcostofsiteselectionoflogisticdistributioncentershouldbechangedastimemoves,themodelofdynamicsiteselectionispresented,andtheshortestrouteofnetworkisbroughtforwardtosolvedthequestion,thencomputeitwithDijkstraalgorithm.Thismethodissimpleandpractica,lespeciallyforsomesmallenterprise.Keywords:logistics,distributioncenter,dynamicsiteselection