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

王帆等

摘要：針對傳統(tǒng)節(jié)約里程法求解過程中，節(jié)約值矩陣和節(jié)約值排序計(jì)算工作量大、費(fèi)時、易出錯的問題，借助EXCEL函數(shù)和VBA進(jìn)行輔助加以解決，實(shí)現(xiàn)了節(jié)約值矩陣和節(jié)約值排序表的快速自動求解。

關(guān)鍵詞：CW節(jié)約算法；EXCEL；自動求解

DOIDOI：10.11907/rjdk.143620

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A 文章編號文章編號：16727800（2015）001007202

0 引言

在物流系統(tǒng)中，經(jīng)常遇到車輛路徑規(guī)劃問題，CW節(jié)約算法是解決車輛路徑規(guī)劃問題的利器，具有很強(qiáng)的實(shí)用價值。然而，該方法如果依靠手工計(jì)算非常復(fù)雜，費(fèi)時還易出錯。本文探索了利用EXCEL輔助進(jìn)行CW節(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)行的最大距離為30km[1]，請?jiān)O(shè)計(jì)配送路線，使行駛路程盡量少。

CW節(jié)約算法能夠有效地求解上述算例，其求解過程可以分為以下4個步驟[2]。

步驟1：根據(jù)圖1所示客戶的位置、距離和用戶需求數(shù)據(jù)計(jì)算各客戶點(diǎn)對間的最短距離，如圖2所示；

步驟2：根據(jù)最短距離表計(jì)算各客戶點(diǎn)對的節(jié)約值矩陣，如圖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)方法

新建一個EXCEL文件，在A1L12區(qū)域內(nèi)輸入如圖2所示的最短距離矩陣。接下來在M2V11區(qū)域內(nèi)計(jì)算出節(jié)約值矩陣。在N2V2區(qū)域依次輸入AI這9個字母，在M3M11區(qū)域依次輸入BJ這9個字母。在N3單元格輸入公式：

“=IF（ISNUMBER（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中任意兩個不同的點(diǎn)。經(jīng)過分析，PX和PY兩個值都可以在B列找到，XY的值在最短路徑表和節(jié)約值矩陣中的位置是完全對應(yīng)的，因此，可以據(jù)此設(shè)計(jì)公式。公式的核心部分是：“INDEX（$B$3：$B$12，ROW（M3）-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個時，相應(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兩個函數(shù)來完成該操作。如圖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ù)點(diǎn)對名稱，利用HLOOKUP函數(shù)到節(jié)約里程表數(shù)據(jù)區(qū)查找。在Z2單元格輸入公式“=HLOOKUP（LEFT（Y2，1），$N$2：$V$11，X2+1）” ，拖拽填充到Z82單元格。

接下來需要將節(jié)約里程值進(jìn)行排序，考慮到程序的復(fù)用性，可以添加一個按鈕，命名為“復(fù)制排序”，通過錄制并修改宏來實(shí)現(xiàn)。修改好的宏代碼及注釋如下：

Sub 復(fù)制排序（）

' 復(fù)制排序

選擇性粘貼

Range（"Y1：Z82"）.Select

Selection.Copy

Range（"AD1"）.Select

Selection.PasteSpecial Paste：=xlPasteValues， Operation：=xlNone， SkipBlanks ：=False， Transpose：=False

升序排列

Application.CutCopyMode = False

Selection.Sort Key1：=Range（"AE2"）， Order1：=xlAscending， Header：=xlGuess， OrderCustom：=1， MatchCase：=False， Orientation：=xlTopToBottom， SortMethod ：=xlPinYin， DataOption1：=xlSortNormal

刪除無效數(shù)據(jù)

k = Range（"AE65536"）.End（xlUp）.Row + 1

s = 2

For i = 2 To k

If Cells（i， 31） <> "" Then

s = s + 1

End If

Next i

Range（"AD65536：AE" & s）.Select

Selection.ClearContents

降序排列

Range（"AD1：AE" & s - 1）.Select

Selection.Sort Key1：=Range（"AE2"）， Order1：=xlDescending， Header：=xlGuess ， OrderCustom：=1， MatchCase：=False， Orientation：=xlTopToBottom， SortMethod：=xlPinYin， DataOption1：=xlSortNormal

End Sub

這樣，在單擊“復(fù)制排序”按鈕之后，程序自動運(yùn)行，計(jì)算結(jié)果如圖6所示。

圖6 節(jié)約值排序結(jié)果

接下來，需要根據(jù)節(jié)約值排序結(jié)果和約束條件確定配

送路線和配載方案，相應(yīng)的方法在很多文獻(xiàn)里都能找到，這里不再贅述。

2 結(jié)語

節(jié)約值排序表的自動計(jì)算為管理決策節(jié)省了大量寶貴時間，并且能夠保證運(yùn)算的準(zhǔn)確性。由于工具易用，有利于CW節(jié)約算法的普及，因而有利于提高管理工作的科學(xué)性。