姚裕華　勇　剛　張　卓

摘要:EXCEL在管理科學(xué)領(lǐng)域的應(yīng)用很多,如線性規(guī)劃、運輸問題、指派問題、網(wǎng)絡(luò)最優(yōu)化問題、項目管理、庫存管理、預(yù)測、排隊論和計算機仿真,等等。運用EXCEL建立模型,求解模型,能對管理者的決策提供很好支持。配送路線的制定和優(yōu)化問題在實際物流操作中有著廣泛的應(yīng)用,也是非常困難的問題,借助EXCEL工具來輔助制定和優(yōu)化配送路線,主要是對起點和終點相同的一類路徑規(guī)劃問題做出分析。

關(guān)鍵詞:配送路線;優(yōu)化;描述法;節(jié)約法;EXCEL

中圖分類號:O227文獻標識碼:A

Abstract: EXCEL has extensive use in management science, such as linear programming, transportation problem, distribute problem, network optimization, program management, inventory management, anticipate, queue theory and compute emulate etc. It's a good support to the decision of manager, using EXCEL to establish and solve models. The choosing and optimization of distribute route is very useful in logistics operation and also very difficult. In this text, we mostly use EXCEL to solve the problem of routing programming with same start and end point.

Key words: distributing route; optimizing; describling method; saving method; EXCEl

0引言

美國物流管理協(xié)會(Council of Logistics Management)把物流定義為迎合顧客需求而對原材料、半成品、產(chǎn)成品以及相關(guān)信息從產(chǎn)地到消費地高效率、低成本流動和存儲而進行的規(guī)劃、實施和控制過程。并且認為一個典型的物流系統(tǒng)組成要素包括:客戶服務(wù)、需求預(yù)測、分撥系統(tǒng)管理、庫存控制、物料搬運、定單處理、零配件和服務(wù)支持、工廠和倉庫選址、區(qū)位分析、采購、包裝、退貨處理、廢棄物處理、運輸管理、倉儲管理。從中我們可以看出運輸時是物流決策的關(guān)鍵所在,除了采購成本以外,一般來講,運輸成本比其他任何物流活動的成本所占的比重都高。其中配送路線的選擇和優(yōu)化是運輸決策中的一項重要決策。

盡管路線選擇問題種類繁多,但我們可以將其分為幾個基本類型:一是起點和終點不同的單一路徑規(guī)劃:二是多個起點和終點的路徑規(guī)劃:三是起點和終點相同的路徑規(guī)劃。

起點和終點不同的單一路徑規(guī)劃這類運輸路徑規(guī)劃問題可以通過特別設(shè)計的方法加以解決,最簡單最直接的方法就是最短路徑法;多個起點和終點的路徑規(guī)劃這類問題經(jīng)常發(fā)生在多個供應(yīng)商,工廠或倉庫服務(wù)于多個顧客的情況下,可以用一類特殊的線性規(guī)劃算法,即運輸方法來解決;起點和終點相同的路徑規(guī)劃這類問題在企業(yè)擁有自己的運輸工具時就相當普遍了。

在這篇文章里,我們將介紹起點和終點相同的路徑規(guī)劃的這類問題。

1提出問題

首先我們來看一個具體的問題,某物流公司有一配送中心(P)就有右圖形狀的配送路線。A～J表示收貨站,括號內(nèi)的數(shù)據(jù)為發(fā)送量(噸),路線上的數(shù)字表示道路距離(公里)。這時,為使行駛盡量少,應(yīng)該如何去求配送路線?假設(shè)能利用的車是2噸和4噸兩種,并限制車輛一次運行的初步距離在30公里內(nèi)。

該問題在起點和終點相同的路徑規(guī)劃的這類問題中具有代表性,這類問題的優(yōu)化方法有掃描法和節(jié)約法。

