Ｆｌｏｙｄ最短路算法在服务网点设置问题中的应用

　　摘要：文章采用Floyd最短路算法求解服务网点设置问题，并提出以“最大服务最小距离”为标准选择网络中心，通过运用此方法解决建筑公司选择总部的问题，显示了这一算法在最佳服务网点设置问题中的有效运用，并大大拓展了此方法的应用领域。
　　关键词：Floyd算法；服务网点设置问题；最短路
　　
　　一、引言
　　
　　服务网点设置问题就是在某一个给定的区域内，各网点位置已经确定的前提下，选择一个网络中心的最佳位置，使运输最为方便，使网络中心到其余各网点的距离最小（或运输时间最少，或运输费用最低）。例如在一个网络中设置一所学校、医院、消防站、购物中心，还有厂址选择、总部选址、公司销售中心选址问题等都属于最佳服务网点设置问题。在服务网点设置问题中合理选择网络中心对于加快运输速度、降低运输成本及增加经济效益都有极大影响。
　　对于服务网点设置问题，目前还没有一种有效的解决方法，本文将此类问题转化成图论中的网络模型，利用图论中的Floyd最短路算法，并以“使最大服务距离达到最小”为标准来解决。
　　
　　二、服务网点设置问题的Floyd最短路解法
　　
　　指定顶点对间最短路算法已在电信、交通等领域中有广泛的应用，而所有顶点间的最短路算法，虽然在物流配送中心选址问题中也有所应用，但求出任意两点间的最短距离后并没有给出一个明确标准来选择中心。下面给出解决服务网点设置问题的解决方法。
　　首先将给出的实际问题转化为网络模型，画出网络图，转化成图论中的最短路问题；然后利用Floyd最短路算法求出任意两点之间的最短距离表；最后，采用“使最大服务距离达到最小”为标准，计算最短距离表中每行的最大距离的最小值，即
　　
　　 L所在行对应的点就是最佳服务点，也称为网络的中心。
　　（一）Floyd算法的基本思想
　　全部顶点间最短路径算法具有代表性的是1962年由福劳德（Floyd）提出的。它的主要思想是从代表任意2个顶点Vi到Vj的距离的带权邻接矩阵开始，用cij表示从Vi到Vj的距离（费用、时间），每次插入一个顶点Vk，然后将vi到vj间的已知最短路径与插入顶点Vk作为中间顶点（一条路径中除始点和终点外的其他顶点）时可能产生的Vi到Vj路径距离比较，取较小值以得到新的距离矩阵。如此循环迭代下去，依次构造出n个矩阵（或表格