大規(guī)模單車(chē)場(chǎng)VRP問(wèn)題中掃描法的改進(jìn)

2014-12-18 18:12:35王詩(shī)瑤王文發(fā)富文軍李曉英

現(xiàn)代電子技術(shù) 2014年24期

王詩(shī)瑤+王文發(fā)+富文軍+李曉英

摘 ?要：為了降低問(wèn)題規(guī)模，提高掃描法應(yīng)用在單車(chē)場(chǎng)VRP問(wèn)題中初始解的有效性，這里借鑒多車(chē)場(chǎng)VRP等問(wèn)題中的分區(qū)思想，以車(chē)場(chǎng)為中心，根據(jù)需求點(diǎn)覆蓋區(qū)域的特點(diǎn)，對(duì)單車(chē)場(chǎng)VRP提出了新的環(huán)形分區(qū)思想，并給出了幾種具體方法。在此基礎(chǔ)上，對(duì)掃描法進(jìn)行改進(jìn)，分區(qū)分別掃描并且集中車(chē)輛使用率低的區(qū)域重新掃描，合理地降低了大規(guī)模單車(chē)場(chǎng)VRP問(wèn)題的復(fù)雜程度，為第二階段的優(yōu)化提供了有效的初始解。算例表明運(yùn)用該算法比傳統(tǒng)掃描法得到的路徑更優(yōu)且使用車(chē)輛數(shù)更少。

關(guān)鍵詞：車(chē)輛路徑問(wèn)題; 掃描法; 改進(jìn)算法; 單車(chē)場(chǎng)VRP; 大規(guī)模單車(chē)場(chǎng)VRP

中圖分類(lèi)號(hào)： TN911?34; O24 ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ? ? ?文章編號(hào)： 1004?373X（2014）24?0034?03

Improvement of sweep algorithm to deal with large?scale SVRP

WANG Shi?yao， WANG Wen?fa， FU Wen?jun， LI Xiao?ying

（School of Mathematics and Computer Science， Yanan University， Yanan 716000， China）

Abstract： To improve the effectiveness of sweep algorithms initial solution in large?scale single?depot vehicle routing problem （LSVRP） and reduce the scale of the problem， the partition thought of multiple?depot VRP （MDVRP） is employed in this paper. Centering on the yard， a new thought of an annular field partition is put forward according to the characteristics of the covered area at the demand points， and several concrete methods is given. Based on this， the sweep method was improved， that is， partition scan and rescan for the areas with low vehicle?usage rate. This method reduced the complexity of the LSVRP reasonably and provided the effective initial solution for the optimization in the second stage. Experiments show that the algorithm is better than traditional sweep algorithm in path selection and uses less number of vehicles.

Keywords： VRP; sweeping algorithm; improved algorithm; single?depot VRP; LSVRP

車(chē)輛路徑問(wèn)題（Vehicle Routing Problem，VRP）隨著物流業(yè)的發(fā)展越來(lái)越值得研究。Gillett和Miller于1974年提出掃描法[1]，將其應(yīng)用在求解VRP問(wèn)題中簡(jiǎn)單易行，當(dāng)節(jié)點(diǎn)規(guī)模較大時(shí)，運(yùn)用傳統(tǒng)掃描法得到的節(jié)點(diǎn)分組不利于第二階段的路徑優(yōu)化 [2?4]。本文借鑒多車(chē)場(chǎng)VRP（Multiple depots VRP，MDVRP）等問(wèn)題中的分區(qū)方法的研究成果[5?11]，提出一種針對(duì)大規(guī)模單車(chē)場(chǎng)VRP問(wèn)題的環(huán)形分區(qū)思想，在此基礎(chǔ)上改進(jìn)了掃描法。最后運(yùn)用Matlab編程并帶入算例，結(jié)果表明本文提出的環(huán)形掃描法比傳統(tǒng)掃描法的路程和車(chē)輛使用情況更優(yōu)。

1 ?單車(chē)場(chǎng)VRP的描述及模型

1.1 ?問(wèn)題的提出

