崔 健，錢楓林，王利光

（江南大學(xué)a.商學(xué)院；b.理學(xué)院，江蘇 無錫 214122）

0 引 言

在大型的物流配送問題中，配送車輛的優(yōu)化調(diào)度是物流系統(tǒng)優(yōu)化中的關(guān)鍵一環(huán)，物流企業(yè)針對配送車輛路線進(jìn)行合理的規(guī)劃，可以提高物流經(jīng)濟(jì)效益，減少了物流成本，實(shí)現(xiàn)了物流的科學(xué)化。車輛路徑問題VRP（Vehicle Routing Problem）最初是由Dantzing和Ramser[1]提出的，是指在客戶需求已知的條件下，確定車輛在各個客戶之間的行程路線，可以使得運(yùn)輸路線最短或者運(yùn)輸成本最低。關(guān)于求解車輛路徑問題的算法有大量的研究成果[2－3]，但這些研究方法絕大多數(shù)是建立在確定性的條件基礎(chǔ)之上的。而在現(xiàn)實(shí)中，有關(guān)VRP的許多參數(shù)可能是不確定的，如車輛在兩地的行駛時間約20min、顧客的需求約為20單位等。對于這類具有模糊性質(zhì)的不確定性VRP問題，所做的研究較少。針對隨機(jī)車輛調(diào)度問題[4－5]，有少數(shù)的不確定研究集中在通過對長期記錄的資料進(jìn)行分析從而得到其統(tǒng)計(jì)規(guī)律。Wang和Wen[6]提出了采用模糊理論對中國郵路問題進(jìn)行研究，由此建立了最大化服務(wù)水平和最小化任務(wù)完成時間的數(shù)學(xué)模型；張建勇[7－8]等對具有模糊預(yù)約時間的多對多貨物收發(fā)情況下的車輛調(diào)度問題進(jìn)行了探討；Tang[9]等在分析模糊時間窗實(shí)際應(yīng)用性的基礎(chǔ)上構(gòu)建了該類問題的數(shù)學(xué)模型，并設(shè)計(jì)了求解多目標(biāo)整數(shù)規(guī)劃模型的兩階段算法。

雖然VRP問題的諸多理論和方法有著比較廣泛應(yīng)用，但是目前物流企業(yè)的運(yùn)作效率普遍不高，運(yùn)作成本較高。針對現(xiàn)行的大型物流企業(yè)的實(shí)際問題，以提高配送效率和降低成本為目標(biāo)，本文首先通過聚類的方法，由模糊數(shù)學(xué)的理論將模糊的顧客需求轉(zhuǎn)化為實(shí)際的需求，進(jìn)而根據(jù)實(shí)際的需求量將物流配送單元進(jìn)行劃分。在此基礎(chǔ)之上引入決策者主觀偏好，建立模糊需求條件下的VRP模型，設(shè)計(jì)并運(yùn)用模擬退火算法進(jìn)行車輛路徑的設(shè)計(jì)，討論在模糊需求信息條件下，在每一個已經(jīng)劃分的物流區(qū)域內(nèi)，決策者偏好對車輛行駛的最短路徑有何影響，進(jìn)而為物流企業(yè)在配送過程中給出優(yōu)化方案。

1 根據(jù)需求量對物流區(qū)域進(jìn)行聚類

在實(shí)際問題中，針對不同需求量的地區(qū)往往需要進(jìn)行分類，使需求相似程度較高的幾個區(qū)域劃分為一類。物流區(qū)域劃分問題可以確定一套車輛派送的方案，用以解決中轉(zhuǎn)站選址及不同載運(yùn)量的車輛安排[10]，使得總的物流費(fèi)用最低，配送效率最高。區(qū)域劃分前的示意圖見圖1，區(qū)域劃分后的示意圖見圖2。其中，根據(jù)區(qū)域劃分的類別不同分別派以不同載運(yùn)量的車輛進(jìn)行配送，從而大大減少了配送時間和行駛車程，降低了物流成本。在本文中，設(shè)每個節(jié)點(diǎn)的需求量為一模糊數(shù)（1，2，…，n），各節(jié)點(diǎn)的實(shí)際需求量采用三角模糊變量（di1，di2，di3）的期望值：來表示[11]。

