EXCEL輔助進(jìn)行CW節(jié)約算法計(jì)算研究

1、 EXCEL輔助進(jìn)行CW節(jié)約算法計(jì)算研究 王帆等Summary：針對傳統(tǒng)節(jié)約里程法求解過程中，節(jié)約值矩陣和節(jié)約值排序計(jì)算工作量大、費(fèi)時(shí)、易出錯(cuò)的問題，借助EXCEL函數(shù)和VBA進(jìn)行輔助加以解決，實(shí)現(xiàn)了節(jié)約值矩陣和節(jié)約值排序表的快速自動求解。Key：CW節(jié)約算法；EXCEL；自動求解DOIDOI：10.11907/rjdk.143620：TP312：A ：16727800（2015）0010072020 引言在物流系統(tǒng)中，經(jīng)常遇到車輛路徑規(guī)劃問題，CW節(jié)約算法是解決車輛路徑規(guī)劃問題的利器，具有很強(qiáng)的實(shí)用價(jià)值。然而，該方法如果依靠手工計(jì)算非常復(fù)雜，費(fèi)時(shí)還易出錯(cuò)。本文探索了利用EXCEL輔助進(jìn)行CW

2、節(jié)約算法計(jì)算的方法，為CW節(jié)約算法的實(shí)際應(yīng)用提供了一套新的解決方案。1 CW節(jié)約算法常規(guī)步驟舉下例說明算法：某物流公司有一配送中心P，負(fù)責(zé)AJ共計(jì)10家客戶的配送任務(wù)，對應(yīng)的配送路線如圖1所示。括號內(nèi)的數(shù)據(jù)為發(fā)送量（t），路線上的數(shù)字表示道路距離（km）。假設(shè)能利用的車是載重2t和4t的兩種車型，并限制車輛一次運(yùn)行的最大距離為30km1，請?jiān)O(shè)計(jì)配送路線，使行駛路程盡量少。CW節(jié)約算法能夠有效地求解上述算例，其求解過程可以分為以下4個(gè)步驟2。步驟1：根據(jù)圖1所示客戶的位置、距離和用戶需求數(shù)據(jù)計(jì)算各客戶點(diǎn)對間的最短距離，如圖2所示；步驟2：根據(jù)最短距離表計(jì)算各客戶點(diǎn)對的節(jié)約值矩陣，如圖3所示；步驟

3、3：根據(jù)節(jié)約值矩陣形成節(jié)約值排序，如圖4所示；步驟4：根據(jù)節(jié)約值排序表和約束條件確定配送路線和配載方案。圖1 VRP算例配送任務(wù)圖2 最短距離矩陣圖3 節(jié)約值矩陣圖4 節(jié)約值排序在上述算例中，根據(jù)條件最終能夠確定3條配送路線：1 PJABCP；2 PDEFGP；3 PHIP 。步驟2和步驟3的計(jì)算非常繁瑣，可以借助EXCEL實(shí)現(xiàn)該操作。1.1 步驟2的實(shí)現(xiàn)方法新建一個(gè)EXCEL文件，在A1L12區(qū)域內(nèi)輸入如圖2所示的最短距離矩陣。接下來在M2V11區(qū)域內(nèi)計(jì)算出節(jié)約值矩陣。在N2V2區(qū)域依次輸入AI這9個(gè)字母，在M3M11區(qū)域依次輸入BJ這9個(gè)字母。在N3單元格輸入公式：“=IF（ISNUMBE

4、R（C4）， IF（N$2$M3， INDEX（$B$3：$B$12，ROW（M3）-1，1）+INDEX（$B$3：$B$12，COLUMN（N2）-13，1）-C4，），）”拖拽填充到V3單元格，再拖拽填充到V11單元格，得到如圖3所示的節(jié)約值矩陣。該公式能夠?qū)崿F(xiàn)通過拖拽方式直接生成全部節(jié)約值。下面對該公式進(jìn)行簡單解釋。節(jié)約值的計(jì)算公式形如“PX+PYXY”，其中，X和Y分別代表AJ中任意兩個(gè)不同的點(diǎn)。經(jīng)過分析，PX和PY兩個(gè)值都可以在B列找到，XY的值在最短路徑表和節(jié)約值矩陣中的位置是完全對應(yīng)的，因此，可以據(jù)此設(shè)計(jì)公式。公式的核心部分是：“INDEX（$B$3：$B$12，ROW（M3）

