北京理工大學珠海學院2020屆本科生畢業論文配送車輛三維裝箱優化方法研究

摘要在貨物運輸的過程中，裝箱貨物是我們能遇到的必不可少的問題。若想大大提高車廂空間的利用率，減少車輛的派送，提高經濟效益，我們則需要一個合理的裝箱方案來減少企業的經濟浪費。就目前的研究狀況表明，研究人員對該問題設計了不少的啟發式算法與智能算法。其中三維裝箱優化問題需要考慮很多因素，本文通過對研究現狀的分析，來對配送車輛裝箱問題求解算法進行優化。通過對裝箱問題的研究與分析，討論了啟發式算法以及智能優化算法，最后采用一種空間合并啟發式算法混合模擬退火算法作為本文優化模型的求解算法。本文針對弱異類裝箱問題建立了優化模型，考慮了眾多的約束條件并對目標函數進行了數學化的解釋。運用啟發式算法以及模擬退火算法優化配送車輛裝箱方案，最后通過MATLAB軟件對算法進行實現。通過實例結果的分析，驗證該方法的有效性。本文選擇珠海市一家S公司的供應實例，運用所建立的模型與算法，對其車廂裝箱過程進行計算求解，驗證該算法的有效性。關鍵詞：三維裝箱問題；弱異類；啟發式算法；空間合并優化；混合模擬退火算法。

AbstractPackingisanindispensableproblemintheprocessofgoodstransportation.Ifwewanttogreatlyimprovetheutilizationrateofcarriagespace,reducethedeliveryofvehiclesandimproveeconomicefficiency,weneedareasonablepackingschemetoreducetheeconomicwasteofenterprises.Accordingtothecurrentresearchsituation,researchershavedesignedmanyheuristicandintelligentalgorithmsforthisproblem.Thethree-dimensionalpackingoptimizationproblemneedstoconsidermanyfactors,thispaperthroughtheanalysisoftheresearchstatus,tooptimizethedistributionvehiclepackingproblemalgorithm.Basedontheresearchandanalysisofpackingproblem,theheuristicalgorithmandintelligentoptimizationalgorithmarediscussed.Atlast,ahybridsimulatedannealingalgorithmbasedonspatialcombinationheuristicalgorithmisadoptedtosolvetheoptimizationmodelinthispaper.Inthispaper,anoptimizationmodelisestablishedfortheproblemofweakheterogeneouspacking,manyconstraintsareconsidered,andtheobjectivefunctionisexplainedmathematically.Heuristicalgorithmandsimulatedannealingalgorithmareusedtooptimizethepackingschemeofdistributionvehicles.Finally,thealgorithmisrealizedbyMATLABsoftware.Andtheeffectivenessofthemethodwasverifiedbyanalyzingtheresultsofanexample.Inthispaper,asupplycaseofScompanyinzhuhaicityisselected,andthemodelandalgorithmestablishedareusedtocalculatethepackingprocessofitscars,soastoverifytheeffectivenessofthealgorithm.Keywords:three-dimensionalpackingproblem;Weakheterogeneous;Heuristicalgorithm;Spacemergeoptimization;Hybridsimulatedannealingalgorithm.