聚類分析的基本思想[12]是，從一批樣本中定義能夠度量樣本間或變量間相似程度的統(tǒng)計(jì)量，在此基礎(chǔ)上求出各樣本之間的相似程度度量值，按相似程度的大小，把變量逐一歸類，關(guān)系密切的類聚集到一個小的分類單位，關(guān)系疏遠(yuǎn)的聚合到一個大的分類單位，直到所有的變量都聚集完畢。利用這種思想，運(yùn)用譜系聚類法中的最短距離法將需求量不同的各個物流區(qū)域進(jìn)行分類，利用SPSS統(tǒng)計(jì)工具進(jìn)行聚類分析，使具有相似需求量的節(jié)點(diǎn)歸為一類，利用不同載運(yùn)量的車輛針對需求不同的區(qū)域進(jìn)行有效率的配送。

2 模糊需求信息下的VRP數(shù)學(xué)模型

對模糊需求的車輛路徑問題的描述如下：有一個配送中心，用0表示；n個顧客（即需要配送的節(jié)點(diǎn)），用1，2，…，n表示。車輛從配送中心出發(fā)，載有一定數(shù)量的貨品，根據(jù)以上聚類分析得到的劃分好的物流區(qū)域，服務(wù)一定數(shù)量的節(jié)點(diǎn)后返回貨運(yùn)中心。已知每輛車的運(yùn)輸能力為Vi（i＝1，2，3，…，w）。設(shè)每個節(jié)點(diǎn)的需求量為一模糊數(shù)～Di（1，2，…，n），Q為所有節(jié)點(diǎn)的最大需求量，且假設(shè)Vi≥Q。節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的距離為cij。由于之前所做的聚類分析工作，已將車輛的配送方向劃分好，假設(shè)將需要配送的節(jié)點(diǎn)劃分為K類，K＝1，2，…，且K＜n。則本文研究在其中一類區(qū)域Ki中分配k輛車的條件下，決策者的偏好性如何選擇，使車輛總的行駛距離最小。

目標(biāo)函數(shù)為：

其中nk表示第k輛車所包含的節(jié)點(diǎn)數(shù)；rk，i表示節(jié)點(diǎn)在路徑k中的順序?yàn)閕。

令P＊（P＊∈ [0，1]）表示決策者是否安排車輛繼續(xù)完成下一任務(wù)的可能性臨界值[13]，或者稱為決策者主觀偏好值。因此，車輛能否服務(wù)第m＋1個節(jié)點(diǎn)，取決于P＝pos｛｝≥P＊是否成立。顯然，P越大，完成配送的可能性越大。但對于決策者來說，P＊反映了其決策時的風(fēng)險(xiǎn)偏好，追求風(fēng)險(xiǎn)型的決策者會傾向于較小的P＊，這時他希望能夠充分利用車輛的剩余載運(yùn)量，以追求車輛的最優(yōu)利用率，而風(fēng)險(xiǎn)規(guī)避型的決策者會選擇較大的P＊，此時他要保證車輛可以滿足下一個節(jié)點(diǎn)的需求量。

3 物流區(qū)域單元內(nèi)的模擬退火算法

模擬退火算法是一種通用概率算法，由Metropolis于1953年提出，其思想源于固體的退火過程，即將固體加熱至足夠高的溫度，再緩慢冷卻。加熱時，固體內(nèi)部粒子隨溫度升高變?yōu)闊o序狀，內(nèi)能增大，而緩慢冷卻時粒子又逐漸趨于有序。在冷卻過程中，任一溫度時固體都能達(dá)到熱平衡，當(dāng)溫度降至結(jié)晶溫度后，液體凝固成固體的晶態(tài)，退火過程完成。

從上述VRP模型來看，求解該問題的關(guān)鍵是合理確定各車輛與各節(jié)點(diǎn)的關(guān)系，在滿足車輛的載運(yùn)量和節(jié)點(diǎn)的需求條件下使得目標(biāo)函數(shù)即車輛行駛總路徑最小。由此構(gòu)造以下的模擬退火算法：

1）令初始值T＝T0，隨機(jī)生成一個初始解x0，并計(jì)算相應(yīng)的目標(biāo)函數(shù)L（x0）。

2）令T等于冷卻進(jìn)度表中的下一個值Ti。

3）根據(jù)當(dāng)前解xi進(jìn)行擾動，產(chǎn)生一個新解xj，計(jì)算相應(yīng)的目標(biāo)函數(shù)值L（xj），得到ΔL＝L（xj）－L（xi）。

4）若ΔL＜0，則新解xj被接受，作為新的當(dāng)前解；若ΔL＞0，則新解xj按概率exp（－ΔL／Ti）接受，Ti為當(dāng)前值。

