物流配送網絡優(yōu)化分析及最短路徑算法

　　摘要：文中根據物流配送網絡問題的特點和要求，對物流配送網絡的目標決策、約束條件、績效測度，配送網絡中Excel優(yōu)化模型進行了探討，并對常見的單源有多條線路可以選擇的單個用戶配送需求問題構建了最短路配送網絡模型，然后應用Excel建模并對最短路問題給出了求解算法。
　　關鍵詞：配送網絡 優(yōu)化探討 最短路 算法
　　中圖分類號：F713.32 文獻標識碼：A
　　
　　一、前言
　　
　　 隨著世界經濟的快速發(fā)展和現(xiàn)代科學技術的進步，物流業(yè)作為國民經濟中的新興產業(yè)正在全球范圍內迅速成長。物流業(yè)的發(fā)展程度已經成為衡量一個國家現(xiàn)代化程度和綜合國力的重要標志之一，被喻為促進經濟增長的“加速器”和“第三利潤源泉”。配送作為物流系統(tǒng)的重要組成部分，從開發(fā)順序和開發(fā)程度上都占有重要的地位，是物流業(yè)中最具潛能、最富活力、最有前景的發(fā)展領域。
　　
　　二、配送網絡中Excel優(yōu)化模型的本質
　　
　　Excel作為Office辦公軟件的套件之一。Excel除了應用在機關辦公日常的報表處理外，還有另外一個強大的功能就是Excel軟件包在企業(yè)管理中的管理決策和優(yōu)化決策應用。
　　 線性規(guī)劃問題的建模與結果分析有助于配送中心的管理者作出決策，這就意味著建立的模型不只是找到問題的解，更主要的是必須準確地從管理的角度出發(fā)，從管理角度說明問題、反映問題。搜尋的模型參數(shù)，確定的績效測度和約束條件都是現(xiàn)實、客觀的，是管理者實用和適用的，是管理視角的反映。這樣的求解結果才能符合配送活動的實際，具有操作性，使得Excel軟件在配送系統(tǒng)中真正實現(xiàn)它的價值，為配送中心創(chuàng)造效益。
　　
　　三、最短路問題描述及算法
　　
　　 在物流配送活動中，主要是把一批貨物從配送中心或者倉庫運送到一個或多個非固定客戶的接貨處。這些客戶坐落的地點、配送時間和需求的數(shù)量大多不盡相同。通常配送中心或者倉庫與客戶之間有多條運輸路線可以選擇。如果配送中心不進行運輸路線的合理規(guī)劃，往往會出現(xiàn)不合理運輸現(xiàn)象，如迂回運輸、重復運輸、重復裝卸等。不合理運輸會造成運輸成本上升，還會導致服務水平的下降。因此確定合理的配送路線，從而使運輸成本降低的同時使服務水平得到改善是物流配送管理工作的一項重要內容。
　　 假如某客戶急需一些貨物，從配送中心到用戶的距離較遠，且有多條路線可以選擇，從配送中心到該客戶的各條路線和相互之間距離如圖1所示。則配送中心需要作出的決策是如何選擇配送路線使得總運輸距離最短，同時既能滿足客戶對時間的需求，又能滿足配送中心節(jié)約成本的要求。下面對最短路問題進行假設和描述。
　　
　　 圖2－1給出了最短路問題的網絡模型。圖中圓圈表示配送網絡的節(jié)點，即A、B、C、D、E、F、G、H表示路線節(jié)點；O是“源”，在這里表示倉庫；T是“目標地”，表示用戶所在地。在網絡圖中，連接節(jié)點的連線叫做“邊”，表示行進可以朝著兩個節(jié)點之間的任一方向。連線旁邊的數(shù)字表示兩個節(jié)點間的距離，單位為公里。
　　 對上述網絡最短路問題求解的算法很多，目前公認的最好算法是E.W.Dijkstra于1959年提出的，Dijkstra算法的主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。
　　該網絡的最短路問題可以理解為配送中心是源，產生流量為1的流，代表此次行程的開始；客戶所在地是目的地，吸收流量為1的流，代表此次行程的結束。可變單元格若出現(xiàn)了流量1，表示了對應的路線被選中；反之，0則此路線表示沒有被選中。
　　首先建立模型，確定約束條件和績效測度。 Excel表格1
　　
　　其次規(guī)劃求解，點擊工具欄中“規(guī)劃求解”按鈕，輸入相應的選項。在“等于”選項中點擊“最小值”；限制條件：節(jié)點（F2:F11）＝供給需求（I2:I11）；因為這是一種特殊的線性規(guī)劃問題，在選項中選擇“線性規(guī)劃”和“非負”條件，點擊“確定”即可得出Excel表格2所示的優(yōu)化結果：Excel表格2
　　
　　
　　結果顯示：從Excel表格2可以看出，此次配送任務選擇的路線是：配送中心—A—B—E—F—用戶，此時配送路徑最短，最短距離為19公里。
　　 作者單位：河南交通職業(yè)技術學院
　　
　　參考文獻：
　　[1] 任建標.數(shù)據、模型與決策[M] . 北京：中國財政經濟出版社，2004.89-95.
　　[2]胡列格.物流運籌學[M]. 北京：電子工業(yè)出版社，2005.120-125.
　　[3]施建年.物流配送[M].北京：人民交通出版社，2003.96-103.
　　[4]