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

　　關鍵詞： 電子技術論文發表,車輛路徑問題,掃描法,改進算法,單車場VRP,大規模單車場VRP

　　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， Yan’an University， Yan’an 716000， China)

　　Abstract： To improve the effectiveness of sweep algorithm’s 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)隨著物流業的發展越來越值得研究。Gillett和Miller于1974年提出掃描法[1]，將其應用在求解VRP問題中簡單易行，當節點規模較大時，運用傳統掃描法得到的節點分組不利于第二階段的路徑優化 [2?4]。本文借鑒多車場VRP(Multiple depots VRP，MDVRP)等問題中的分區方法的研究成果[5?11]，提出一種針對大規模單車場VRP問題的環形分區思想，在此基礎上改進了掃描法。最后運用 Matlab編程并帶入算例，結果表明本文提出的環形掃描法比傳統掃描法的路程和車輛使用情況更優。

　　1 單車場VRP的描述及模型

　　1.1 問題的提出

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

　　1.2 模型的建立

　　N：井點個數;

　　[qi，i∈1，2，…，N]：井點日產油量;

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

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

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

　　2 掃描法

　　2.1 傳統掃描法

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

　　2.2 改進的環形掃描法基本思想

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

　　2.3 改進的環形掃描法實現過程

　　2.3.1 分區個數

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

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

　　2.3.2 幾種環形分區方法舉例(以分兩區為例)

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

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

　　圖1 環形分區(一)

　　圖2 環形分區(二)

　　(2) 當整個區域橫縱坐標范圍差距較大且大致呈“矩形”時，劃分“回”字環形區域，以車場所在點作為坐標原點，合適的方向建立坐標軸，將x、y值分別考慮，見圖3。設半徑向量為[xa，ya，xb，yb]，則區域劃分為：

　　一區：

　　[(x，y)x∈-xa，xa，y∈-ya，ya]

　　二區：

　　[(x，y)x∈-xb，-xa?xa，xb?y∈-yb，-ya?ya，yb]

　　圖3 回形分區法

　　2.3.3 分組并形成子路徑

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

　　2.3.4 優化子路徑

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

　　3 算法仿真對比

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

　　表1 各井點位置與產量信息

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

　　[(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組也分兩區，分區向量為：

　　[(lx，ly)，(rx，ry)=5.7，11，12，27]

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

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

　　第六組分三區，分區向量為：

　　[(13rx，13ry)，(23rx，23ry)，(rx，ry)=4，9，(8，18)，12，27]

　　六組算例結果如表2所示。算例結果表明，針對本文測試的數據，三組傳統掃描法的平均總路程為1 161.5，采用本文思想的環形分區掃描法的結果中，第一組分區法的總路程最優為1 097.7，使用車輛數也最少，與傳統掃描法相比平均節約路程(1 161.5-

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

　　表2 改進掃描法與傳統掃描法結果對比

　　4 結 論

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

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