矩阵迭代法在物流中心选址中的应用分析

开篇：润墨网以专业的文秘视角，为您筛选了一篇矩阵迭代法在物流中心选址中的应用分析范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：物流中心选址不仅是物流企业面临的一个普遍问题，而且是供应链管理的重要环节之一。首先对物流中心的选址进行了定义，提出选址应以总费用最低作为经济性原则，进而采用矩阵迭代算法对该问题做出定量描述，并以某轮毂产业园的物流中心选址为例验证了基于最优化思想的该算法应用。

关键词：物流中心选址；矩阵迭代法；最短路径法

中图分类号：

F25

文献标识码：A

文章编号：1672-3198（2013）20-0064-03

0 引言

随着科技的飞速发展和经济全球化，“地球村”和“世界工厂网”的出现，在现代化生产中，通过降低原材料成本和提高设备本身生产能力的手段，来提高企业的效益已经变得极其有限。于是，现代物流成为了一个新的经济热点，物流是企业的第三利润源泉，整个物流系统中却蕴藏着巨大的潜在经济效益。

物流系统是指由两个或两个以上的物流功能单元构成，以完成物流服务为目的有机集合体，是指在一定的时间和空间里，由所需输送的物料和包括有关设备、输送工具、仓储设备、人员以及通信联系等若干相互制约的动态要素构成的具有特定功能的有机整体。系统中既包括物料输送、物流线路等实体网络，也包含通讯及计算机联系等非实体网络。

在物流系统及网络中，物流中心是重要的节点，在物流系统中扮演着集散货物的重要角色，也是整个物流网络的核心所在。因此，如何选择合适的物流中心对整个物流系统来说具有重要的意义。

1 问题的提出

根据广义的定义，物流中心是处于枢纽或重要地位的、具有较完整物流环节，并能将物流集散、信息和控制等功能实现一体化运作的物流据点，其具有物流网络节点的系列功能。

物流中心选址的过程中需要考虑如下原则：首要考虑的为经济性（即建设费用、物流费用或经营费用）原则，因为这条原则是物流中心选址中最为重要的原则，也是物流企业运营与管理的基础。其次需要考虑的原则为接近用户原则，其实质为在符合经济性的前提下满足客户对快速反应速度的需求。

本文应用实例提到的物流中心服务的范围虽然仅覆盖某轮毂产业园，属于狭义的物流中心，但同样具有完整的物流环节，能够将轮毂生产的关联环节、产品信息和网络控制等功能实现一体化运作，因此广义物流中心选址过程中需要考虑的原则同样适用于应用实例提到的狭义的物流中心选址。

基于如何确定物流中心的选址以增加生产规模经济和减少运输成本，是物流企业面临的普遍问题，加之上述经济性原则的重要性，本文物流中心选址主要围绕考虑经济费用最小（即从物流中心到达服务区域内的其他地点所需的物流费用最少）进行论述。

2 概念的引入

图论中所谓的“图”（即网络图，是一种图解模型，由作业箭线、节点和路线三个因素组成。）是指某类具体事物和这些事物之间的联系。节点表示具体事物，两节点间的线段（直线或曲线）表示事物间的特定联系。目前在图论领域中形成两个不同的方向，分别为抽象图论和最优化图论，前者着重研究图的性质，后者着重讨论与图有关的最优化问题。

物流中心与各配送点间的空间位置关系可以抽象为网路图，用节点代表可用来设置物流中心的点，路线（双向，可任意赋值）代表节点间的物流费用，将物流中心选址问题抽象为网络图后即可采用图论理论确定合适的物流中心选址。基于此，物流中心选址过程中广泛使用了与图论相关的最优化方法，如最短路径法算法，多种最短路径计算方法在物流中心选址中的应用也证实了该方法的有效性和重要性。

3 最短路径的计算方法

最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由节点和路径组成的）中两两节点之间的最短路径。在物流中心选址过程中，最短路径的计算及寻找是确定物流中心位置的关键环节。

对于最短路权矩阵计算，国际上采用比较多的是Dijkstra算法（即标号法），该方法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。但实际问题中往往要求所有各节点之间的最短距离，如果仍采用Dijkstra算法逐个节点分别计算，计算速度较慢。

有研究表明，通过矩阵迭代法寻找最短路径是一种非常有效的手段。该方法主要是通过不断修正原路权矩阵D而达到逐步向最短路权矩阵D0逼近的目的，最终获得最短路权矩阵D0，其迭代公式如下：

利用（1）、（2）两式反复迭代，直至D（n）=D（n-1），即第n次迭代后的路权矩阵中的每一元素与第（n-1）次迭代后的路权矩阵中的对应元素全部相等，那么矩阵D（n-1）就是最短路权矩阵D0，即D0=D（n）=D（n-1）。