目錄第一章緒論 緒論1.1研究背景：當今我國的市場經濟迅速發展，越來越多的新型行業逐漸涌出，其中物流行業便得到了人們的關注。在整個的經濟建設中，物流行業獲得了不可或缺的地位。在該行業中，配送效率是各個行業最為關注的環節，其中包括配送路徑的優化，裝箱問題的研究等等。而在很多情況下，供應商與采購商所在位置的固定使得運送路徑的確定，在整個配送過程中，裝箱問題（BinPackingProblem,BPP）則起到了至關重要的作用。同時，不僅在物流行業，裝箱問題在很多工業生產方面也有著重要意義，例如工廠的物品堆放等等都可運用到裝箱的方案。在本文中，我們針對配送車的裝載進行設計，在設立裝箱方案時，我們把持的宗旨是盡量減少車輛的使用量，同時滿足最大需求，來達到提高車輛容積與體積利用率的目的。想要得到相對應的實際問題的可行方案，圍繞這一中心思想便可以較大程度的提高運輸過程中的工作效率，達到降低成本，節約勞動力，減少企業消費的效果。裝箱問題的解決可以給生產效率帶來有效的優化效果，同時也使得人們的關注到了更加廣闊的應用價值，其中我們不難看出其思想運用了工業工程的思想，提高效率，減少成本，在有限的資源下盡量達到最高的利用率。三維裝箱問題的實際解決過程中是有很多不確定因素的，我們是很難運用傳統的數學方法來計算的。因此更多的研究人員面對該問題是想到的是運用智能算法或者啟發式算法來進行求解。歷史上，在面臨實際問題時，很多研究都是運用一種算法，如蟻群算法，粒子群算法，遺傳算法，免疫算法，差分進化算法和模擬退火算法等原始算法。隨著物流業的發展，人們在裝箱過程中遇到的不同狀況，研究人員綜合了原始算法的優勢，同時根據實際問題的需求對啟發式算法以及智能優化算法進行處理或集成，形成一種更加優化的算法來求解，從而得到更為精確且優化的計算結果。在不同的應用場合下，裝箱問題追求的效益目標也有所不同，這使得在具體的實例分析中，求解的過程差異很大，所以該問題目前并沒有一個普適方法。所以我們也將針對不同的狀況與需求設計不同的算法。1.2研究意義：從實際的角度出發，隨著當今生產速度的發展，人們對運輸貨物有了更高的要求。而裝箱問題在運輸的過程中，是人們迫切需求解決的重要問題。解決裝箱問題可直接提高效率，降低成本，可為企業帶來可觀的收益。進入21世紀后，人們的消費水平逐步提高，對運輸的需求有了進一步的提高，且在時效性方面漸漸地出現了競爭的趨勢，在物資資源分布不均衡的狀況下，裝箱問題的求解方法已然成為一個很重要的指標。從理論的角度出發，作為多約束且復雜的優化問題，裝箱問題于20世紀70年代初便引起了學術界與企業界的關注。裝箱問題可以抽象為一種三維物理空間的裝填問題和裁剪問題的結合。因此，裝箱問題可在眾多領域得到應用，具有很大的研究價值。為了能夠找到更有效的求解該裝箱問題的方法，本文參考且分析了以往的文獻，并嘗試使用先進的智能算法對該問題的可解決性進行探討。1.3國內外發展狀況1.3.1國內研究狀況就目前的情況看，我國對裝箱的問題的研究以及涉及到的相關問題都不是很多，下面介紹幾個國內研究人員的算法（何大勇等人的算法是裝箱問題的研究，后面的只是與之相類似的問題的研究。曹先彬等人算法是關于抽象裝箱問題的研究，是同一伙人提出的兩種算法，王金敏等人的算法是三維布局的問題研究）。何大勇等人(北方交通大學機電工程學院)針對裝箱問題的深入探討并提出算法。計算方法的大體思路是運用三叉樹結構來描述矩形貨物三維局部狀態。在不提盒子特征與類別的情況下，通過計算機隨機產生了貨物的起初尺寸數據，是一種構造型啟發式算法。在運算的過程中是通過一定的優先級來裝第一個貨箱，此時將整個集裝箱的空間都看做為三叉樹的根結點，然后將第一個貨箱放到根結點的左后下角，此時貨物周圍空間劃分為三個剩余空間，根據三叉樹的數據結構，對貨物周圍的三個剩余空間分別進行填裝，其中三個剩余空間是根據貨物的空間布局來分割的。分別將這三個空閑空間看作根結點的左、中、右三個子結點，此時的優先原則按深度進行篩選，對這三個獨立的布局空間分別進行上述的算法過程，直到最后一個貨箱裝入為止。該算法有一個弊端，就是盒子被逐放入，并沒有處理空隙的問題。[4]曹先彬等人（中國科技大學計算機科學技術系）針對裝箱問題運用的是遺傳算法和免疫遺傳算法來求解。該論述并沒有給出實際的應用背景。他們用40個隨機產生的小盒子和一個確定尺寸的長方體箱體作為研究對象。[5]他們用的第一個算法就是遺傳算法。是按照每個盒子之間的尺寸差，即寬、高度的差以及總長度和長方體箱體之間的長度差來給出適應度函數，采用二進制編碼，其中，變異概率取的是0.1，交叉算子運用的是兩點交叉法。通過對第一個算法的理解并加以改進，得到了他們的第二個算法。該算法采用的是免疫遺傳算法，但編碼的方式仍為二進制編碼。算法的結果給出了局部的平面圖。以上兩種算法的初始解均為隨機產生的一組0、1二進制編碼。但該算法是通按標準的免疫速傳算法和遺傳算法的步驟進行一步一步求解計算的，同時算法的最初也是由0，1兩個染色體編碼隨機生成而產生的，因此，計算結果很難保證是最優解。另外，貨物箱體是會出現懸浮狀態或傾斜狀態的問題，此現象是大大降低箱子的空間利用率的，且在運輸特殊物品時不符合實際情況。同時從最終的顯示結果上看，該算法沒有考慮到每一層自上而下的貨物箱體高度的一致性。王金敏等人（天大機械工程學院）是三維布局的問題進行了深入探討，同時運用模擬退火算法進行求解。但該算法沒有應用到具體的實際應用背景。其中，算法提出了求解的初始溫度的方法以及退火的策略，還有目標函數以及它的約束條件。該算法將得到的隨機解作為其初始解，于此同時，通過隨機移動操作產生鄰域解。而不足之處是該算法沒有與其他算法的結果進行比對，無法表明該算法的有效性，同時它的收斂速度較慢，增加了求解的時間。[6]1.3.2國外研究狀況通過閱讀外國文獻，國外學者對集裝箱裝箱問題的的研究起步比較早，且已經有了很長時間的發展，以下為本文列舉的具有代表性的作品，同時在外國著名期刊上發表的研究成果。Correa等人針對裝箱問題做出的研究與分析,是假設了可以控制的物品的尺寸,同時規定了每個物品各自的懲罰值,最后將整個過程中所有使用到的盒子進行累加求和,最后的目標函數是求得其累加值最小。[7]Crainic等人對求解三維裝箱優化問題進行了深刻的理解，思路是盡可能的減少裝箱過程中用到的箱子數量，來改善大箱子的布局，達到優化求解的效果，該方法分為了兩個階段，運用的算法是禁忌搜索算法。[9]Baldi等人針對的是裝箱問題中的一類，即廣義裝箱。并對該問題后續進行了研究，不久之后針對隨機的廣義裝箱問題進行了更多方面的探討。針對此類問題，他們給出了具體的求解算法，其中約束條件包括箱子的成本費用與其大小尺寸，并把待裝箱的物品分為兩類，一個是利潤會有變動的物品，另一類是利潤不會變的的物品。同時學者們考慮到了經濟特征的隨機性，用到了極值的漸進的原理，把物品的利潤用隨機函數表示，從而得到一個結果的漸近值。[9]YongWu等人通過對各種各樣類型的三維貨箱的批處理進行分析與研究，運用的是混合遺傳算法的方法，根據實際環境，預設箱體都為長方體，并針對其高度運用堆積指數的方法設計了裝箱的方法。最后通過對比Liao等121人對于三維裝箱方案的最終結果，證明自己算法的有效性。[8]AlvarezValdes等人對裝箱問題分了兩方面的研究，分別對二維和三維裝箱進行了例證。其中該研究主要考慮的因素是成本費用的控制與貨箱的尺寸大小，也針對其隨機性給出了相應的策略與求解的算法，并對于每個優化階段需求的不同，進行了職責的分配，大大提高裝箱的效率。[9]綜上所述，我們不難看出國外的研究人員研究的裝箱優化算法大多限定在一維和二維的研究分析上，所使用的算法大多包括啟發式算法和遺傳算法、禁忌搜索法等智能算法。裝箱問題的不定因素,約束條件等等都比較復雜,因此,對于三維裝箱問題相關研究并不多見。1.4研究方法1.4.1研究內容本文是通過介紹以往對裝箱問題的研究成果，比較其優劣性，最終形成自己的一個優化算法，目標為盡量提高車廂的容積利用率，減少車輛的派送，從而降低物流的成本，并將本文的算法——空間合并啟發式算法和模擬退火算法——應用到實際例子當中，最終達到預期目標，得到其可行解。通過對配送車三維裝箱過程的研究與分析，本文構建了一個三維模型，運用了啟發式算法進行計算，以空間利用率最大作為目標函數，以車廂容積作為約束條件，構造出一種空間合并啟發式算法混合模擬退火算法。通過進行求解。通過MATLAB平臺對該算法進行實現，并以珠海市某汽車制造企業為實例，進而證明該算法的有效性。本文設計了裝箱的算法來求解現實生活中配送車輛裝箱優化問題，其中較為重點研究部分的內容為:1.為求解本文采用的裝箱優化算法，本文介紹了眾多針對裝箱問題研究所設計出的啟發式算法，以及介紹針對該問題應用的智能算法，分別寫出了其優缺點來對該問題有一個更加明確的表達。最后運用了一種空間合并啟發式算法混合模擬退火算法，介紹了該算法的優越性,并與以往的研究算法進行比對。經實例驗證，算法求解優化。2.在我們建立三維裝箱模型時，考慮了較為全面的因素，其中包括裝載順序、裝載的合并、擺放方向、容積的有限性以及裝定位規則等等。盡可能去滿足日常生活中實際裝箱問題的需求。1.4.2技術路線：本文的技術路線如圖1所示:啟發式算法和模擬退火算法的特點啟發式算法和模擬退火算法的特點圖1-1技術路線1.5本章小結本章指出三維裝箱問題實際的應用價值，并裝箱問題進行了詳細的描述與分析。通過概述幾個針對裝箱問題來設計的經典算法，來闡述了裝箱問題國內外的發展狀況，并明確的敘述了本文的設計思路與結構框架，提出了本文的研究重點，明確本文的中心。

