崔 健，錢(qián)楓林，王利光

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3）根據(jù)當(dāng)前解xi進(jìn)行擾動(dòng)，產(chǎn)生一個(gè)新解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次的擾動(dòng)和接受過(guò)程，即執(zhí)行步驟3）和4）。

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

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

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

4.1 模糊需求條件下的聚類(lèi)分析

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

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

表1 各地需求量Table1 Demand all over

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 論

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

Matlab進(jìn)行最短路徑的安排實(shí)驗(yàn)，從所產(chǎn)生的最短路徑情況來(lái)看，在越小的P＊值下，車(chē)輛的行駛路徑最短，這一結(jié)論為決策者在模糊需求的問(wèn)題上所做決策時(shí)提供了參考標(biāo)桿，有助于決策者在動(dòng)態(tài)的車(chē)輛路徑安排上做出更好的決策，從而減少了物流成本和風(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ù)約時(shí)間的VRP混合遺傳算法 [J].管理科學(xué)學(xué)報(bào)，2005，8（3）：64-71.

[8]張建勇，李 軍，郭耀煌.帶模糊預(yù)約時(shí)間的動(dòng)態(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]王 勇，毛海軍，劉 靜.帶時(shí)間窗的物流配送區(qū)域劃分模型及其算法 [J].東南大學(xué)學(xué)報(bào)，2010，40（5）：1077-1083.

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

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

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