淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-2906201700131900
中文論文名稱 以遺傳演算法求解儲位指派問題
英文論文名稱 Solving the Storage assignment problem by Genetic Algorithm
校院名稱 淡江大學
系所名稱(中) 資訊管理學系碩士班
系所名稱(英) Department of Information Management
學年度 105
學期 2
出版年 106
研究生中文姓名 翁毓婍
研究生英文姓名 Yu-Chi Weng
學號 605630085
學位類別 碩士
語文別 中文
口試日期 2017-06-04
論文頁數 64頁
口試委員 指導教授-鄭啟斌
委員-鄭啟斌
委員-廖賀田
委員-壽大衛
中文關鍵字 遺傳演算法  倉儲管理  揀貨  儲位指派 
英文關鍵字 Genetic Algorithm  Warehouse Management  Picking  Storage Assignments 
學科別分類
中文摘要 揀貨作業是物流中心營運成本的主要組成之一,入庫時儲位指
派的適切性是提升揀貨效率的前提。良好的儲位指派同時也可縮短
入庫時間、提升儲位利用率以及改善庫存管理。本研究之目的為提
出一儲位指派方法以降低入庫作業成本並提升揀貨作業效率。儲位 指派問題可建構為二次指派問題(Quadratic assignment problem, QAP),亦為一 NP-Complete 問題,因此在求解大型問題有其困難
性。因此本研究制定一遺傳演算法來求解儲位指派問題,其目標是
最小化入庫移動距離並將同時揀貨機率高的品項存放至鄰近儲位,
以縮短未來揀貨時之移動距離。由於問題多目標的特性,本研究亦
設計挑選效率解的方式以獲得儲位指派決策。為了驗證本研究方法
之績效,我們以某物流中心作業資料為基礎,模擬在應用本研究方
法與現行作業的情況下,兩者之績效差異。
英文摘要 Picking operation is one of the major operating costs of a distribution center, and the proper assignment of storages to stocks is critical to the improvement of picking efficiency. Appropriate storage assignments can also shorten storing time, improve storage utilization, and facilitate inventory management. The purpose of this study is to propose a storage location assignment method to reduce the cost of storage operations and improve the efficiency of picking operations. The storage assignment problem can be modeled as a quadratic assignment problem(QAP), which also appertain to an NP-Complete problem, and hence creates difficulties in solving large scale problems. To fill this gap, this study develops a genetic algorithm to solve the problem with the objectives of minimizing the distance of moving and storing the stocks, and maximizing the chance of simultaneous picking of adjacent stocks to reduce the future possible picking movement distance. Considering the multi-objectives characteristics of the problem, this study devises a method to determine the final storage assignment from a set of Pareto solutions. Performance of the proposed approach is evaluated via a computer simulation based on historical orders of the distribution center, by comparing the results from the proposed approach and the current operations of the distribution center respectively.
論文目次 目錄
===================================
第一章 緒論1
1.1.研究背景與動機1
1.2.研究目的4
1.3.研究架構5
第二章 文獻探討7
2.1.倉儲佈置8
2.2.儲位規劃10
2.2.1.儲存策略10
2.2.2.儲存指派11
2.2.3.二次指派問題14
2.2.4.通用啟發式搜尋法15
2.3.遺傳演算法18
2.4.快速混亂遺傳演算法25
2.5.Dijkstra演算法32
第三章 研究方法與系統架構35
3.1.問題描述35
3.2.倉儲環境與研究限制36
3.3.演算法架構37
3.3.1.演算法的參數設定38
3.3.2.演算法的演算步驟43
第四章 模型建構與模擬分析47
4.1.模擬驗證相關設定47
4.2.最佳權重設定49
4.3.輪盤法與競爭法之比較54
4.4.待入庫量多寡對於複製法運算時間之比較56
4.5.出庫與入庫距離結果分析57
第五章 結論與建議60
5.1.研究特色及結論60
5.2.後續研究與建議61
第六章 參考文獻62

表目錄
===============================

表 2-1儲存策略類型10
表 2-2遺傳演算法之相關名詞解釋19
表 3-1 XOR運算例子41
表 4-1遺傳演算法個參數設定49
表 4-2 66組權重其各目標值及最佳值計算50
表 4-3 2017/1/13訂單明細及頻率58