某采油廠下設(shè)一個(gè)車(chē)場(chǎng)，包含足夠的車(chē)輛且型號(hào)相同，每個(gè)井點(diǎn)都有各自的日產(chǎn)油量，井點(diǎn)、車(chē)場(chǎng)在平面圖上的坐標(biāo)和實(shí)際行駛距離已知，日常運(yùn)作為車(chē)輛從車(chē)場(chǎng)出發(fā)，沿規(guī)定去各個(gè)井點(diǎn)泵油，當(dāng)車(chē)輛剩余載重量無(wú)法滿足下一井點(diǎn)時(shí)返回車(chē)場(chǎng)。要求每個(gè)井點(diǎn)的產(chǎn)量一日內(nèi)僅由一輛車(chē)一次完成。安排怎樣的車(chē)輛調(diào)度方案，可滿足問(wèn)題條件且總路程最小。此問(wèn)題即帶容量約束的單車(chē)場(chǎng)集貨VRP問(wèn)題，總路程為目標(biāo)函數(shù)。

1.2 ?模型的建立

N：井點(diǎn)個(gè)數(shù);

[qi，i∈1，2，…，N]：井點(diǎn)日產(chǎn)油量;

[Q]：車(chē)輛的額定容量;

[dij，i，j∈1，2，…，N+1]：井點(diǎn)間的實(shí)際行駛距離;

[xijm=1，車(chē)輛m從節(jié)點(diǎn)i行駛到節(jié)點(diǎn)j0，否則， ? ? ? ? ? ? ? ? ? i，j=1，2，…，N+1]

[minZ=mMiN+1jN+1xijm] （1）

[j=1N+1m=1Mxijm=1，i∈1，2，…，N+1] （2）

[i=1N+1m=1Mxijm=1，j∈1，2，…，N+1] （3）

[i=1N+1qij=1N+1xijm≤Q，m∈1，2，…，M] （4）

式（1）表示的是一日配送的總路徑，為目標(biāo)函數(shù)。式（2）、式（3）保證每個(gè)用戶(hù)只能被一輛車(chē)服務(wù)一次。式（4）表示車(chē)輛的容量約束。

2 ?掃描法

2.1 ?傳統(tǒng)掃描法

求解過(guò)程從車(chē)場(chǎng)所在點(diǎn)向任意方向引一條射線沿順時(shí)針或逆時(shí)針?lè)较蛐D(zhuǎn)，將掃到的點(diǎn)按順序加入到路徑當(dāng)中，直到加入某點(diǎn)時(shí)貨物量超出車(chē)載量，則剔除此點(diǎn)得到一個(gè)分組并確定一條路線，繼續(xù)旋轉(zhuǎn)構(gòu)造新的路徑直到所有點(diǎn)都被分組并安排到路線中，結(jié)果通常被用作一組可行的初始解，再結(jié)合其他算法進(jìn)行優(yōu)化。

2.2 ?改進(jìn)的環(huán)形掃描法基本思想

環(huán)形掃描法是在傳統(tǒng)掃描法的基礎(chǔ)上，一種改進(jìn)的構(gòu)造啟發(fā)式算法，主要分兩步：分區(qū)和掃描。首先對(duì)井點(diǎn)覆蓋的區(qū)域找出合適的中心點(diǎn)和半徑向量，將其劃分為一些環(huán)形區(qū)域，在此基礎(chǔ)上，以傳統(tǒng)掃描法為原理分區(qū)掃描，最后優(yōu)化初始解。

2.3 ?改進(jìn)的環(huán)形掃描法實(shí)現(xiàn)過(guò)程

2.3.1 ?分區(qū)個(gè)數(shù)

劃分合適的區(qū)域個(gè)數(shù)以及選擇合適的環(huán)形寬度至關(guān)重要。假設(shè)劃分環(huán)形區(qū)域之后掃描得到的分組接近正方形時(shí)最為理想，計(jì)算車(chē)容量約束下此正方形的邊長(zhǎng)即“理想環(huán)寬”。井點(diǎn)區(qū)域覆蓋的面積為S，則平均每個(gè)井點(diǎn)占面積[s=SN]。平均井點(diǎn)產(chǎn)量為[qi]，平均每趟車(chē)包含x個(gè)井點(diǎn)，即[x=Qqi]。則理想分組下正方形邊長(zhǎng)[e=sx=SQNqi]，即“理想環(huán)寬”。

