姚裕華 勇 剛 張 卓
摘要:EXCEL在管理科學(xué)領(lǐng)域的應(yīng)用很多,如線性規(guī)劃、運(yùn)輸問(wèn)題、指派問(wèn)題、網(wǎng)絡(luò)最優(yōu)化問(wèn)題、項(xiàng)目管理、庫(kù)存管理、預(yù)測(cè)、排隊(duì)論和計(jì)算機(jī)仿真,等等。運(yùn)用EXCEL建立模型,求解模型,能對(duì)管理者的決策提供很好支持。配送路線的制定和優(yōu)化問(wèn)題在實(shí)際物流操作中有著廣泛的應(yīng)用,也是非常困難的問(wèn)題,借助EXCEL工具來(lái)輔助制定和優(yōu)化配送路線,主要是對(duì)起點(diǎn)和終點(diǎn)相同的一類路徑規(guī)劃問(wèn)題做出分析。
關(guān)鍵詞:配送路線;優(yōu)化;描述法;節(jié)約法;EXCEL
中圖分類號(hào):O227文獻(xiàn)標(biāo)識(shí)碼: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引言
美國(guó)物流管理協(xié)會(huì)(Council of Logistics Management)把物流定義為迎合顧客需求而對(duì)原材料、半成品、產(chǎn)成品以及相關(guān)信息從產(chǎn)地到消費(fèi)地高效率、低成本流動(dòng)和存儲(chǔ)而進(jìn)行的規(guī)劃、實(shí)施和控制過(guò)程。并且認(rèn)為一個(gè)典型的物流系統(tǒng)組成要素包括:客戶服務(wù)、需求預(yù)測(cè)、分撥系統(tǒng)管理、庫(kù)存控制、物料搬運(yùn)、定單處理、零配件和服務(wù)支持、工廠和倉(cāng)庫(kù)選址、區(qū)位分析、采購(gòu)、包裝、退貨處理、廢棄物處理、運(yùn)輸管理、倉(cāng)儲(chǔ)管理。從中我們可以看出運(yùn)輸時(shí)是物流決策的關(guān)鍵所在,除了采購(gòu)成本以外,一般來(lái)講,運(yùn)輸成本比其他任何物流活動(dòng)的成本所占的比重都高。其中配送路線的選擇和優(yōu)化是運(yùn)輸決策中的一項(xiàng)重要決策。
盡管路線選擇問(wèn)題種類繁多,但我們可以將其分為幾個(gè)基本類型:一是起點(diǎn)和終點(diǎn)不同的單一路徑規(guī)劃:二是多個(gè)起點(diǎn)和終點(diǎn)的路徑規(guī)劃:三是起點(diǎn)和終點(diǎn)相同的路徑規(guī)劃。
起點(diǎn)和終點(diǎn)不同的單一路徑規(guī)劃這類運(yùn)輸路徑規(guī)劃問(wèn)題可以通過(guò)特別設(shè)計(jì)的方法加以解決,最簡(jiǎn)單最直接的方法就是最短路徑法;多個(gè)起點(diǎn)和終點(diǎn)的路徑規(guī)劃這類問(wèn)題經(jīng)常發(fā)生在多個(gè)供應(yīng)商,工廠或倉(cāng)庫(kù)服務(wù)于多個(gè)顧客的情況下,可以用一類特殊的線性規(guī)劃算法,即運(yùn)輸方法來(lái)解決;起點(diǎn)和終點(diǎn)相同的路徑規(guī)劃這類問(wèn)題在企業(yè)擁有自己的運(yùn)輸工具時(shí)就相當(dāng)普遍了。
在這篇文章里,我們將介紹起點(diǎn)和終點(diǎn)相同的路徑規(guī)劃的這類問(wèn)題。
1提出問(wèn)題
首先我們來(lái)看一個(gè)具體的問(wèn)題,某物流公司有一配送中心(P)就有右圖形狀的配送路線。A~J表示收貨站,括號(hào)內(nèi)的數(shù)據(jù)為發(fā)送量(噸),路線上的數(shù)字表示道路距離(公里)。這時(shí),為使行駛盡量少,應(yīng)該如何去求配送路線?假設(shè)能利用的車是2噸和4噸兩種,并限制車輛一次運(yùn)行的初步距離在30公里內(nèi)。
該問(wèn)題在起點(diǎn)和終點(diǎn)相同的路徑規(guī)劃的這類問(wèn)題中具有代表性,這類問(wèn)題的優(yōu)化方法有掃描法和節(jié)約法。
掃描法的步驟為:(1)在地圖或方格圖中確定所有站點(diǎn)的位置(含倉(cāng)庫(kù))。(2)至倉(cāng)庫(kù)始沿任一方向外劃一條直線,沿順時(shí)針或逆時(shí)針?lè)较蛐D(zhuǎn)該方向直到與某一站點(diǎn)相交。考慮:如果在某線路上增加該站點(diǎn),是否會(huì)超過(guò)車輛的載貨能力?如果沒(méi)有,繼續(xù)旋轉(zhuǎn)直線,直到與下一個(gè)站點(diǎn)相交,再次計(jì)算累計(jì)貨運(yùn)量是否超過(guò)車輛的運(yùn)載能力(先使用最大的車輛),如果超過(guò)就剔除最后的哪個(gè)站點(diǎn),并確定路線。隨后,從不包含上一條線路上的站點(diǎn)開(kāi)始,繼續(xù)旋轉(zhuǎn)直線以尋找新路線,繼續(xù)該過(guò)程直到所有站點(diǎn)都被安排到路線中。(3)排定各路線上每個(gè)站點(diǎn)的順序使行車距離最短,排序時(shí)可用“水滴法”或求解“流動(dòng)推銷員”問(wèn)題的任何算法。
節(jié)約法是由克拉克?懷特發(fā)現(xiàn)的,它能夠靈活地處理許多現(xiàn)實(shí)中的約束條件,對(duì)站點(diǎn)數(shù)量不大的問(wèn)題能夠較快地算出結(jié)果,且結(jié)果與最優(yōu)解很接近,該方法能過(guò)同時(shí)確定路線和經(jīng)過(guò)各站點(diǎn)的順序。節(jié)約法的目標(biāo)是使所有車輛的行使總里程最短,并進(jìn)而為所有站點(diǎn)提供運(yùn)輸?shù)能嚁?shù)最少。該方法首先假定每一個(gè)站點(diǎn)都由一輛虛擬的卡車提供服務(wù),隨后返回倉(cāng)庫(kù),如右圖所示。
這時(shí)的路線是最長(zhǎng)的,下一步將兩個(gè)站點(diǎn)合并到同一條行車路線上,減少一輛運(yùn)輸車,相應(yīng)地縮短運(yùn)輸距離,不過(guò)合并一定要注意滿足約束條件。合并后縮短的距離減少了dAO+dOB-dAB。只要條件滿足就可以繼續(xù)合并,直到所有的站點(diǎn)的路線都完成。
2用EXCEL輔助解決問(wèn)題
對(duì)于上面的具體問(wèn)題的分析步驟如下:
第一步:繪出最短距離距陣圖,從配送網(wǎng)絡(luò)圖中計(jì)算出配送中心與收貨點(diǎn)及收貨點(diǎn)之間的最短距離矩陣:
用EXCEL的求解方法如下:
用FLOYD算法需要進(jìn)行11步迭代計(jì)算,令該網(wǎng)絡(luò)圖的全矩陣為
Dd,當(dāng)兩點(diǎn)間沒(méi)有直達(dá)路時(shí),d為無(wú)窮大,這里令d=100足以解決問(wèn)題。算法基本步驟為:
(1)輸入權(quán)矩陣D=D
(2)計(jì)算D=dk=1,2,…,11
其中,d=mind,d+d
(3)D=d中元素d就是從配送網(wǎng)絡(luò)圖中計(jì)算出配送中心與收貨點(diǎn)及收貨點(diǎn)之間的最短距離矩陣。
(4)D0為權(quán)矩陣,數(shù)據(jù)要自己輸入,D1到D11為每步迭代中產(chǎn)生的矩陣,D11為從配送網(wǎng)絡(luò)圖中計(jì)算出配送中心與收貨點(diǎn)及收貨點(diǎn)之間的最短距離矩陣,F0到F10為輔助矩陣,他們?cè)诒砀裰形蛔尤缦?
根據(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”,當(dāng)鼠標(biāo)移至單元格右下角時(shí)變成實(shí)心加號(hào),此時(shí)按住左鍵,朝各個(gè)方向拖拉可以將整個(gè)矩陣用公式覆蓋,這時(shí)你可以點(diǎn)擊該矩陣內(nèi)的任一單元格,如單元格E21就會(huì)顯示公式“=IFE7>S7,S7,E7”。
if函數(shù)中有三項(xiàng),第一項(xiàng)為邏輯運(yùn)算式,如果它的值取true函數(shù)就返回第二項(xiàng)值,否則就返回第三項(xiàng)值,用以計(jì)算d=mind,d+d。
選中D1中的公式區(qū)B17∶L27,用Ctrl+C復(fù)制,然后用Ctrl+V將其中的公式粘貼到D2到D11的對(duì)應(yīng)公式區(qū)中。
(4)對(duì)輔助矩陣Fii=1,…,10,進(jìn)行從F0到F10的依次計(jì)算。這里只介紹F0,其他的依此類推。
對(duì)于F0:
(a)先將D0的第一行的數(shù)值賦給F0的橫填充區(qū),將D0的第一行列的數(shù)值賦給F0的豎填充區(qū),可先賦一個(gè)值,然后進(jìn)行拖拉;要是對(duì)于Fi,就要將Di的第i+1行和列的數(shù)據(jù)分別賦予Fi的橫填充區(qū)和豎填充區(qū)。
(b)在o2單元格中填入公式=n2+o1;要是對(duì)于Fi就要在對(duì)應(yīng)的單元格中填入公式=該單元格左邊的單元格
+該單元格上面的單元格。
(c)用模擬運(yùn)算表進(jìn)行求和運(yùn)算:選中黑框內(nèi)區(qū)域。
在“數(shù)據(jù)”菜單中選擇“模擬運(yùn)算表”項(xiàng),會(huì)彈出下圖的對(duì)話框,將o2單元格左邊的單元格填入到“輸入引用行的單元格”,將o2單元格上邊的單元格填入到“輸入引用列的單元格”,然后按確定,這樣就得到矩陣F0;對(duì)于Fi可以對(duì)應(yīng)操作。
當(dāng)從F0到F10都運(yùn)算好之后,就會(huì)得到從配送網(wǎng)絡(luò)圖中計(jì)算出配送中心與收貨點(diǎn)及收貨點(diǎn)之間的最短距離矩陣,以上完成了第一步。
第二步:繪出節(jié)約里程項(xiàng)目圖,從最短距離矩陣中計(jì)算收貨點(diǎn)相互間的節(jié)約里程。將最短路矩陣的第一行和第一列復(fù)制到行豎填充區(qū)中,并在單元格B2內(nèi)填入公式,用模擬運(yùn)算表進(jìn)行求和運(yùn)算的到下面表格:
然后將矩陣中的數(shù)據(jù)與最短距離矩陣D11中的數(shù)據(jù)對(duì)應(yīng)相減,就得到節(jié)約里程項(xiàng)目(圖中三角形部分)。
第三步:節(jié)約項(xiàng)目的分類,把節(jié)約項(xiàng)目有大到小順序排列。如下表:
第四步:組成配送路線,從節(jié)約項(xiàng)目表中,按節(jié)約里程大小的順序組成路線圖。
(1)初次解。
線路數(shù):10總行走距離:148公里車輛臺(tái)數(shù):2噸車10臺(tái)
(2)二次解。按節(jié)約里程由大到小的順序,連接A-B,A-J,B-C連接線。
線路數(shù):7總行走距離:109公里車輛臺(tái)數(shù):2噸車6臺(tái)4噸車1臺(tái)
(3)三次解。其次,節(jié)約里程最大的是C-D和D-E。C-D和D-E兩者都有可能與二次解的線路甲相連接,但由于甲的車輛載重與行走距離有限,不能再增加收貨點(diǎn),為此,略去C-D而連接D-E。
線路數(shù):6總行走距離:99公里車輛臺(tái)數(shù):2噸車5臺(tái)4噸車1臺(tái)
(4)四次解。接下來(lái)節(jié)約里程最大的是A-E和E-F。由于A已組合在完成的線路甲中,所以略去A-E而將E-F連接在線路乙上。
線路數(shù):5總行走距離:90公里車輛臺(tái)數(shù):2噸車3臺(tái)4噸車2臺(tái)
(5)五次解。按上面的方法繼續(xù)即得到五次解。
線路數(shù):4總行走距離:85公里車輛臺(tái)數(shù):2噸車2臺(tái)4噸車2臺(tái)
(6)六次解。按上面的方法繼續(xù)即得到6次解。
線路甲:4噸車總行走距離:27公里裝載量:3.6噸
線路乙:4噸車總行走距離:30公里裝載量:3.9噸
線路丙:2噸車總行走距離:23公里裝載量:1.3噸
3結(jié)束語(yǔ)
在這篇文章里,我們介紹了起點(diǎn)和終點(diǎn)相同的路徑規(guī)劃的這類問(wèn)題。用EXCEL工具來(lái)輔助配送路線的選擇問(wèn)題的決策,能夠達(dá)到比較好的效果。EXCEL在管理科學(xué)領(lǐng)域的應(yīng)用很多,如線性規(guī)劃、運(yùn)輸問(wèn)題、指派問(wèn)題、網(wǎng)絡(luò)最優(yōu)化問(wèn)題、項(xiàng)目管理、庫(kù)存管理、預(yù)測(cè)、排隊(duì)論和計(jì)算機(jī)仿真,等等。運(yùn)用EXCEL建立模型,求解模型,能對(duì)管理者的決策提供很好支持。
參考文獻(xiàn):
[1] Ronald H. Ballou(美). 企業(yè)物流管理——供應(yīng)鏈的規(guī)劃、組織和控制[M]. 王曉東,胡瑞娟,等譯. 北京:機(jī)械工業(yè)出版社,2002:145-197.
[2] 弗雷德里克?S?希利爾,馬克?S?希利爾,杰拉爾德?S?利伯曼(美). 數(shù)據(jù)、模型與決策[M]. 任建標(biāo),譯. 北京:中國(guó)財(cái)政經(jīng)濟(jì)出版社,2001.
[3] 胡運(yùn)權(quán). 運(yùn)籌學(xué)教程[M]. 北京:清華大學(xué)出版社,2000:241-242.
[4] 晶辰工作室. Excel2000預(yù)測(cè)分析和目標(biāo)求解實(shí)例指南[M]. 北京:電子工業(yè)出版社,2001:1-24.