高珊珊，李萌萌

(1.蘭州商學(xué)院 管理科學(xué)與工程學(xué)院，甘肅 蘭州730020;2.蘭州商學(xué)院 統(tǒng)計(jì)學(xué)院，甘肅 蘭州730020)

0 引 言

隨著我國(guó)經(jīng)濟(jì)的快速發(fā)展，物流作為社會(huì)經(jīng)濟(jì)活動(dòng)的基礎(chǔ)，被稱(chēng)為企業(yè)的“第三利潤(rùn)源泉”［1］。物流業(yè)的發(fā)展與進(jìn)步受到了越來(lái)越多的重視，因此物流產(chǎn)業(yè)的專(zhuān)業(yè)化程度也不斷的提高。配送方案的合理與否對(duì)物流成本、效益、服務(wù)水平以及顧客的滿(mǎn)意度都有著重要的影響。本文針對(duì)物流配送路徑問(wèn)題進(jìn)行研究。合理選擇最優(yōu)的配送路徑，以減少配送時(shí)間、節(jié)約配送成本、提高服務(wù)質(zhì)量、增加經(jīng)濟(jì)效益以及提高顧客滿(mǎn)意度。

車(chē)輛路徑問(wèn)題(Vehicle Routing Problem)是1959年由Dantzig 和Ramser 提出的［2］，該問(wèn)題在現(xiàn)實(shí)生活中的應(yīng)用相當(dāng)廣泛。近幾年越來(lái)越多的人對(duì)其進(jìn)行優(yōu)化研究，然而現(xiàn)實(shí)路徑中存在很多的約束條件，如:配送中心的多少、配送車(chē)輛的類(lèi)型、客戶(hù)對(duì)時(shí)間的要求、客戶(hù)需求的隨機(jī)性、動(dòng)態(tài)道路堵車(chē)情況等，在研究模型中考慮的約束條件越多則研究結(jié)果越接近現(xiàn)實(shí)路徑問(wèn)題。

目前對(duì)多約束條件車(chē)輛調(diào)度問(wèn)題的研究有:文獻(xiàn)［4］等人用兩階段法研究了多配送中心問(wèn)題;文獻(xiàn)［1］考慮了車(chē)容量的限制，即對(duì)車(chē)型問(wèn)題進(jìn)行了研究;文獻(xiàn)［10］考慮的帶時(shí)間窗的約束;文獻(xiàn)［7］在時(shí)間窗的基礎(chǔ)上加入了非滿(mǎn)載條件;文獻(xiàn)［3］考慮了帶時(shí)間窗的多配送中心約束條件。本文在已有研究的基礎(chǔ)上，用改進(jìn)的節(jié)約法研究了帶時(shí)間窗的多配送中心多車(chē)型的車(chē)輛調(diào)度問(wèn)題。(1)針對(duì)模型利用重心法把客戶(hù)分配到不同的配送中心，每個(gè)配送中心的客戶(hù)是確定的，然后建立多配送中心多車(chē)型的VSP 數(shù)學(xué)模型，模型基于配送費(fèi)用最少為目標(biāo)函數(shù)。(2)對(duì)各個(gè)分配送中心應(yīng)用改進(jìn)的節(jié)約算法進(jìn)行求解帶時(shí)間窗約束的單配送中心車(chē)輛調(diào)度路徑模型。

1 路徑調(diào)度問(wèn)題模型建立

1.1 時(shí)間窗約束問(wèn)題