大多數(shù)情況下并不能根據(jù)理想環(huán)寬e剛好劃分為整數(shù)個(gè)區(qū)域，可以根據(jù)井點(diǎn)、車(chē)場(chǎng)坐標(biāo)和e共同決定劃分幾個(gè)區(qū)域，并適當(dāng)調(diào)整實(shí)際每個(gè)環(huán)的寬度，實(shí)際環(huán)寬應(yīng)大于等于e或不小于e太多。

2.3.2 ?幾種環(huán)形分區(qū)方法舉例（以分兩區(qū)為例）

（1）當(dāng)整個(gè)區(qū)域接近圓形時(shí)，根據(jù)理想環(huán)寬設(shè)計(jì)合適的半徑向量（a，b）劃分圓環(huán)形區(qū)域。圓心為P半徑為a的圓及其內(nèi)部為第一區(qū)域，內(nèi)圓為a外圓為b的環(huán)為第二區(qū)域，如圖1所示。

當(dāng)井點(diǎn)覆蓋的區(qū)域橫縱坐標(biāo)范圍差距較大時(shí)，運(yùn)用這種方法不能達(dá)到理想的分區(qū)效果，如圖2所示。此時(shí)如果將橫縱坐標(biāo)調(diào)整比例伸縮為圓形，雖然可以使用方法（1）但會(huì)影響到目標(biāo)函數(shù)值。

圖1 環(huán)形分區(qū)（一）

圖2 環(huán)形分區(qū)（二）

（2）當(dāng)整個(gè)區(qū)域橫縱坐標(biāo)范圍差距較大且大致呈“矩形”時(shí)，劃分“回”字環(huán)形區(qū)域，以車(chē)場(chǎng)所在點(diǎn)作為坐標(biāo)原點(diǎn)，合適的方向建立坐標(biāo)軸，將x、y值分別考慮，見(jiàn)圖3。設(shè)半徑向量為[xa，ya，xb，yb]，則區(qū)域劃分為：

一區(qū)：

[（x，y）x∈-xa，xa，y∈-ya，ya]

二區(qū)：

[（x，y）x∈-xb，-xa?xa，xb?y∈-yb，-ya?ya，yb]

圖3 回形分區(qū)法

2.3.3 ?分組并形成子路徑

以車(chē)場(chǎng)為中心，分別在每個(gè)區(qū)域中選擇相同的起始方向，分別運(yùn)用傳統(tǒng)掃描法，以掃描到的順序?yàn)槊拷M井點(diǎn)的初始解。因?yàn)樗袇^(qū)域的最后一個(gè)分組幾乎都沒(méi)有完全利用車(chē)載量，因此將所有區(qū)域的最后一個(gè)分組合并為一個(gè)區(qū)域，并以車(chē)場(chǎng)為圓心半徑升序掃描分組。

2.3.4 ?優(yōu)化子路徑

運(yùn)用Matlab編程使用節(jié)約算法或WinQSB的Cheapest insertion heuristic功能，對(duì)2.3.2節(jié)得到的每組結(jié)果加入車(chē)場(chǎng)點(diǎn)，以路程為目標(biāo)進(jìn)行優(yōu)化。

3 ?算法仿真對(duì)比

以陜北地區(qū)某單車(chē)場(chǎng)采油廠的泵油作業(yè)為例，包含200個(gè)井點(diǎn)，車(chē)型相同載重量均為20 t。車(chē)場(chǎng)為坐標(biāo)原點(diǎn)，井點(diǎn)的位置和產(chǎn)油量如表1所示。

表1 各井點(diǎn)位置與產(chǎn)量信息

運(yùn)用傳統(tǒng)掃描法和改進(jìn)的環(huán)形掃描法對(duì)算例進(jìn)行測(cè)試。根據(jù)計(jì)算理想環(huán)寬，本例最多可分三區(qū)。前三組傳統(tǒng)掃描法選擇不同的掃描起始點(diǎn);根據(jù)井點(diǎn)分布，后三組改進(jìn)的環(huán)形掃描法都采用“回”字分區(qū)：第四組分兩區(qū)，分區(qū)向量為：

[（0.5rx，0.5ry），（rx，ry）=6，13.5，12，27]

式中[rx]，[ry]為所有井點(diǎn)x，y方向上到車(chē)場(chǎng)的最遠(yuǎn)距離，即[rx=maxxi=13，ry=maxyi=27，i=1，2，…，N];第5組也分兩區(qū)，分區(qū)向量為：

[（lx，ly），（rx，ry）=5.7，11，12，27]

