發(fā)布時(shí)間：2018-01-07 02:01

  本文關(guān)鍵詞：組合裝箱問題模型與算法研究　出處：《上海交通大學(xué)》2015年碩士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 混合整數(shù)規(guī)劃模型 組合裝箱問題 分枝定界 貪婪算法

【摘要】：本文研究近年新提出的汽車物流組合裝箱問題。該問題在國內(nèi)汽車物流領(lǐng)域?qū)嶋H存在,并且伴隨著中國汽車工業(yè)的迅速發(fā)展,凸顯出來,對物流運(yùn)輸公司造成了很大的困擾。因此,針對性的解決該問題具有非常重要的現(xiàn)實(shí)意義。通過研究該問題,提出有效的解決方案,并應(yīng)用到實(shí)踐中,對于汽車物流來說,能夠非常有效的降低成本并且提高效率。首先,本文在研究其他經(jīng)典裝箱問題的基礎(chǔ)上,將組合裝箱調(diào)研與實(shí)踐中遇到的目標(biāo)需求與操作要求進(jìn)行分析與整理,將其轉(zhuǎn)化為問題的目標(biāo)與約束,形成完整的問題描述,并且建立混合整數(shù)規(guī)劃模型。其次,為了快速、有效的求解該問題模型,本文設(shè)計(jì)了兩種算法,一種是基于分枝定界思想的精確求解算法,針對本文所研究的問題以及模型,分別給出了分枝定界算法的分枝策略、上界、下界、搜索模式和支配規(guī)則,并且給出了詳細(xì)的算法流程。另一種算法則是基于貪婪思想的啟發(fā)式算法。本文詳盡介紹了貪婪算法的基本思想以及算法流程。最后,通過數(shù)值實(shí)驗(yàn)驗(yàn)證所提出模型與算法的有效性。本文使用ILOG CPLEX優(yōu)化工具和設(shè)計(jì)的算法對模型進(jìn)行求解,進(jìn)行數(shù)值實(shí)驗(yàn),通過比較一些指標(biāo),分析實(shí)驗(yàn)結(jié)果來對模型的有效性以及設(shè)計(jì)的算法的高效性進(jìn)行驗(yàn)證。同時(shí),對組合裝箱調(diào)度的實(shí)際數(shù)據(jù)進(jìn)行實(shí)例驗(yàn)證,通過與實(shí)際人工調(diào)度的結(jié)果比較待裝載商品車完成數(shù)量以及高緊急程度的商品車的完成比例,證明建立的模型以及算法較人工調(diào)度的優(yōu)勢,從而驗(yàn)證了實(shí)際應(yīng)用價(jià)值。本文通過構(gòu)建數(shù)學(xué)模型、設(shè)計(jì)有效算法,為組合裝箱問題提供了高效的、智能化的解決方案。通過數(shù)值實(shí)驗(yàn)表明,本文研究成果可直接應(yīng)用于實(shí)踐活動,對組合優(yōu)化的理論與方法的發(fā)展具有一定的推動作用。
[Abstract]:This paper studies the combined packing problem of automobile logistics in recent years. The new problems in the domestic auto logistics field, and with the rapid development of automobile industry, Chinese emerged, caused great distress to the logistics company. Therefore, to solve this problem has very important practical significance. Through the study of the problem and propose effective solutions, and applied to practice, for the automotive logistics, can effectively reduce the cost and improve the efficiency. Firstly, based on the study of other classical bin packing problems, the combination of demand and operation encountered packing investigation and practice requirements of collation and analysis, will be transformed into objectives and constraints, the formation of a complete description, and a mixed integer programming model is built. Secondly, in order to quickly and effectively solve the problem of the model. Two kinds of algorithm design, an exact solution algorithm is based on the idea of branch and bound, in view of the problems studied in this paper and the model of the branch and bound algorithm are given branching strategy, upper bound, lower bound, the search mode and control rules, and gives the detailed algorithm process. Another algorithm is a greedy heuristic algorithm based on the idea. This paper introduces the basic idea and algorithm of greedy algorithm. Finally, the effectiveness of the proposed model and algorithm is verified through numerical experiments. This paper uses ILOG CPLEX optimization tools and design the algorithm to solve the model by numerical experiments, through the comparison of some indicators, analysis of the experimental results to the validity of the model the design and efficiency of the proposed algorithm is verified. At the same time, the actual data to verify the combination of scheduling cases, compared with the actual results than manual scheduling Is to be loaded goods vehicles complete volume and high degree of completion of the emergency vehicle proportion, the established model and algorithm with artificial scheduling advantage, which proves the practical value. This paper constructs the mathematical model, the design of effective algorithm, provides a combination of packing problem efficiently, intelligent solution by numerical. Experiments show that the results of this study can be directly applied to practice, has a certain role in promoting the development of the theory and method of combinatorial optimization.