帶時(shí)間窗約束的車(chē)輛調(diào)度問(wèn)題，即為客戶(hù)對(duì)配送任務(wù)有時(shí)間的要求，要在最早時(shí)間ET 與最晚時(shí)間LT之間(ET ＜t ＜LT)進(jìn)行配送活動(dòng)。時(shí)間窗問(wèn)題可以分為硬時(shí)間窗和軟時(shí)間窗兩種。對(duì)于硬時(shí)間窗問(wèn)題，車(chē)輛必須在時(shí)間窗［ET，LT］內(nèi)進(jìn)行配送，在時(shí)間窗外客戶(hù)則不接受貨物配送，即得到的解為不可行解。而對(duì)于軟時(shí)間窗問(wèn)題。如果車(chē)輛早于ET 到達(dá)，則需等到ET 再進(jìn)行配送，此時(shí)需要承擔(dān)一定的成本損失，若遲于LT 到達(dá)，則要承擔(dān)一定的懲罰費(fèi)用，若過(guò)早或過(guò)遲，客戶(hù)將不接受配送，即又變成了硬時(shí)間窗問(wèn)題，此時(shí)需要一個(gè)無(wú)窮大的懲罰成本L 來(lái)表示。本文采用軟時(shí)間窗約束來(lái)求解［3］。其懲罰成本可表示如下:

其中，p(t)是有時(shí)間窗約束所引起的懲罰成本;A 為可接受的最早等待時(shí)間，a 為等待時(shí)產(chǎn)生的成本系數(shù);B 為可接受的最晚時(shí)間，b 為延遲送貨需要承擔(dān)的懲罰成本系數(shù);L 為無(wú)窮大的懲罰成本。

1.2 問(wèn)題與約束條件

物流配送路徑優(yōu)化問(wèn)題可以描述為:某配送中心需要多臺(tái)車(chē)向此分區(qū)的多個(gè)客戶(hù)提供送貨?？蛻?hù)和配送中心的位置確定，且每個(gè)客戶(hù)對(duì)貨物的需求量確定。每個(gè)配送中心有多種車(chē)型，每種車(chē)型載貨量確定，最大行駛距離確定。每輛車(chē)可以為多個(gè)客戶(hù)服務(wù)，每個(gè)客戶(hù)只能有一輛車(chē)提供服務(wù)，車(chē)輛從配送中心出發(fā)完成配送任務(wù)后返回原配送中心。配送中心要在客戶(hù)規(guī)定的時(shí)間內(nèi)將貨物送到。要求合理調(diào)度車(chē)輛安排配送路徑，使目標(biāo)函數(shù)即配送費(fèi)用最小得到優(yōu)化。問(wèn)題的基本約束條件如下:

(1)有多個(gè)配送中心，每個(gè)配送中心有多種車(chē)型;

(2)配送中心車(chē)型不同，載重量不同，最大行駛距離不同;

(3)配送中心對(duì)客戶(hù)的配送需求和位置是已知的;

(4)每個(gè)客戶(hù)的實(shí)際需求量不超過(guò)每種車(chē)型的最大載貨量，一次配送任務(wù)的總距離不大于配送車(chē)輛一次行駛的最大距離;

(5)每輛車(chē)僅調(diào)度一次，每個(gè)客戶(hù)只能有一輛車(chē)進(jìn)行配送，車(chē)輛從配送中心出發(fā)最后又回到原配送中心。

(6)客戶(hù)要求在一定的時(shí)間范圍內(nèi)把貨物送到，即考慮時(shí)間窗約束。

1.3 VSP 模型的建立

由以上的約束條件可以將多配送中心多車(chē)輛的VSP 的數(shù)學(xué)模型設(shè)計(jì)如下:

其中，I 為配送中心集合，i 為各分配送中心;J 為客戶(hù)集合，j 為客戶(hù);H 為車(chē)輛集合，h 為各車(chē)輛;K 為車(chē)型集合，k 為車(chē)型;qj為j 客戶(hù)的需求量，Qihk為i 配送中心的h 車(chē)輛為k 車(chē)型的最大載重量;dij為i 配送中心到j(luò) 客戶(hù)的距離，Dihk為i 配送中心h 車(chē)輛為k 車(chē)型的最大行駛距離;y 為單位貨物單位里程的運(yùn)輸費(fèi)用;p(t)為時(shí)間窗約束的懲罰成本;Xijh為i 配送中心的h 車(chē)輛為j 客戶(hù)提供服務(wù)，若為1 即參與配送，反之為0。