掃描法的步驟為:(1)在地圖或方格圖中確定所有站點的位置(含倉庫)。(2)至倉庫始沿任一方向外劃一條直線,沿順時針或逆時針方向旋轉(zhuǎn)該方向直到與某一站點相交?？紤]:如果在某線路上增加該站點,是否會超過車輛的載貨能力?如果沒有,繼續(xù)旋轉(zhuǎn)直線,直到與下一個站點相交,再次計算累計貨運量是否超過車輛的運載能力(先使用最大的車輛),如果超過就剔除最后的哪個站點,并確定路線。隨后,從不包含上一條線路上的站點開始,繼續(xù)旋轉(zhuǎn)直線以尋找新路線,繼續(xù)該過程直到所有站點都被安排到路線中。(3)排定各路線上每個站點的順序使行車距離最短,排序時可用“水滴法”或求解“流動推銷員”問題的任何算法。

節(jié)約法是由克拉克?懷特發(fā)現(xiàn)的,它能夠靈活地處理許多現(xiàn)實中的約束條件,對站點數(shù)量不大的問題能夠較快地算出結(jié)果,且結(jié)果與最優(yōu)解很接近,該方法能過同時確定路線和經(jīng)過各站點的順序。節(jié)約法的目標是使所有車輛的行使總里程最短,并進而為所有站點提供運輸?shù)能嚁?shù)最少。該方法首先假定每一個站點都由一輛虛擬的卡車提供服務(wù),隨后返回倉庫,如右圖所示。

這時的路線是最長的,下一步將兩個站點合并到同一條行車路線上,減少一輛運輸車,相應(yīng)地縮短運輸距離,不過合并一定要注意滿足約束條件。合并后縮短的距離減少了dAO+dOB-dAB。只要條件滿足就可以繼續(xù)合并,直到所有的站點的路線都完成。

2用EXCEL輔助解決問題

對于上面的具體問題的分析步驟如下:

第一步:繪出最短距離距陣圖,從配送網(wǎng)絡(luò)圖中計算出配送中心與收貨點及收貨點之間的最短距離矩陣:

用EXCEL的求解方法如下:

用FLOYD算法需要進行11步迭代計算,令該網(wǎng)絡(luò)圖的全矩陣為

Dd,當兩點間沒有直達路時,d為無窮大,這里令d=100足以解決問題。算法基本步驟為:

(1)輸入權(quán)矩陣D=D

(2)計算D=dk=1,2,…,11

其中,d=mind,d+d

(3)D=d中元素d就是從配送網(wǎng)絡(luò)圖中計算出配送中心與收貨點及收貨點之間的最短距離矩陣。

(4)D0為權(quán)矩陣,數(shù)據(jù)要自己輸入,D1到D11為每步迭代中產(chǎn)生的矩陣,D11為從配送網(wǎng)絡(luò)圖中計算出配送中心與收貨點及收貨點之間的最短距離矩陣,F0到F10為輔助矩陣,他們在表格中位子如下:

根據(jù)FLOYD算法,下面介紹用EXCEL的分析步驟:

(1)建立結(jié)構(gòu)。

Dii=0,…,11的結(jié)構(gòu)為:

Fii=0,…,10的結(jié)構(gòu)為:

(2)輸入權(quán)矩陣D0的數(shù)據(jù)。

(3)選中矩陣D1中B17單元格輸入公式“=IFB3>P3,P3,B3”,當鼠標移至單元格右下角時變成實心加號,此時按住左鍵,朝各個方向拖拉可以將整個矩陣用公式覆蓋,這時你可以點擊該矩陣內(nèi)的任一單元格,如單元格E21就會顯示公式“=IFE7>S7,S7,E7”。

if函數(shù)中有三項,第一項為邏輯運算式,如果它的值取true函數(shù)就返回第二項值,否則就返回第三項值,用以計算d=mind,d+d。

選中D1中的公式區(qū)B17∶L27,用Ctrl+C復(fù)制,然后用Ctrl+V將其中的公式粘貼到D2到D11的對應(yīng)公式區(qū)中。

(4)對輔助矩陣Fii=1,…,10,進行從F0到F10的依次計算。這里只介紹F0,其他的依此類推。

對于F0:

(a)先將D0的第一行的數(shù)值賦給F0的橫填充區(qū),將D0的第一行列的數(shù)值賦給F0的豎填充區(qū),可先賦一個值,然后進行拖拉;要是對于Fi,就要將Di的第i+1行和列的數(shù)據(jù)分別賦予Fi的橫填充區(qū)和豎填充區(qū)。

(b)在o2單元格中填入公式=n2+o1;要是對于Fi就要在對應(yīng)的單元格中填入公式=該單元格左邊的單元格

