大規(guī)模單車場VRP問題中掃描法的改進(jìn)-精選文檔

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

2、WANGShi?yao , WANGWen?fa, FU Wen?jun, LI Xiao?yingSchool of Mathematics and Computer Science , Yan, anUniversity , Yan，an 716000 , China ):To improve the effectiveness of sweep algorithm ' s initial solution in large?scale single?depot vehicle routing problem ( LSV R P) and reduce the scale of t

3、he problem , the partition thought of multiple?depot VRPMDVR)P 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 thedemand points , and several concrete methods is given.Based on this ,

4、 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 t

5、han 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于1 974年提出掃描法1,將其應(yīng)用在求解VRP問題中簡單易行，當(dāng)節(jié)點(diǎn)規(guī)模較大時，運(yùn)用傳統(tǒng)掃描法得到的節(jié)點(diǎn)分組不利于第二階段的路徑優(yōu)化 2?4 o

6、 本文借鑒多車場 VRP( Multiple depots VRP, MDVRP等問題中的分區(qū)方法的研究成果：5?11,提出一種針對大規(guī)模單車場VRP問題的 環(huán)形分區(qū)思想，在此基礎(chǔ)上改進(jìn)了掃描法。最后 運(yùn)用Mat lab編程 并帶入算 例，結(jié)果表明本文提出的環(huán)形掃描法比傳統(tǒng)掃描法的路程和車輛使用情況更優(yōu)。1單車場VRP的描述及模型1. 1問題的提出某采油廠下設(shè)一個車場，包含足夠的車輛且型號相同，每個 井點(diǎn)都有 各自 的日產(chǎn)油量，井點(diǎn)、車場在平面圖上的坐標(biāo)和實(shí)際行駛距離已知，日常運(yùn)作為車輛 從車場出發(fā)，沿規(guī)定去各個井點(diǎn)泵油，當(dāng)車輛剩余載重量無法滿足下一井點(diǎn)時返回 車場。要求每 個井點(diǎn)的產(chǎn)量一日內(nèi)

7、僅由一輛車一次完成。安排怎樣的車輛調(diào)度 方 案，可滿足問題條件且總路程最小。此問題即帶容量約束的單車場集貨VRP問 題，總路程為目標(biāo)函數(shù)。1. 2模型的建立N：井點(diǎn)個數(shù)；qi , i 1, 2, , N：井點(diǎn)日產(chǎn)油量;Q:車輛的額定容量；dij , i , j 1, 2, - N+1：井點(diǎn)間的實(shí)際行駛距離;xijm=l,車輛m從節(jié)點(diǎn)i行駛到節(jié)點(diǎn)jO ,否則，i , M , 2,N+1minZ=mMiN+ljN+lxijm，j 二 IN+Im 二 IMxijm 二 1 , i 1, 2,，N+1 (2)i=lN+lm=lMxijm=l , j 1, 2,，N+1(3)_i 二 IN+lqi j=

8、lN+l xi jm <Q me 1, 2, 一，M (4)式(1)表示的是一日配送的總路徑，為目標(biāo)函數(shù)。式、式(3)保證 每個用 戶只能被一輛車服務(wù)一次。式(4)表示車輛的容量約束。2掃描法2. 1傳統(tǒng)掃描法求解過程從車場所在點(diǎn)向任意方向引一條射線沿順時針或逆時針方向旋轉(zhuǎn)，將掃到的點(diǎn)按順序加入到路徑當(dāng)中，直到加入某點(diǎn)時貨物量超出車載量，則剔 除此點(diǎn)得到一個分組并確定一條路線，繼續(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ā)式算法，主要 分

9、兩步：分區(qū)和掃描。首先對井點(diǎn)覆蓋的區(qū)域找出合適的中心點(diǎn)和半徑向量，將其 劃分為一些環(huán)形區(qū)域，在此基礎(chǔ)上，以傳統(tǒng)掃描法為原理分區(qū)掃描，最后優(yōu)化初 始解。2. 3改進(jìn)的環(huán)形掃描法實(shí)現(xiàn)過程2. 3. 1分區(qū)個數(shù)劃分合適的區(qū)域個數(shù)以及選擇合適的環(huán)形寬度至關(guān)重要。設(shè)劃分環(huán)形區(qū)域之后掃描得到的分組接近正方形時最為理想，算車容量約束下此正 方形的邊長即“理想環(huán)寬”。井點(diǎn)區(qū)域覆蓋 的面積為S,則平均每個井點(diǎn)占面積 s=SN。平均井點(diǎn)產(chǎn)量為 qi,平均每趟車包含x個井點(diǎn)，即x=Qqi。則理想分組下正 方形邊 長e二sx 二SQNqi,即“理想環(huán)寬”。大多數(shù)情況下并不能根據(jù)理想環(huán)寬e剛好劃分為整數(shù)個區(qū)域，可以根據(jù)

10、井 點(diǎn)、車場坐標(biāo)和e共同決定劃分幾個區(qū)域，并適當(dāng)調(diào)整實(shí)際每個環(huán)的寬度，實(shí)際環(huán)寬應(yīng)大于等于e或不小于e太多。2. 3. 2幾種環(huán)形分區(qū)方法舉例（以分兩區(qū)為例）1）當(dāng)整個區(qū)域接近圓形時，根據(jù)理想環(huán)寬設(shè)計合適的半徑向量（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)范圍差距較大時，運(yùn)用這種方法不能達(dá)到理想的分區(qū)效果，如圖2所示。此時如果將橫縱坐標(biāo)調(diào)整比例伸 縮為圓 形，雖然可以使用方法（1）但會影響到目標(biāo)函數(shù)值。圖1環(huán)形分區(qū)（一）圖2環(huán)形分區(qū)（二）2）當(dāng)整個區(qū)域橫縱坐標(biāo)范圍差距較大且大致呈“矩形”時，劃分“回”字