上述模型中:式(1)為目標(biāo)函數(shù)，即要求配送費(fèi)用最小;式(2)－－(6)為模型的約束條件。其中式(2)為j 客戶(hù)的需求量不大于i 配送中心k 車(chē)型h 車(chē)輛的最大載重量;式(3)為i 配送中心h 車(chē)輛完成一次配送任務(wù)的距離不大于此配送車(chē)型的最大行駛距離;式(4)為車(chē)輛若參與配送最后要返回原配送中心;式(5)為一輛車(chē)只能從配送中心調(diào)度一次，且一個(gè)客戶(hù)只能有一輛車(chē)進(jìn)行配送;式(6)客戶(hù)要求進(jìn)行配送的時(shí)間約束。

2 重心法分區(qū)算法

2.1 重心法介紹

本文研究的是大規(guī)模的車(chē)輛配送問(wèn)題，由于配送距離遠(yuǎn)，道路的動(dòng)態(tài)狀況，單配送中心已經(jīng)不能滿(mǎn)足貨物的及時(shí)有效的配送，因此多配送中心被廣泛的應(yīng)用。本文將運(yùn)用幾何重心的分區(qū)方法將多配送中心問(wèn)題分成各個(gè)單配送中心問(wèn)題來(lái)解決，大大的提高了多配送中心車(chē)輛調(diào)度的效率。

重心分區(qū)法是以連接所有配送中心的幾何重心和相鄰兩個(gè)配送中心的中點(diǎn)的做中垂線(xiàn)將配送中心分為不同的區(qū)域［4］。有幾個(gè)配送中心將會(huì)得到幾個(gè)分區(qū)，每個(gè)分區(qū)內(nèi)的客戶(hù)是確定的。各個(gè)配送中心的路徑互不交叉、業(yè)務(wù)相互獨(dú)立，且操作簡(jiǎn)單，大大減少了計(jì)算量，在大規(guī)模多配送中心問(wèn)題中有很大優(yōu)勢(shì)。

2.2 算法步驟

(1)確定各個(gè)配送中心的位置，計(jì)算所有配送中心的重心位置O;

(2)將O 與兩兩配送中心連線(xiàn)的中線(xiàn)做中垂線(xiàn);

(3)相鄰兩條射線(xiàn)圍成的區(qū)域即為在此區(qū)域內(nèi)配送中心的配送范圍，垂線(xiàn)上的點(diǎn)歸為右側(cè)。

2.3 算例描述

設(shè)有2 個(gè)配送中心，10 個(gè)客戶(hù)，其位置坐標(biāo)如下表一所示。用重心法進(jìn)行分區(qū)，可得配送中心I1的客戶(hù)為4 個(gè):1，3，9，10;配送中心I2的客戶(hù)為6 個(gè):2，4，5，6，7，8。

表1 客戶(hù)與配送中心數(shù)據(jù)

3 節(jié)約算法解決路徑優(yōu)化

3.1 節(jié)約算法介紹

C－W 節(jié)約算法是1964年Clarke 和Wright 提出的［5］，是為了解決以最短路徑為優(yōu)化目標(biāo)的問(wèn)題［6］。其基本思想是:(1)將配送中心與各個(gè)客戶(hù)之間進(jìn)行連線(xiàn)構(gòu)成線(xiàn)路Si;(2)任意兩個(gè)客戶(hù)之間相連接形成路徑Sij，計(jì)算節(jié)約值Wij=Si+Sj－ Sij，Sij越大則連接后節(jié)約的費(fèi)用約多;(3)將Sij由小到大進(jìn)行排序依次連接各點(diǎn)，直到Sij=0，即可得到此配送路徑的最小總路程［7］。

3.2 改進(jìn)節(jié)約算法設(shè)計(jì)

由于節(jié)約算法最初是為了解決旅行商的問(wèn)題提出的，因此對(duì)路徑中的各種約束條件沒(méi)有加以考慮，故無(wú)法直接用以解決VRP 問(wèn)題，但可以通過(guò)改進(jìn)來(lái)完善此算法，文獻(xiàn)［8］［9］都是對(duì)節(jié)約算法的改進(jìn)，本文通過(guò)模型的特點(diǎn)對(duì)其進(jìn)行改進(jìn)。