+該單元格上面的單元格。

(c)用模擬運算表進行求和運算:選中黑框內(nèi)區(qū)域。

在“數(shù)據(jù)”菜單中選擇“模擬運算表”項,會彈出下圖的對話框,將o2單元格左邊的單元格填入到“輸入引用行的單元格”,將o2單元格上邊的單元格填入到“輸入引用列的單元格”,然后按確定,這樣就得到矩陣F0;對于Fi可以對應(yīng)操作。

當從F0到F10都運算好之后,就會得到從配送網(wǎng)絡(luò)圖中計算出配送中心與收貨點及收貨點之間的最短距離矩陣,以上完成了第一步。

第二步:繪出節(jié)約里程項目圖,從最短距離矩陣中計算收貨點相互間的節(jié)約里程。將最短路矩陣的第一行和第一列復(fù)制到行豎填充區(qū)中,并在單元格B2內(nèi)填入公式,用模擬運算表進行求和運算的到下面表格:

然后將矩陣中的數(shù)據(jù)與最短距離矩陣D11中的數(shù)據(jù)對應(yīng)相減,就得到節(jié)約里程項目(圖中三角形部分)。

第三步:節(jié)約項目的分類,把節(jié)約項目有大到小順序排列。如下表:

第四步:組成配送路線,從節(jié)約項目表中,按節(jié)約里程大小的順序組成路線圖。

(1)初次解。

線路數(shù):10總行走距離:148公里車輛臺數(shù):2噸車10臺

(2)二次解。按節(jié)約里程由大到小的順序,連接A-B,A-J,B-C連接線。

線路數(shù):7總行走距離:109公里車輛臺數(shù):2噸車6臺4噸車1臺

(3)三次解。其次,節(jié)約里程最大的是C-D和D-E。C-D和D-E兩者都有可能與二次解的線路甲相連接,但由于甲的車輛載重與行走距離有限,不能再增加收貨點,為此,略去C-D而連接D-E。

線路數(shù):6總行走距離:99公里車輛臺數(shù):2噸車5臺4噸車1臺

(4)四次解。接下來節(jié)約里程最大的是A-E和E-F。由于A已組合在完成的線路甲中,所以略去A-E而將E-F連接在線路乙上。

線路數(shù):5總行走距離:90公里車輛臺數(shù):2噸車3臺4噸車2臺

(5)五次解。按上面的方法繼續(xù)即得到五次解。

線路數(shù):4總行走距離:85公里車輛臺數(shù):2噸車2臺4噸車2臺

(6)六次解。按上面的方法繼續(xù)即得到6次解。

線路甲:4噸車總行走距離:27公里裝載量:3.6噸

線路乙:4噸車總行走距離:30公里裝載量:3.9噸

線路丙:2噸車總行走距離:23公里裝載量:1.3噸

3結(jié)束語

在這篇文章里,我們介紹了起點和終點相同的路徑規(guī)劃的這類問題。用EXCEL工具來輔助配送路線的選擇問題的決策,能夠達到比較好的效果。EXCEL在管理科學(xué)領(lǐng)域的應(yīng)用很多,如線性規(guī)劃、運輸問題、指派問題、網(wǎng)絡(luò)最優(yōu)化問題、項目管理、庫存管理、預(yù)測、排隊論和計算機仿真,等等。運用EXCEL建立模型,求解模型,能對管理者的決策提供很好支持。

參考文獻:

[1] Ronald H. Ballou(美). 企業(yè)物流管理——供應(yīng)鏈的規(guī)劃、組織和控制[M]. 王曉東,胡瑞娟,等譯. 北京:機械工業(yè)出版社,2002:145-197.

[2] 弗雷德里克?S?希利爾,馬克?S?希利爾,杰拉爾德?S?利伯曼(美). 數(shù)據(jù)、模型與決策[M]. 任建標,譯. 北京:中國財政經(jīng)濟出版社,2001.

[3] 胡運權(quán). 運籌學(xué)教程[M]. 北京:清華大學(xué)出版社,2000:241-242.

[4] 晶辰工作室. Excel2000預(yù)測分析和目標求解實例指南[M]. 北京:電子工業(yè)出版社,2001:1-24.