floyd最短路徑算法在配送中心選址中的應(yīng)用

《floyd最短路徑算法在配送中心選址中的應(yīng)用》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、Floyd最短路徑算法在配送中心選址中的應(yīng)用胡桔州(湖南商學(xué)院信息系，湖南長沙410205)摘要：以故少物流費用為故優(yōu)目標(biāo)的配送中心選址的定量技術(shù)頗多，英屮，故優(yōu)化規(guī)劃法及圖論方法是研究熱點.闡述了Hoyd全部頂點間最短路徑算法選址的原理，并通過實例討論了配送中心選址算法的步驟及MATLAB程序?qū)崿F(xiàn)的全過程.關(guān)鍵詞：Floyd最短路徑算法；配送中心選址；最優(yōu)化規(guī)劃；MATLAB中圖分類號：TP301.6文獻(xiàn)標(biāo)識碼：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配送中心是物流網(wǎng)絡(luò)中最具有影響力的結(jié)點，是物流系統(tǒng)的重要基礎(chǔ)設(shè)施.它不僅承擔(dān)多種物流功能，而且越來

4、越多地執(zhí)行指揮調(diào)度、信息處理等神經(jīng)中樞的職能，是整個物流網(wǎng)絡(luò)的核心所在，所以，合理選擇配送中心對于物流系統(tǒng)的規(guī)劃至關(guān)重要.通常，在配送中心及網(wǎng)點布局決策時要考慮眾多影響因素.這導(dǎo)致配送中心的選址成為一個相當(dāng)復(fù)雜的問題，往往要通過泄性與定量技術(shù)聯(lián)合使用，運用多種方法才能獲得最佳布局方案.筆者所指的配送中心的選址主要考慮經(jīng)濟因素，即如何使從配送中心到達(dá)其他地點所需物流總費用最少⑴.1配送中心選址的定量技術(shù)選擇物流費用是由運輸方式與運輸距離決定的，其定量性較強，目前通常使用解析法、最優(yōu)化規(guī)劃方收稿日期：2004-03-12基金項目：湖南省教育

5、廳資助項目(03C204)作者簡介：胡桔州(1965-),男，漢族，湖南桃江人，湖南商學(xué)院講師.法、啟發(fā)式方法、圖論與網(wǎng)絡(luò)分析方法等.(1)解析法.解析法通常是指物流地理重心方法.它根據(jù)距離、需求量、時間或者前三者的結(jié)合，以可選配送中心位置為因變量，用代數(shù)方法來求解配送中心的坐標(biāo).因其考慮因素較少，數(shù)學(xué)模型簡單，所以主要適應(yīng)于單配送中心選址問題.(2)最優(yōu)化規(guī)劃方法.它要求在一些特定的約束條件下，從許多可用的選擇中挑選出一個最佳的方案.它是冃前應(yīng)用最廣泛的選址技術(shù)，其特點是能夠獲得較為精確的最優(yōu)解，但對一些復(fù)雜問題要建立恰當(dāng)?shù)哪Ｐ蛥s比較

6、困難，或者模型太復(fù)雜，具有NP-Hard性質(zhì)，存在著變量與約束條件數(shù)量的維數(shù)災(zāi)難.(3)啟發(fā)式方法.此方法不是精確式算法，而是一種逐次逼近最優(yōu)解的方法.雖然比最優(yōu)化規(guī)劃法計算簡單，但不能保證最優(yōu).(4)圖論與網(wǎng)絡(luò)分析方法.圖論是數(shù)學(xué)的一個分支，它以圖為研究對象.圖論中的圖是由若干給定的點及連接兩點的邊所構(gòu)成的圖形.這種圖形通常用點代表事物，用連接兩點的邊表示相應(yīng)兩個事物I、可具有某種特定關(guān)系.在配送屮心的選址問題屮，點表示可供選擇的配送中心，而其間的連線(邊)則表示物流費用.這種由頂點、邊和某些數(shù)量指標(biāo)組成的圖，是客觀世界的多層次、多結(jié)

7、構(gòu)、多序列在人腦中的一種反映，能形彖、清晰地描述空間中的位置關(guān)系，可以定量處理許多問題.例如，由于約束條件(指系統(tǒng)或系統(tǒng)環(huán)境屮那些由于種種原因而不能改變的因素)的限制，配送中心選址的注意力只能放在特定的區(qū)域，同吋運輸費用與運輸距離呈非線性關(guān)系，所以，運用圖論中的有關(guān)理論和方法解決配送中心選址問題具有一定的實際意義.2最短路徑算法原理圖論中的最短路徑算法包括指定的頂點對之間的最短路徑算法和全部頂點間的最短路徑算法.前者可用于運輸?shù)暮侠砘瘺Q策分析，而后者很適合于選擇合理的配送中心，使得總的物流費用最少.2.1算法的基本思想全部頂點間最短路徑

8、算法具有代表性的是1962年由福勞德(Floyd)提出的算法.它的主要思想是從代表任意2個頂點叫到的距離的帶權(quán)鄰接矩陣開始，每次插入一個頂點欣，然后將勺到y(tǒng)?間的己知最短路徑與插入頂點％作為中間頂點(一條路