3.2.1 軟時(shí)間窗設(shè)計(jì)

軟時(shí)間窗約束主要考慮i 與j 進(jìn)行連接后，客戶(hù)i 之后各客戶(hù)點(diǎn)的貨物到達(dá)時(shí)間變化ij=Wij/v 所引起的懲罰成本P()。將懲罰成本與減少的里程費(fèi)用進(jìn)行比較確定是否進(jìn)行此次連接。具體步驟如下:

(1)減少的里程費(fèi)用:Fij=Wij* y=(Si+Sj－ Sij)* y;

(2)時(shí)間變化引起的懲罰成本:若ij＜ET，則懲罰成本P()=a(ET－ Tij);若ET ＜Tij＜LT，則P()=0;若ij＞LT，則P()=b(ij－ LT);

(3)若P()＞Fij，證明此次連接引起的懲罰成本大于連接減少的里程費(fèi)用，則取消此次連接;若P()=Fij，則可連接可不連接;若P()＜Fij，則進(jìn)行此次連接。

3.2.2 多車(chē)型設(shè)計(jì)

將多種車(chē)型加入進(jìn)行考慮，每種車(chē)型的最大容載量Q、最大行駛里程S 以及單位公里的行駛費(fèi)用y 都不同，而車(chē)輛的行駛速度v 一定。在連接Sij之前先計(jì)算連接后的車(chē)載量與行駛總里程是否超過(guò)此車(chē)型的最大容載量及最大行駛里程［10］。若不超過(guò)則進(jìn)行下一個(gè)連接，若超過(guò)則不連接，結(jié)束該路徑。

4 實(shí)驗(yàn)分析

配送中心與客戶(hù)信息如表1所示，其中參數(shù)設(shè)置為:a=1/h ;b=5/h ;y 代表單位里程費(fèi)用，其中包括燃油費(fèi)，司機(jī)工資等，yk1=1.1/km;yk2=1/km;車(chē)型容量Ck1=8t;Ck2=4t;最大行程:Sk1=15;Sk2=10;車(chē)速v=2;卸貨時(shí)間統(tǒng)一為10min;用節(jié)約法進(jìn)行路徑優(yōu)化求解可得:

配送中心I1的路徑L1:I1－ K1－1－3－10－ I1;L2:I1－ K2－9－ I1;

配送中心I2的路徑L3:I2－ K1－4－6－2－5－ I2;L4:I2－ K2－8－7－ I2;

L1，L2表示配送中心1 派2 輛車(chē)K1，K2分別為1，3，10 和9 服務(wù)后返回配送中心1;L3，L4表示配送中心2 派2 輛車(chē)K1，K2分別為4，6，2，5 和8，7 服務(wù)后返回配送中心2。完成路徑L1所需費(fèi)用:F11=Si1k1* yk1=11.708* 1.1=12.879;同理可得L2，L3，L4的費(fèi)用為F12=Si1k2* yk2=6.325* 1=6.325;F21=Si2k1* yk1=14.307* 1.1=15.738;F22=Si2k2* yk2=7.634* 1=7.634。

其在路徑L1中K1到達(dá)客戶(hù)1 的時(shí)間10:30［9:45－10:45］，即不產(chǎn)生懲罰成本;K1到達(dá)客戶(hù)3 的時(shí)間為11:47［12:30－－13:00］，即產(chǎn)生等待懲罰成本P(t)=43/60* 1=0.716;客戶(hù)10 的時(shí)間屬于全天，即不產(chǎn)生懲罰成本;則路徑L1產(chǎn)生的懲罰成本為P(t)=0.716;同理可得L2無(wú)懲罰成本;L3的延遲懲罰成本為:P(t)=17/60* 5=1.417;L4產(chǎn)生的等待懲罰成本為:P(t)=8/60* 1=0.133。

