【畢業(yè)學(xué)位論文】（Word原稿）矩形裝箱問題的協(xié)同決策模型

目 錄 矩形裝箱問題的協(xié)同決策模型 .未定義書簽。 中文摘要 .未定義書簽。 .未定義書簽。 目 錄 . 1 圖目錄 . 4 第一章 緒論 . 1 究背景 .題的提出 .究意義 .究現(xiàn)狀 .章結(jié)構(gòu) .二章 矩形洞 . 9 義及表示 .號約定 . 10 空四元組 . 10 行四元組 . 11 大四元組 . 11 于 . 11 含 . 11 點(diǎn) . 12 界點(diǎn) . 12 集 . 12 集 . 13 集 . 13 置關(guān)系 . 13 同 . 14 含 . 14 鄰 . 16 離 . 18 交 . 20 結(jié) . 21 關(guān)定理 . 21 本運(yùn)算及其實(shí)現(xiàn) . 24 R ） . 24 R ， r ） . 25 R ， r ） . 25 R，2R） . 28 結(jié) . 30 第三章 矩形裝箱問題容器格局 . 32 則描述 . 32 示方式 . 34 關(guān)定理 . 35 本運(yùn)算及其實(shí)現(xiàn) . 36 C， r ） . 37 C， r ） . 37 C， r ） . 38 C， R ） . 38 C， r ） . 39 C， r ） . 40 行策略 . 41 態(tài)模式 . 41 態(tài)模式 . 42 結(jié) . 44 據(jù)大小 . 44 結(jié) . 44 第四章 基于矩形洞的算法實(shí)現(xiàn) . 45 排放算法 . 45 法 . 47 法 . 48 法 . 49 結(jié) . 50 層排放算法 . 51 法 . 53 法 . 54 法 . 55 結(jié) . 57 面排放算法 . 57 法 . 58 F（ 法 . 60 法 . 64 結(jié) . 68 結(jié) . 68 第五章 協(xié)同決策模型 . 69 題定義 . 69 型結(jié)構(gòu) . 70 器格局 . 71 價(jià)標(biāo)準(zhǔn) . 71 度變化量 . 72 局變化量 . 72 間浪費(fèi)量 . 73 配變化量 . 74 結(jié) . 75 策模式 . 76 同類型的裝箱算法之間的決策 . 77 同類型的裝箱算法之間的決策 . 81 結(jié) . 83 雜度分析 . 84 結(jié) . 85 第六章 實(shí)驗(yàn)與分析 . 86 器格局規(guī)模 . 86 放高度 . 89 結(jié) . 92 第七章 結(jié)論與展 望 . 94 文工作總結(jié) . 94 續(xù)工作展望 . 95 參考文獻(xiàn) . 96 在學(xué)期間的研究成果 . 103 致 謝 . 104 圖目錄 圖 1箱問題的早期應(yīng)用 . 1 圖 1箱問題的現(xiàn)代應(yīng)用 . 2 圖 1于 優(yōu)化下料模型 . 2 圖 1口直角容器矩形裝箱問題實(shí)例 . 3 圖 1解圖 1示問題的 法示例 . 4 圖 1 及 法的比較 . 5 圖 1 1實(shí)例的一個(gè)最優(yōu) 解 . 5 圖 2形洞示例 . 9 圖 2形塊的集合表示 . 9 圖 2形洞的四元組表示 . 10 圖 2形洞 R 與待放矩形塊 r 的四元組解釋 . 10 圖 2行四元組之間的位置關(guān)系：內(nèi)含 . 14 圖 2行四元組之間的位置關(guān)系：邊內(nèi)含 . 15 圖 2行四元組之間的位置關(guān)系：角內(nèi)含 . 16 圖 2行四元組之間的位置關(guān)系：相鄰 . 17 圖 2行四元組之間的位置關(guān)系：相離 . 19 圖 2行四元組之間的位置關(guān)系：相交 . 21 圖 2元組 r 與 R 在 時(shí)的位置關(guān)系 . 26 圖 2交可行四元組之間的位置關(guān)系 . 28 圖 2行四元組的合并 . 29 圖 3角容器矩形裝箱問題示例 . 32 圖 3角容器中的空白部分示例 . 33 圖 3兩矩形塊同時(shí)相鄰的矩形洞個(gè)數(shù)示例 . 36 圖 3同裝箱算法的靜態(tài)工作區(qū)域 . 41 圖 3同算法的動態(tài)工作區(qū)域 . 42 圖 4排放裝箱算法示例 . 45 圖 4層排放算法示例 . 51 圖 4面排放算法示例 . 57 圖 4 區(qū)別 . 58 圖 4略示例 . 61 圖 4F 策略中左對齊放置對空間造成的浪費(fèi) . 62 圖 4F 策略中右對齊放置時(shí)對空間造成的浪費(fèi) . 62 圖 4略下的可行點(diǎn) . 64 圖 4略下的不能放置任何待放矩形塊的可行點(diǎn) . 65 圖 4意圖 . 66 圖 5形裝箱問題協(xié)同決策模型 . 70 圖 5箱算法之間的共同決策模型 . 76 圖 5箱算法之間的并行決策 . 77 圖 5面算法之間的決策 . 80 圖 5排放算法與平面算法之間的決策示例 . 82 圖 5層排放算法與平面算法之間的決策示例 . 83 圖 6A 求解 時(shí)的容器格局的規(guī)模 . 87 圖 6-2 1,2,3j ）協(xié)同求解 時(shí)的容器格局規(guī)模 . 87 圖 6-3 13 ）協(xié)同 求解 時(shí)的容器格局規(guī)模 . 88 圖 6A 求解 時(shí)的排放高度 . 89 圖 6-5 1,2,3j ）協(xié)同求解 時(shí)的排放高度 . 90 圖 6-6 13 ）協(xié)同求解 時(shí)的排放高度 . 91 圖 6類型裝箱算法與不同類型裝箱算法決策效果比較 . 92 圖 6間排放場景個(gè)數(shù)對求解結(jié)果的影響 . 93 蘭州大學(xué)博士學(xué)位論文 矩形裝箱問題的協(xié)同決策模型 1 第一章 緒論 究背景 裝箱問題（ 有悠久的 歷史 。早在一千年前，它就以駱駝、馬、驢子等家畜馱運(yùn)貨物（如 圖 1a）所示），抑或馬車運(yùn)貨（如 圖 1 1b）所示）的形式呈現(xiàn) 在現(xiàn)實(shí)生活中 了 。這類早期的裝箱問題 大 都局限于較小的規(guī)模， 排放者一般可以依照自己的經(jīng)驗(yàn)或者直覺找到一個(gè)足夠好、甚至是最優(yōu)的排放方案。 （ a） （ b） 圖 1箱問題的早期應(yīng)用 雖然 于 1939 年就從線性規(guī)劃的數(shù)學(xué)角度 給出了一維裝箱問題的求解思路，但是這并不能給早期的排放者帶來太大 的實(shí)惠。 因?yàn)?這些出身于農(nóng)民抑或工人的 排放者 并不擅于求解抽象的數(shù)學(xué)問題。 他們 更喜歡具體的、實(shí)實(shí)在在的、逐步完成的排放方案。通過世代的積累與沉淀， 人們總結(jié)出了一系列的經(jīng)典排放策略 ，如“ 金角銀邊草肚皮 ，價(jià)值最高鉆石穴 ” 2、“物以類聚” 3、 、 、 ， 以及 等等。 隨著現(xiàn)代工業(yè)與運(yùn)輸?shù)陌l(fā)展，裝箱問題廣泛應(yīng)用于機(jī)械工程、航空航天、造船、鈑金、制衣、玻璃切割、出版印刷 6、交通運(yùn)輸、大規(guī)模集成電路設(shè)計(jì) 7, 8、城市規(guī)劃和建筑設(shè)計(jì)等諸多行業(yè) 9, 10。與早期的應(yīng)用不同，這些應(yīng)用中的裝箱問題往往都具有較大的規(guī)模 7, 11如 圖 1示）。傳統(tǒng)的個(gè)人經(jīng)驗(yàn)與直覺式的求解模式面臨極大的挑戰(zhàn)。 裝箱問題是 14隨著規(guī)模的增大，尋求該問題最優(yōu)解的時(shí)間將以指數(shù)速度增加。從實(shí)用性角度來看，最優(yōu)解算法 18適用于規(guī)模較小的裝箱實(shí)例；而在規(guī)模較大時(shí)，啟發(fā)式算法 25往成為 最佳 選擇。 蘭州大學(xué)博士學(xué)位論文 矩形裝箱問題的協(xié)同決策模型 2 與最優(yōu)解算法不同，啟發(fā)式算法雖然并不能保證最優(yōu)解的獲取，但是卻能在較短的時(shí)間內(nèi)尋找到“較好”的可行解 29, 39這里所謂的“較好”是相對于大量測試實(shí)例而言的。從統(tǒng)計(jì)意義上來說，這足以說明一個(gè)算法的優(yōu) 越性；但是 就具體 的裝箱問題來說 ，這樣的結(jié)果可能有明顯的缺憾。 （ a） （ b） 圖 1箱問題的現(xiàn)代應(yīng)用 為了避免這種缺憾的產(chǎn)生，閻春平 教授 于 2001 提出了基于 二維優(yōu)化下料方法 43。 如 圖 1示 ， 這種方式雖然說能夠在不增加優(yōu)化時(shí)間的前提下獲取比單一軟件更好的結(jié)果，但是由于缺乏優(yōu) 化軟件間的互動而無法 組合各個(gè)優(yōu)化軟件的優(yōu)勢 ， 進(jìn)而 獲取優(yōu)于所有參與優(yōu)化的單一軟件所得最好結(jié)果的結(jié)果 。 因而我們需要尋求一種能夠?qū)崿F(xiàn)不同裝箱算法之間互動的 求解 模型。 下 料 數(shù) 據(jù)前 處 理 前 處 理 前 處 理優(yōu) 化 軟 件 1 優(yōu) 化 軟 件 2 優(yōu) 化 軟 件 理 后 處 理 后 處 理結(jié) 果 評 判優(yōu) 化 結(jié) 果 圖 1于 優(yōu)化下料模型 蘭州大學(xué)博士學(xué)位論文 矩形裝箱問題的協(xié)同決策模型 3 題的提出 古語有云：“尺有所短，寸有所長，物有所不足?！毖b箱算法也不例外。從統(tǒng)計(jì)學(xué)角度來看，現(xiàn)存的每一個(gè)裝箱算法都是比較優(yōu)秀的，但是 就 具體的裝箱實(shí)例而言 ，任何一個(gè)裝箱算法都有表現(xiàn)不佳的時(shí)候。也就是說，任何一個(gè)裝箱 算法都不是十全十美的，它都有一定的優(yōu)點(diǎn)，也 有一定的不足。為了使 每一個(gè)裝箱實(shí)例都有最好的排放效果，我們需要各個(gè)不同的裝箱算法之間的 協(xié)同決策 。 為了便于描述，本文只考慮矩形裝箱問題。通常來說，矩形裝箱問題又可以分為直角容器矩形裝箱問題 44 敞口直角容器矩形裝箱問題 49 敞開相鄰兩邊的直角容器矩形裝箱問題 53 嚴(yán)格來說，在允許容器的高 度 或者寬度為 時(shí)，這三類矩形裝箱問題可以相互轉(zhuǎn)化，因而本文僅僅以 例來介紹如何實(shí)現(xiàn)裝箱算法之間的 協(xié)同決策 。 究意義 112233554466待 放 矩 形 塊待 放 矩 形 塊敞 口 直 角 容 器敞 口 直 角 容 器圖 1口直角容器矩形裝箱問題實(shí)例 1980 年證明了 （ 法的近似率為 1710； 1983 年指出 （ 法一般都會優(yōu)于 且其近似率不超過 3。 這兩個(gè)算法都是十分優(yōu)秀的，但是 在求解 圖 1 矩形裝箱問題的協(xié)同決策模型 4 所示的實(shí)例時(shí)， 它們 卻有明顯的不足。 如 圖 1示，這兩個(gè)算法都有 明顯 的空間浪費(fèi)情況： 法造成了 下部空間 的浪費(fèi)，而 法 則 造成了上部空間的浪費(fèi)；而且 造成空間浪費(fèi)的罪魁禍?zhǔn)拙褪蔷匦螇K 4。此外 浪費(fèi)空間 出現(xiàn) 的位置 與 矩形塊 4 的 排放次序 和 排放 策略有直接的關(guān)系 。 F F D F D 123546圖 1解 圖 1示問題的 法示例 從優(yōu)勢互補(bǔ)的角度來考慮， 法能夠有效消除瘦長矩形塊 4 對排放結(jié)果的影響，卻不能有效避免下部空間的浪費(fèi)； 而 法 能 夠有效 避免下部空間的浪費(fèi)，卻不能 消除 瘦長矩形塊 4 對上部空間的浪費(fèi)。 這足以說明 但是如何才能將這兩個(gè)算法有機(jī)地結(jié)合起來 ，以充分發(fā)揮各自的長處而避免相應(yīng)的缺陷 呢？ 一個(gè)簡單的方法就是 采用 排放次序、 法的排放策略 ，這稱為 法。 圖 1明 法 能夠 比較 完美地避免瘦長矩形塊 4 對空間造成的浪費(fèi)， 但是 這并不能說明 法 的優(yōu)越性。 因?yàn)檫@僅僅是一個(gè)實(shí)例的比較，而非統(tǒng)計(jì)意義上的 分 析 。 如 圖 1示 ， 及 法 雖然 都沒有明顯的空間浪費(fèi)，但是 法 卻 有更高的空間利用率 。 之所以出現(xiàn)如此尷尬的境地，是因?yàn)?法不能很好地解決矮寬型矩形塊 3 的排放。 值得注意的是， 優(yōu)先解決矮寬型矩形塊正是 法的 精華所在 。這說明， 單純地 將兩個(gè)算法結(jié)合起來 并不一定能取得較好的排放方案。 蘭州大學(xué)博士學(xué)位論文 矩形裝箱問題的協(xié)同決策模型 5 從最優(yōu)解的角度來看， 法就是 圖 1示問題的一個(gè)最優(yōu)解 算法 。 事實(shí)上，該最優(yōu)解方案還可以看成是 依次運(yùn)行 法三次、 法一次的結(jié)果。 對于 圖 1的實(shí)例來說， 它的一個(gè)最優(yōu)解方案可以通過依次運(yùn)行 法兩次、 法三次 得來 ，如 圖 1示 。 F F D H B F D 及 法的比較 123546圖 1 1實(shí)例的一個(gè)最優(yōu)解 以上分析說明，不同的裝箱算法可以通過某種特定的溝通與交流達(dá)到更優(yōu)的排放 結(jié)果。 這正應(yīng)了一句古話， “人多力量大” 。 亦即， 裝箱 算法之間通過某種合作可以獲取更優(yōu)的 排放 結(jié)果 。 蘭州大學(xué)博士學(xué)位論文 矩形裝箱問題的協(xié)同決策模型 6 究現(xiàn)狀 裝箱問題具有悠久的歷史。起初，受到生產(chǎn)力發(fā)展的限制，裝箱實(shí)例往往規(guī)模較小。排放者完全可以根據(jù)自身的生活經(jīng)歷找到一個(gè)比較滿意、甚至是最優(yōu)的排放 方案 1859, 60