【學(xué)位授予單位】：上海交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：F426.471;F252

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 陸一江,邢文訓(xùn);在線A形裝箱問題:模型及算法研究[J];清華大學(xué)學(xué)報(bào)(自然科學(xué)版);2001年12期

2 楊殿生;求解裝箱問題的一種變長度染色體遺傳算法[J];長春工程學(xué)院學(xué)報(bào)(自然科學(xué)版);2004年02期

3 徐麗麗;季忠;夏繼梅;;同規(guī)格貨物裝箱問題的優(yōu)化計(jì)算[J];山東大學(xué)學(xué)報(bào)(工學(xué)版);2008年03期

4 肖人岳，謝樂軍，昌志華，，朱鋒峰;鎖具裝箱問題評述[J];華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版);1995年09期

5 方平,李娟;求解裝箱問題的遺傳算法[J];南昌航空工業(yè)學(xué)院學(xué)報(bào);1998年02期

6 王秀清;邱洪澤;徐法升;;求解裝箱問題的一種混合分組遺傳算法[J];濟(jì)南大學(xué)學(xué)報(bào)(自然科學(xué)版);2010年02期

7 劉春霞,于洪霞;有色裝箱問題的一種新的近似算法[J];佳木斯大學(xué)學(xué)報(bào)(自然科學(xué)版);2005年04期

8 曹大勇;楊梅;科托夫·弗拉基米爾·米哈伊拉維奇;劉潤濤;;二維一刀切裝箱問題的兩階段啟發(fā)式算法[J];計(jì)算機(jī)集成制造系統(tǒng);2012年09期

9 程浩;劉心報(bào);劉林;經(jīng)懷明;;一種用遺傳算法求解裝箱問題的新編碼方法[J];合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年02期

10 吳令一;劉青峰;盧家廣;;基于二分圖的改進(jìn)裝箱算法[J];硅谷;2009年17期

相關(guān)會議論文 前4條

1 張國川;;組合優(yōu)化算法研究-從裝箱問題說起[A];2006年中國運(yùn)籌學(xué)會數(shù)學(xué)規(guī)劃分會代表會議暨第六屆學(xué)術(shù)會議論文集[C];2006年

2 陳鋒;邢文訓(xùn);;在線塔狀裝箱問題(英文)[A];中國運(yùn)籌學(xué)會第六屆學(xué)術(shù)交流會論文集（上卷）[C];2000年

3 ;Voronoi Diagram Approximate the Extreme Packing and Its Applications[A];中國運(yùn)籌學(xué)會第六屆學(xué)術(shù)交流會論文集（上卷）[C];2000年

4 董杰方;張漢欣;李安平;;冷卷入庫的數(shù)學(xué)模型及算法[A];2001中國鋼鐵年會論文集（下卷）[C];2001年

相關(guān)博士學(xué)位論文 前4條

1 王俊嶺;矩形裝箱問題的協(xié)同決策模型[D];蘭州大學(xué);2013年

2 于洪霞;二維裝箱問題的非線性優(yōu)化方法[D];大連理工大學(xué);2006年

3 余國松;與裝箱相關(guān)的幾類問題[D];浙江大學(xué);2009年

4 石永強(qiáng);若干批處理機(jī)排序與裝箱問題的算法研究[D];浙江大學(xué);2005年

相關(guān)碩士學(xué)位論文 前10條

1 江瀑;組合裝箱問題模型與算法研究[D];上海交通大學(xué);2015年

2 邱朝陽;考慮重量約束的集裝箱裝箱問題[D];華南理工大學(xué);2010年

3 王鐘;染色裝箱問題的相關(guān)研究[D];浙江大學(xué);2007年

4 劉林浩;關(guān)于脆度裝箱問題的若干研究[D];長沙理工大學(xué);2013年

5 徐妮;具有不同價(jià)格的裝箱問題[D];云南大學(xué);2015年

6 王秀清;基于混合分組遺傳算法的裝箱問題研究[D];山東大學(xué);2010年

7 劉春霞;關(guān)于裝箱問題的若干研究[D];大連理工大學(xué);2006年

8 徐霞;具有不同容量的裝箱問題[D];云南大學(xué);2015年

9 金潔;二維矩形裝箱問題及其算法設(shè)計(jì)[D];云南大學(xué);2015年

10 彭煜;求解三維裝箱問題的啟發(fā)式分層搜索算法[D];廈門大學(xué);2009年

本文編號：1390481