5）在當(dāng)前值Ti下，重復(fù)lk次的擾動和接受過程，即執(zhí)行步驟3）和4）。

6）判斷T是否已到達(dá)Tf，是，則終止算法；否，則轉(zhuǎn)到步驟2）繼續(xù)執(zhí)行。

P＊的引入對于所安排的車輛計(jì)劃有很大的影響。P＊值越小，則所派車輛的載重量能夠被充分利用，預(yù)計(jì)的行駛距離越短；同時，小的P＊值也使配送失敗的可能性增大，從而產(chǎn)生較多的額外行駛距離。反之，大的P＊值相應(yīng)減少了配送失敗的可能性，額外行駛距離也相應(yīng)減小。因此，在考慮模糊需求信息條件的車輛路徑安排問題中，加入了決策者的風(fēng)險(xiǎn)偏好這一控制參數(shù)，通過觀察P＊值研究對最終的VRP決策有何影響。

4 數(shù)據(jù)實(shí)驗(yàn)及結(jié)果分析

4.1 模糊需求條件下的聚類分析

一配送中心負(fù)責(zé)對12個地區(qū)的分銷點(diǎn)進(jìn)行配送，各個地區(qū)的實(shí)際需求量見表1，根據(jù)此基礎(chǔ)，對12個地區(qū)進(jìn)行區(qū)域劃分，從而決定車輛的配送路徑。

應(yīng)用譜系聚類法中的最短距離法，對下表問題進(jìn)行聚類。其模型[12]為：以i，j等分別表示樣品xi，xj，以dij簡記樣品i與j之間的距離d（xi，xj），用Gp和Gq表示兩個類，它們所包含的樣品個數(shù)分別記為np和nq，類Gp和Gq之間的距離用D（Gp，Gq），表示，則 D（Gp，Gq）＝min｛dij，即定義Gp與Gq中最鄰近的兩個樣本的距離為這兩個類之間的距離。

表1 各地需求量Table1 Demand all over

根據(jù)需求量，用SPSS的聚類分析得到以下結(jié)果（表2）：

表2 分銷點(diǎn)的相關(guān)系數(shù)矩陣Table2 Correlation coefficient matrix of distributions ／t

從圖3可以看出整個聚類過程及相應(yīng)的水平，其為分銷點(diǎn)的譜系圖。

根據(jù)譜系圖，將這12個分銷點(diǎn)分為4類比較合適，即F、J、D、C、G、K為一類，H、I為一類，B、L為一類，A、E為一類。由此可見，物流公司可以建立4個配送中心，分別派送相應(yīng)載運(yùn)量的車輛對4類分銷點(diǎn)進(jìn)行配送。在此基礎(chǔ)之上，可以進(jìn)一步將分銷點(diǎn)劃分的更為接近，如F、J、D為一類，C、G為一類，H、I為一類，B、L為一類，A、E為一類，K自成一類。從而使配送中心可以安排車輛對其需求進(jìn)行配送，針對不同的需求量，發(fā)送相應(yīng)載運(yùn)量的貨車進(jìn)行指定的配送，從而提高了配送效率，節(jié)約配送時間，減少物流成本。

圖3 分銷點(diǎn)最小距離譜系圖Fig.3 Minimum distances dendritic diagram of distributions

4.2 應(yīng)用模擬退火算法求解最短路徑問題

表3為根據(jù)聚類分析得到的F、J、D、C、G、K區(qū)域中共50個城市的坐標(biāo)位置，根據(jù)不同的P＊值，根據(jù)模擬退火算法逐步求得每個P＊值下的最短路徑及車輛的配送路徑。

表3 50座城市的坐標(biāo)Table3 Coordinates of 50Cities

在參數(shù)的選擇中，令P＊＝0.01T，通過控制參數(shù)T的變化進(jìn)而推斷出決策者偏好值P＊對決策的影響。

Markov鏈長度的選取原則是在控制參數(shù)T的衰減函數(shù)已定的前提下，lk應(yīng)能使在控制參數(shù)T的每一個取值上達(dá)到準(zhǔn)平衡。

在實(shí)際運(yùn)行中，各參數(shù)取值見表4。

表4 各參數(shù)取值Table4 Value of parameter

由Matlab運(yùn)行得到如下結(jié)果：

即決策者的主觀偏好P＊值與實(shí)際運(yùn)行中車輛所行駛的最短距離的關(guān)系見表5。

