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

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

關鍵詞： 車輛路徑問題; 掃描法; 改進算法; 單車場VRP; 大規(guī)模單車場VRP

中圖分類號： TN911?34; O24 ? ? ? ? ? ? ? ? ? 文獻標識碼： A ? ? ? ? ? ? ? ? ? ? ?文章編號： 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

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

1 ?單車場VRP的描述及模型

1.1 ?問題的提出

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

1.2 ?模型的建立

N：井點個數(shù);

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

[Q]：車輛的額定容量;

[dij，i，j∈1，2，…，N+1]：井點間的實際行駛距離;

[xijm=1，車輛m從節(jié)點i行駛到節(jié)點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）表示的是一日配送的總路徑，為目標函數(shù)。式（2）、式（3）保證每個用戶只能被一輛車服務一次。式（4）表示車輛的容量約束。

2 ?掃描法

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

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

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

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

2.3 ?改進的環(huán)形掃描法實現(xiàn)過程

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

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

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

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

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

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

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

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

（2） 當整個區(qū)域橫縱坐標范圍差距較大且大致呈“矩形”時，劃分“回”字環(huán)形區(qū)域，以車場所在點作為坐標原點，合適的方向建立坐標軸，將x、y值分別考慮，見圖3。設半徑向量為[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 ?分組并形成子路徑

以車場為中心，分別在每個區(qū)域中選擇相同的起始方向，分別運用傳統(tǒng)掃描法，以掃描到的順序為每組井點的初始解。因為所有區(qū)域的最后一個分組幾乎都沒有完全利用車載量，因此將所有區(qū)域的最后一個分組合并為一個區(qū)域，并以車場為圓心半徑升序掃描分組。

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

運用Matlab編程使用節(jié)約算法或WinQSB的Cheapest insertion heuristic功能，對2.3.2節(jié)得到的每組結果加入車場點，以路程為目標進行優(yōu)化。

3 ?算法仿真對比

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

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

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

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

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

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

式中[lx]，[ly]為所有井點x，y方向上到車場的距離均值，即：

[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]

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

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

表2 改進掃描法與傳統(tǒng)掃描法結果對比

4 ?結 ?論

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

參考文獻

[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] 曹二保，賴明勇，聶凱，等.大規(guī)模物流配送車輛調(diào)度問題研究[J].湖南大學學報：自然科學版，2007（12）：94?97.

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

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

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

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

[10] 楊文霞，郭海湘，楊娟，等.改進的掃描法求解單車場多車型車輛路徑問題[J].物流技術，2010（8）：56?59.

[11] 鄧欣.多車場車輛路徑問題的改進遺傳算法求解[J].計算機科學，2007，34（8）：103?107.

參考文獻

[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] 曹二保，賴明勇，聶凱，等.大規(guī)模物流配送車輛調(diào)度問題研究[J].湖南大學學報：自然科學版，2007（12）：94?97.

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

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

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

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

[10] 楊文霞，郭海湘，楊娟，等.改進的掃描法求解單車場多車型車輛路徑問題[J].物流技術，2010（8）：56?59.

[11] 鄧欣.多車場車輛路徑問題的改進遺傳算法求解[J].計算機科學，2007，34（8）：103?107.

參考文獻

[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] 曹二保，賴明勇，聶凱，等.大規(guī)模物流配送車輛調(diào)度問題研究[J].湖南大學學報：自然科學版，2007（12）：94?97.

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

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

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

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

[10] 楊文霞，郭海湘，楊娟，等.改進的掃描法求解單車場多車型車輛路徑問題[J].物流技術，2010（8）：56?59.

[11] 鄧欣.多車場車輛路徑問題的改進遺傳算法求解[J].計算機科學，2007，34（8）：103?107.