圖目錄
====================================
圖 1-1巧固架示意圖3
圖 1-2 研究架構圖6
圖 2-1遺傳演算法流程示意圖24
圖 2-2快速混亂遺傳演算法之染色體編碼25
圖 2-3快速混亂遺傳演算法流程圖27
圖 2-4快速混亂遺傳演算法之染色體過度編碼28
圖 2-5快速混亂遺傳演算法之染色編碼不足29
圖 2-6快速混亂遺傳演算法之門檻選取29
圖 2-7快速混亂遺傳演算法之基因砌塊30
圖 2-8快速混亂遺傳演算法之切割與結合30
圖 2-9 3×3 的2D網格圖33
圖 3-1倉庫平面圖 37
圖 3-2演算法架構流程圖38
圖 3-3每個物料相對應的揀取機率示意圖40
圖 3-4相互異位45
圖 4-1 O1O3 Pareto Fontier 2D 52
圖 4-2 O1O2 Pareto Fontier 2D 53
圖 4-3 O2O3 Pareto Fontier 2D 53
圖 4-4 O1O2O3 Pareto Fontier 3D 54
圖 4-5 複製法之比較 55
圖 4-6 待入庫量多寡對於複製法運算時間之比較 56
圖 4-7 一季中出庫距離與入庫距離比較結果57
參考文獻 [1] Annealing, S., & Kirkpatrick, S. (1983). Gelatt; CD, Vecchi, MP: Optimization. Science, New Series, 220(4598), 671-680.
[2] Austin, S. (1990). An introduction to genetic algorithms. AI expert, 5(3), 48-53.
[3] Ben-Mahmud, Y. S. (1987). The effect of warehouse layout on order-picking efficiency, Oregon State University.
[4] Cheng, P. Y., & Liu, D. C. (2003). The Shortest Path Planning for Robot on a 3D Obstacle. In Proceedings of International Conference of the Automation.
[5] Caron, F., Marchet, G., & Perego, A. (2000). Layout design in manual picking systems: a simulation approach. Integrated Manufacturing Systems, 11(2), 94-104.
[6] Coyle, J. J., Bardi, E. J., & Langley, C. J. (1996). The management of business logistics (Vol. 6). St Paul, MN: West publishing company.
[7] Davis, L. (1985, July). Job shop scheduling with genetic algorithms. In Proceedings of an international conference on genetic algorithms and their applications (Vol. 140).
[8] Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische mathematik, 1(1), 269-271.
[9] Dorigo, M. (1992). Optimization, learning and natural algorithms. Ph. D. Thesis, Politecnico di Milano, Italy.
[10] Eberhart, R., & Kennedy, J. (1995, October). A new optimizer using particle swarm theory. In Micro Machine and Human Science, 1995. MHS'95., Proceedings of the Sixth International Symposium on (pp. 39-43). IEEE.
[11] Frangioni, A. (1996). Solving semidefinite quadratic problems within nonsmooth optimization algorithms. Computers & Operations Research, 23(11), 1099-1118.
[12] Frazele, E. A., & Sharp, G. P. (1989). Correlated assignment strategy can improve any order-picking operation. Industrial Engineering, 21(4), 33-37.
[13] Gary, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-completeness: WH Freeman and Company, New York.
[14] Glover, F. (1989). Tabu search—part I. ORSA Journal on computing, 1(3), 190-206.
[15] Goldberg, D. E., Deb, K., Kargupta, H., & Harik, G. R. (1993, June). RapidAccurate Optimization of Difficult Problems Using Fast Messy Genetic Algorithms. In ICGA (Vol. 5, pp. 56-64).
[16] Grefenstette, J. J. (1986). Optimization of control parameters for genetic algorithms. IEEE Transactions on systems, man, and cybernetics, 16(1), 122-128.
[17] Hausman, W. H., Schwarz, L. B., & Graves, S. C. (1976). Optimal storage assignment in automatic warehousing systems. Management science, 22(6), 629-638.
[18] Heskett, J. L. (1963). Cube-per-order index-a key to warehouse stock location. Transportation and distribution Management, 3(1), 27-31.
[19] Koopmans, T. C., & Beckmann, M. (1957). Assignment problems and the location of economic activities. Econometrica: journal of the Econometric Society, 53-76.
[20] Lawler, E. L. (1963). The quadratic assignment problem. Management science, 9(4), 586-599.
[21] Man, K. F., Tang, K. S., Kwong, S., Johnson, M., & Grimble, M. (1999). Genetic Algorithms: Concepts and Designs with Disk.
[22] Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953). Equation of state calculations by fast computing machines. The journal of chemical physics, 21(6), 1087-1092.
[23] Pardalos, P. M., & Wolkowicz, H. (Eds.). (1994). Quadratic Assignment and Related Problems: DIMACS Workshop, May 20-21, 1993 (Vol. 16). American Mathematical Soc...
[24] Petersen II, C. G., & Schmenner, R. W. (1999). An evaluation of routing and volume-based storage policies in an order picking operation. Decision Sciences, 30(2), 481..
[25] Roodbergen, K. J., & De Koster, R. (2001). Routing order pickers in a warehouse with a middle aisle. European Journal of Operational Research, 133(1), 32-43.
[26] Rosenwein, M. B. (1994). An application of cluster analysis to the problem of locating items within a warehouse. IIE transactions, 26(1), 101-103..
[27] Sahni, S., & Gonzalez, T. (1976). P-complete approximation problems. Journal of the ACM (JACM), 23(3), 555-565..
[28] Srinivas, M., & Patnaik, L. M. (1994). Genetic algorithms: A survey. computer, 27(6), 17-26..
[29] Tompkins, J. A., White, J. A., Bozer, Y. A., & Tanchoco, J. M. A. (2010). Facilities planning. John Wiley & Sons.
[30] Vaughan, T. S. (1999). The effect of warehouse cross aisles on order picking efficiency. International Journal of Production Research, 37(4), 881-897.
[31] Winston, W. L., & Goldberg, J. B. (2004). Operations research: applications and algorithms (Vol. 3). Boston: Duxbury press.
[32] Wilson, H. G. (1977). Order quantity, product popularity, and the location of stock in a warehouse. AIIE transactions, 9(3), 230-237.
[33] 王麗慧(1999),物流中心儲位指派與揀貨順序整合模式之研究,台灣科技大學管理技術研究所工業管理學程碩士論文。
[34] 吳恆睿(2000),中醫院揀藥儲位規劃之研究,逢甲大學工業工程所碩士論文。
[35] 林國傑(1997),物流中心品項儲位指派之研究,台灣工業技術學院管理技術研究所碩士論文。
[36] 孫海皎、董福慶(1995),物流中心儲位管理:經濟部商業自動化系列叢書。
[37] 張壯營(1998) ,塔布搜尋法在物流中心品項儲位指派問題之應用,台灣科技大學管理技術研究所工業管理學程碩士論文。
[38] 張明洲(2000),基因演算法在物流中心品項儲位指派問題之應用,台灣科技大學工業管理系碩士論文。
[39] 陳世興(2004),物流中心之儲位指派與揀貨問題研究,義守大學工業工程與管理學系碩士論文
[40] 陳品均、鄭璧瑩(2012),針對動態路徑規劃之D++演算法研究及其應用,國立交通大學機械工程系所博士論文。
[41] 陳建良、杜志挺、饒忻、王木坤、姜世川(1996),物流中心撿貨路徑之研究,中國工業工程學會八十五年年會論文集,448-454。
[42] 陳昭吉(2003),應用遺傳基因演算法於晶圓製造廠之施規佈置問題,元智大學工業工程與管理學系學位論文,1-76。
[43] 黃建霖(2009),物流中心揀貨系統之整合設計規劃,中華大學科技管理學系碩士論文。
[44] 資策會(2014),國內B2C網路商店經營及調查報告。
[45] 經濟部商業司(1995),物流中心作業系統。
[46] 蕭文綺(2003),不同訂單型態下揀貨環境配置對揀貨效率之影響,國立高雄第一科技大學運輸倉儲營運所碩士論文。
[47] 蘇木春、張孝德(1997),機器學習:類神經網路、模糊系統以及基因演算法則,全華科技圖書,民國八十八年。
[48] 鈴木震(1994),如何利用『EIQ法』來進行配送中心系統計劃,中華民國物流協會。
[49] 賴伊娟(2010),EIQ 與資料探勘應用於儲位規劃之探討,銘傳大學企業管理研究所碩士論文
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2017-07-03公開。
  • 同意授權瀏覽/列印電子全文服務,於2017-07-03起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2486 或 來信