配送車輛三維裝箱理論基礎2.1三維裝箱問題的基本內容2.1.1裝箱問題的分類針對裝箱問題的分類，研究人員根據集裝箱的不同特點，提出了不同的分類方法。如考慮重量限制，貨物種類，分布狀態，集裝箱的數量限制以及維度等等。下面是對近年主要考慮的兩大主要的分類方式進行詳細描述。1.按照貨物種類分類裝箱問題基本上被分為3類：箱子里裝的為同一種物品——規格完全相同，尺寸大小完全相同。該問題稱為：同類問題。箱子里裝的為不同種物品，若物品有很多種不同類型，該問題稱為：強異類問題。箱子里裝的為不同種物品，若物品只用幾種不同類型，該問題稱為：弱異類問題。2.按照維度分類裝箱問題基本上被分為3類：一維裝箱問題，如鋼管下料等問題，只考慮長度因素。二維裝箱問題，如場地劃分區域等問題，考慮長與寬兩個因素。三維裝箱問題，會考慮長、寬、高組成的空間因素。本文裝箱問題的模型是基于三維建立的。2.1.2裝箱問題的基本描述無論面對多么復雜多樣的物品，在裝箱的過程中，我們都應盡量做到歸類，即盡量把相同尺寸的物品放在一起。在當今社會大批量生產逐漸盛行的情況下，裝箱問題主要在于單一的裝箱問題上，使得車廂空間利用率最大。即可以稱為弱異類問題。為了簡化且不失一般性的描述，我們可以對該問題進行如下描述：車廂為一個大型規則的長方體，在后部開門。車廂的長寬高分別設為坐標系的x軸，y軸，z軸。貨物都被裝在長方體的盒子當中，搬運中盒子的擠壓變形將被忽略不計。貨物的長寬高都將平行于車廂的長寬高，不可以斜放。一種貨物可以與任意其他種貨物相鄰，且可以放到車廂的任何位置。貨物的總體積不能超出車廂的容積。2.2啟發式算法啟發式算法可以定義為：一個基于直觀或經驗構造的算法，在可接受的花費（指計算時間和空間）下給出待解決組合優化問題每一個實例的一個可行解，該可行解與最優解的偏離程度一般不能被預計。為了便于描述，我們在這里引入“層”的概念——裝入車廂，可以看成一層一層的把貨物裝進去。“層”分為水平和豎直，映射到坐標上為XY面、YZ面和XZ面。在裝箱的順序中，我們設為從原點開始，一層裝好再開始新的一層，直到裝滿車廂。2.3構造型啟發式算法構造型啟發式算法是研究人員根據自己的實驗經驗，設計一種空間搜索的規則。理論上，啟發式算法已經得到了學者們的不斷完善，并且也被廣泛的應用。但在實際的應用上，最后結果很難保證是最優解，通常情況下會得到一個可以接受的可行解。且該算法易于實現，具有非常實用的價值。因此，得到了大量學者的研究。2.3.1Georgr&Robinson算法Georgr和Robinson的算法采用了構造型啟發式算法，首次提出了“層”的概念，該概念對后來其他學者研究裝箱問題產生了巨大的影響。該算法主要的思路是：貨物在裝箱的過程中，以“層”的形式裝載，并以X軸作為“層”的方向。每一層的深度卻決于該層第一個裝入的貨物的長度，之后裝入該層的貨物不得超過第一個的長度，直至該層沒有空間裝入貨物時，啟用新層，直到裝完整個箱子為止。其中值得注意的兩點是：貨物優先順序的確定。首先，把貨物歸類為兩個狀態——打開的狀態和關閉的狀態（打開的狀態為：以裝入箱內貨物的狀態。關閉的狀態：沒有裝入箱內貨物的狀態。）。由于，如果裝入較少數量的貨物，極易出現一層裝不滿的現象。因此，通常選用數量較多并且已經處于打開狀態的貨物開始第一層的裝入。也不難看出其弊端，就是若一層有兩種或兩種以上的不同種類的貨物便會出現縫隙，大大降低空間利用率。其次，對于關閉狀態的貨物，該算法給出了三個級別的標準（按照每個貨物有長、寬、高三個尺寸中的最小尺寸排序，最小尺寸越大，貨物級別越高，也就也先裝入箱體，為的就是以免到最后大尺寸的貨物難裝入箱子。對于同一級別的貨物，數量多的優先裝入箱體，便于同種貨物可以裝滿一層從而提高空間利用率。如果以上兩點都滿足，即仍然在同一級別，則我們開始把貨物長、寬、高尺寸中最大的那一種作為優先級別）。“層”使用是豎直的YZ→X層。在優先級確定以后，則按照”層“的方式裝入箱體。Georgr和Robinson采用的是YZ→X層（轉滿YZ平面，延X軸方向建立新層）。尤主要思路所述將貨物裝入箱體。當貨物裝入箱體時，該算法總結為：該貨物四周會出現三個空間，即上方，前方和右方。在第一個箱子的基準下，按照先向上裝箱，其次向右方裝箱，最后向前。如圖2-1所示：圖SEQ圖片\*ARABIC圖SEQ圖片\*ARABIC2-1空間劃分圖右方向空間上方向空間前方向空間其中Georgr和Robinson注意到一個問題，即若一層中有不同尺寸的貨物，便會出現凹槽。此時他們會保留凹槽的空間，會將新層中的剩余空間與凹槽融合在一起，形成一種統一空間來提高空間利用率。如圖2-2所示：圖2-2層關系圖圖2-2層關系圖新舊層融合的空間新層向空間新舊層融合的空間新層向空間舊層舊層Georgr&Robinson算法不足之處：耗時長。該算法是針對每個貨物逐一獨立的分析，因此會用很多時間去計算和分析。在裝載每一層的過程中，依然存在裝箱過程中貨物與貨物之間的縫隙，浪費了空間。由于該算法是針對每個貨物個體分析的，每個個體周圍都只有三個方向，即上方，前方和右方。所以在裝載每一層的時候，會由于位于底端的貨物過大，而造成圖中的縫隙存在，降低了裝箱空間的利用率。如圖2-3所示：圖2圖2-3裝箱效果圖實際裝箱效果理想裝箱效果在層與層之間，空間融合僅僅只是新層與上一層空隙的融合，而我們想要的融合是所有層的空隙與新層的融合。該方法沒有做到充分的空間融合。2.3.2Gehring算法Gehring等研究的屬于是強異類問題。該算法也是基于“層“的概念展開的。與Georgr&Robinson算法不同的是，一方面，該算法沒有打開狀態和關閉狀態，因為貨物尺寸無一相同，所以貨物裝箱優先級只由體積大小決定，體積越大優先級越高。因此，所有貨物當中最大的那個貨物就為第一層第一個裝入的貨物（該貨物叫做LDB）。LDB有六種放置方式，根據放置方式的不同，有不同的本層深度，進而有不同的裝箱方式。另一方面，該算法的裝箱順序與Georgr&Robinson算法不同。在裝箱時，每個個體周圍都只有三個方向，即右方，上方和右前方。在第一個箱子的基準下，按照先向右方裝箱，其次向上方裝箱，最后向前。因此剩余空間的劃分也與上述不同，如圖2-4所示：圖2圖2-4空間劃分圖上方向空間右方向空間前方向空間Gehring算法不足之處：在每一層的裝箱過程中，裝完底部時，由于是在面對強異類問題，極易造成底部高度不同，導致在裝載第二排時出現貨物傾斜的狀態，在實際工作當中帶來極大的不便。層與層裝載過程中，沒有提到空隙的融合，導致層與層之間出現縫隙，沒有達到充分的利用空間。2.3.3Bischoff&Marriott算法Bischoff&Marriott算法依舊采用YZ→X層。與其他不同的是它有一個改進，引入了“完全層”的概念，即裝載每一層的時候裝同一尺寸的貨物，則稱該層為完全層。其優先級別的確立為：首先選擇數量比較多的貨物，保證可以構成完全層。由于貨物長寬高的不同，一層可能出現3種不同的深度，選取可以擺滿完全層截面占比最大的貨物。裝載過程中會有兩種情況：一種就是選擇的那類貨物剛好擺滿完全層，另一種情況是擺滿完全層還有剩余，此時該算法會采用Georgr&Robinson算法解決剩余的貨物。如圖2-5所示：圖2圖2-5完全層圖完全層2.3.4Loh&Nee算法Loh&Nee算法針對的是弱異類問題，即很多相同尺寸的貨物。與上述方法不同的是，采用層的方式是XY→Z層。為保證層與層之間的截面平整，所以考慮的是高度優先級。為隔離已裝載和未裝載的區域，該算法引入了一個移動邊界的概念。同時，設置了若干個節點去跟蹤貨物的高度差。但在實際的應用中裝載的車廂大部分是后開門，所以該算法并不符合實際應用。2.4智能優化算法2.4.1遺傳算法遺傳算法是模擬自然環境中生物的遺傳和進化過程而產生的一種自適應全局優化算法。該算法思路的形成基于孟德爾遺傳學說與達爾文生物進化論。20世紀60年代，遺傳算法最早被美國Holland教授提出。Holland教授認為這種自然界的遺傳法則是有規律可循的，同時利用這一規律設計出了人工的遺傳算法。20世紀70年代，DeJong通過對Holland教授提出的遺傳算法進行分析與研究，運用其思想，首次在計算機上實現并對一系列的純數字函數進行優化實驗。20世紀80年代，Goldberg的遺傳算法正式開始成熟起來。近年來，遺傳算法越來越得到了人們的重視，變成了一種全局搜索的智能優化算法。它在搜索過程中符合生物進化的過程，可以自行學習知識，積累知識。同時具有一定的自適性，因此得出的結果有一定可靠性，是當今社會中常被應用的一種智能搜索技術。和孟德爾遺傳學所說明的遺傳過程很相像，對于一組現有的種群，通過選擇，交叉，變異，猶如染色體遺傳的操作一樣，從而得到新一代的種群，以此類推，得到一組最為優質的種群，形成最優解。其中，最為復雜且關鍵的地方便是染色體的編碼與解碼，這部分便涉及到使用該算法的學者們的設計與創行了。簡言之，遺傳算法是通過對初始種群進行選擇，變異，交叉，得到一組新一代種群，逐漸形成優質的一組解進而得到最優解。其思想是模仿自然界進化論與遺傳學中的遺傳過程，最終設計出一套計算機科學的算法。因此涉及到了計算機與自然科學兩個領域，且他們之間有著共通之處，因此，在這里為了方便讀者的閱讀與理解，我們列出來一些專有名詞的類比，如2-1表所示：表2-SEQ表格\*ARABIC1遺傳算法對照表遺傳學術語遺傳算法術語群體可行解集個體可行解染色體可行解的編碼基因可行解編碼的分量基因形式遺傳編碼適應度評價函數值選擇選擇操作交叉交叉操作變異變異操作遺傳算法特點：遺傳算法是一種全局搜索算法，其最終結果具有可靠性，因此成為當今使用頻率極高的算法之一。其算法具也具有很多特點，如下：（1）遺傳算法可直接搜索并記錄目標函數的函數值。直接搜索目標函數的函數值是可以大大方便計算過程的，它不需要搜索目標函數產生的派升值與其他一些附加信息，這一點可以加快其搜索速度，提高計算效率。對于一些不能導出函數的優化問題，遺傳算法避開了這些問題的困擾，便捷了人們的使用。（2）遺傳算法以決策變量編碼為操作對象。遺傳算法是通過模擬自然界生物染色體基因交叉變異，從而進化出新一代種群來進行編碼和解碼。因此，在計算過程中，其遺傳算子易于應用到實際情況當中。尤其針對一些沒有數據的編碼，以及那些很難賦予數值的編碼的實際問題，該算法起到了明顯的優勢，方便人們使用。（3）遺傳算法具有自學性，自適應性以及自組織性。遺傳算法會留下更適應環境生存的種群，符合進化論中適者生存的理論。同時具有一定的學習能力，在變異過程中也會出現較優質的解。遺傳算法是一種容易與其他算法相結合的算法，這也符合了它適應環境的特點。因此，在我們實際應用時，我們可以根據實際情況對問題進行分析，適當運用遺傳算法與其他算法集成的思路，互相取長補短，設計出更加便于求解的算法。（4）遺傳算法的搜索技術存在概率因素。在遺傳算法中，算子之間的選擇，交叉，變異的過程都是有一定概率發生的，不是一定發生，也不是一定不發生，是具有靈活性的。就像自然界的進化一樣，不一定產生的新個體一定優于舊個體，但是隨著時間的推移，根據優勝劣汰的原則，總體的趨勢是產生優質的個體。（5）遺傳算法可以同時對多個搜索點進行信息的搜索。遺傳算法求解最優解的研究過程是從一個由多個個體而不是單個個體組成的第一組開始的。該種群的選擇、頻響和變異操作產生了新一代種群，包含了大量的種群信息。這種信息可以避免搜索一些不必要的點，這就相當于教授更多的點，這是遺傳算法特有的一種隱式并行性。2.4.2蟻群算法蟻群算法是通過對螞蟻集體的一些列行為盡心研究與分析，并模仿其行為構造出來的一種智能優化算法，是一種新型的放生進化算法。20世紀90年代初期，由意大利學者M.Dorigo根據螞蟻的集體行為最早提出蟻群算法。通過觀察，研究人員發現，螞蟻群體會不借助任何的外界力量，便可以找到一條離自己洞穴最近的食物的路徑，每一次覓食也會遇到新的環境，螞蟻群體也依舊可以適應新環境，找到最短路徑。通過不斷的深入研究，學者們發現螞蟻會分泌一種“信息素”，這些“信息素”會讓同群異地的螞蟻之間產生聯系，進而對它們的行為產生影響。最短的路徑，行走的螞蟻會越多，留下來的“信息素”濃度也就越高，因此螞蟻群體最終通過“信息素”來找到最近的路徑。當然，這總“信息素”長時間暴露在空氣中，是可以被蒸發的，所以“信息素”的濃度決定了螞蟻選擇這條路的概率。越來越多的螞蟻會經過“信息素”高的地方，食物距離遠的路徑，會隨著時間漸漸蒸發，最后螞蟻群體幾乎大概率的在這條距離最短的路徑上行動，以此類推，形成了正反饋。蟻群算法由于它的實用性，在現實生活中得到了廣泛的應用。如車輛的調度問題，聚類問題，TSP問題等等。該算法也屬于一種貪婪搜索算法，具有極強的擇優能力。它的系統化，以及正反饋機制都有利于搜索到全局的最優解。但在實際應用當中，蟻群算法的搜索耗時長，因此在解決實際問時，學者們常常把該算法與其他算法進行集成，來彌補其不足之處。蟻群算法優點：蟻群算法的魯棒性很強。運用蟻群算法得出的結果與其最初的初始路徑的選擇沒有太直接的關系，也就是說初始路徑的選擇不會影響結果的好壞。同時該算法中的參數很少，易于應用，同時一旦計算開始，就不需要人們在中途做人工調試，便于人們使用。蟻群算法具有通用性。對于大部分的路徑優化問題，都可以通過該算法進行仿真與建模找出最優答案。蟻群算法具有自組織性與并行性。該算法在計算過程中，其組織調令都是自己系統內部的，不需要外界的干預。在路徑選擇上可以自行從無序到有序的發展形成。具有很強的自組織性。但與此同時，算法中的每個個體也都是獨立的，具有并行性。它可以同時對多點進行搜索，因此可以對全局進行搜索，優化結果具有可靠性。蟻群算法具有正反饋機制，但同時接受負反饋機制。由上文敘述可知，正反饋機制來自“信息素”的堆積。但同時該算法接受負反饋，因此可以借此跳出局部最優的陷阱。蟻群算法缺點：該算法搜索時間長，效率低，在面對大規模的問題，會產生停滯的結果，從而得到局部最優解。2.4.3模擬退火算法模擬退火算法來源于固體退火原理，將固體加熱到最大高度，然后緩慢冷卻。有物理知識，我們直到固體加熱時，其內部會由于高溫的影響使其內部的粒子具有極高的能量。當冷卻時，粒子會逐漸平穩有序，在冷卻過程中，在每一個溫度時，內部粒子都有一個穩定的狀態，直到常溫，我們把此時粒子的狀態成為基態，粒子的能量達到最小。由于模擬退火算法是模仿固體退火的過程，其過程有相通之處，在這里我們對此作一個類比，如2-2表所示：表2-2模擬退火算法對照表物理退火模擬退火粒子狀態解能量最低態最優解溶解過程設定初溫等溫過程Metropolis采樣過程冷卻控制參數下降能量目標函數模擬退火算法思想模擬退火是模擬固體退火原理，其主要思想是:在實際應用中，我們選擇要搜索的區域，在搜索區間隨機游走(即隨機選擇點)，再利用Metropolis抽樣準則，使隨機游走逐漸收斂于局部最優解。而溫度是Metropolis算法中的一個重要控制參數，可以認為這個參數的大小控制了隨機過程向局部或全局最優解移動的快慢。Metropolis是一種有效的重點抽樣法，其算法為:系統從一個能量狀態變化到另一個狀態時，相應的能量從E1變化到E2,其概率為p=exp?E2?E如果E2<E1,系統接受此狀態;否則，以一個隨機的概率接受或丟棄此狀態。狀態2被接受的概率為p(1→2)=1E2<E這樣經過定次數的迭代，系統會逐漸趨于一個穩定的分布狀態。重點抽樣時，新狀態下如果是向下，則接受（局部最優）；若向上（全局搜索），也不會完全拒絕，而是會以一定概率接受。模擬退火算法從某個初始解出發，經過大量解的變換后，可以求得給定控制參數值時組合優化問題的相對最優解。然后減小控制參數T的值，重復執行Metropolis算法，就可以在控制參數T趨于零時，最終求得組合優化問題的整體最優解。控制參數的值必須緩慢衰減。溫度是Metropolis算法的一個重要參數，模擬退火可視為遞減控制參數T時Metropolis算法的迭代。開始時T值大，可以接受較差的惡化解:隨著T的減小只能接受較好的惡化解:最后在T趨于0時，就不再接受任何惡化解了。T在無限高溫時，系統立即均勻分布，接受所有提出的變換。T的衰減越小，有到達終點的時間越長:但可使馬爾可夫(Markov)鏈減小，以使得到達準平衡分”布的時間會便短。2.5本章小結介紹了很多關于裝箱問題提出的啟發式算法以及現代化智能優化算法的簡介與特點，為后文提出的空間合并啟發式算法混合模擬退火算法奠定了理論基礎。

