Ｆｌｏｙｄ最短路算法在服務網點設置問題中的應用

　　摘要：文章采用Floyd最短路算法求解服務網點設置問題，并提出以“最大服務最小距離”為標準選擇網絡中心，通過運用此方法解決建筑公司選擇總部的問題，顯示了這一算法在最佳服務網點設置問題中的有效運用，并大大拓展了此方法的應用領域。
　　關鍵詞：Floyd算法；服務網點設置問題；最短路
　　
　　一、引言
　　
　　服務網點設置問題就是在某一個給定的區(qū)域內，各網點位置已經確定的前提下，選擇一個網絡中心的最佳位置，使運輸最為方便，使網絡中心到其余各網點的距離最?。ɑ蜻\輸時間最少，或運輸費用最低）。例如在一個網絡中設置一所學校、醫(yī)院、消防站、購物中心，還有廠址選擇、總部選址、公司銷售中心選址問題等都屬于最佳服務網點設置問題。在服務網點設置問題中合理選擇網絡中心對于加快運輸速度、降低運輸成本及增加經濟效益都有極大影響。
　　對于服務網點設置問題，目前還沒有一種有效的解決方法，本文將此類問題轉化成圖論中的網絡模型，利用圖論中的Floyd最短路算法，并以“使最大服務距離達到最小”為標準來解決。
　　
　　二、服務網點設置問題的Floyd最短路解法
　　
　　指定頂點對間最短路算法已在電信、交通等領域中有廣泛的應用，而所有頂點間的最短路算法，雖然在物流配送中心選址問題中也有所應用，但求出任意兩點間的最短距離后并沒有給出一個明確標準來選擇中心。下面給出解決服務網點設置問題的解決方法。
　　首先將給出的實際問題轉化為網絡模型，畫出網絡圖，轉化成圖論中的最短路問題；然后利用Floyd最短路算法求出任意兩點之間的最短距離表；最后，采用“使最大服務距離達到最小”為標準，計算最短距離表中每行的最大距離的最小值，即
　　
　　 L所在行對應的點就是最佳服務點，也稱為網絡的中心。
　　（一）Floyd算法的基本思想
　　全部頂點間最短路徑算法具有代表性的是1962年由福勞德（Floyd）提出的。它的主要思想是從代表任意2個頂點Vi到Vj的距離的帶權鄰接矩陣開始，用cij表示從Vi到Vj的距離（費用、時間），每次插入一個頂點Vk，然后將vi到vj間的已知最短路徑與插入頂點Vk作為中間頂點（一條路徑中除始點和終點外的其他頂點）時可能產生的Vi到Vj路徑距離比較，取較小值以得到新的距離矩陣。如此循環(huán)迭代下去，依次構造出n個矩陣（或表格