5、-1， 1）+INDEX（$B$3：$B$12， COLUMN （N2）-13， 1）-C4”在單元格N3中，即代表“PB+PAAB”。其中的絕對引用、相對引用、INDEX函數(shù)、ROW函數(shù)和COLUMN函數(shù)的設(shè)置，都是為了能夠利用拖拽填充的方法快速求得所有節(jié)約值。公式括號內(nèi)部的IF函數(shù)確保右上側(cè)三角區(qū)域不生成數(shù)據(jù)，只生成如圖3所示的三角式矩陣。括號外部的IF函數(shù)確保當(dāng)客戶節(jié)點(diǎn)不足10個(gè)時(shí)，相應(yīng)的位置不進(jìn)行計(jì)算。1.2 步驟3的實(shí)現(xiàn)方法首先需要將點(diǎn)對名稱與節(jié)約里程對應(yīng)起來，要寫出所有可能的點(diǎn)對，并標(biāo)出節(jié)約里程。點(diǎn)對可以手動輸入，但操作繁瑣，這里可以結(jié)合CONCATENATE和INDEX兩個(gè)函數(shù)來

6、完成該操作。如圖5所示，先在W列和X列輸入輔助數(shù)據(jù)，W列從W2單元格開始輸入數(shù)字1-9各9個(gè)，共81個(gè)數(shù)字；X列從X2單元格開始輸入數(shù)字1-9，輸入9次，共81個(gè)數(shù)字。在Y2單元格輸入如下公式“=CONCATENATE（INDEX（$M$2：$V$11， 1， 1+W2）， INDEX（$M$2：$V$11， X2+1， 1）”，拖拽填充到Y(jié)82單元格。圖5 輔助數(shù)據(jù)的設(shè)置節(jié)約里程則根據(jù)點(diǎn)對名稱，利用HLOOKUP函數(shù)到節(jié)約里程表數(shù)據(jù)區(qū)查找。在Z2單元格輸入公式“=HLOOKUP（LEFT（Y2，1），$N$2：$V$11，X2+1）” ，拖拽填充到Z82單元格。接下來需要將節(jié)約里程值進(jìn)行排序

7、，考慮到程序的復(fù)用性，可以添加一個(gè)按鈕，命名為“復(fù)制排序”，通過錄制并修改宏來實(shí)現(xiàn)。修改好的宏代碼及注釋如下：Sub 復(fù)制排序（） 復(fù)制排序選擇性粘貼Range（Y1：Z82）.SelectSelection.CopyRange（AD1）.SelectSelection.PasteSpecial Paste：=xlPasteValues， Operation：=xlNone， SkipBlanks ：=False， Transpose：=False升序排列Application.CutCopyMode = FalseSelection.Sort Key1：=Range（AE2）， Order1

8、：=xlAscending， Header：=xlGuess， OrderCustom：=1， MatchCase：=False， Orientation：=xlTopToBottom， SortMethod ：=xlPinYin， DataOption1：=xlSortNormal刪除無效數(shù)據(jù)k = Range（AE65536）.End（xlUp）.Row + 1s = 2For i = 2 To kIf Cells（i， 31） Thens = s + 1End IfNext iRange（AD65536：AE & s）.SelectSelection.ClearContents降序排列R

9、ange（AD1：AE & s - 1）.SelectSelection.Sort Key1：=Range（AE2）， Order1：=xlDescending， Header：=xlGuess ， OrderCustom：=1， MatchCase：=False， Orientation：=xlTopToBottom， SortMethod：=xlPinYin， DataOption1：=xlSortNormalEnd Sub這樣，在單擊“復(fù)制排序”按鈕之后，程序自動運(yùn)行，計(jì)算結(jié)果如圖6所示。圖6 節(jié)約值排序結(jié)果接下來，需要根據(jù)節(jié)約值排序結(jié)果和約束條件確定配送路線和配載方案，相應(yīng)的方法在很多文獻(xiàn)里都能找到，這里不再贅述。2 結(jié)語節(jié)約值排序表的自動計(jì)算為管理決策節(jié)省了大量寶貴時(shí)間，并且能夠保證運(yùn)算的準(zhǔn)確性。由于工具易用，有利于CW節(jié)約算法的普及，因而有利于提高管理工作的科學(xué)性