帶時間窗的多配送中心多車型車輛調(diào)度問題

高珊珊，李萌萌

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

0 引 言

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

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

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

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

1.1 時間窗約束問題

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

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

1.2 問題與約束條件

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

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

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

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

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

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

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

1.3 VSP 模型的建立

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

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

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

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

2.1 重心法介紹

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

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

2.2 算法步驟

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

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

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

2.3 算例描述

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

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

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

3.1 節(jié)約算法介紹

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

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

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

3.2.1 軟時間窗設(shè)計

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

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

(2)時間變化引起的懲罰成本:若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 多車型設(shè)計

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

4 實驗分析

配送中心與客戶信息如表1所示，其中參數(shù)設(shè)置為:a=1/h ;b=5/h ;y 代表單位里程費(fèi)用，其中包括燃油費(fèi)，司機(jī)工資等，yk1=1.1/km;yk2=1/km;車型容量Ck1=8t;Ck2=4t;最大行程:Sk1=15;Sk2=10;車速v=2;卸貨時間統(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 輛車K1，K2分別為1，3，10 和9 服務(wù)后返回配送中心1;L3，L4表示配送中心2 派2 輛車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á)客戶1 的時間10:30［9:45－10:45］，即不產(chǎn)生懲罰成本;K1到達(dá)客戶3 的時間為11:47［12:30－－13:00］，即產(chǎn)生等待懲罰成本P(t)=43/60* 1=0.716;客戶10 的時間屬于全天，即不產(chǎn)生懲罰成本;則路徑L1產(chǎn)生的懲罰成本為P(t)=0.716;同理可得L2無懲罰成本;L3的延遲懲罰成本為:P(t)=17/60* 5=1.417;L4產(chǎn)生的等待懲罰成本為:P(t)=8/60* 1=0.133。

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

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

5 結(jié) 語

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

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

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

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

［4］陳誠，李正紅.多配送中心車輛路徑問題的兩階段算法［J］.三明學(xué)院學(xué)報，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)，劉彥，劉光前.車輛路徑問題優(yōu)化——基于改進(jìn)節(jié)約算法［J］.社會科學(xué)家，2013，11(9):76－79.

［7］宋偉剛，張宏霞，佟 玲.有時間窗約束非滿載車輛調(diào)度問題的節(jié)約算法［J］.科技導(dǎ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］崔宏志，龔加安.帶時間窗車輛路徑問題的改進(jìn)節(jié)約算法［J］.純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué)，2011，27(5):688－693.

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

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