• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    基于多元優(yōu)化算法的三維裝箱問題的研究

    2018-03-10 02:52:01李孫寸施心陵張松海
    自動化學(xué)報 2018年1期
    關(guān)鍵詞:裝箱搜索算法箱子

    李孫寸 施心陵 張松海 董 易 高 蓮

    裝箱問題按照目標(biāo)函數(shù)的不同類型分為容器裝載問題、箱柜裝載問題和背包裝載問題[1].容器裝載問題是將所有待裝箱子裝入一個不限尺寸的容器中,在諸多方案中找到一個使容器體積最小的裝載方案,該類型問題一般規(guī)定容器的長和寬為常數(shù),高為變量;箱柜裝載問題是給定一些規(guī)格統(tǒng)一的方型容器和一些不同類型的方型箱子,找到一個能把所有箱子裝入最少容器中的裝載方案;背包裝載問題是給定一個固定規(guī)格的容器和一些有一定價值的箱子,然后將部分箱子裝入容器中,找到一個使得裝入容器中箱子總價值最大的裝載方案,若將箱子的體積作為價值,則背包裝載問題就轉(zhuǎn)換為找到一個如何使容器的填充率最大的裝載方案.其中容器裝載問題和箱柜裝載問題具有一定的局限性,限制了其工業(yè)領(lǐng)域的應(yīng)用范圍.因此本文從背包裝載問題入手對三維裝箱問題作初步研究.

    裝箱問題是傳統(tǒng)的NP問題,具有廣泛的應(yīng)用領(lǐng)域.隨著當(dāng)今世界信息技術(shù)、大數(shù)據(jù)、數(shù)據(jù)流、數(shù)據(jù)關(guān)系的分析處理的不斷發(fā)展,為裝箱問題的應(yīng)用拓展了新的領(lǐng)域,例如信息網(wǎng)絡(luò)、交通網(wǎng)和云存儲等有限資源的最大利用率問題,有限資金投資的收益率最大化問題,以及大數(shù)據(jù)相對關(guān)系匹配度最大化問題等.如何提高容器的空間利用率,是當(dāng)代科學(xué)研究和實踐中一個非常重要的課題.找到高利用率的裝箱方案,對節(jié)約天然資源,降低企業(yè)成本,提高企業(yè)利潤,有著十分積極的現(xiàn)實意義.

    近年來,國內(nèi)外的學(xué)者們陸續(xù)提出了一些解決三維裝箱問題的算法.Ngoi等[2]采用獨特的空間表征技術(shù)求解裝箱問題.Bischoあ等提出了一種啟發(fā)式算法,同時給出了三維裝箱問題的一些測試實例[3?4],其中文獻[3]根據(jù)層和條的選擇策略,提出了按層布局的貪婪算法.Sixt提出了基于元啟發(fā)式的禁忌搜索和模擬退火算法[5].Gehring等提出并行化的遺傳算法,該方法先對箱子進行一定的預(yù)處理,再用遺傳算法對箱子進行優(yōu)化組合來獲得裝載方案[6].Bortfeldt等提出了一種禁忌搜索算法,但該種方法只適用于箱子種類較少的情況[7].接著, Bortfeldt等針對層的策略,又提出一種混合遺傳算法[8].同時期,國內(nèi)學(xué)者何大勇等提出了求解復(fù)雜集裝箱裝載問題的遺傳算法[9].隨后,Eley提出了基于“塊”的算法[10],在此基礎(chǔ)上,Bortfeldt等也基于“塊”的概念,給出了并行禁忌搜索算法[11]. Moura等基于“剩余空間的概念”,提出了一個貪心隨機自適應(yīng)搜索算法(Greedy randomized adaptive search procedures,GRASP)[12].張德富等針對圓形的裝箱問題提出了擬人退火算法[13],隨后,又提出了三維裝箱問題的組合啟發(fā)式算法[14].Parren′oo等在文獻[12]的基礎(chǔ)上往前發(fā)展了一步,將GRASP做了改進,取得了明顯的裝箱效果[15].Huang等針對單一類型的裝箱問題提出了一個有效的擬人型穴度算法[16].張德富等提出了混合模擬退火算法,該方法首先將箱子生成復(fù)合塊,接著給出一個基于塊裝載的構(gòu)造型啟發(fā)式算法,然后將該啟發(fā)式算法和模擬退火算法相結(jié)合,提出了一個有效求解三維裝箱問題的混合模擬退火算法[17].Fanslau等也基于復(fù)合塊的概念,設(shè)計了一個有效的啟發(fā)式樹狀搜索算法[18].張德富等又在文獻[17?18]的基礎(chǔ)上設(shè)計了一個多層啟發(fā)式搜索算法[19],該算法是采用深度和寬度同時搜索的思想,提出的多層搜索算法,該算法用多層搜索思想來選擇一個近似最優(yōu)塊進行裝載,然后逐步構(gòu)造直到獲得一個裝載序列,較之前的算法取得了很好的裝載效果,但隨著箱子規(guī)模的增大,該算法需要較長的計算時間.劉勝等提出的求解三維裝箱問題的啟發(fā)式正交二叉樹搜索算法[20],該裝箱算法裝箱效率較已有算法裝箱效率有顯著提高,但是當(dāng)箱子種類較少時,該算法的優(yōu)勢不明顯.當(dāng)然,還有一些學(xué)者也取得了很好的研究成果[21?28].

    在很多實際工業(yè)應(yīng)用中,待裝箱子具有規(guī)格多樣性和數(shù)量不確定性等特點.因此本文結(jié)合最優(yōu)化原理,用多元優(yōu)化算法(Multi-variant optimization algorithm,MOA)實現(xiàn)三維裝箱問題的求解,該算法的基本思想是隨機放置、局部調(diào)整和逐步逼近.通過對BR1~BR10共1000組實例的仿真測試,取得明顯的裝箱效果,證明了本文算法的有效性和可行性.

    1 問題描述

    給定一個長L、寬W、高H的矩形容器C和n個矩形箱子b1,···,bi,···,bn.每個箱子bi的長為li,寬為wi,高為hi,體積為vi=li×wi×hi,容器C的體積V=L×W×H.該問題的目標(biāo)為:在箱子沒有溢出容器,且滿足方向性約束和穩(wěn)定性約束的條件下使容器的填充率最大,即要盡可能多地將箱子裝入容器中.問題的目標(biāo)函數(shù)為

    在實際裝箱問題中,一般會遇到3個著名的約束條件[18]:

    約束1(C1).方向性約束.在許多應(yīng)用場合下,箱子的裝載具有方向性約束.方向性約束即為箱子的長度邊、寬度邊和高度邊是否可以與容器的高度邊平行放置.若沒有這個約束條件的問題,在裝箱過程中,箱子的任意一條邊都可以豎直放置.

    約束2(C2).穩(wěn)定性約束.在許多應(yīng)用場合下,像在物流和交通運輸?shù)阮I(lǐng)域中,有時箱子在裝載時必須滿足穩(wěn)定性約束.也就是說每個箱子在裝載時要必須得到容器底部或是其他已經(jīng)裝載了的箱子的支撐.針對不同的應(yīng)用情況,穩(wěn)定性約束有部分支撐約束和完全支撐約束.部分支撐約束是指被裝載箱子的底部允許有部分懸空,完全支撐約束是指被裝載箱子的底部不允許有懸空的部分.

    約束3(C3).完全切割約束.在切割時,每一刀必須將材料完全分割成兩個部分.例如在木材和石材等的切割應(yīng)用中,一般的切割機只能做到完全切割.

    本文算法在裝箱過程中,箱子的放置方式只選擇其中的幾種,即并不是箱子的每一條邊都可以與容器的高度邊平行放置,這就保證了本文算法滿足C1方向性約束,箱子的放置方式見第2.3節(jié)述;同時,剩余空間的分割與合并方式保證了本文算法滿足C2穩(wěn)定性約束,剩余空間的分割與合并方式見第2.2節(jié)和第2.4節(jié).綜上所述,本文算法是基于C1和C2兩個約束進行的.

    2 裝箱準(zhǔn)備

    2.1 最優(yōu)化原理

    根據(jù)一類多階段決策問題的特性,由Bellman等提出了解決動態(tài)規(guī)劃的“最優(yōu)化原理”,作為整個過程的最優(yōu)策略具有這樣的性質(zhì):無論過去的狀態(tài)和決策如何,對當(dāng)前決策形成的狀態(tài)而言,余下的所有狀態(tài)必須構(gòu)成最優(yōu)策略.即若要解決某一個優(yōu)化問題,需要做出n個決策D1,···,Di,···,Dn,若這個決策序列是最優(yōu)策略,對于任何一個i,1<i<n,不論前面的i個決策是如何,i決策以后的最優(yōu)決策只取決于由前面決策所確定的當(dāng)前的i狀態(tài),即以后的決策Di+1,Di+2,···,Dn也是最優(yōu)的[29].

    2.2 空間的劃分

    箱子的裝載是在容器的剩余空間中進行的,剩余空間是指容器中未被填充的空間.箱子理論上可以放在容器的任意位置,但不能超出容器的容納范圍,也不能與其他貨物交迭放置.為了滿足裝箱問題的穩(wěn)定性約束和保證每一個箱子裝進容器之前,剩余空間都是立方體空間,本文選擇將箱子從容器的原點坐標(biāo)處開始放置,并且箱子擺放時必須與坐標(biāo)軸平行或正交,不能斜放,也不能懸浮放置.當(dāng)?shù)谝粋€箱子裝進容器后,將剩余空間分割成相對于剛剛裝入的箱子的前空間、右空間和上空間三個立方體空間,如圖1所示.對每一個箱子裝入容器后產(chǎn)生的剩余空間都嚴格做同樣的分割處理.為了裝箱的有效進行,每裝進一個箱子,更新記錄一次容器的剩余空間.

    圖1 空間的分割Fig.1 Space division

    2.3 箱子的放置

    假設(shè)箱子的擺放沒有方向性約束C1,則在裝箱過程中,箱子的任意一條邊都可以豎直放置,此時可以將箱子的擺放方式細分為6種:1)l平行于L,w平行于W,h平行于H;2)w平行于L,l平行于W,h平行于H;3)l平行于L,h平行于W,w平行于H;4)h平行于L,l平行于W,w平行于H; 5)h平行于L,w平行于W,l平行于H;6)w平行于L,h平行于W,l平行于H.如圖2(a)~2(f)所示.如果箱子的擺放有方向性約束C1,則根據(jù)具體的方向性約束來選擇箱子的擺放方式.箱子放入容器時,本文算法先選擇擺放方式后選擇放置空間.

    2.4 剩余子空間的合并

    隨著裝箱的不斷進行,剩余空間中可能會產(chǎn)生一些廢棄空間,廢棄空間指的是裝不下任何一個待裝箱子的剩余子空間.要提高容器的利用率,就要最大程度的使用廢棄空間,即要盡可能地將廢棄空間變?yōu)榭捎每臻g,唯一的辦法就是將廢棄空間與其他剩余子空間合并.空間合并需同時滿足3個條件:1)兩個空間相鄰;2)兩個空間底面同高;3)兩個空間合并后,可用空間必須增大.在同時滿足上述3個條件時,根據(jù)兩個相鄰空間的相對位置,將空間的合并方式分為左右合并和前后合并兩種方式,如圖3所示.

    圖2 箱子的擺放方式Fig.2 The placement method of box

    圖3 空間合并方式Fig.3 The merging method of residual space

    3 多元優(yōu)化算法

    3.1 算法簡述

    多元優(yōu)化算法(Multi-variant optimization algorithm,MOA)是基于全局和局部搜索交替進行的思想提出的一種全新的群智能算法,該算法在問題的解空間中隨機產(chǎn)生全局搜索元及相應(yīng)的局部搜索元,對解空間進行全面細致地搜索,從而逐漸逼近全局最優(yōu)解.算法基于計算機的數(shù)據(jù)結(jié)構(gòu),構(gòu)造多元化結(jié)構(gòu)體,結(jié)構(gòu)體用于記憶并協(xié)調(diào)搜索信息、調(diào)動全局局部交替尋優(yōu)、記憶尋優(yōu)過程,多次全局局部交叉搜索后,獲得全局最優(yōu)解和多個次優(yōu)解[30].結(jié)構(gòu)體是搜索元全局和局部交替尋優(yōu)信息交流的平臺,是尋優(yōu)過程記憶的載體.搜索元和結(jié)構(gòu)體構(gòu)成了MOA的基本框架[30].

    結(jié)構(gòu)體是一種能夠按照一定規(guī)則,記憶協(xié)調(diào)搜索信息,有固定結(jié)構(gòu)的數(shù)據(jù)表,如圖4所示.

    圖4 MOA數(shù)據(jù)結(jié)構(gòu)圖Fig.4 The data structure diagram of MOA

    結(jié)構(gòu)體是用指針實現(xiàn)的二維有序鏈表,由全局鏈表和局部鏈表組成.結(jié)構(gòu)體中,第一行為全局鏈表,用于保存全局搜索元并記憶和共享全局信息;每一列叫做局部鏈表,用于保存各個局部解空間內(nèi)的局部搜索元和記憶局部信息.

    全局鏈表和局部鏈表都是以搜索元的適應(yīng)度值為關(guān)鍵字(Key)的有序鏈表.全局鏈表中前端搜索元優(yōu)于后端搜索元,局部鏈表中上部搜索元優(yōu)于下部搜索元.搜索元是結(jié)構(gòu)體的組織細胞,用于存放和接收尋優(yōu)信息.搜索元具有進行全局探索和局部調(diào)整的功能.

    式中,li和ui分別為第i維待優(yōu)化參數(shù)xi的下限和上限,unifrnd(li,ui)為返回li和ui之間的一個隨機數(shù).

    局部搜索元La(Local atom)是以某個全局元為中心的局部鄰域內(nèi)隨機生成的一個解.以全局元為中心的局部搜索元描述如下:

    式中r為局部鄰域半徑,決定了局部搜索的范圍.

    將全局鏈表記憶較優(yōu)的全局元作為具有搜索價值的局部解空間的中心,根據(jù)其所在全局鏈表中的位置共享該局部解空間在所有已經(jīng)發(fā)現(xiàn)的具有搜索價值局部解空間中的優(yōu)越程度:位置越靠前,其所在區(qū)域越優(yōu).當(dāng)局部搜索元發(fā)現(xiàn)優(yōu)于全局元的解時,局部鏈表記憶較優(yōu)的局部元將取代全局元作為新的具有搜索價值的局部解空間的中心,以分享局部搜索獲得的信息.

    為了更好地說明MOA的實現(xiàn)過程,給出測試函數(shù)

    在給定的區(qū)間0≤x≤1內(nèi),用MOA求F(x)取最大值時對應(yīng)的解,尋優(yōu)過程如圖5所示,多個全局搜索元和對應(yīng)的局部搜索元對解空間進行全面細致地搜索,逐漸逼近最優(yōu)解x=0.1,搜索結(jié)果如圖6所示.

    圖5 測試尋優(yōu)過程圖Fig.5 The test optimization graph

    圖6 測試尋優(yōu)結(jié)果圖Fig.6 The result of test results

    3.2 問題的解

    針對待裝箱子在實際應(yīng)用中的復(fù)雜性和不確定性,本文采用多元優(yōu)化算法實現(xiàn)三維裝箱問題,基本思想是:

    1)隨機放置:裝入容器的箱子以及箱子的擺放方式均隨機選擇;

    2)局部調(diào)整:對裝入容器的局部箱子按目標(biāo)函數(shù)值作局部調(diào)整;

    3)逐步逼近:遞推的局部隨機放置與調(diào)整優(yōu)化,使目標(biāo)函數(shù)值逐步逼近最優(yōu)值.

    在用MOA實現(xiàn)三維裝箱問題的求解之前進行預(yù)處理:

    1)箱子編號:按自然數(shù)序列對待裝箱子進行編號,若待裝箱子總數(shù)為d,則所有待裝箱子的編號為1,2,···,i,···,d.若箱子數(shù)量很龐大或不確定,則可以省略這一步,直接分批次裝即可.

    2)箱子擺放方式編號:若沒有方向性約束C1,則待裝箱子的擺放方式編號為:1,2,3,4,5,6,這6種擺放方式分別代表第2.3節(jié)中描述的6種擺放方式;若有方向性約束C1,則根據(jù)具體的方向約束,待裝箱子的擺放方式編號為第2.3節(jié)中的一種或幾種.

    多元優(yōu)化算法實現(xiàn)背包裝載問題的具體步驟如下:

    步驟1.編碼.編碼是應(yīng)用多元優(yōu)化算法首先要解決的問題.根據(jù)不同研究對象的不同性質(zhì),把一個問題的可行解從其解空間轉(zhuǎn)換到多元優(yōu)化算法能處理的搜索空間中.假設(shè)總共有d個待裝的箱子,則MOA結(jié)構(gòu)體里一個全局搜索元的編碼方式為是1~d之間的隨機的且互不重復(fù)的整數(shù),表示箱子的序號,i表示箱子ai裝入容器的次序.d維的搜索元P由全局搜索元式(2)產(chǎn)生,裝箱問題中,需要全局搜索,同時對局部進行調(diào)整.

    步驟2.分批隨機放置箱子.在實際應(yīng)用中,待裝箱子的種類多樣且數(shù)量龐大,因此將待裝箱子分幾批次裝入容器.首先取出中的前n個待裝箱子,即第一批次的裝箱個數(shù)為n,然后將此批次的箱子依次裝入容器中,n的大小根據(jù)箱子的數(shù)量設(shè)置.每一個箱子裝入容器時,采取一種擬人的方法,先隨機放置,再做逐步調(diào)整.具體如下:

    步驟2.1.首先隨機選取一個可用空間即剩余空間,然后隨機選取一種貨物即箱子的擺放方式,最后按該種擺放方式將箱子裝入選取好的剩余空間.

    步驟2.2.若該箱子無法以該種擺放方式裝入剩余空間,則從箱子剩下的幾種擺放方式中再隨機選取一種,并判斷是否可以裝入剩余空間.如果可以,則將箱子放入所選的剩余空間并記錄箱子的擺放方式;反之,繼續(xù)選取擺放方式,直到將箱子放入剩余空間或已遍歷完該箱子的所有擺放方式為止.

    步驟2.3.重復(fù)步驟2.1和步驟2.2,直到將箱子放入剩余空間或遍歷完所有的剩余空間為止.每裝一個箱子,更新記錄一次容器的剩余空間,若有廢棄空間且滿足合并的條件,則將廢棄空間與其相鄰的剩余空間合并.

    步驟2.4.重復(fù)步驟2.1~2.3,直到無剩余空間可裝載或這一批次的n個箱子全部裝入為止.

    步驟3.調(diào)整優(yōu)化.利用最優(yōu)化原理調(diào)整優(yōu)化容器的填充率.已有的決策序DDD1=[a1,a2,···,an]不一定是最優(yōu)的決策序列,要使該序列為最優(yōu)決策序列,利用最優(yōu)化原理逐步調(diào)整該序列,直到得到一個滿意的結(jié)果,具體步驟如下:

    步驟3.1.在容器外未裝的箱子集中隨機抽取一個箱子及其對應(yīng)的擺放方式.

    步驟3.2.將抽取的箱子的體積與a1的體積相比較,若抽取的箱子體積大于a1的體積,同時抽取的箱子能夠放入a1放進容器之前對應(yīng)的剩余空間(指a1被放入容器之前算法記錄的剩余空間),則用隨機抽取的箱子替換a1.反之,若抽取的箱子的體積小于或等于a1的體積,或者抽取的箱子不能放入a1放進容器之前對應(yīng)的剩余空間,則a1不用被隨機抽取的箱子替換.用同樣的方法依次優(yōu)化該批次裝進容器的箱子,得到新的裝箱序列DDD2=[a1,a2,···,an],DDD2是DDD1的優(yōu)化序列.

    步驟 3.3.將下一批箱子裝入容器后,按步驟3.1和步驟3.2中的方法對新裝進容器的幾個箱子進行調(diào)整優(yōu)化.重復(fù)上述步驟,直到待裝箱子已裝完或剩余空間全為廢棄空間時,即可獲得一個潛在的裝箱方案.由于局部調(diào)整后的每一個局部序列都是最優(yōu)序列,因此整個全局序列同樣也是最優(yōu)序列,符合最優(yōu)化原理.

    步驟4.逐次逼近,漸近收斂裝箱過程,直到滿意為止.

    算法的偽代碼如下:

    Begin

    設(shè)置全局元個數(shù)m;每個全局元內(nèi)部的局部元個數(shù)即分的批次數(shù)bn;每個局部元的維度即每批次裝箱的個數(shù)bni(1≤i≤bn);全局解空間的下限l=1和上限u=sumbox,sumbox為箱子總數(shù);最大循環(huán)次數(shù)Imax;最大適應(yīng)度值(即最大填充率)fitinessmax;初始化適應(yīng)度值fitinessbest=0,K=0.

    算法的時間復(fù)雜度分析.如算法的偽代碼所示,算法中最外層的While大循環(huán)內(nèi)有兩層并列的循環(huán),其中第一個For循環(huán)內(nèi)的每一個全局元是一個隨機生成的數(shù)組,只需一個執(zhí)行周期,即生成每個全局元的時間復(fù)雜度為O(1),因此第一個For循環(huán)的時間復(fù)雜度為O(m);第二個循環(huán)內(nèi)包含兩層嵌套的For循環(huán),其中內(nèi)層的For循環(huán)內(nèi)的局部元生成的時間復(fù)雜度為O(1),由于對每一個局部元優(yōu)化調(diào)整的次數(shù)即每批次裝箱的個數(shù)bni與局部元的個數(shù)bn相互獨立,則內(nèi)層For循環(huán)的時間復(fù)雜度為O(sumbox+bn),因此第二個循環(huán)的時間復(fù)雜度為O(m(sumbox+bn));再綜合最外層While大循環(huán)的時間復(fù)雜度O(K),因此算法的時間復(fù)雜度的通式為O(K(m+m(sumbox+bn))).

    由于算法中fitinessbest的更新具有隨機性,在最好的情況下,在K=1時,fitinessbest=fitinessmax,此時算法的時間復(fù)雜度為 O(m+m(sumbox+bn)),但發(fā)生這種情況的概率極小.在一般情況中,fitinessbest只會不斷趨近于fitinessmax,因此算法在一般情況下的時間復(fù)雜度為O(Imax(m+m(sumbox+bn))).

    4 實驗測試

    4.1 測試準(zhǔn)備

    為了證明本文算法的有效性和可行性,用具體的三維裝箱測試數(shù)據(jù)對算法做了大量測試.采用的測試數(shù)據(jù)來自文獻[9],測試了其中的BR1~BR10共1000個實例,這些數(shù)據(jù)可以從OR-Library網(wǎng)站下載.在BR1~BR10中,每種類型有100組測試實例,同時每種類型中箱子的類型數(shù)分別為3,5,8, 10,12,15,20,30,40,50,箱子的多樣性從弱到強,從而能夠更好地反映算法在不同多樣性裝箱問題中的應(yīng)用情況.本文算法用Matlab實現(xiàn),實驗程序運行在Intel Core(TM)i3-3240 CPU@3.40GHz處理器上,運行環(huán)境為Windows 7專業(yè)版.

    4.2 測試過程

    以BR1中第1組實例為例具體描述測試過程,將該實例取名為BR1-1.表1為BR1-1的待裝箱子的三維值及數(shù)量.

    表1 BR1-1待裝箱子的三維值及數(shù)量Table 1 The speci fi cation and quantity of BR1-1

    1)在測試之前的預(yù)處理

    預(yù)處理1.讀取表1數(shù)據(jù).通過程序?qū)⒈?轉(zhuǎn)換為具體的數(shù)據(jù)矩陣,數(shù)據(jù)矩陣的每一行代表一種類型的箱子,每一行的前三列分別代表箱子的長、寬、高的值,最后一列代表該種類型箱子的數(shù)量.

    預(yù)處理 2.對所有箱子按順序編號.由表1可知,BR1-1中共有112個箱子,其中,第1種類型有40個,第2種類型有33個,第3種類型有39個.因此第1種類型的箱子的編號為1~40,第2種類型的箱子的編號為41~73,第3種類型的箱子的編號為74~112.

    2)以BR1-1為例的測試過程

    步驟 1.編碼.隨機產(chǎn)生112個1~112之間不重復(fù)的整數(shù)串,如[91,63,3,36,18,39,···,52, 74,10,97,2],此整數(shù)串中的每一個整數(shù)與預(yù)處理2中的箱子的編號對應(yīng),例如91代表91號箱子.相當(dāng)于把所有待裝箱子打亂.

    步驟2.分批次裝載箱子.根據(jù)待裝箱子的總數(shù)設(shè)置裝箱過程分幾批次裝載,同時設(shè)定每一批次裝多少個箱子.例如BR1-1有112個待裝箱子,裝箱過程即可設(shè)置為分5批次裝載,第1批次裝32個,第2批次裝27個,第3批次裝22個,第4批次裝17個,第5批次裝14個,這些具體的數(shù)據(jù)只是某一次實驗設(shè)置的結(jié)果,并不是固定不變的.接著進行裝箱過程,先將在步驟1產(chǎn)生的箱子序列串中從91號開始的前32個箱子依次裝入容器中,每一個箱子裝入容器之前更新記錄一次當(dāng)前的剩余空間,若中間有裝不下的箱子,則取該箱子后面的箱子繼續(xù)裝,直到已裝入容器的個數(shù)達到設(shè)定的32個或者是剩余空間已裝不下任何一個未被裝的箱子為止,此時將箱子分為已裝箱子和未裝箱子兩部分.

    步驟3.調(diào)整優(yōu)化.從未被裝入容器的箱子中隨機抽取一個如編號為10的箱子,比較10號箱子與91號箱子的體積大小,若10號箱子的體積小于91號箱子的體積,則裝入容器的箱子保持不動,同時將10號箱子放回未被裝入容器的箱子集中,此時默認91號箱子作為第一個裝入容器的最優(yōu)態(tài);接著從剩下的未被裝入容器的箱子中隨機抽取一個如編號為97的箱子,比較63號箱子與97號箱子的體積大小,若97號箱子的體積大于63號箱子,則此時判斷若97號箱子是否能被63號箱子裝入容器之前的剩余空間裝下,若能裝下,則將63號箱子替換成97號箱子作為第二裝入容器的最優(yōu)態(tài),63號箱子則放到未裝的箱子集中.替換后及時更新剩余空間,以便于下一個箱子正確地裝入容器中.如上所述,依次將第1批的32個箱子優(yōu)化完后,繼續(xù)將第2批次的箱子裝入容器中,對第2批次裝入的箱子也做同樣的優(yōu)化處理,第3批、第4批和第5批亦然.

    步驟4.逐次逼近.經(jīng)過5次的裝載調(diào)整優(yōu)化之后,容器的填充率逐漸逼近上限100%.表2是某一次實驗時容器填充率逐漸變化逼近的過程.整個裝箱過程滿足最不利原則.最不利原則是指:若最不利的情況也能滿足問題的要求,則其他情況必然滿足問題的要求.

    4.3 實驗結(jié)果與分析

    許多國內(nèi)外的研究者對文獻[3]中的測試數(shù)據(jù)做了一些測試,本文對文獻[18]提出的啟發(fā)式樹狀搜索算法、文獻[3]提出的按層布局的貪婪算法、文獻[6]提出的并行遺傳算法、文獻[7]提出的禁忌搜索算法、文獻[12]提出的貪心隨機自適應(yīng)搜索算法、文獻[15]提出的改進的GRASP、文獻[17]提出的混合模擬退火算法、文獻[19]提出的多層啟發(fā)式搜索算法、文獻[24]提出的VNS算法和文獻[25]提出的FDA算法等比較典型的算法得到的裝箱效果進行比較分析,這些算法的計算結(jié)果與用多元優(yōu)化算法實現(xiàn)裝箱問題的計算結(jié)果如表3和表4所示.表3是前500組實例的測試結(jié)果,表4是后500組實例的測試結(jié)果.表4中最后一列是每個算法針對裝箱實例BR1~BR10取得的平均填充率.

    從表3和表4中可以看出:1)從橫向數(shù)據(jù)來看,針對每一種算法,表3的裝箱效果明顯優(yōu)于表4中的裝箱效果,且從相鄰算例之間填充率的變化量來看,表3要小于表4.不難看出是箱子種類數(shù)的不同造成這一現(xiàn)象.表3中箱子的種類數(shù)、相鄰算例之間箱子種類數(shù)的變化量都小于表4.箱子種類數(shù)很多即同類箱子的數(shù)量很少時,裝箱過程中立方體對齊的難度大大增加,箱子與箱子中間產(chǎn)生的廢棄空間就隨之增多,從而問題求解結(jié)果的優(yōu)度呈單調(diào)遞減的趨勢,這在一定程度上體現(xiàn)了三維裝箱問題存在的一個難題:箱子的種類數(shù)越多,即箱子的多樣性越強,問題的求解就越困難.2)從具體的平均填充率數(shù)據(jù)來看,在同時滿足方向性約束C1和穩(wěn)定性約束C2的情況下,填充率最高的是由張德富等提出的多層啟發(fā)式搜索算法MLHS的94.02%,第2是本文算法MOA的93.64%,第3是Fanslau等提出的啟發(fā)式搜索算法CLTRS的93.42%,第4是由張德富等提出的混合模擬退火算法HAS的92.24%,第5為Bortfeldt等提出的禁忌搜索算法的 89.00%,第6為Gehring等提出的并行化遺傳算法的87.20%,第7是Bischoあ等提出的按層布局的貪婪算法的81.88%.因此從數(shù)據(jù)分析結(jié)果來看,本文算法具有有效性和可行性.

    表2 某次實驗得到的填充率的變化關(guān)系表Table 2 The change table of fi lling rate obtained from an experiment

    表3 各種算法的裝箱效果比較(1~500組)Table 3 Comparison of packing eあects of various(groups 1~500)algorithms

    表4 各種算法的裝箱效果比較(501~1000)Table 4 Comparison of packing eあects of various(groups 501~1000)algorithms

    表5給出了本文算法對BR1~BR10測試時的具體細節(jié).表5中從左起的第三列Minimum到最后一列Average分別表示本文算法在同一類型的100個測試實例的運行中記錄下的最短運行時間、最長運行時間、平均運行時間、最小填充率、最大填充率和平均填充率,這里的運行時間指程序的實際運行時間.

    從表5可以看出,1)算法最短運行時間與最長運行時間相差很大,原因是本文算法具有較強的隨機性;2)隨著箱子種類數(shù)的增加,算法的運行時間近似呈單調(diào)遞增的趨勢,這是由于箱子種類數(shù)越多,在求解問題時,箱子的組合情況越復(fù)雜,要取得好的裝箱效果就需付出較大的時間代價.

    用多元優(yōu)化算法實現(xiàn)三維裝箱問題時,經(jīng)多批次隨機放置和局部調(diào)整優(yōu)化,裝箱結(jié)果逐步逼近全局最優(yōu)解的過程如圖7所示.在實驗過程中,裝箱的批次數(shù)和每批次的裝箱個數(shù)等這些參數(shù)的設(shè)置與每一個算例的箱子總數(shù)緊密相關(guān).針對1000個算例,經(jīng)過測試,得出裝箱的批次數(shù)的取值范圍為[5,12]比較適中,每批次的裝箱個數(shù)呈緩慢遞減的趨勢.

    圖7 MOA實現(xiàn)裝箱問題過程中填充率變化圖Fig.7 The fi lling rate variation diagram of packing problem with MOA

    本文主要驗證MOA算法實現(xiàn)三維裝箱問題的有效性和可行性,進一步工作將對算法參數(shù)的設(shè)置做自適應(yīng)討論研究.

    表5 多元優(yōu)化算法實現(xiàn)三維裝箱問題時的一些測試細節(jié)Table 5 Some test details of MOA for 3D packing problem

    5 結(jié)束語

    三維裝箱問題屬于典型的NP難題,本文采用多元優(yōu)化算法求解,具有隨機放置、局部調(diào)整和逐步逼近三大特性.經(jīng)過多次實驗測試,取得理想的裝箱效果,證明了多元優(yōu)化算法實現(xiàn)三維裝箱問題的有效性和可行性.由于本文采用的是分批次隨機放置,因此針對實際裝箱問題中的復(fù)雜性和不確定性具有很好的優(yōu)勢.但是算法若要得到更高的裝箱效果,就要增大試驗次數(shù),隨之計算時間也會增大.同時,分多少批次裝載和每批次裝多少個等這些參數(shù)的設(shè)置與對象緊緊相關(guān),不具有一般性.

    1 DyckhoあH,Finke U.Cutting and Packing in Production and Distribution.Heidelberg:Physica-Verlag,1992.

    2 Ngoi B K A,Tay M L,Chua E S.Applying spatial representation techniques to the container packing problem.International Journal of Production Research,1994,32(1):111?123

    3 BischoあE E,RatcliあB S W.Issues in the development of approaches to container loading.Omega,1995,23(4):377?390

    4 Davies A P,BischoあE E.Weight distribution considerations in container loading.European Journal of Operational Research,1999,114(3):509?527

    5 Sixt M.Dreidimensionale Packprobleme.Losungsverfahren Basierend auf den Meta-Heuristiken Simulated Annealing und Tabu-Suche.Frankfurt am Main:Europaischer Verlag der Wissenschaften,1996.

    6 Gehring H,Bortfeldt A.A genetic algorithm for solving the container loading problem.International Transactions in Operational Research,1997,4(5?6):401?418

    7 Bortfeldt A,Gehring H.A tabu search algorithm for weakly heterogeneous container loading problems.OR Spectrum, 1998,20:237?250

    8 Bortfeldt A,Gehring H.A hybrid genetic algorithm for the container loading problem.European Journal of Operational Research,2001,131(1):143?161

    9 He Da-Yong,Zha Jian-Zhong,Jiang Yi-Dong.Research on solution to complex container-loading problem based on genetic algorithm.Journal of Software,2001,12(9):1380?1385

    (何大勇,查建中,姜義東.遺傳算法求解復(fù)雜集裝箱裝載問題方法研究.軟件學(xué)報,2001,12(9):1380?1385)

    10 Eley M.Solving container loading problems by block arrangement.European Journal of Operational Research, 2002,141(2):393?409

    11 Bortfeldt A,Gehring H,Mack D.A parallel tabu search algorithm for solving the container loading problem.Parallel Computing,2003,29(5):641?662

    12 Moura A,Oliveira J F.A GRASP approach to the containerloading problem.IEEE Intelligent Systems,2005,20(4):50?57

    13 Zhang D F,Li X.A personi fi ed annealing algorithm for circles packing problem.Acta Automatica Sinica,2005,31(4): 590?595

    14 Zhang De-Fu,Wei Li-Jun,Chen Qing-Shan,Chen Huo-Wang.A combinational heuristic algorithm for the threedimensional packing problem.Journal of Software,2007, 18(9):2083?2089

    (張德富,魏麗軍,陳青山,陳火旺.三維裝箱問題的組合啟發(fā)式算法.軟件學(xué)報,2007,18(9):2083?2089)

    15 Parren′oo F,Alvarez-Valdes R,Oliveira J F,Tamarit J M.A maximal space-algorithm for the container loading problem.INFORMS Journal on Computing,2008,20(3):412?422

    16 Huang W Q,He K.A caving degree approach for the single container loading problem.European Journal of Operational Research,2009,196(1):93?101

    17 Zhang De-Fu,Peng Yu,Zhu Wen-Xing,Chen Huo-Wang. A hybrid simulated annealing algorithm for the threedimensional packing problem.Chinese Journal of Computers,2009,32(11):2147?2156

    (張德富,彭煜,朱文興,陳火旺.求解三維裝箱問題的混合模擬退火算法.計算機學(xué)報,2009,32(11):2147?2156)

    18 Fanslau T,Bortfeldt A.A tree search algorithm for solving the container loading problem.INFORMS Journal on Computing,2010,22(2):222?235

    19 Zhang De-Fu,Peng Yu,Zhang Li-Li.A multi-layer heuristic search algorithm for three dimensional container loading problem.Chinese Journal of Computers,2012,35(12):2553?2561

    (張德富,彭煜,張麗麗.求解三維裝箱問題的多層啟發(fā)式搜索算法.計算機學(xué)報,2012,35(12):2553?2516)

    20 Liu Sheng,Zhu Feng-Hua,Lv Yi-Sheng,Li Yuan-Tao.A heuristic orthogonal binary tree search algorithm for three dimensional container loading problem.Chinese Journal of Computers,2015,38(8):1530?1543

    (劉勝,朱鳳華,呂宜生,李元濤.求解三維裝箱問題的啟發(fā)式正交二叉樹搜索算法.計算機學(xué)報,2015,38(8):1530?1543)

    21 Zhang Ya-Jian,Liu Yong,Xie Song-Jiang.An improved genetic algorithm for bin-packing problem.Control Engineering of China,2016,23(3):327?331

    (張雅艦,劉勇,謝松江.一種求解裝箱問題的改進遺傳算法.控制工程,2016,23(3):327?331)

    22 Wang Yan,Pan Wei-Ping,Zhang Jun-Hui.An algorithm for solving the problem of three-dimensional packing of singlesized cuboids.Packaging Engineering,2015,36(11):96?99

    (王巖,潘衛(wèi)平,張俊暉.單一尺寸長方體三維裝箱問題的一種求解算法.包裝工程,2015,36(11):96?99)

    23 Ren Yue-Miao,Chen Xian-Fu,Liu Bin.Study on algorithm of three-dimensional bin packing problem for trapezoidal bin.Microcomputer and Its Applications,2015,34(9):18?21,25

    (任岳淼,陳賢富,劉斌.面向梯形箱子的三維裝箱問題算法研究.微型機與應(yīng)用,2015,34(9):18?21,25)

    24 Parre?no F,Alvarez-Valdes R,Oliveira J F,Tamarit J M. Neighborhood structures for the container loading problem: a VNS implementation.Journal of Heuristics,2010,16(1): 1?22

    25 He K,Huang W Q.An eきcient placement heuristic for three-dimensional rectangular packing.Computers and Operations Research,2011,38(1):227?233

    26 You Wei,Lei Ding-You,Zhu Xiang.Biased random-key hybrid genetic algorithm for three-dimensional loading problem.Computer Engineering and Applications,2014,50(22): 265?270

    (游偉,雷定猷,朱向.三維裝箱問題的偏隨機密鑰混合遺傳算法.計算機工程與應(yīng)用,2014,50(22):265?270)

    27 Zhang Ying,Liu Er-Chao,Qi Ming-Yao.Quick algorithm for the three-dimensional bin packing problem with support surface constraints.Journal of Transportation Systems Engineering and Information Technology,2014,14(2):192?198

    (張瑩,劉二超,戚銘堯.考慮支撐面約束的三維裝箱問題快速求解方法.交通運輸系統(tǒng)工程與信息,2014,14(2):192?198)

    28 He Kun,Huang Wen-Qi.An action space based deterministic eきcient algorithm for solving the three-dimensional container loading.Chinese Journal of Computers,2014,37(8): 1786?1793

    (何琨,黃文奇.基于動作空間的三維裝箱問題的確定性高效率求解算法.計算機學(xué)報,2014,37(8):1786?1793)

    29 Xia Cheng-Ren.Methodology of teaching the principal of optimality.Journal of Anqing Teachers College(Natural Science),2003,9(2):93?95

    (夏成仁.關(guān)于最優(yōu)化原理的教學(xué).安慶師范學(xué)院學(xué)報(自然科學(xué)版), 2003,9(2):93?95)

    30 Li Bao-Lei,Shi Xin-Ling,Gou Chang-Xing,Lv Dan-Ju,An Zhen-Zhou,Zhang Yu-Feng.Multivariant optimization algorithm and its convergence analysis.Acta Automatica Sinica, 2015,41(5):949?959

    (李寶磊,施心陵,茍常興,呂丹桔,安鎮(zhèn)宙,張榆鋒.多元優(yōu)化算法及其收斂性分析.自動化學(xué)報,2015,41(5):949?959)

    猜你喜歡
    裝箱搜索算法箱子
    改進的和聲搜索算法求解凸二次規(guī)劃及線性規(guī)劃
    電機裝箱設(shè)計系統(tǒng)解決方案和應(yīng)用
    一模一樣的箱子
    好孩子畫報(2017年5期)2017-07-14 15:01:15
    箱子
    薄箱子
    三維貨物裝箱問題的研究進展
    領(lǐng)個箱子去街上
    Coco薇(2015年11期)2015-11-09 12:19:33
    基于汽車接力的潮流轉(zhuǎn)移快速搜索算法
    基于逐維改進的自適應(yīng)步長布谷鳥搜索算法
    基于三維模型的可視化裝箱系統(tǒng)
    河南科技(2015年2期)2015-02-27 14:20:23
    黑丝袜美女国产一区| 大香蕉97超碰在线| 亚洲图色成人| 在线天堂中文资源库| 男的添女的下面高潮视频| 最新中文字幕久久久久| 天堂8中文在线网| 久久精品夜色国产| 国产av一区二区精品久久| 亚洲欧美精品自产自拍| 我的女老师完整版在线观看| 成人无遮挡网站| 国产精品蜜桃在线观看| 亚洲在久久综合| 亚洲精品自拍成人| 久久影院123| 国产 精品1| 国产精品久久久av美女十八| 久久99一区二区三区| 亚洲综合色惰| 春色校园在线视频观看| 国产色爽女视频免费观看| 久久久国产精品麻豆| 波多野结衣一区麻豆| 青青草视频在线视频观看| 秋霞在线观看毛片| 国产不卡av网站在线观看| 午夜福利在线观看免费完整高清在| 日韩不卡一区二区三区视频在线| 少妇猛男粗大的猛烈进出视频| 亚洲精品456在线播放app| 国产精品国产av在线观看| 成人毛片60女人毛片免费| 一本色道久久久久久精品综合| 美女内射精品一级片tv| 中文字幕制服av| 久久精品国产亚洲av涩爱| 国产极品天堂在线| 国产综合精华液| 国产精品国产三级国产专区5o| 两个人免费观看高清视频| 亚洲国产精品一区二区三区在线| 精品久久国产蜜桃| 日韩 亚洲 欧美在线| 国产淫语在线视频| 久久久久久久久久久久大奶| 亚洲国产精品一区三区| 三级国产精品片| kizo精华| av免费观看日本| 久久人人爽av亚洲精品天堂| 飞空精品影院首页| 夫妻性生交免费视频一级片| 日韩中文字幕视频在线看片| 狂野欧美激情性bbbbbb| 国产精品不卡视频一区二区| 国产 一区精品| 欧美日韩视频高清一区二区三区二| 国产精品久久久久久精品电影小说| 美女视频免费永久观看网站| 深夜精品福利| 国产国语露脸激情在线看| 日日爽夜夜爽网站| 精品人妻一区二区三区麻豆| 国产免费一级a男人的天堂| 亚洲av福利一区| 国产精品嫩草影院av在线观看| 欧美精品高潮呻吟av久久| 日本免费在线观看一区| 亚洲综合色网址| 大香蕉97超碰在线| 国产不卡av网站在线观看| 汤姆久久久久久久影院中文字幕| 成人18禁高潮啪啪吃奶动态图| 亚洲精品成人av观看孕妇| 考比视频在线观看| 男女免费视频国产| 国产精品一区二区在线不卡| 美女视频免费永久观看网站| 插逼视频在线观看| 久久久久视频综合| 久久久久国产精品人妻一区二区| 久久久久精品人妻al黑| 国产欧美日韩综合在线一区二区| 亚洲欧美清纯卡通| 少妇的逼水好多| 这个男人来自地球电影免费观看 | 99精国产麻豆久久婷婷| 在线观看三级黄色| 青春草国产在线视频| 色5月婷婷丁香| 国产精品成人在线| 亚洲国产最新在线播放| 夜夜爽夜夜爽视频| 一级,二级,三级黄色视频| 男女高潮啪啪啪动态图| 麻豆精品久久久久久蜜桃| 国产成人一区二区在线| 26uuu在线亚洲综合色| 少妇猛男粗大的猛烈进出视频| 亚洲伊人色综图| 熟女电影av网| 大码成人一级视频| 久久99热6这里只有精品| 欧美+日韩+精品| 哪个播放器可以免费观看大片| 看免费av毛片| 97在线人人人人妻| 亚洲精品aⅴ在线观看| 国产精品欧美亚洲77777| 久久久久国产精品人妻一区二区| 亚洲精华国产精华液的使用体验| 欧美精品一区二区免费开放| 亚洲欧洲日产国产| 热re99久久精品国产66热6| 精品人妻熟女毛片av久久网站| 婷婷色综合大香蕉| 日韩免费高清中文字幕av| 国产xxxxx性猛交| 最近最新中文字幕大全免费视频 | 十八禁网站网址无遮挡| 99热网站在线观看| 五月天丁香电影| 考比视频在线观看| 国产一区二区在线观看av| 国产精品久久久久成人av| 在线观看免费视频网站a站| 18在线观看网站| 综合色丁香网| 国产高清三级在线| 日产精品乱码卡一卡2卡三| 午夜免费鲁丝| 国产一区有黄有色的免费视频| 成人毛片a级毛片在线播放| 国产日韩一区二区三区精品不卡| av黄色大香蕉| 一级片免费观看大全| 久久热在线av| av在线app专区| 最近最新中文字幕大全免费视频 | 90打野战视频偷拍视频| 一级片'在线观看视频| 秋霞在线观看毛片| 国产有黄有色有爽视频| 美女xxoo啪啪120秒动态图| 纯流量卡能插随身wifi吗| 99国产综合亚洲精品| 一级片'在线观看视频| 99热这里只有是精品在线观看| 看免费成人av毛片| 午夜久久久在线观看| 天堂俺去俺来也www色官网| 九草在线视频观看| 国产精品三级大全| 黑人巨大精品欧美一区二区蜜桃 | 一边摸一边做爽爽视频免费| 精品国产一区二区三区久久久樱花| 国产亚洲欧美精品永久| 男人舔女人的私密视频| 日韩一本色道免费dvd| 精品少妇久久久久久888优播| 99久久人妻综合| 中文字幕人妻丝袜制服| 综合色丁香网| 精品一区二区三卡| 香蕉国产在线看| 成人无遮挡网站| 久久这里有精品视频免费| 日产精品乱码卡一卡2卡三| 美女福利国产在线| 成人综合一区亚洲| 日本-黄色视频高清免费观看| 观看av在线不卡| 亚洲欧洲日产国产| 老司机影院成人| 涩涩av久久男人的天堂| 在线天堂最新版资源| 如日韩欧美国产精品一区二区三区| 国产亚洲欧美精品永久| a级毛片黄视频| 亚洲精品一区蜜桃| 久久鲁丝午夜福利片| 男女边摸边吃奶| 又粗又硬又长又爽又黄的视频| 精品卡一卡二卡四卡免费| 亚洲精品456在线播放app| 国产精品人妻久久久久久| 精品熟女少妇av免费看| 成人国语在线视频| 高清欧美精品videossex| 久久久久久人人人人人| 人妻一区二区av| 最近最新中文字幕大全免费视频 | 97在线视频观看| 亚洲高清免费不卡视频| 国产一级毛片在线| 九草在线视频观看| 国产精品秋霞免费鲁丝片| 黑人欧美特级aaaaaa片| 欧美成人午夜免费资源| 欧美亚洲 丝袜 人妻 在线| av卡一久久| 精品一品国产午夜福利视频| 观看av在线不卡| 99久久精品国产国产毛片| 亚洲精华国产精华液的使用体验| 日本wwww免费看| 日韩 亚洲 欧美在线| 亚洲中文av在线| 一边亲一边摸免费视频| av线在线观看网站| 如日韩欧美国产精品一区二区三区| 美国免费a级毛片| 亚洲精华国产精华液的使用体验| 久久这里只有精品19| 午夜激情av网站| 伦理电影大哥的女人| 亚洲国产欧美在线一区| 18禁动态无遮挡网站| 午夜福利网站1000一区二区三区| 亚洲婷婷狠狠爱综合网| 亚洲性久久影院| 最近最新中文字幕免费大全7| 久久久久国产精品人妻一区二区| 黑丝袜美女国产一区| 成人影院久久| 欧美97在线视频| 哪个播放器可以免费观看大片| 国产精品久久久久成人av| 欧美人与善性xxx| 亚洲精品色激情综合| 亚洲av综合色区一区| 欧美日韩一区二区视频在线观看视频在线| 中国国产av一级| 日日啪夜夜爽| 日本色播在线视频| 亚洲国产精品成人久久小说| 夫妻性生交免费视频一级片| 天美传媒精品一区二区| 热99久久久久精品小说推荐| 黑人高潮一二区| 婷婷成人精品国产| 亚洲激情五月婷婷啪啪| 在现免费观看毛片| 欧美最新免费一区二区三区| 黄色怎么调成土黄色| 国产成人精品一,二区| 如日韩欧美国产精品一区二区三区| 国产精品久久久久成人av| 日本黄色日本黄色录像| 国产片内射在线| 午夜福利视频在线观看免费| 亚洲欧洲国产日韩| 免费看av在线观看网站| 亚洲精品视频女| 午夜91福利影院| 欧美老熟妇乱子伦牲交| 久久人人爽人人爽人人片va| 国产深夜福利视频在线观看| 日本午夜av视频| 亚洲国产精品成人久久小说| 欧美日韩一区二区视频在线观看视频在线| 午夜福利视频精品| 国产在线视频一区二区| 在线观看国产h片| 在线观看人妻少妇| 久久这里只有精品19| 天堂俺去俺来也www色官网| 男女免费视频国产| 亚洲欧美清纯卡通| 久久久久久久久久人人人人人人| 看免费av毛片| 高清视频免费观看一区二区| 国产片内射在线| 亚洲国产毛片av蜜桃av| 亚洲国产精品专区欧美| 亚洲国产成人一精品久久久| 欧美日韩视频精品一区| 麻豆精品久久久久久蜜桃| 高清黄色对白视频在线免费看| 热re99久久国产66热| 国产伦理片在线播放av一区| 国国产精品蜜臀av免费| 国产又爽黄色视频| 女人精品久久久久毛片| 九九爱精品视频在线观看| 国产极品天堂在线| 在线免费观看不下载黄p国产| 成人亚洲欧美一区二区av| 日本爱情动作片www.在线观看| 久久精品熟女亚洲av麻豆精品| 草草在线视频免费看| 麻豆精品久久久久久蜜桃| 国产成人精品无人区| 亚洲婷婷狠狠爱综合网| videosex国产| 亚洲,一卡二卡三卡| 免费看不卡的av| 五月玫瑰六月丁香| 国产乱人偷精品视频| 久久99蜜桃精品久久| 色婷婷久久久亚洲欧美| 午夜福利在线观看免费完整高清在| 91精品伊人久久大香线蕉| 久久av网站| 午夜激情久久久久久久| 一级爰片在线观看| 亚洲综合色惰| 国产深夜福利视频在线观看| 精品国产乱码久久久久久小说| 人妻少妇偷人精品九色| 大话2 男鬼变身卡| av电影中文网址| 大香蕉久久网| 人人妻人人添人人爽欧美一区卜| 国产又色又爽无遮挡免| 午夜久久久在线观看| 黑人巨大精品欧美一区二区蜜桃 | 涩涩av久久男人的天堂| 搡女人真爽免费视频火全软件| 啦啦啦啦在线视频资源| 免费人妻精品一区二区三区视频| 人妻系列 视频| 日韩人妻精品一区2区三区| 我要看黄色一级片免费的| 久久久久久久久久久免费av| 国精品久久久久久国模美| 高清视频免费观看一区二区| 欧美日韩视频高清一区二区三区二| 国产午夜精品一二区理论片| 中文精品一卡2卡3卡4更新| 久久精品国产鲁丝片午夜精品| 哪个播放器可以免费观看大片| 人妻系列 视频| 日韩av不卡免费在线播放| 99久国产av精品国产电影| 黑丝袜美女国产一区| 国产免费视频播放在线视频| 黄色配什么色好看| 国精品久久久久久国模美| 亚洲久久久国产精品| 成人影院久久| 久久av网站| 中文字幕最新亚洲高清| 宅男免费午夜| 精品第一国产精品| 亚洲久久久国产精品| 成人漫画全彩无遮挡| 久久久欧美国产精品| 国国产精品蜜臀av免费| 久久毛片免费看一区二区三区| 免费久久久久久久精品成人欧美视频 | 免费看光身美女| 亚洲情色 制服丝袜| 午夜免费男女啪啪视频观看| 久久ye,这里只有精品| 精品一品国产午夜福利视频| 黑人猛操日本美女一级片| 午夜免费观看性视频| 午夜激情久久久久久久| 一区二区日韩欧美中文字幕 | 久久久久久人妻| 日韩中字成人| 国产深夜福利视频在线观看| 亚洲av.av天堂| 老熟女久久久| 亚洲一级一片aⅴ在线观看| 黑人巨大精品欧美一区二区蜜桃 | 国产精品免费大片| 精品人妻在线不人妻| 多毛熟女@视频| 午夜免费观看性视频| 午夜久久久在线观看| 在线观看免费视频网站a站| 一边亲一边摸免费视频| av视频免费观看在线观看| 男女高潮啪啪啪动态图| 亚洲,欧美精品.| 国产视频首页在线观看| 午夜视频国产福利| 成人18禁高潮啪啪吃奶动态图| 国产精品不卡视频一区二区| 亚洲精品国产色婷婷电影| 午夜视频国产福利| 亚洲情色 制服丝袜| 深夜精品福利| 免费观看无遮挡的男女| 久久久久久久久久人人人人人人| 99久久精品国产国产毛片| 天堂中文最新版在线下载| 99久国产av精品国产电影| 寂寞人妻少妇视频99o| 国产精品久久久久成人av| 亚洲欧美一区二区三区黑人 | 免费少妇av软件| 久久久国产一区二区| h视频一区二区三区| 亚洲欧洲日产国产| 久久亚洲国产成人精品v| 免费大片18禁| 性高湖久久久久久久久免费观看| 王馨瑶露胸无遮挡在线观看| 久久人妻熟女aⅴ| www日本在线高清视频| 天天操日日干夜夜撸| a级毛片黄视频| 一级片免费观看大全| 在线免费观看不下载黄p国产| 国产极品天堂在线| 国产精品蜜桃在线观看| 亚洲综合色惰| 亚洲国产看品久久| 男女国产视频网站| 亚洲精品美女久久久久99蜜臀 | 成人亚洲欧美一区二区av| 国产在视频线精品| 国产av码专区亚洲av| 天美传媒精品一区二区| 国产精品人妻久久久久久| 黑人高潮一二区| 自线自在国产av| 大香蕉久久成人网| 国产 精品1| 熟女电影av网| 嫩草影院入口| 国产成人精品福利久久| 青春草亚洲视频在线观看| 巨乳人妻的诱惑在线观看| 日韩不卡一区二区三区视频在线| 亚洲精品中文字幕在线视频| 亚洲av国产av综合av卡| 大香蕉97超碰在线| 九九在线视频观看精品| 久久97久久精品| kizo精华| 各种免费的搞黄视频| 亚洲国产欧美日韩在线播放| 男女啪啪激烈高潮av片| 热99国产精品久久久久久7| 国产欧美亚洲国产| 亚洲av电影在线观看一区二区三区| 亚洲美女搞黄在线观看| 国产 一区精品| 在线免费观看不下载黄p国产| 午夜福利在线观看免费完整高清在| 嫩草影院入口| 国产白丝娇喘喷水9色精品| 9色porny在线观看| 蜜桃在线观看..| 大片电影免费在线观看免费| 巨乳人妻的诱惑在线观看| 亚洲av男天堂| 亚洲图色成人| 亚洲美女视频黄频| 亚洲伊人色综图| 中文精品一卡2卡3卡4更新| 久久久欧美国产精品| 啦啦啦中文免费视频观看日本| 成人亚洲欧美一区二区av| 亚洲国产精品成人久久小说| 国产精品一国产av| 十八禁高潮呻吟视频| 亚洲国产欧美在线一区| 免费看不卡的av| 亚洲欧美日韩卡通动漫| 免费观看av网站的网址| 免费观看性生交大片5| 国产免费现黄频在线看| 曰老女人黄片| 波多野结衣一区麻豆| 新久久久久国产一级毛片| 日本猛色少妇xxxxx猛交久久| 尾随美女入室| 午夜91福利影院| 男的添女的下面高潮视频| 啦啦啦啦在线视频资源| 亚洲av.av天堂| 一区二区日韩欧美中文字幕 | 人妻 亚洲 视频| 亚洲情色 制服丝袜| 久久女婷五月综合色啪小说| 97人妻天天添夜夜摸| 两性夫妻黄色片 | 如日韩欧美国产精品一区二区三区| 亚洲图色成人| 多毛熟女@视频| 欧美日本中文国产一区发布| 高清欧美精品videossex| 这个男人来自地球电影免费观看 | 啦啦啦啦在线视频资源| 女人精品久久久久毛片| 国产又色又爽无遮挡免| 丝袜美足系列| 男女啪啪激烈高潮av片| 自线自在国产av| 大片电影免费在线观看免费| 捣出白浆h1v1| 国产精品熟女久久久久浪| 国产精品偷伦视频观看了| 久久精品国产亚洲av天美| 九色成人免费人妻av| 精品少妇黑人巨大在线播放| 美国免费a级毛片| 最新的欧美精品一区二区| 黑人巨大精品欧美一区二区蜜桃 | 免费大片黄手机在线观看| 中文字幕精品免费在线观看视频 | 亚洲精品一区蜜桃| www.熟女人妻精品国产 | 丝袜脚勾引网站| 免费观看a级毛片全部| 丁香六月天网| 青春草亚洲视频在线观看| 夫妻性生交免费视频一级片| 侵犯人妻中文字幕一二三四区| 日韩中字成人| 久久精品熟女亚洲av麻豆精品| 看免费av毛片| 午夜福利网站1000一区二区三区| 女的被弄到高潮叫床怎么办| 精品午夜福利在线看| 亚洲成av片中文字幕在线观看 | 麻豆精品久久久久久蜜桃| 精品一区二区免费观看| 国产成人午夜福利电影在线观看| 精品国产国语对白av| 日韩人妻精品一区2区三区| 天天躁夜夜躁狠狠躁躁| 大片电影免费在线观看免费| 岛国毛片在线播放| 精品一区二区三区视频在线| 免费观看a级毛片全部| 国产又爽黄色视频| 精品少妇久久久久久888优播| 日本-黄色视频高清免费观看| 欧美3d第一页| 777米奇影视久久| 亚洲精品美女久久久久99蜜臀 | 国产探花极品一区二区| 卡戴珊不雅视频在线播放| 久久精品人人爽人人爽视色| 日韩免费高清中文字幕av| 男女免费视频国产| 最近的中文字幕免费完整| 91国产中文字幕| 飞空精品影院首页| 极品人妻少妇av视频| 久久久久久久亚洲中文字幕| 亚洲内射少妇av| a级片在线免费高清观看视频| 黄色怎么调成土黄色| 国产免费现黄频在线看| 婷婷色综合www| 男的添女的下面高潮视频| 99热全是精品| 国产一区二区三区av在线| 免费黄网站久久成人精品| 日日撸夜夜添| 国产淫语在线视频| 青春草亚洲视频在线观看| 欧美日本中文国产一区发布| 亚洲婷婷狠狠爱综合网| 一区二区日韩欧美中文字幕 | 欧美亚洲日本最大视频资源| 搡女人真爽免费视频火全软件| 精品亚洲成a人片在线观看| 大码成人一级视频| 久久久欧美国产精品| 校园人妻丝袜中文字幕| 波野结衣二区三区在线| av不卡在线播放| 久久久亚洲精品成人影院| 热re99久久精品国产66热6| 又大又黄又爽视频免费| 亚洲伊人色综图| 国产成人91sexporn| 丁香六月天网| 夫妻午夜视频| 久久精品国产亚洲av涩爱| 最近手机中文字幕大全| 2022亚洲国产成人精品| 国产在线一区二区三区精| 亚洲国产精品一区三区| 制服丝袜香蕉在线| 精品99又大又爽又粗少妇毛片| 欧美另类一区| 久久久久久久久久人人人人人人| 九色亚洲精品在线播放| 亚洲伊人久久精品综合| 一本一本久久a久久精品综合妖精 国产伦在线观看视频一区 | 国内精品宾馆在线| av福利片在线| 免费看不卡的av| 2021少妇久久久久久久久久久| 国产精品一国产av| 精品国产一区二区三区四区第35| 啦啦啦视频在线资源免费观看| 日韩av不卡免费在线播放| 乱码一卡2卡4卡精品| 黄色怎么调成土黄色| 22中文网久久字幕| 十八禁高潮呻吟视频| 校园人妻丝袜中文字幕| 国产精品 国内视频| 极品少妇高潮喷水抽搐| 亚洲成人一二三区av| 桃花免费在线播放| 在线精品无人区一区二区三| 国产 精品1| 女人精品久久久久毛片| 成年人免费黄色播放视频| 亚洲人与动物交配视频| 18禁裸乳无遮挡动漫免费视频| www.av在线官网国产| 欧美精品亚洲一区二区|