配送車輛三維裝箱的模型構建3.1配送車輛三維裝箱的模型構建3.1.1目標函數的建立：解決配送車輛三維裝箱問題時，我們會將抽象的空間思想盡量數學化直觀化，對該問題進行如下描述：在我們事先規定好的約束條件下，把待裝貨箱依次裝載到配送車箱中，盡量使得每一輛配送車裝載更多貨物從而減少車輛的派送，我們可以用數學化的思想描述為通過使得車輛的容積利用率和裝載質量利用率達到最大，進而達到我們優化到的目的。設車廂的長、寬、高分別為L、W、H，最大裝載容積和最大裝載質量分別為V、G。待裝載的箱體（均為規則的長方體）數量為n，長、寬、高的尺寸分別為l、w、h。質量為g。本文我們建立的目標函數為：Maxz=(λ?1)j其中：λ是0-1變量，當要求目標為容積利用率最大時λ=1，當要求目標函數質量利用率最大是λ=0，β為[0,1]當箱體i裝入車輛中時，βi=1；當箱體i沒有裝入車輛時β本文意在事先知道將要運輸的物品，配送相應可承重的車輛，即本文只需考慮車輛的空間利用率。則上述目標函數的λ=1，則目標函數可描述為：Maxz=j=1m3.1.2約束條件貨物和車廂本身的約束條件車廂為一個大型規則的長方體，貨物的大小尺寸均小于車廂的大小尺寸。貨物重量均勻分布。貨物的擠壓變形忽略不計。貨物可承載的重量是無限大的，貨物上可以裝載任何貨物。在裝箱過程中的約束條件：擺放貨物的側壁方向平行于車廂的側壁，即X、Y、Z軸。貨物不能懸空擺放，不可斜放。貨物的總重量不超過車輛的載重。貨物的總體體積不能超過車廂的容積，即貨物的長寬高不高于車廂的長寬高，用符號表示：st.3.2配送車輛三維裝箱的算法通過第二章的描述，我們不難發現在研究裝箱問題的過程中，研究人員普遍把裝入的盒子孤立的進行分析，這些都是容易導致貨物之間的縫隙的出現，降低空間利用率。通過閱讀與分析眾多文獻，本文考慮不把貨物孤立的來看待，從而降低縫隙出現率，加以改進。3.2.1“塊”的概念本文引出生成“塊”的思想，其中包括兩大類生成過程。一是對一種貨箱進行排列形成大“塊”，二是由多種貨箱組成的復合“塊”。其中，由于復合“塊”中有不同種類大小的貨箱，不可避免形成復合“塊”內部的縫隙，對此我們忽略不計。生成“塊”有很多好處，因我們事先將大量貨箱生成“塊”，“塊”的數量是遠小于貨箱數量的，在裝載過程中，大大減小了待裝物的數量，同時一次性裝入配送車的貨物數量大大提高，在算法中，減少了空間搜索次數，從而提高了裝載效率。算法描述：本文講述的裝載算法屬于一種啟發式算法。算法的大致描述為：將所有待裝貨物以上述生成“塊”的形式排號，生成一系列的簡單塊與復合“塊”。裝載這些“塊”時，以“塊”體積降序的順序排列，通過計算車廂剩余空間大小將這些排好的序列形成塊表，優先級為塊表裝入車廂空間利用率最大，則最先裝入。在裝載的最后，極易出現“塊”裝載不下的狀況，此時對該類“塊”進行重新分割，再以上述方式排列，重新裝入車廂。這種裝在算法與大部分算法不同的是，該算法在裝箱過程中裝載的是一個序列，即一個向量，而非個體，大大提高裝載速率。通過該裝載方案，我們可以得到裝載順序與車廂空間的擺放位置的關系，采用模擬退火算法對得到的結果進行優化。3.2.2名詞概念為更加清晰的描述算法的過程，我們介紹一些在算法中涉及到的概念。在裝載過程中，每當貨物裝載到一個合理的位置，都可以用一個坐標來表示該位置，即等價位置。當貨物在這位置時是不可以下移，左移和后移的。則這個等價位置的坐標便設為該貨物當時的初始坐標，我們這里用（x，y，z）表示。本文默認所有待裝貨物均為長方體，所以每個待裝載的物體都有長、寬、高，我們這里分別用lx，ly，lz來表示其長度。不同大小的箱子視為不同種類type的箱子，即lx，ly，lz其中有一個不同，則按不同種類來劃分（其中朝向不同的箱子也視為不同種類）。“塊”是本文所描述算法中最小的裝載單位。它是同種或多種貨物組成的序列，其長、寬、高用lx，ly，lz來表示。由于每個“塊”內部由多個貨箱組成，所以容易出現“塊”頂部不整齊導致在實際情況中無法繼續向上面填裝貨箱，此時，我們搜索“塊”上方可放置貨箱的矩形區域，來實現繼續裝載貨物的需求，該長方形區域的長與寬我們用?x與?y來描述。塊表:塊表的形成有利于快速形成待裝載的塊序列，它是按照“塊”體積降序的順序排出的序列，記作blockform。剩余空間：剩余空間是指在車廂中未裝入貨箱的空間，這里我們把這些剩余空間進行分割，放在剩余空間棧spacestack里。在裝載過程中，我們從剩余空間站里隨機得到到一個剩余空間，然后在對應的塊表中搜索出一個與之相配的塊表進行放置。直到沒有剩余空間為止，即裝滿車廂為止。放置：放置是指把塊序列放入到剩余空間棧中的剩余空間里，是一個二元組，用（block，space）表示。在放置過程中塊序列的等價位置點與剩余空間的等價位置點重合。通過不同的空間分割方式，與不同的“塊”的排列，則會形成很多的放置方案volume，直觀的講，這些放置方案都為該啟發算法的一個解。生成“塊”的算法：本文保證“塊”盡量形成一個大的長方體，所以這里“塊”的生成包含兩種生成方式，分別為簡單生成“塊”算法與復合“塊”生成算法。簡單生成塊：我們把同種類型的箱子，以單一方向的形式（上文交代不同方向擺放貨箱按照不同種類箱子計算）排列成的“塊”稱作簡單“塊”。簡言之，該簡單“塊”是由多個貨箱組成，其形狀也要保證為一個大的長方體。用nx，ny，nz分別表示大長方體的長、寬、高分別由幾個貨箱組成。如3-1圖所示，簡單“塊”的表現形式。圖3-1塊形成圖生成復合“塊”復合“塊”是多種簡單塊組合而成的，從而包含多種貨箱。在實際情況中，“塊”大部分都是以復合“塊”的形式存在的。在形成復合“塊”的過程中，最值得注意的地方就是每個復合“塊”的內部包含的多種簡單“塊”的相對位置。這里本文通過圖片直觀的描述兩個簡單“塊”的相對擺放位置。其中包含三種相對擺放位置，分別按照坐標系的三個軸的方向來擺放，如3-2圖所示。圖3-2復合塊形成圖3.3空間合并啟發式算法（裝載過程）按上述操作之后，我們做好了裝載之前的準備，明確了裝載過程實際上是指：把“塊”序列裝載到剩余空間當中，完成放置動作，直至剩余空間棧為空（即沒有剩余空間）。接下來我們進行的就是裝載的過程，該過程我們用到的是一種構造型啟發式算法。該算法可描述為：起初，剩余空間棧的剩余空間為整個車廂，我們的宗旨是將“塊”裝入與之匹配的剩余空間，我們分割出一個剩余空間時，有與之匹配的“塊”可以放置，則成該“塊”為可行塊。隨著可行“塊”不斷的加入車廂，剩余空間棧中的剩余空間不斷減小，每每減小一次剩余空間，該算法規定要重新劃分一下剩余空間棧中的剩余空間，由于“塊”的大小不一，極容易出現沒有被“塊”填充的剩余空間，此時依舊將這部分小的剩余空間回歸到剩余空間棧，盡量與其他空間進行合并再劃分。而我們的劃分剩余空間棧的原則為：優先劃分出體積最大的剩余空間。若最后剩余的為填充區域，沒有找到合適的“塊”來進行填充，我們便舍去該空間，這也是不可避免的實際情況。本文的構造型啟發式算法的空間分割是為了使“塊”找到剩余空間的。上文也有提到，當我們實際設計編寫算法時，裝在過程中依舊會存在很多零零散散的未填充位置，所以我們要運用空間合并原則，對這些剩余空間進行合并，來提高車廂空間的利用率。空間合并可以更加充分的利用裝箱空間。下面我們對剩余空間的合并規則進行描述。如圖3-3所示：圖3圖3-3空間合并圖根據很多的研究文獻（第二章有詳細描述），面對裝箱問題，研究人員對于一個貨物裝入集裝箱時，通常把剩余空間分割為三個子空間，本文也采用該思想。當一個可行“塊”裝入剩余空間時，剩余空間將被分為前，右，上三個子空間，分割思想源于這三個方向分別沿x軸，y軸，z軸的方向，在進行計算時，直觀且便捷。而我們這里著重提到的一點是：z軸方向的空間，即上空間。上空間放置下一個“塊”的時候，由于貨物不能懸空擺放，所以該“塊”的擺放卻決于上一個可行“塊”的上表面，可擺放區域上文已提到，用?x與?y來表示該長方形的長與寬。如3-4圖所示。圖3-4空間分割圖我們劃分好區域之后，對剩余空間棧進行重新劃分，其優先原則是先劃分出體積最大的剩余空間。衡量一個體積的大小有很多種方法。為詳細闡述本文搜索體積最大的空間，本文在這里提出一個概念：變動空間。如圖3-5所示可變動空間的位置。可變動空間可變動空間圖3-5可變動空間位置圖該空間是一個長方體，該位置與上圖的前，右，上空間不同，該位置不受以擺放貨物的束縛，我們稱它為可變動空間。為實現劃分出的剩余空間體積盡量大，我們以剩余空間中x軸，y軸的長度，記為mx，my。找出mx，my最長的部分，與此同時映射出來的z軸方向的高組成的空間與可變動空間進行組合，形成體積最大的剩余空間。通過上述描述，我們可以總結為一個剩余空間，在裝載的過程中有兩種狀態，一是該空間有可行“塊”的放置，二是該空間無可行“塊”放置。當有可行“塊”放置時，則意味著該可行“塊”滿足實現規定的一切約束條件，但避免不了存在有剩余空間，此時將剩余空間歸回剩余空間棧，再將剩余空間棧中的剩余空間重新分割，搜索新的與之相匹配的可行“塊”。以此類推，直到最后沒有與之相配的“塊”，則舍棄該剩余空間，進而使得裝載率最大。綜上所述，裝載“塊”到剩余空間中是十分重要的環節，下面本文有一個流程圖來描述裝載的基本流程，如圖3-6所示：圖3-6流程圖3.4本章小結本章介紹了對于配送車裝箱方案構建模型的方法。描述了本文運用的啟發式算法，并對其涉及到的名詞概念做出解釋，為下文模擬退火算法擇優，生成初始方案。

