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

電子技術(shù)文章發(fā)表大規(guī)模單車場(chǎng)VRP問題中掃描法的改進(jìn)摘要：為了降低問題規(guī)模，提高掃描法應(yīng)用在單車場(chǎng)VRP問題中初始解的有效性，這里借鑒多車場(chǎng)VRP等問題中的分區(qū)思想，以車場(chǎng)為中心，根據(jù)需求點(diǎn)覆蓋區(qū)域的特點(diǎn)，對(duì)單車場(chǎng)VRP提出了新的環(huán)形分區(qū)思想，并給出了幾種具體方法。在此基礎(chǔ)上，對(duì)掃描法進(jìn)行改進(jìn)，分區(qū)分別掃描并且集中車輛使用率低的區(qū)域重新掃描，合理地降低了大規(guī)模單車場(chǎng)VRP問題的復(fù)雜程度，為第二階段的優(yōu)化提供了有效的初始解。算例表明運(yùn)用該算法比傳統(tǒng)掃描法得到的路徑更優(yōu)且使用車輛數(shù)更少。關(guān)鍵詞：電子技術(shù)文章發(fā)表,車輛路徑問題,掃描法,改進(jìn)算法,單車場(chǎng)VRP,大規(guī)模單車場(chǎng)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問題中簡(jiǎn)單易行，當(dāng)節(jié)點(diǎn)規(guī)模較大時(shí)，運(yùn)用傳統(tǒng)掃描法得到的節(jié)點(diǎn)分組不利于第二階段的路徑優(yōu)化[2?4]。本文借鑒多車場(chǎng)VRP(MultipledepotsVRP，MDVRP)等問題中的分區(qū)方法的研究成果[5?11]，提出一種針對(duì)大規(guī)模單車場(chǎng)VRP問題的環(huán)形分區(qū)思想，在此基礎(chǔ)上改進(jìn)了掃描法。最后運(yùn)用Matlab編程并帶入算例，結(jié)果表明本文提出的環(huán)形掃描法比傳統(tǒng)掃描法的路程和車輛使用情況更優(yōu)。1單車場(chǎng)VRP的描述及模型1.1問題的提出某采油廠下設(shè)一個(gè)車場(chǎng)，包含足夠的車輛且型號(hào)相同，每個(gè)井點(diǎn)都有各自的日產(chǎn)油量，井點(diǎn)、車場(chǎng)在平面圖上的坐標(biāo)和實(shí)際行駛距離已知，日常運(yùn)作為車輛從車場(chǎng)出發(fā)，沿規(guī)定去各個(gè)井點(diǎn)泵油，當(dāng)車輛剩余載重量無法滿足下一井點(diǎn)時(shí)返回車場(chǎng)。要求每個(gè)井點(diǎn)的產(chǎn)量一日內(nèi)僅由一輛車一次完成。安排怎樣的車輛調(diào)度方案，可滿足問題條件且總路程最小。此問題即帶容量約束的單車場(chǎng)集貨VRP問題，總路程為目標(biāo)函數(shù)。21.2模型的建立N：井點(diǎn)個(gè)數(shù);[qi，i∈1，2，…，N]：井點(diǎn)日產(chǎn)油量;[Q]：車輛的額定容量;[dij，i，j∈1，2，…，N+1]：井點(diǎn)間的實(shí)際行駛距離;[xijm=1，車輛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è)用戶只能被一輛車服務(wù)一次。式(4)表示車輛的容量約束。掃描法2.1傳統(tǒng)掃描法求解過程從車場(chǎng)所在點(diǎn)向任意方向引一條射線沿順時(shí)針或逆時(shí)針方向旋轉(zhuǎn)，將掃到的點(diǎn)按順序加入到路徑當(dāng)中，直到加入某點(diǎn)時(shí)貨物量超出車載量，3則剔除此點(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)過程2.3.1分區(qū)個(gè)數(shù)劃分合適的區(qū)域個(gè)數(shù)以及選擇合適的環(huán)形寬度至關(guān)重要。假設(shè)劃分環(huán)形區(qū)域之后掃描得到的分組接近正方形時(shí)最為理想，計(jì)算車容量約束下此正方形的邊長(zhǎng)即“理想環(huán)寬”。井點(diǎn)區(qū)域覆蓋的面積為S，則平均每個(gè)井點(diǎn)占面積[s=SN]。平均井點(diǎn)產(chǎn)量為[qi]，平均每趟車包含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ǎ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ū)為例)當(dāng)整個(gè)區(qū)域接近圓形時(shí)，根據(jù)理想環(huán)寬設(shè)計(jì)合適的半徑向量(a，b)劃分圓環(huán)形區(qū)域。圓心為P半徑為a的圓及其內(nèi)部為第一區(qū)域，內(nèi)圓為a外圓4為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ū)(二)當(dāng)整個(gè)區(qū)域橫縱坐標(biāo)范圍差距較大且大致呈“矩形”時(shí)，劃分“回”字環(huán)形區(qū)域，以車場(chǎng)所在點(diǎn)作為坐標(biāo)原點(diǎn)，合適的方向建立坐標(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分組并形成子路徑以車場(chǎng)為中心，分別在每個(gè)區(qū)域中選擇相同的起始方向，分別運(yùn)用傳統(tǒng)掃描法，以掃描到的順序?yàn)槊拷M井點(diǎn)的初始解。因?yàn)樗袇^(qū)域的最后一個(gè)分組幾乎都沒有完全利用車載量，因此將所有區(qū)域的最后一個(gè)分組合并為一個(gè)區(qū)域，并5以車場(chǎng)為圓心半徑升序掃描分組。2.3.4優(yōu)化子路徑運(yùn)用Matlab編程使用節(jié)約算法或WinQSB的Cheapestinsertionheuristic功能，對(duì)2.3.2節(jié)得到的每組結(jié)果加入車場(chǎng)點(diǎn)，以路程為目標(biāo)進(jìn)行優(yōu)化。算法仿真對(duì)比以陜北地區(qū)某單車場(chǎng)采油廠的泵油作業(yè)為例，包含200個(gè)井點(diǎn)，車型相同載重量均為20t。車場(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ǎ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ǎng)的距離均值，即：[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é)果表明，針對(duì)本文測(cè)試的數(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%。其他兩組改進(jìn)掃描法的結(jié)果在車輛和總路程上也較傳統(tǒng)掃描法有所改進(jìn)。