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