配送車輛三維裝箱算法實現通過對第三章的描述，我們確定了貨箱裝載過程的啟發式算法。顯而易見，等待我們解決的問題就是如何將上述思想用計算機語言來實現。在本章當中，我們將介紹如何編碼“塊”，如何實現可行“塊”放置到剩余空間中的編碼過程。最后我們通過混合模擬退火算法，搜索出裝箱方案的最優解。“塊”是該算法中最小的單位，這里我們先介紹對于“塊”，我們編碼的方法如下：在上述編碼序列中，i為車廂的序號；j為貨物的種類號；n為該“塊”內部貨物的個數；x,y,z為貨物放置的初始坐標；l,w,h為貨物的長、寬、高。當貨物的初始坐標不在遠原點是，剩余空間的長度表示為：mx；剩余空間寬度表示為：my；所以本文貨物的初始空間表示為：θ4.1裝載算法的步驟算法的具體步驟如下：步驟1：輸入車廂和貨物的基本數據（車廂和貨物的長、寬、高等）。步驟2：對“塊”的放置位置進行編碼其中，i為車廂的序號；j為“塊”表的序號；n為每個“塊“內貨物的個數；x,y,z為貨物放置的等價位置，即初始坐標。步驟3：事先排列好的“塊”列表進行評估，選擇可以滿足St.0≤li≤步驟4：當“塊”滿足約束條件時，對該可行“塊”進行步驟二進行編碼。根據本文第三章描述的從剩余空間棧分割出剩余空間，通過放置原則進行可行“塊”與剩余空間的裝載。步驟5：記錄裝載“塊”的總體積，保證不超過車廂的容積。步驟6：返回步驟3，實現下一個可行“塊”與剩余空間的放置，直至車廂的裝載空間最大。步驟7：當貨物無法再裝進剩余空間，則進行對下一個車廂的裝載。步驟8：得裝載出數據結果。簡單用流程圖4-1總結如下：圖4-1流程圖4.2混合模擬退火算法本文第二章已經對模擬退火算法有了粗略的描述，這里進一步對該算法的思想與步驟進行解釋。模擬退火算法的本質和爬山算法一致，在這里我們先介紹爬山算法：爬山算法運用了啟發式算法的思想，但同時是一種智能算法。它是通過局部搜索的方式對可行解展開搜索。該算法也是貪心搜索算法的一種，通過局部擇優的思想，在當前解附近的鄰域空間上搜素并進行比較，選出在該域中的最優解。很顯然，運用該算法，我們得到的是一個局部最優解，這也是該算法一個最大的缺點，得到的最優解太具有局部性。該算法沒有對全局進行一個普遍的搜索，得到的解不一定是全局的最優解。這里本文引用一個圖來形象的描述，如圖4-2所示，假設當前搜索到最優解為A點，爬山算法會搜索該解附近的解空間，即可以搜索到B點，此時很明顯B點為該局部的最優解，但很顯然，D點可能是全局的最優解。所以該算法只是一個簡單的貪心法，搜索很具有局限性。BACEDBACED圖4-2數據圖模擬退火算法和爬山算法的思想很相像，也是一種貪心搜索算法，與其不同的是，它是屬于全局優化算法，在搜索可行解時具有一定的隨機性。模擬退火算法是在全局中隨機搜索可行解，每一個可行解在自己局部的位置有自己的鄰域，此時每一個局部解都運用了爬山算法的思想，對鄰域的解進行擇優，選出局部最優解。然而這個隨機機制在搜索這些局部可行解時起到了作用，它對優質的解會無條件接受，對劣質的解也不是完全拒絕，而是以一定概率去接受（本文在第二章有詳細敘述怎樣以一定概率接受較為不好的解），從而使得最終結果更具可靠性，得到全局最優解。同樣以4-2圖為例，模擬退火算法會在已經搜索到B點的最優解的情況下，繼續對鄰域探索，以一定的概率去搜索C點，此時就會由于C點的右側有優于C點的解，而會逐步搜索到D附近的點，以此類推，最終會探尋到E點，得到優于B的點，跳出B的鄰域，進而搜索到全局最優解。模擬退火算法是模擬退火過程所設計出來的算法，其思路描述為：設置初始溫度并且創造一個隨機的初始解。循環，直到滿足條件停止。一般系統會充分冷卻，或找到一個足夠好的解。對當前解進行一些運算，得到相鄰空間解中的一個新解。比較新解，看是否換成相鄰的解。降低溫度，繼續循環。通過上述描述，不難看出模擬退火算法這類隨機搜索算法的優勢，它可以跳出局部最優解的陷阱，找到全局最優解，因此本文選用該方法對裝載方案進行擇優。混合模擬退火算法：綜上所述，本文所采用的算法大體分三個階段。第一個階段，我們對貨物與車廂空間進行處理，對貨物，我們進行生成“塊”處理，進而生成“塊”表；對車廂，我們將其視為剩余空間棧中的剩余空間。第二個階段，我們通過裝載的啟發式算法，使可行“塊”與剩余空間進行放置處理，形成一系列放置方案。第三階段，我們運用模擬退火算法，對得到的裝載方案進行擇優，選擇最終的最優解。下面本文開始介紹其思路與步驟。對這些裝載方案的擇優，我們使用模擬退火算法的設計思路是：已知我們已經存在n個可行的裝載方案。每一個裝載方案都是一個可裝載的序列L。其鄰域包含很多滿足條件的裝載序列L’。最終選擇出最優解。綜上所述，對混合模擬算法的算法步驟進行總結，如下：步驟1：輸入裝載數據；步驟2：設置模擬退火算法的參數；步驟3：根據生成“塊”的算法形成塊表，生成一系列裝載序列;步驟4：通過啟發式算法，得出一些列的裝載方案，即初始種群：L;步驟5：通過適度函數，找出L鄰域中的的適度值L’；步驟6：進行模擬退火算法，得到新一代種群，結果趨向于最優解所在的區域；步驟7：終止條件判斷，若不符合，跳回步驟6，若符合，得到最優解。算法流程圖4-3如下：圖4-3流程圖4.4本章小結本章介紹了如何編碼，進而實現構造型啟發式算法。并對生成的裝載方案通過模擬退火算法進行擇優，提出了采用啟發式算法混合模擬退火算法對配送車裝箱方案進行求解。

