论文部分内容阅读
摘要：文章采用Floyd最短路算法求解服务网点设置问题，并提出以“最大服务最小距离”为标准选择网络中心，通过运用此方法解决建筑公司选择总部的问题，显示了这一算法在最佳服务网点设置问题中的有效运用，并大大拓展了此方法的应用领域。
关键词：Floyd算法；服务网点设置问题；最短路
一、引言
服务网点设置问题就是在某一个给定的区域内，各网点位置已经确定的前提下，选择一个网络中心的最佳位置，使运输最为方便，使网络中心到其余各网点的距离最小（或运输时间最少，或运输费用最低）。例如在一个网络中设置一所学校、医院、消防站、购物中心，还有厂址选择、总部选址、公司销售中心选址问题等都属于最佳服务网点设置问题。在服务网点设置问题中合理选择网络中心对于加快运输速度、降低运输成本及增加经济效益都有极大影响。
对于服务网点设置问题，目前还没有一种有效的解决方法，本文将此类问题转化成图论中的网络模型，利用图论中的Floyd最短路算法，并以“使最大服务距离达到最小”为标准来解决。
二、服务网点设置问题的Floyd最短路解法
指定顶点对间最短路算法已在电信、交通等领域中有广泛的应用，而所有顶点间的最短路算法，虽然在物流配送中心选址问题中也有所应用，但求出任意两点间的最短距离后并没有给出一个明确标准来选择中心。下面给出解决服务网点设置问题的解决方法。
首先将给出的实际问题转化为网络模型，画出网络图，转化成图论中的最短路问题；然后利用Floyd最短路算法求出任意两点之间的最短距离表；最后，采用“使最大服务距离达到最小”为标准，计算最短距离表中每行的最大距离的最小值，即
L所在行对应的点就是最佳服务点，也称为网络的中心。
（一）Floyd算法的基本思想
全部顶点间最短路径算法具有代表性的是1962年由福劳德（Floyd）提出的。它的主要思想是从代表任意2个顶点Vi到Vj的距离的带权邻接矩阵开始，用cij表示从Vi到Vj的距离（费用、时间），每次插入一个顶点Vk，然后将vi到vj间的已知最短路径与插入顶点Vk作为中间顶点（一条路径中除始点和终点外的其他顶点）时可能产生的Vi到Vj路径距离比较，取较小值以得到新的距离矩阵。如此循环迭代下去，依次构造出n个矩阵（或表格）L1,L2,...Ln，当所有的顶点均作为任意 2 个顶点Vi到Vj中间顶点时得到的最后的带权邻接矩阵Ln反映了所有顶点对之间的最短距离信息，成为图G的距离矩阵。
（二）Floyd算法实现原理
对一个有n个顶点的图G，将顶点用n个整数（从1到n）进行编号，把G的带权邻接矩阵W（从1到n）进行编号，把G的带权邻接矩阵W作为距离的初值。
Floyd算法基本步骤如下：
第一步：写出Vi一步到达Vj的距离矩阵：
L1＝((1)ij)
L1也是一步到达的最短距离矩阵。如果Vi与Vj之间没有边关联，则令cij=+∞
第二步：计算两步最短距离
设Vi到Vj经过一个中间点Vr两步到达Vj，则Vi到Vj的最短距离为
第三步：计算k步最短距离矩阵
设Vi经过中间点Vr到达Vj，Vi经过k-1步到达点Vr的最短距离为L(k-1)ir，Vr经过k-1步到达Vj的最短距离为
L(k)ir=min{L(k-1)ir+L(k-1)rj}②
最短距离矩阵记为Lk=(L(k)ij)。
第四步：比较矩阵Lk与Lk-1
当Lk=Lk-1时得到任意两点间的最短距离矩阵Lk。设图中点的个数为n且cij≥0，迭代次数由式③估计得到。
2k-1-1≤n-2≤2k-1
三、实证案例
一个建筑公司总部拥有的6个最新建筑工程项目遍布于一个三个县区大的区域内，有些建筑工地距总部远达40公里以上。总部与工地之间需要每天几次运送员工、设备和补给，与运输活动有关的成本相当高，为了降低运输成本、加快运输速度，现在公司决定从这几个工地所在地中选择一个作为总部，使运输最为方便，应怎样选择。
已知这六个工地所在地分别为V1、V2、V3、V4、V5、V6，V1到V2、V3、V4、V5、V6的距离分别为25.5、27、16.5、24、18公里，V2到V3、V4、V6的距离分别为9、13.5、42、公里，V4到V5的距离分别为36公里，V5到V6的距离分别为27公里。
解：首先画出网络图，对于任何一个指定的建筑工地，它与其余工地之间的运输路线可被看成一个由小路、街道和公路组成的网络。网络的节点代指建筑工地所在地，那些小路、街道及公路看作网络上的线段，又已知可以相通的任两工地间的距离，由此画出网络图如图1所示，图1展示的网络描述了来往于公司总部6最新建筑工地的运输路线：
其次，根据Floyd最短路算法求得任意两工地间的最短距离表。
最后，由最短距离表中的最大距离最小值，从而得到设置总部的最佳位置。
对表1中每行取最大值再对最后一列取最小值，见表（2），最后一列最小值为8.5，位于第一行，则V1为网络的中心，即选择工地V1所在地作为总部可使运输最为方便。
四、结束语
在许多服务网点设置问题中并不是以距离为标准，如果每个点还有一个权数，例如一个网点的人数、需要运送的物质数量、产量等，在这些情况下也可以用Floyd算法，但是要将标准改为“最大服务总运量最小”，即解法中计算步骤的第二步的最大距离改为总运量，总运量的最小值对应的点就是最佳服务点。
本文通过Floyd算法在服务网点设置问题中的有效运用，大大拓展了此方法的应用范围。对于环节较多的过程，对应的图中的节点就比较多，求解的复杂度就会很大，若利用计算机高级语言程序来实现，最短路算法在服务网点设置问题中会得到更好的应用。
参考文献：
1、Gamache M,Grimard R,Cohen P.A shortest-path algorithm for solving the fleet management problem in underground mines[J].European Journal of Operational Research,2005(2).
2、Zhan F B.Three fastest shortest path algorithms on real road networks[J].Journal of Geographic Information and Decision Analysis,1997(1).
3、胡桔州.Floyd最短路径算法在配送中心选址中的应用[J].湖南农业大学学报,2004(4).
4、王俊珺.物流配送路线规划中的最短路径研究[J].农业网络信息,2007(5).
5、熊伟.运筹学[M].机械工业出版社,2005.
（作者单位：南京农业大学理学院）
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”
关键词：Floyd算法；服务网点设置问题；最短路
一、引言
服务网点设置问题就是在某一个给定的区域内，各网点位置已经确定的前提下，选择一个网络中心的最佳位置，使运输最为方便，使网络中心到其余各网点的距离最小（或运输时间最少，或运输费用最低）。例如在一个网络中设置一所学校、医院、消防站、购物中心，还有厂址选择、总部选址、公司销售中心选址问题等都属于最佳服务网点设置问题。在服务网点设置问题中合理选择网络中心对于加快运输速度、降低运输成本及增加经济效益都有极大影响。
对于服务网点设置问题，目前还没有一种有效的解决方法，本文将此类问题转化成图论中的网络模型，利用图论中的Floyd最短路算法，并以“使最大服务距离达到最小”为标准来解决。
二、服务网点设置问题的Floyd最短路解法
指定顶点对间最短路算法已在电信、交通等领域中有广泛的应用，而所有顶点间的最短路算法，虽然在物流配送中心选址问题中也有所应用，但求出任意两点间的最短距离后并没有给出一个明确标准来选择中心。下面给出解决服务网点设置问题的解决方法。
首先将给出的实际问题转化为网络模型，画出网络图，转化成图论中的最短路问题；然后利用Floyd最短路算法求出任意两点之间的最短距离表；最后，采用“使最大服务距离达到最小”为标准，计算最短距离表中每行的最大距离的最小值，即
L所在行对应的点就是最佳服务点，也称为网络的中心。
（一）Floyd算法的基本思想
全部顶点间最短路径算法具有代表性的是1962年由福劳德（Floyd）提出的。它的主要思想是从代表任意2个顶点Vi到Vj的距离的带权邻接矩阵开始，用cij表示从Vi到Vj的距离（费用、时间），每次插入一个顶点Vk，然后将vi到vj间的已知最短路径与插入顶点Vk作为中间顶点（一条路径中除始点和终点外的其他顶点）时可能产生的Vi到Vj路径距离比较，取较小值以得到新的距离矩阵。如此循环迭代下去，依次构造出n个矩阵（或表格）L1,L2,...Ln，当所有的顶点均作为任意 2 个顶点Vi到Vj中间顶点时得到的最后的带权邻接矩阵Ln反映了所有顶点对之间的最短距离信息，成为图G的距离矩阵。
（二）Floyd算法实现原理
对一个有n个顶点的图G，将顶点用n个整数（从1到n）进行编号，把G的带权邻接矩阵W（从1到n）进行编号，把G的带权邻接矩阵W作为距离的初值。
Floyd算法基本步骤如下：
第一步：写出Vi一步到达Vj的距离矩阵：
L1＝((1)ij)
L1也是一步到达的最短距离矩阵。如果Vi与Vj之间没有边关联，则令cij=+∞
第二步：计算两步最短距离
设Vi到Vj经过一个中间点Vr两步到达Vj，则Vi到Vj的最短距离为
第三步：计算k步最短距离矩阵
设Vi经过中间点Vr到达Vj，Vi经过k-1步到达点Vr的最短距离为L(k-1)ir，Vr经过k-1步到达Vj的最短距离为
L(k)ir=min{L(k-1)ir+L(k-1)rj}②
最短距离矩阵记为Lk=(L(k)ij)。
第四步：比较矩阵Lk与Lk-1
当Lk=Lk-1时得到任意两点间的最短距离矩阵Lk。设图中点的个数为n且cij≥0，迭代次数由式③估计得到。
2k-1-1≤n-2≤2k-1
三、实证案例
一个建筑公司总部拥有的6个最新建筑工程项目遍布于一个三个县区大的区域内，有些建筑工地距总部远达40公里以上。总部与工地之间需要每天几次运送员工、设备和补给，与运输活动有关的成本相当高，为了降低运输成本、加快运输速度，现在公司决定从这几个工地所在地中选择一个作为总部，使运输最为方便，应怎样选择。
已知这六个工地所在地分别为V1、V2、V3、V4、V5、V6，V1到V2、V3、V4、V5、V6的距离分别为25.5、27、16.5、24、18公里，V2到V3、V4、V6的距离分别为9、13.5、42、公里，V4到V5的距离分别为36公里，V5到V6的距离分别为27公里。
解：首先画出网络图，对于任何一个指定的建筑工地，它与其余工地之间的运输路线可被看成一个由小路、街道和公路组成的网络。网络的节点代指建筑工地所在地，那些小路、街道及公路看作网络上的线段，又已知可以相通的任两工地间的距离，由此画出网络图如图1所示，图1展示的网络描述了来往于公司总部6最新建筑工地的运输路线：
其次，根据Floyd最短路算法求得任意两工地间的最短距离表。
最后，由最短距离表中的最大距离最小值，从而得到设置总部的最佳位置。
对表1中每行取最大值再对最后一列取最小值，见表（2），最后一列最小值为8.5，位于第一行，则V1为网络的中心，即选择工地V1所在地作为总部可使运输最为方便。
四、结束语
在许多服务网点设置问题中并不是以距离为标准，如果每个点还有一个权数，例如一个网点的人数、需要运送的物质数量、产量等，在这些情况下也可以用Floyd算法，但是要将标准改为“最大服务总运量最小”，即解法中计算步骤的第二步的最大距离改为总运量，总运量的最小值对应的点就是最佳服务点。
本文通过Floyd算法在服务网点设置问题中的有效运用，大大拓展了此方法的应用范围。对于环节较多的过程，对应的图中的节点就比较多，求解的复杂度就会很大，若利用计算机高级语言程序来实现，最短路算法在服务网点设置问题中会得到更好的应用。
参考文献：
1、Gamache M,Grimard R,Cohen P.A shortest-path algorithm for solving the fleet management problem in underground mines[J].European Journal of Operational Research,2005(2).
2、Zhan F B.Three fastest shortest path algorithms on real road networks[J].Journal of Geographic Information and Decision Analysis,1997(1).
3、胡桔州.Floyd最短路径算法在配送中心选址中的应用[J].湖南农业大学学报,2004(4).
4、王俊珺.物流配送路线规划中的最短路径研究[J].农业网络信息,2007(5).
5、熊伟.运筹学[M].机械工业出版社,2005.
（作者单位：南京农业大学理学院）
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”