式中[lx]，[ly]為所有井點(diǎn)x，y方向上到車(chē)場(chǎng)的距離均值，即：

[lx=avexi=5.7， ?ly=aveyi=11， ? i=1，2，…，N]

第六組分三區(qū)，分區(qū)向量為：

[（13rx，13ry），（23rx，23ry），（rx，ry）=4，9，（8，18），12，27]

六組算例結(jié)果如表2所示。算例結(jié)果表明，針對(duì)本文測(cè)試的數(shù)據(jù)，三組傳統(tǒng)掃描法的平均總路程為1 161.5，采用本文思想的環(huán)形分區(qū)掃描法的結(jié)果中，第一組分區(qū)法的總路程最優(yōu)為1 097.7，使用車(chē)輛數(shù)也最少，與傳統(tǒng)掃描法相比平均節(jié)約路程（1 161.5-

[1 018.4）1 161.5]=12.3%。其他兩組改進(jìn)掃描法的結(jié)果在車(chē)輛和總路程上也較傳統(tǒng)掃描法有所改進(jìn)。

表2 改進(jìn)掃描法與傳統(tǒng)掃描法結(jié)果對(duì)比

4 ?結(jié) ?論

對(duì)于大規(guī)模單車(chē)場(chǎng)VRP問(wèn)題，本文提出的改進(jìn)掃描得到的分組更集中便于管理;并且提高了二階段優(yōu)化路徑目標(biāo)的效果，使用車(chē)輛減少，平均每輛車(chē)服務(wù)的節(jié)點(diǎn)數(shù)增加，平均載重率提高，總路程明顯減少;同時(shí)，以環(huán)形或回型劃分區(qū)域之后，掃描寬度減小，更加便于掃描法的人工計(jì)算。算例表明，合適的分區(qū)個(gè)數(shù)和分區(qū)方法是環(huán)形掃描法的關(guān)鍵。第四、五、六組算例表明在分區(qū)的個(gè)數(shù)和分區(qū)界限選取上還有很大的研究空間。

參考文獻(xiàn)

[1] GILLET B E， MILLER L R. A heuristic algorithm for the vehicle dispatch problem [J]. Operations Research， 1974， 22： 340?349.

[2] WREN A. Computers in transport planning and operation [M]. London： Ian Allan， 1971.

[3] WREN A， HOLLIDAY A. Computer scheduling of vehicles from one or more depots to a number of delivery points [J]. Operational Research， 1972， 23： 333?344.

[4] RENAUD J， BOCTOR F F. A sweep?based algorithm for the fleet size and mix vehicle routing problem [J]. European Journal of Operational Research， 2002， 140： 618?628.

[5] 曹二保，賴(lài)明勇，聶凱，等.大規(guī)模物流配送車(chē)輛調(diào)度問(wèn)題研究[J].湖南大學(xué)學(xué)報(bào)：自然科學(xué)版，2007（12）：94?97.

[6] 曲志偉，蔡臨寧，李晨，等.大規(guī)模車(chē)輛配送/收集問(wèn)題的求解框架[J].清華大學(xué)學(xué)報(bào)：自然科學(xué)版，2004（5）：7?10.

[7] 李兵，鄭四發(fā)，曹劍東，等.基于路網(wǎng)分層策略的多源點(diǎn)最短距離算法[J].計(jì)算機(jī)工程，2008（12）：43?45.

[8] 李松，劉興，張愛(ài)國(guó)，等.基于SWEEP方法的改進(jìn)車(chē)輛路徑協(xié)作策略研究[J].系統(tǒng)工程與電子技術(shù)，2008（3）：103?105.

[9] 丁源，李引珍.物流配送（集貨）中運(yùn)輸車(chē)輛優(yōu)化的Greedy Sweep算法[J].蘭州交通大學(xué)學(xué)報(bào)，2004（6）：144?146.

[10] 楊文霞，郭海湘，楊娟，等.改進(jìn)的掃描法求解單車(chē)場(chǎng)多車(chē)型車(chē)輛路徑問(wèn)題[J].物流技術(shù)，2010（8）：56?59.

[11] 鄧欣.多車(chē)場(chǎng)車(chē)輛路徑問(wèn)題的改進(jìn)遺傳算法求解[J].計(jì)算機(jī)科學(xué)，2007，34（8）：103?107.