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

1、 EXCEL輔助進行CW節(jié)約算法計算研究 王帆等Summary：針對傳統(tǒng)節(jié)約里程法求解過程中，節(jié)約值矩陣和節(jié)約值排序計算工作量大、費時、易出錯的問題，借助EXCEL函數(shù)和VBA進行輔助加以解決，實現(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ī)劃問題的利器，具有很強的實用價值。然而，該方法如果依靠手工計算非常復雜，費時還易出錯。本文探索了利用EXCEL輔助進行CW

2、節(jié)約算法計算的方法，為CW節(jié)約算法的實際應用提供了一套新的解決方案。1 CW節(jié)約算法常規(guī)步驟舉下例說明算法：某物流公司有一配送中心P，負責AJ共計10家客戶的配送任務(wù)，對應的配送路線如圖1所示。括號內(nèi)的數(shù)據(jù)為發(fā)送量（t），路線上的數(shù)字表示道路距離（km）。假設(shè)能利用的車是載重2t和4t的兩種車型，并限制車輛一次運行的最大距離為30km1，請設(shè)計配送路線，使行駛路程盡量少。CW節(jié)約算法能夠有效地求解上述算例，其求解過程可以分為以下4個步驟2。步驟1：根據(jù)圖1所示客戶的位置、距離和用戶需求數(shù)據(jù)計算各客戶點對間的最短距離，如圖2所示；步驟2：根據(jù)最短距離表計算各客戶點對的節(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的計算非常繁瑣，可以借助EXCEL實現(xiàn)該操作。1.1 步驟2的實現(xiàn)方法新建一個EXCEL文件，在A1L12區(qū)域內(nèi)輸入如圖2所示的最短距離矩陣。接下來在M2V11區(qū)域內(nèi)計算出節(jié)約值矩陣。在N2V2區(qū)域依次輸入AI這9個字母，在M3M11區(qū)域依次輸入BJ這9個字母。在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é)約值。下面對該公式進行簡單解釋。節(jié)約值的計算公式形如“PX+PYXY”，其中，X和Y分別代表AJ中任意兩個不同的點。經(jīng)過分析，PX和PY兩個值都可以在B列找到，XY的值在最短路徑表和節(jié)約值矩陣中的位置是完全對應的，因此，可以據(jù)此設(shè)計公式。公式的核心部分是：“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ù)確保當客戶節(jié)點不足10個時，相應的位置不進行計算。1.2 步驟3的實現(xiàn)方法首先需要將點對名稱與節(jié)約里程對應起來，要寫出所有可能的點對，并標出節(jié)約里程。點對可以手動輸入，但操作繁瑣，這里可以結(jié)合CONCATENATE和INDEX兩個函數(shù)來

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

7、，考慮到程序的復用性，可以添加一個按鈕，命名為“復制排序”，通過錄制并修改宏來實現(xiàn)。修改好的宏代碼及注釋如下：Sub 復制排序（） 復制排序選擇性粘貼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這樣，在單擊“復制排序”按鈕之后，程序自動運行，計算結(jié)果如圖6所示。圖6 節(jié)約值排序結(jié)果接下來，需要根據(jù)節(jié)約值排序結(jié)果和約束條件確定配送路線和配載方案，相應的方法在很多文獻里都能找到，這里不再贅述。2 結(jié)語節(jié)約值排序表的自動計算為管理決策節(jié)省了大量寶貴時間，并且能夠保證運算的準確性。由于工具易用，有利于CW節(jié)約算法的普及，因而有利于提高管理工作的科學性