由圖4可見，優(yōu)化后路徑長度得到很大的改進(jìn)，并且，隨著P＊逐漸減小，所分配車輛行駛的距離越短，即優(yōu)化的結(jié)果越來越好。但從理論上分析，P＊逐漸減小會使任務(wù)失敗的可能性增加。因此，在大型的物流企業(yè)中，決策者的偏好往往決定了運(yùn)輸策略的優(yōu)劣。在實(shí)際的車輛調(diào)度中，若以車輛行駛距離最短為目標(biāo)函數(shù)來看，企業(yè)應(yīng)該選擇風(fēng)險(xiǎn)偏好型的決策，即越小的P＊值會帶來越低的物流成本。P＊＝0.03時優(yōu)化過程圖見圖5。

表5 P＊與實(shí)際運(yùn)行中車輛所行駛的最短距離的關(guān)系Table5 Relation between P＊and the actual operation of the vehicle traveling on the shortest distance

5 結(jié) 論

在引入決策者偏好的基礎(chǔ)之上，把客戶的模糊需求進(jìn)行實(shí)際需求模擬，用簡單的聚類分析的方法對物流區(qū)域進(jìn)行劃分，使具有相似需求的節(jié)點(diǎn)歸為一類，從而使物流企業(yè)在面對大型的物流配送問題時可以分類解決，減少了物流成本，提高了配送效率。在每個物流區(qū)域內(nèi)部根據(jù)節(jié)點(diǎn)的位置坐標(biāo)利用模擬退火算法進(jìn)行車輛路徑安排，其中將決策者的主觀偏好P＊值作為一個控制參數(shù)，觀察P＊值的大小對車輛行駛的最短路徑有何影響，通過運(yùn)用

Matlab進(jìn)行最短路徑的安排實(shí)驗(yàn)，從所產(chǎn)生的最短路徑情況來看，在越小的P＊值下，車輛的行駛路徑最短，這一結(jié)論為決策者在模糊需求的問題上所做決策時提供了參考標(biāo)桿，有助于決策者在動態(tài)的車輛路徑安排上做出更好的決策，從而減少了物流成本和風(fēng)險(xiǎn)。

[1]Dantzig G B，Ralnser J H.The truck dispatching problem [J].Management Science，1959，6（1）：80-91.

[2]Holland J H.Adaptations in natural and artificial systems[M].AnnAror：University of Michigan Press.1976.

[3]Gillett B，Miller L.A heuristic algorithm for the vehicle dispatch problem [J].Operations Research，1974，22：340-349.

[4]Moshe D，Gilbert L，Pierre T.Vehicle routing withstochastic demands：Properties and solution frameworks[J].Transportation Science，1989，23（3）：166-176.

[5]Michel G，Gilbert L，Rene S.An exact algorithm for the vehicle routing problem with stochastic demands and customers[J].Transportation Science，1995，29（2）：143-155.

[6]Wang Hsiao-Fan，Wen Yu-Pin.Time-constrained Chinese postman problems [J].Computers ＆ Mathematics with Applications，2002，44（34）：375-387.

[7]張建勇，李 軍，郭耀煌.具有模糊預(yù)約時間的VRP混合遺傳算法 [J].管理科學(xué)學(xué)報(bào)，2005，8（3）：64-71.

[8]張建勇，李 軍，郭耀煌.帶模糊預(yù)約時間的動態(tài)VRP的插入啟發(fā)式算法 [J].西南交通大學(xué)學(xué)報(bào)，2008，43（1）：108-114.

[9]Tang Jia-fu，Pan Zhen-dong，F(xiàn)ung Richard Y K，et a1.Vehicle routing problem with fuzzy time windows[J].Fuzzy Setsand Systems，2009，160（5）：683-695.

[10]王 勇，毛海軍，劉 靜.帶時間窗的物流配送區(qū)域劃分模型及其算法 [J].東南大學(xué)學(xué)報(bào)，2010，40（5）：1077-1083.

[11]于 波，丁 源.帶模糊需求的多類型車輛路徑問題研究 [J].蘭州交通大學(xué)學(xué)報(bào)：自然科學(xué)版，2006，25（3）：134-140.

[12]梅長林，周家良.實(shí)用統(tǒng)計(jì)方法 [M].北京：科學(xué)出版社，2002.

[13]張建勇，郭耀煌，李 軍.模糊需求信息條件下的車輛路徑問題研究 [J].系統(tǒng)工程學(xué)報(bào)，2004，19（1）：74-78.