電子技術(shù)文章發(fā)表大規(guī)模單車場VRP問題中掃描法的改進

電子技術(shù)文章發(fā)表大規(guī)模單車場VRP問題中掃描法的改進摘要：為了降低問題規(guī)模，提高掃描法應(yīng)用在單車場VRP問題中初始解的有效性，這里借鑒多車場VRP等問題中的分區(qū)思想，以車場為中心，根據(jù)需求點覆蓋區(qū)域的特點，對單車場VRP提出了新的環(huán)形分區(qū)思想，并給出了幾種具體方法。在此基礎(chǔ)上，對掃描法進行改進，分區(qū)分別掃描并且集中車輛使用率低的區(qū)域重新掃描，合理地降低了大規(guī)模單車場VRP問題的復(fù)雜程度，為第二階段的優(yōu)化提供了有效的初始解。算例表明運用該算法比傳統(tǒng)掃描法得到的路徑更優(yōu)且使用車輛數(shù)更少。關(guān)鍵詞：電子技術(shù)文章發(fā)表,車輛路徑問題,掃描法,改進算法,單車場VRP,大規(guī)模單車場VRPImprovementofsweepalgorithmtodealwithlarge?scaleSVRPWANGShi?yao，WANGWen?fa，F(xiàn)UWen?jun，LIXiao?ying(SchoolofMathematicsandComputerScience，Yan’anUniversity，Yan’an716000，China)Abstract：Toimprovetheeffectivenessofsweepalgorithm’sinitialsolutioninlarge?scalesingle?depotvehicleroutingproblem(LSVRP)andreducethescaleoftheproblem，thepartitionthoughtofmultiple?depotVRP(MDVRP)isemployedinthispaper.Centeringontheyard，anewthoughtofanannularfieldpartitionisputforwardaccordingtothecharacteristicsofthecoveredareaatthedemandpoints，andseveralconcretemethodsisgiven.Basedonthis，thesweepmethod1wasimproved，thatis，partitionscanandrescanfortheareaswithlowvehicle?usagerate.ThismethodreducedthecomplexityoftheLSVRPreasonablyandprovidedtheeffectiveinitialsolutionfortheoptimizationinthesecondstage.Experimentsshowthatthealgorithmisbetterthantraditionalsweepalgorithminpathselectionanduseslessnumberofvehicles.Keywords：VRP;sweepingalgorithm;improvedalgorithm;single?depotVRP;LSVRP車輛路徑問題(VehicleRoutingProblem，VRP)隨著物流業(yè)的發(fā)展越來越值得研究。Gillett和Miller于1974年提出掃描法[1]，將其應(yīng)用在求解VRP問題中簡單易行，當(dāng)節(jié)點規(guī)模較大時，運用傳統(tǒng)掃描法得到的節(jié)點分組不利于第二階段的路徑優(yōu)化[2?4]。本文借鑒多車場VRP(MultipledepotsVRP，MDVRP)等問題中的分區(qū)方法的研究成果[5?11]，提出一種針對大規(guī)模單車場VRP問題的環(huán)形分區(qū)思想，在此基礎(chǔ)上改進了掃描法。最后運用Matlab編程并帶入算例，結(jié)果表明本文提出的環(huán)形掃描法比傳統(tǒng)掃描法的路程和車輛使用情況更優(yōu)。1單車場VRP的描述及模型1.1問題的提出某采油廠下設(shè)一個車場，包含足夠的車輛且型號相同，每個井點都有各自的日產(chǎn)油量，井點、車場在平面圖上的坐標(biāo)和實際行駛距離已知，日常運作為車輛從車場出發(fā)，沿規(guī)定去各個井點泵油，當(dāng)車輛剩余載重量無法滿足下一井點時返回車場。要求每個井點的產(chǎn)量一日內(nèi)僅由一輛車一次完成。安排怎樣的車輛調(diào)度方案，可滿足問題條件且總路程最小。此問題即帶容量約束的單車場集貨VRP問題，總路程為目標(biāo)函數(shù)。21.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)表示的是一日配送的總路徑，為目標(biāo)函數(shù)。式(2)、式(3)保證每個用戶只能被一輛車服務(wù)一次。式(4)表示車輛的容量約束。掃描法2.1傳統(tǒng)掃描法求解過程從車場所在點向任意方向引一條射線沿順時針或逆時針方向旋轉(zhuǎn)，將掃到的點按順序加入到路徑當(dāng)中，直到加入某點時貨物量超出車載量，3則剔除此點得到一個分組并確定一條路線，繼續(xù)旋轉(zhuǎn)構(gòu)造新的路徑直到所有點都被分組并安排到路線中，結(jié)果通常被用作一組可行的初始解，再結(jié)合其他算法進行優(yōu)化。2.2改進的環(huán)形掃描法基本思想環(huán)形掃描法是在傳統(tǒng)掃描法的基礎(chǔ)上，一種改進的構(gòu)造啟發(fā)式算法，主要分兩步：分區(qū)和掃描。首先對井點覆蓋的區(qū)域找出合適的中心點和半徑向量，將其劃分為一些環(huán)形區(qū)域，在此基礎(chǔ)上，以傳統(tǒng)掃描法為原理分區(qū)掃描，最后優(yōu)化初始解。2.3改進的環(huán)形掃描法實現(xiàn)過程2.3.1分區(qū)個數(shù)劃分合適的區(qū)域個數(shù)以及選擇合適的環(huán)形寬度至關(guān)重要。假設(shè)劃分環(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ù)井點、車場坐標(biāo)和e共同決定劃分幾個區(qū)域，并適當(dāng)調(diào)整實際每個環(huán)的寬度，實際環(huán)寬應(yīng)大于等于e或不小于e太多。2.3.2幾種環(huán)形分區(qū)方法舉例(以分兩區(qū)為例)當(dāng)整個區(qū)域接近圓形時，根據(jù)理想環(huán)寬設(shè)計合適的半徑向量(a，b)劃分圓環(huán)形區(qū)域。圓心為P半徑為a的圓及其內(nèi)部為第一區(qū)域，內(nèi)圓為a外圓4為b的環(huán)為第二區(qū)域，如圖1所示。當(dāng)井點覆蓋的區(qū)域橫縱坐標(biāo)范圍差距較大時，運用這種方法不能達到理想的分區(qū)效果，如圖2所示。此時如果將橫縱坐標(biāo)調(diào)整比例伸縮為圓形，雖然可以使用方法(1)但會影響到目標(biāo)函數(shù)值。1環(huán)形分區(qū)(一)2環(huán)形分區(qū)(二)當(dāng)整個區(qū)域橫縱坐標(biāo)范圍差距較大且大致呈“矩形”時，劃分“回”字環(huán)形區(qū)域，以車場所在點作為坐標(biāo)原點，合適的方向建立坐標(biāo)軸，將x、y值分別考慮，見圖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分組并形成子路徑以車場為中心，分別在每個區(qū)域中選擇相同的起始方向，分別運用傳統(tǒng)掃描法，以掃描到的順序為每組井點的初始解。因為所有區(qū)域的最后一個分組幾乎都沒有完全利用車載量，因此將所有區(qū)域的最后一個分組合并為一個區(qū)域，并5以車場為圓心半徑升序掃描分組。2.3.4優(yōu)化子路徑運用Matlab編程使用節(jié)約算法或WinQSB的Cheapestinsertionheuristic功能，對2.3.2節(jié)得到的每組結(jié)果加入車場點，以路程為目標(biāo)進行優(yōu)化。算法仿真對比以陜北地區(qū)某單車場采油廠的泵油作業(yè)為例，包含200個井點，車型相同載重量均為20t。車場為坐標(biāo)原點，井點的位置和產(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]6第六組分三區(qū)，分區(qū)向量為：[(13rx，13ry)，(23rx，23ry)，(rx，ry)=4，9，(8，18)，12，27]六組算例結(jié)果如表2所示。算例結(jié)果表明，針對本文測試的數(shù)據(jù)，三組傳統(tǒng)掃描法的平均總路程為1161.5，采用本文思想的環(huán)形分區(qū)掃描法的結(jié)果中，第一組分區(qū)法的總路程最優(yōu)為1097.7，使用車輛數(shù)也最少，與傳統(tǒng)掃描法相比平均節(jié)約路程(1161.5-[1018.4)1161.5]=12.3%。其他兩組改進掃描法的結(jié)果在車輛和總路程上也較傳統(tǒng)掃描法有所改進。