基于Dijkstra算法的物流网络库存需求水平预测模型

1、基于dijkstra算法的物流网络库存需求水平预测模型技术与方法 物流技术2014年第33卷第3期(总第306期) doi：l03969dissn1005152x201403061 基于dij kstra算法的物流网络 库存需求水平预测模型 周云霞 (苏州经贸职业技术学院，江苏 苏州 215009) 【摘 要将配送中心和需求点抽象为节点，将道路抽象为线段，形象地描述了区域物流网络结构图，然后采用dijkstra算法求 解区域物流网络的最短路径，得出了配送中心库存量预测模型。最后结合实际例子对预测模型进行了验证，结果表明，多配送中 心库存需求量预测模型能够对配送中心库存量进行有效的预测，对库存管

2、理具有很好的指导作用。 【关键词】物流网络；库存预测；dijkstra算法 【中图分类-n-lf2536 【文献标识码】a 文章编号】1005152x(204)03019003 forecasting model of inventory demand level of logistics networks based on dijkstra algorithm zhou yunxia (suzhou vocationaltechnicai college of economics&trade，suzhotl 215009，chinaj abstract：in this pap

3、er，by abstracting the distribution centers and demand nodes into points and the roads into lines，we graphically described the structure(讦a regional logistics networkand then used the dijkstra algorithm to obtain the shortest path in the network as well as the forecasting model of the inventory volun

4、le of the distribution centers therein at the end，in connection with a practical example we verified the eftctiveness ofthe fi)mcasting mode1 keywords：logistics network；inventory forecasting；dijkstra algorithm 1 引言 2 物流网络库存需求水平数学模型的建立 区域物流是为了支撑区域可持续发展而建立的物流活动 体系，该物流活动体系能够适应区域环境特征 、提供区域物流 功能、满足区域经济、政

5、治、自然和军事等的发展需要 ，具有一 定的空问结构和服务规模，并且能够实现有效的组织和管 理。相对于国际物流而言，区域物流可以是一个国家范围内 的物流、一个经济区域范围内的物流或者一个城市范围内的 物流 ，但都具有其区域内的特点。区域物流网络是指一定区 域范围内的物流节点 、连线以及节点相互之间的联系和作用 构成的结构体系 ，其是 目前学者重点研究的一个方向。配送 中心是区域物流网络的核心节点，配送中心的库存是企业即 将销售或者使用的储备物料，对库存进行有效的管理能够降 低企业的物流成本，提高企业的服务水平，对企业的发展具有 重要作用。但是，库仔一直受供货周期和需求不确定性的影 响而难于管理。

6、因此，库存需求量预测问题是一个非常热门 的研究课题。本文建立区域物流库存需求量预测模型，并结 合实例对预测模型进行了验证。 所谓区域物流网络 ，是指由各级物流节点(配送中心或者 需求节点)和连线(配送中心与需求节点之间的连接道路)以 及所属经济组织构成的相互联系 、相互作用的系统结构形 式。而配送中心需求量的预测是区域物流网络库存管理的一 个核心问题。本文将建立库存需求量预测模型，并提出模型 的求解方法。 21 假设条件 本文的库存需求水平预洲模型是基于以下应用背景建立 的 ： (1)配送中心选址确定 ； (2)区域物流网络中各个零售商的需求在短期 内不会发 生变化； (3)零售商在取货时，以

7、取货是否方便为考虑依据，优先 选择距离 自己较近的配送中心取货； (4)零售商会从离自己近的配送中心选择较多的货品，从 离自己远的配送中心选择较少的货品，即零售商的需求量与 零售商和配送中心之问的距离成反比。 收稿日期120130806 【基金项目】苏州市科技计划项目(sgz2010206) 【作者简介】周云霞(1973一)，女，河南商丘人，苏州经贸职业技术学院副教授，研究方向：t商管理。 190 周云霞：基于dijkstra算法的物流网络库存需求水平预测模型 技术与方法 在建立物流网络库存需求水平的数学模型之前 ，要先做 如下假设 ： (1)在一个给定的物流区域内有 n个零售商 ，in个配送

8、中 心 ，且 m<<n； (2)配送中心的地址是已知的； (3)每个需求点的需求量是确定的，且相同，即q。-1； (4)需求点i对配送中心 i有一定的需求量，记为q。 ； (5)需求点i到配送中心j的距离为l ，且只考虑qf与lf之 间的关系，根据前文分析知道qf与l 成反比。 22 模型的建立 (1)区域物流网络。由于需求点和配送中心具有相同的 特点 ：都是接受或者发送货品的固定点，因此可以将需求点和 配送中心抽象为节点。节点和节点之间通过道路连接，可以 将道路抽象为节点和节点之间的连线，连线的长度代表节点 之间的距离。如图1所示，节点和连接节点的连线构成了该区

9、域的物流网络。 图 1 区域物流网络 连线边上的数字代表节点i与节点 i之间的连接权重w 图1所示的区域物流网络可以通过顶点集v和边集 e构成的 图g=(v，e)来表示，其中v表示n个节点构成的顶点集 ，e表示 m个边构成的边集。 v=v-v2 ，v e=el，e2， ) 如果对于任意两个节点构成的组合 (v_，v )与( v )对应于 同一条边和相同的权值w 则称这样的物流网络为无向加权 网络(undirected weighted network)。 (2)加权矩阵。区域物流网络 g=(v，e)中顶点集v和边集 e之间的关系可以通过邻接矩阵a= 来描述。其中： f0，节点 和节点 之间没有