配送車輛三維裝箱模型算法的實例分析通過對珠海一家汽車制造公司S的調查與收集數據，本文對此進行實例分析。該公司需要為供應商配送十幾種不同的零部件。而本文的目標是對貨物裝箱方案的優化，提高車輛空間的利用率，使得每輛車在不超重的情況下盡可能多裝載貨物，從而減少了配送車的數量，無論是在物流成本還是配送效率上都可以得到有效的提高。也符合了工業工程的思想，減少成本，提高效率，為公司企業帶來更大的效益。該汽車制造公司S的現狀是：該公司以明確列出需要采購的汽車零部件，并也聯系好m家供貨商，其地理位置與運輸路線均已確定。而本文對路線優化不作研究，因此假定公司運輸路線不具明顯問題，只需對車廂裝箱率進行研究。5.1S公司配送概述該汽車制造公司S在這次生產過程中，需要采購大批量的汽車零部件。根據本公司的自身質量需求，選擇了多家供應商進行采購，其供應商多達幾十家。下面是對其中的一些供應商進行介紹，并標明S公司在其供應商采購的零部件，如5-1表所示：表格5-1供應商供貨表供應商零件類別湖北通達、珠海洪湖、上海賢華；消聲器、排氣管；馬勒、曼胡默爾；進氣歧管，空氣濾清系統；鄭州泰新、上海泰嘩；座椅日立、浙江德宏；發電機浙江亨達，開封中達；保險杠法拉達散熱器上海特殊陶業火花塞開封中達、江蘇新泉；車門內飾板5.2S公司的實際裝載過程的數據分析由于該汽車制造公司S在這次采購中需要很大一批零部件，種類繁多，與此同時，該公司聯系的供應商公司規模大小不一，因此與每家供應商采購的數量十分懸殊。本文決定選用三家采購數量多的公司作為代表，來對本文建立的裝箱方案模型進行實例驗證。本文選用珠海洪湖消聲器企業公司、上海特殊陶業有限公司、浙江亨達集團有限公司三家公司，對其進行數據調查，運用本文論述的算法對這三家公司裝載過程進行優化。下面我們對珠海洪湖消聲器企業公司、上海特殊陶業有限公司、浙江亨達集團有限公司三家公司供應的零部件種類以及每個貨箱的尺寸大小進行介紹，如5-2表所示：表5-2裝載數據表供應商名稱零部件裝箱后的箱體尺寸序號長度（mm）寬度（mm）高度（mm）珠海洪湖消聲器企業公司（甲）1500400200260040020035004003004140010001000522001200170061800800300上海特殊陶業有限公司（乙）1400350400222001500150036004005004600400300580060040064003503007750400400浙江亨達集團有限公司（丙）118001500150028006004003200012001600416001200140056004004006600400300740035040088006006005.3S公司車輛裝箱優化本文所選擇的供應商珠海洪湖消聲器企業公司（甲）、上海特殊陶業有限公司（乙）、浙江亨達集團有限公司（丙），經過數據的記錄調查，我們獲得了以上數據。根據我們對配送現場進一步調查，與對S公司需求量的評估計算，我們得知針對每一個供應商，該公司需要采購每一種零部件的數量，以及供應商選用的配送車的型號。已知這三個供應商使用的配送車均為一種車型，通過測量與對該車型的查詢，我們得知該類配送車車廂的大小尺寸：長：8.2m；寬：2.42m；高：2.39m。其限重為8噸。現將調研獲得的珠海洪湖消聲器企業公司（甲）、上海特殊陶業有限公司（乙）、浙江亨達集團有限公司（丙）三家公司的配送數據分別進行統計，匯總出如下面的表格5-3到表格5-5：表5-3裝載數據表待裝箱體序號長度（mm）寬度（mm）高度（mm）數量（個）配送車車廂數據150040020013長8200mm寬2420mm高2390mm260040020010350040030012414001000100085220012001700126180080030010表5-4裝載數據表待裝箱體序號長度（mm）寬度（mm）高度（mm）數量（個）配送車車廂數據140035040012長8200mm寬2420mm高2390mm222001500150083600400500124600400300858006004001264003503001077504004005表5-5裝載數據表待裝箱體序號長度（mm）寬度（mm）高度（mm）數量（個）配送車車廂數據11800150015008長8200mm寬2420mm高2390mm28006004001232000120016005416001200140085600400400126600400300107400350400888006006005通過對上述三家公司配送數據的介紹，顯然浙江亨達集團有限公司（丙）的貨物種類以及數量較多，為了驗證本文所論述的算法具有說服力，我們選用浙江亨達集團有限公司（丙）的調查數據，對其裝箱方案的優化過程以及得到的結果進行詳細的描述。首先，將所有貨物數據輸入計算機，通過生成“塊”的算法形成“塊”表，實現“塊”與剩余空間的放置，為啟發式算法做好準備。其次，運行啟發式算法的代碼文件，形成一系列的放置方案。其放置方案是該裝箱問題的可行解。最后，通過混合模擬退火算法，對所有可行解進行擇優，得到最終的最優方案。通過計算機的運行，我們得到如下計算結果，如5-6表所示：表5-6實驗結果配送車序號容積利用率（%）貨物序號數量貨物裝載的初始坐標XYZ183.396100.000.000.00421.350.000.00422.980.000.00424.050.000.00425.870.000.00550.000.450.00550.001.050.00511.350.001.80783.850.001,80245.870.001.80116.700.000.00118.100.000.00272.18240.000.000.00243.240.000.00844.480.000.00815.560.000.00316.500.500.00376.77310.000.000.00311.600.000.00113.000.000.00114.400.000.00115.800.000.00479.36310.000.000.00311.600.000.00113.000.000.00114.400.000.00115.800.000.00通過上表，可以看出，該公司需要派送4輛配送車，以及每輛車的空間利用率如表所示，經本文模型和算法的求解，4個配送車輛的容積利用率均高于70%計算結果較為理想。圖5-1空間利用率統計圖綜上所述，在這里我們對該實驗結果做出一個總結：我們以1號配送車裝載結果為例進行描述。1號車廂中待裝載的貨物有6種，我們這里描述為6類不同大小尺寸的貨物。裝載的第一類貨物是6號貨物，該貨物的長、寬、高的尺寸分別為600mm，400mm，300mm。一共裝載10個。放置方式：一共擺放5排，每排2個。裝載的第二類貨物是4號貨物，該貨物的長、寬、高的尺寸分別為1600mm，1200mm，1400mm。一共裝載8個。放置方式：一共擺放4排，每排2個。裝載的第三類貨物是5號貨物，該貨物的長、寬、高的尺寸分別為600mm，400mm，400mm。一共裝載11個。裝載的第四類貨物是7號貨物，該貨物的長、寬、高的尺寸分別為400mm，350mm，400mm。一共裝載8個。裝載的第五類貨物是2號貨物，該貨物的長、寬、高的尺寸分別為800mm，600mm，400mm。一共裝載4個。裝載的第六類貨物是1號貨物，該貨物的長、寬、高的尺寸分別為1800mm，1500mm，1500mm。一共裝載2個。通過計算得出此時該車箱的空間利用率為83.39%，以此類推，其余三個配送車車廂的裝載情況也以此方式進行描述。5.4本章小結本章節通過對汽車制造公司S的部分裝載數據的記錄，運用本文描述的算法，對其裝箱方案進行了優化，并得出了較為滿意的解，證明了該算法的有效性與合理性。