11、環(huán)形區(qū)域，以車場所在點(diǎn)作為坐標(biāo)原點(diǎn)，合適的方向建立坐標(biāo)軸，將x、y值分別考慮，見圖3o設(shè)半徑向量為xa , ya, xb, yb,則區(qū)域劃分為：一區(qū)：_ （x, y）xe -xa , xa, ye -ya , ya.二區(qū)：_ （x, y）xe -xb , -xa?xa , xb?ye -yb , -ya?ya , yb.圖3回形分區(qū)法2. 3. 3分組并形成子路徑以車場為中心，分別在每個區(qū)域中選擇相同的起始方向，分別運(yùn)用傳統(tǒng)掃描法，以掃描到的順序為每組井點(diǎn)的初始解。因為所有區(qū)域的最后一個分組幾乎都沒有完全利用車載量，因此將所有區(qū)域的最后一個分組合并為一個區(qū)域，并以車場為圓心半徑升序掃描分組。2

12、. 3. 4優(yōu)化子路徑Win QSB 的 Chea pest節(jié)得到的每組結(jié)果加入車運(yùn)用Mat lab編程使用節(jié)約算法或 insertion heuristic 功能， 對 2 3 2場點(diǎn)，以路程為目標(biāo)進(jìn)行優(yōu)化。3算法仿真對比以陜北地區(qū)某單車場采油廠的泵油作業(yè)為例，包含200個井點(diǎn)，車型相同載重量均為20 t。車場為坐標(biāo)原點(diǎn)，井點(diǎn)的位置和產(chǎn)油量如表1所示。表1各井點(diǎn)位置與產(chǎn)量信息運(yùn)用傳統(tǒng)掃描法和改進(jìn)的環(huán)形掃描法對算例進(jìn)行測試。 根據(jù)計算理想環(huán)寬，本例最多可分三區(qū)。前三組傳統(tǒng)掃描法選擇不同的掃描起始點(diǎn)；根據(jù)井點(diǎn)分布，后三組改進(jìn)的環(huán)形掃描法都采用回”字分區(qū)：第四組分兩區(qū)，分區(qū)向量為：_ (0. 5r

13、x , 0. 5ry ) , ( rx , ry ) =6, 13. 5, 12, 27.式中rx , ry為所有井點(diǎn)x, y方向上到車場的最遠(yuǎn)距離，即rx 二 maxxi 二 13 , ry=maxyi=27 , i=l , 2 ,N；第 5 組也分兩 區(qū)，分區(qū)向量為:.(lx , ly ) , rx , ry )=5. 7, 11, 12, 27：式中l(wèi)x , ly為所有井點(diǎn)X, y方向上到車場的距離均值，即：lx=avexi=5 , 7 ly=aveyi=lli=l , 2, , , , , N第六組分三區(qū)，分區(qū)向量為：(13rx , 13ry ) ,(23rx , 23ry ) , (rx , ry ) =4, 9,(8,18),12, 27六組算例結(jié)果如表2所示。算例結(jié)果表明，針對本文測試的數(shù)據(jù)，三組傳統(tǒng) 掃描法的平均總路程為1 161. 5，采用本文思想的環(huán)形分區(qū)掃描法 的結(jié)果中，第一 組分區(qū)法的總路程最優(yōu)為1 097. 7，使用車輛數(shù)也最少，與傳統(tǒng)掃描法相比平均節(jié) 約路程(1 161.5-1 018. 4 ) 1 161. 5二12. 3%。其他兩組改進(jìn)掃描法的結(jié)果在 車輛和 總路程上也較傳統(tǒng)掃描法有所改進(jìn)