在根据（2）式计算路权矩阵的同时可得到路径矩阵，计算见应用实例。矩阵D（n-1）（也即最短路权矩阵D0）给出网络中任意两点直接到达，经过一个、两个……到（2n-1）个中间点时比较得到的最短距离和所经过的路径。若网络有p个点，则一般计算到不超过D（n），n的值按以下公式计算：2n-1-1

通过实例可以验证该方法的实用性和快速性，其最大的优点是在获取任意点间的最短路径的同时可获知所经过的路径情况。

4 最短路径算法在物流中心选址中的应用

现有轮毂产业园（可划分为6个服务区域），要在这6个服务区域中选择一处设置物流中心，该物流中心的服务面积即为这6个区域。通过上文的分析，我们可以对该6个区域彼此间的物流费用进行统计，按文中给出的计算方法转化为6个区域的距离。设Dij为两个区域之间的物流费用，Dij=d（vi，vj），（i，j=1，2…6）；

假定各点到各点的费用已知，在①-⑥六个地点中选择一个物流中心，要求其到其他几个点的费用最小。6个区域中心之间的费用情况见表1。

根据表1画出网络图1。其中，网络中各节点①-⑥代表服务区域中心，各边的权值表示可直接连通的中心距离。通过矩阵迭代法求最短路径过程如下：根据矩阵迭代法对路权矩阵中相关元素的定义，则原路权矩阵D的元素[dij]可以定义如下：

dij=任意给定的数值；从节点i直接到节点j的路径存在时

∞；从节点i直接到节点j的路径不存在时

0；上述两种情况以外时

如果图为有向连接图时，则原路权矩阵D可以表示成上三角阵，如果图为无向图时，则原路权矩阵可以表示成对称矩阵。

根据对原路权D中元素的定义，图1的原始路权矩阵D可以表示成如下的对称矩阵。

〖TP刘洪丽-02.TIF；%85%85；S*2；X*2；Z4；Y4，BP#〗

根据式（1）、（2）依次计算路权矩阵中的相关元素，将通过式（2）计算所得的最小数值填入左部矩阵（即路权矩阵）的相应位置上，并把通过计算所得等式后面括号中所得的列数填入右部矩阵（即路径矩阵）的相应位置上。

d（2）11=min（d1k+dk1）=min（0+0，7+7，2+2，∞+∞，∞+∞，∞+∞）=0（第一列）（k=1……6）以下的k取值均为1……6

依次可算得：d（2）12=3（第三列） d（2）13=2（第一列） d（2）14=7（第三列）

d（2）15=3（第三列） d（2）16=∞（两段路无法到达）。同理可得：……

d（2）45=2（第四列） d（2）46=3（第五列） d（2）56=1（第五列）

通过以上计算得新的距离矩阵和路径矩阵如下：

本例中lg（p-1）/lg2=lg5/lg2≈2.322所以最多计算到D（3），继续计算也一定可得，D（4）=D（3），即可停止计算，矩阵D（3）就是最短路权矩阵D0。

D（3）的元素值就是相应顶点间的最短路径。第一行（或列）值之和即为①处到其他5处的物流费用总和，可知①处到其他各处的费用总和为17，同理，②处到其他各处的费用总和为10，③处到其他各处的费用总和为9，④处到其他各处的费用总和为16，⑤处到其他各处的费用总和为8，⑥处到其他各处的费用总和为12。

综上，可知⑤处到其他各处的费用最小，因此，就经济因素而言物流中心选址于⑤处是最优选择。同时可从右侧矩阵看出从其他几处到达⑤处所经过的最短路径。

5 结束语

本文介绍了矩阵迭代法求最短路径问题，该方法与常用的Dijkstra算法相比，具有计算简单且计算量小的优点，能够在确定物流中心选址的同时显示出所经过路径，这是其他算法所不具备的突出优点，并以某轮毂产业园区为例对该方法的应用、特点进行了验证。为物流中心选址提供了新思路。

参考文献

[1]王炜等.城市交通规划理论及其应用[M].南京：东南大学出版社，1998.

[2]胡运权.运筹学基础及应用[M].哈尔滨：哈尔滨工业大学出版社，1992.

[3]李腊元，李春林.计算机网络技术[M].第二版.北京：国防工业出版社，2004.

[4]刘玉增.城市交通流分配的最优化方法[J].四川警官高等专科学校学报，Jun.2003，51-53.

[5]钟孝顺，陈祥宝.优化原理在公路工程中的应用[M].北京：人民交通出版社，1989.

[6]张志勇，匡兴华.最短路径算法在物流中心选址中的应用[J].物流技术，2004，（1）.