floyd最短路径算法在配送中心选址中的应用

《floyd最短路径算法在配送中心选址中的应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、Floyd最短路径算法在配送中心选址中的应用胡桔州(湖南商学院信息系，湖南长沙410205)摘要：以故少物流费用为故优目标的配送中心选址的定量技术颇多，英屮，故优化规划法及图论方法是研究热点.阐述了Hoyd全部顶点间最短路径算法选址的原理，并通过实例讨论了配送中心选址算法的步骤及MATLAB程序实现的全过程.关键词：Floyd最短路径算法；配送中心选址；最优化规划；MATLAB中图分类号：TP301.6文献标识码：AAnAlgorithmforDistributionCenterBasedontheFloyd-Shortest-Path

2、HUJu-zhou(InformationDepartment,HunanBusinessCollege,Changsha410205,PRC)Abstract：Thepaperdiscusseshowtodecidethedistributioncenterlocationattheleastlogisticscost・Firstly,theoptimizationprogrammingiscompareciwiththegraphtheoryandnetworkanalysis,andthenanalgorithmfordistri

3、butioncenterbasedontheFloyd・Shortest-Path,alongwithanapplicationexample»ispresented・Finally,aMATLABcodeisgiventoillustrateitscfficicncy.Keywords：floyd-shortest-path:distributioncenterlocation；optimizationprogramming；MATLAB配送中心是物流网络中最具有影响力的结点，是物流系统的重要基础设施.它不仅承担多种物流功能，而且越来

4、越多地执行指挥调度、信息处理等神经中枢的职能，是整个物流网络的核心所在，所以，合理选择配送中心对于物流系统的规划至关重要.通常，在配送中心及网点布局决策时要考虑众多影响因素.这导致配送中心的选址成为一个相当复杂的问题，往往要通过泄性与定量技术联合使用，运用多种方法才能获得最佳布局方案.笔者所指的配送中心的选址主要考虑经济因素，即如何使从配送中心到达其他地点所需物流总费用最少⑴.1配送中心选址的定量技术选择物流费用是由运输方式与运输距离决定的，其定量性较强，目前通常使用解析法、最优化规划方收稿日期：2004-03-12基金项目：湖南省教育

5、厅资助项目(03C204)作者简介：胡桔州(1965-),男，汉族，湖南桃江人，湖南商学院讲师.法、启发式方法、图论与网络分析方法等.(1)解析法.解析法通常是指物流地理重心方法.它根据距离、需求量、时间或者前三者的结合，以可选配送中心位置为因变量，用代数方法来求解配送中心的坐标.因其考虑因素较少，数学模型简单，所以主要适应于单配送中心选址问题.(2)最优化规划方法.它要求在一些特定的约束条件下，从许多可用的选择中挑选出一个最佳的方案.它是冃前应用最广泛的选址技术，其特点是能够获得较为精确的最优解，但对一些复杂问题要建立恰当的模型却比较

6、困难，或者模型太复杂，具有NP-Hard性质，存在着变量与约束条件数量的维数灾难.(3)启发式方法.此方法不是精确式算法，而是一种逐次逼近最优解的方法.虽然比最优化规划法计算简单，但不能保证最优.(4)图论与网络分析方法.图论是数学的一个分支，它以图为研究对象.图论中的图是由若干给定的点及连接两点的边所构成的图形.这种图形通常用点代表事物，用连接两点的边表示相应两个事物I、可具有某种特定关系.在配送屮心的选址问题屮，点表示可供选择的配送中心，而其间的连线(边)则表示物流费用.这种由顶点、边和某些数量指标组成的图，是客观世界的多层次、多结

7、构、多序列在人脑中的一种反映，能形彖、清晰地描述空间中的位置关系，可以定量处理许多问题.例如，由于约束条件(指系统或系统环境屮那些由于种种原因而不能改变的因素)的限制，配送中心选址的注意力只能放在特定的区域，同吋运输费用与运输距离呈非线性关系，所以，运用图论中的有关理论和方法解决配送中心选址问题具有一定的实际意义.2最短路径算法原理图论中的最短路径算法包括指定的顶点对之间的最短路径算法和全部顶点间的最短路径算法.前者可用于运输的合理化决策分析，而后者很适合于选择合理的配送中心，使得总的物流费用最少.2.1算法的基本思想全部顶点间最短路径

8、算法具有代表性的是1962年由福劳德(Floyd)提出的算法.它的主要思想是从代表任意2个顶点叫到的距离的带权邻接矩阵开始，每次插入一个顶点欣，然后将勺到y•间的己知最短路径与插入顶点％作为中间顶点(一条路