總結與展望6.1總結本文介紹了裝箱問題國內外研究的過程與現狀，也指明了其方法的優缺點，分析了裝箱問題在求解時可能面對的問題。針對此問題，本文系統且詳細的分析了裝箱問題的目標函數以及約束條件等等，從而進行了數學化的建模。本文針對弱異類問題，運用了空間合并啟發式算法混合模擬退火算法對配送車裝載問題進行求解。本文完成了幾方面工作：對裝箱問題的約束條件具體化：方向的約束，容積的約束，擺放方式的約束等等。并建立了目標函數，從而將裝箱問題數學化。介紹了配送車裝箱過程涉及到的概念，分析了其問題所在。基于本文提出的算法，在裝載過程中，初始化了裝載信息，設置了模擬退火的參數，同時對裝箱過程貨物的位置進行編碼。在算法運行的過程中，運用了空間分割法把貨物周圍分割了三個區域：上方向空間，右方向空間以及前方向空間。根據目標函數生成初始種群自然的將空間合并啟發式算法與模擬退火算法鏈接。進而形成了對裝箱問題的求解算法，對實際應用到達最優解的效果。基于對珠海S公司的概述與分析，符合本文針對弱異類問題的求解，據實際數據進行調查，針對該公司的一個供貨商的需求，本文用該算法進行實驗，用得出的結論來證明該算法的有效性，其過程運用MATLAB軟件進行實現，為本文結論提出有利證據。6.2展望通過本次對配送車裝箱方案的研究，我們不難發現在裝箱問題方面，還有很多需要改進的地方。隨著經濟的全球化，物流行業的逐漸崛起，該問題也將成為人們的一大焦點問題。與此同時，我們的社會逐漸智能化，我相信還會出現更多的智能優化算法去解決問題。現在的市場，很多工藝會出現個人化的現象，私人制品也會越來越大，那么在運輸該種強異類的裝箱問題也會愈顯突出，而現在研究表明對于強異類的研究方案并不多見，我們的未來也要對該類問題進行著重的研究，為裝箱問題的解決進行完善與優化。

參考文獻張德富，彭煜,張麗麗求解三維裝箱問題的多層啟發式搜索算法[D].