10、公路连接 l 1，节点 和节点 之间有公路连接 图i中区域物流网络的邻接矩阵为： a= 连接矩阵a只是简单地描述了节点之间是否有连接，而 并没有说明连接的程度。通过加权矩阵w=w 可以定量地描 述节点和节点之间的连接关系。其中： i r上 =1 = 0， = l，=0 式中，w 表示节点v，与节点v 之间的实际距离，例如图1 中，节点v 与节点v2之间的距离为2，即w。 =2；节点2与节点4 之间没有连接，则w = 。由此分析 ：可以得到图1中区域物 流网络的加权矩阵为： w= (3)最短路径矩阵。最短路径问题描述的是已知物流网 络g=v，e，w，求网络中两个给定节点之间的最短路径，即从 需求

11、点i出发，前往配送中心i取货，i和j之间存在道路网络， 求解从节点i出发前往节点i，怎样走路线最短。 用于求解最短路径问题的算法通常被称为最短路径算 法 ，简称路径算法。其中最常用的路径算法有：a 算法、bell mailford算法、dijkstra算法和floydwarshall算法等。dijks tra算法是典型的最短路径算法，其以起始点为中心向外层层 扩展 ，直到扩展到终点为止。dijkstra算法是一种很具有代表 性的最短路径算法 ，在很多方面被应用 ，如数据结构、图论和 运筹学等。 dijkstra算法的主要思想为 ：设g=(v，e)是一个带权有向 图，把图中顶点集合v分成两组 ，

12、第一组为已求出最短路径的 顶点集合(用 s表示 ，初始时s中只有一个源点 ，以后每求得一 条最短路径，就将顶点加入到集合s中，直到全部顶点都加入 到s中，算法就结束了)；第二组为其余未确定最短路径的顶点 集合(用u表示)，按最短路径长度的递增次序依次把第二组 的顶点加入s中。在加人的过程中，总保持从源点 v到s中各 顶点的最短路径长度不大于从源点v到 u中任何顶点的最短 路径长度。此外 ，每个顶点对应一个距离 ，s中的顶点距离就 是从 v到此顶点的最短路径长度 ，u中的顶点距离是从 v到此 顶点只包括s中的顶点为中间顶点的当前最短路径长度。 最后求解得到节点问的最短路径矩阵为： ， ： 21

13、22 ，j：l ： l 0 z 式中，lij表示节点i到配送中心j的最短路径。 (4)需求矩阵。用 q 来表示需求点i对配送中心 j的需求 量，则有需求矩阵q： q= ql ql? ql g2 g2? q2 q q ? g 节点i的需求总量为： q =ql+ql+?+g =zq =1 =1,2，?，n 根据前文的分析，qij与l 成反比，于是有： 、 古： ：亡 ?，n 191 2 2 3 0 2 3 3 o 2 0 3 2 0 2 3 2 2 0 2 3 2 0 2 2 o l l 1 o 0 l 1 l o 0 0 0 o 1 o o l 0 1 0 1 1 1 1 0 l o 1 l 0

14、 1 o o l 0 技术与方法 物流技术2014年第33卷第3期(总第306期) 配送中心i的总需求量为： 需求矩阵为： q =q +g +?+q：=zq =1，2，?，m (5)库存需求预测模型。联立方程式，得到多配送中心的 库存需求预测模型。通过求解可以预测各个配送中心的库存 一 量 3 案例分析 为了验证本文预测模型的正确性和有效性，以北京市海 淀区中关村分中心、上庄分中心和万柳分中心构成的物流配 送网络为背景，预测配送中心的需求量。如图2所示，三个配 送中心构成的区域物流网络中，黑点和白点分别代表配送中 心和零售商节点，线段代表节点之间的道路，线段的长度是实 际的距离按同等比例缩小之

15、后的数值。其中，节点c ，c ，c 分 别表示中关村分中心、上庄分中心和万柳分中心，v。(i_1 2一， 24)为该区域内的24个零售商。 0 需求点 配送中心 图2 海淀区三中心的物流网络 图2所示网络的邻接矩阵a为一个27 x 27的矩阵，由于 多数元素的值都为零，所以为了使问题描述起来更简单，采用 由行号、列号和值构成的三元组(i，j，aij)来表示非零元素，见表 1。 表1 邻接矩阵非零元素 通过dijkstra算法可以得到距离矩阵为 192 2l 3 6 l l7 l0 13 21 14 19 i4 22 l6 1l 0163 5 o270 3 0392 5 o。243 8 0 26

16、4 2 0270 3 0。243 o o32o 8 0 572 3 o 459 5 0 364-5 0 435 4 按照预测模型计算得到，每个配送中心的需求量分别为： q =0163 5+0270 3+0392 5+?+02286=62962 q =02642+0270 3+0243+?+0314 3=6983 8 q =0572 3+0459 5+03645+?+0457 1=1072 对结果进行归一化得到： qc,;- qcl -026 q#- qc2 -0_29 qo= _(】_45 每个配送中心的平均需求量为033，三个配送 中心的方 差为： d四 ：(qc,'-0-

17、33)2+(qo2;-下0-33)2+(qc3;- 0一-33)2： 0_007 8 方差d(q)反映了需求量 q的离中程度 ，它是描述配送中 心库存需求差异的一个重要指标。案例结果表明，j个配送 中心的库存需求差异较大，因此进行库存需求预测对货物的 配送具有很重要的指导意义 4 总结 本文将配送中心和需求点抽象为节点，将道路抽象为线 段，形象地描述了区域物流网络，并采用dijkstra算法求解区 域物流网络的最短路径，建立了配送 中心库存量预测模型。 最后结合北京市海淀区三个配送中心的例子对预测模型进行 了验证。实例结果表明，本文建立的多配送中心库存需求预 测模型，是对配送中心库存量进行预测的有效方法，该模型对 库存管理具有很好的指导作用。但是，本文预测模型是在一