以上實(shí)驗(yàn)?zāi)Ｐ途哂? 個(gè)配送中心2 種車(chē)型10 個(gè)客戶(hù)數(shù)且?guī)к洉r(shí)間窗約束，用節(jié)約法進(jìn)行路徑優(yōu)化可得:整個(gè)配送網(wǎng)絡(luò)共派出4 輛車(chē)，2 輛K1和2 輛K2;總路程長(zhǎng)為39.974km;最小費(fèi)用minY=F+P(t)=39.11+2.266=41.376。

通過(guò)以上實(shí)驗(yàn)分析可知，對(duì)于帶軟時(shí)間窗的多配送中心多種車(chē)型的車(chē)輛調(diào)度問(wèn)題可以用此改進(jìn)的節(jié)約算法進(jìn)行優(yōu)化，以實(shí)現(xiàn)配送車(chē)輛最少、總路程最短，從而實(shí)現(xiàn)配送費(fèi)用最小的目標(biāo)。

5 結(jié) 語(yǔ)

論文在研究多配送中心多車(chē)型的車(chē)輛調(diào)度問(wèn)題的基礎(chǔ)上，考慮了更接近現(xiàn)實(shí)情況的軟時(shí)間窗約束，并結(jié)合模型特點(diǎn)用重心法先對(duì)多配送中心進(jìn)行分區(qū)變成各個(gè)單配送中心，然后對(duì)傳統(tǒng)節(jié)約算法進(jìn)行改進(jìn)，加入了多車(chē)型與軟時(shí)間窗約束條件對(duì)單配送中心模型進(jìn)行求解。最后用實(shí)驗(yàn)分析驗(yàn)證了此改進(jìn)的節(jié)約算法對(duì)此模型的有效性。

［1］占焱發(fā).基于遺傳算法的物流配送車(chē)輛路徑問(wèn)題研究［D］.陜西:長(zhǎng)安大學(xué)碩士學(xué)位論文，2010.

［2］Golden B L.Transportation planning models［M］.Amsterdam:Elsevier Science Publishers，1984:384－418.

［3］施朝春，王 旭，葛顯龍.帶有時(shí)間窗的多配送中心車(chē)輛調(diào)度問(wèn)題研究［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45(33):21－24.

［4］陳誠(chéng)，李正紅.多配送中心車(chē)輛路徑問(wèn)題的兩階段算法［J］.三明學(xué)院學(xué)報(bào)，2010，27(6):517－520.

［5］Clarke G，Wright J.Scheduling of vehicles from a central depot to a number of delivery points［J］.OperationResearch，1964，12(4):12－18.

［6］李遠(yuǎn)遠(yuǎn)，劉彥，劉光前.車(chē)輛路徑問(wèn)題優(yōu)化——基于改進(jìn)節(jié)約算法［J］.社會(huì)科學(xué)家，2013，11(9):76－79.

［7］宋偉剛，張宏霞，佟 玲.有時(shí)間窗約束非滿(mǎn)載車(chē)輛調(diào)度問(wèn)題的節(jié)約算法［J］.科技導(dǎo)報(bào)，2006，27(1):65－68.

［8］Golden B，Assad A，Levy L，et al.The fleet size and mix vehicle routing problem［J］.Comps.Opns.Res.，1984，11:49－66.

［9］Ferland J A，Michelon P.The Vehicle scheduling problem with multiple vehicle types［J］.Operational Research Society，1988，39(6):577－583.

［10］崔宏志，龔加安.帶時(shí)間窗車(chē)輛路徑問(wèn)題的改進(jìn)節(jié)約算法［J］.純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué)，2011，27(5):688－693.

［11］陳一永，許力.C－K 節(jié)約算法在配載車(chē)輛調(diào)度問(wèn)題上的應(yīng)用研究［J］.商場(chǎng)現(xiàn)代化，2009，56:149.

［12］張建同，馮子炎.求解車(chē)輛路徑問(wèn)題的改進(jìn)CW 節(jié)約算法［J］.物流技術(shù)，2012，18(2):75－83.