簡易檢索 / 詳目顯示

回結果列表
研究生： 黃雅雯
Ya-wen Huang
論文名稱： 考慮批量結合問題在基因演算法下使路徑最小化
Order batching heuristic based on genetic algorithms in warehouse minimizing travel distance
指導教授： 潘昭賢
Chao-hsiew Pan
口試委員: 許總欣
Tsung-shin Hsu
何文宗
Wen-tsung Ho
學位類別： 碩士
Master
系所名稱： 管理學院 - 工業管理系
Department of Industrial Management
論文出版年： 2009
畢業學年度： 97
語文別： 英文
論文頁數： 46
中文關鍵詞： 批量揀貨 、倉儲 、基因演算法
外文關鍵詞： Order batching, Warehouses, Genetic algorithms
相關次數： 點閱：284  下載：6 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 在有效地倉儲管理中，批量揀貨是個值得被探討的問題。在批量揀貨中，訂單盡可能地被合併使檢貨人員可以依被合併的訂單在同一個時間來做批量揀貨。這個批量揀貨的問題已經被認為是一個NP-hard，而且在可以等待的時間內很難在大量訂單中找到最佳解；在此文章中我們主要是針對大量的訂單做批量揀貨。
    在本研究中，採用三個常用的路徑分析法，traversal、return和largest gap，將這三個路徑加到所要研究的問題中。本研究所建立的數學模式就是依largest gap而發展出來的，而另外兩個路徑—traversal 和 return的數學模式則是沿用Hwang and Kim’s (2005)。透過這些數學模式，採用近年來常被採用的的基因演算法來找出最短的行走距離。為了得知基因演算法在批量揀貨中是否為一個有效率的方法，本研究將基因演算法與群組分析做比較。從小批量到大批量的訂單例子中，可以得知利用基因演算法可以使大批量的訂單有效地被結合並且找到最小的行走距離。

    Order batching is a key factor in managing a warehouse efficiently. In order batching, orders are combined as much as possible so that the order picker can pick a set of combined orders at the same time. This study deals with the order batching problem in large-sized. The order batching problem is recognized to be NP-hard, and it is extremely difficult to obtain optimal solutions for large-sized order batching problem within a tolerable computation time.
    Generally, there are three significant routing policies decisions that determine the efficiency of order batching, traversal policy, return policy and largest gap. This study develops an order batching mathematical model based on genetic algorithms (GAs) with largest gap. Beside, we quote two mathematical models with traversal policy and return policy from Hwang and Kim (2005) to develop the genetic algorithms. The proposed genetic algorithms (GAs) that directly minimizes the total travel distance. To show the validity of the genetic algorithms, comparing with a cluster analysis (CA) in terms of the total distance of batches grouped. The potential of applying GAs for solving small-sized to large-sized order batching problems is also investigated by using several examples. The results show that orders are combined effectively and find the minimum distance.

    中文摘要 I ABSTRACT II ACKNOWLEDGEMENTS III CONTENTS IV TABLE INDEX VI FIGURE INDEX VII CHAPTER 1 Introduction 8 CHAPTER 2 Literature review 11 2.1 Order picking 11 2.2 Order batching 12 2.2.1 Seed Algorithms 13 2.2.2 Savings Algorithms 14 2.3 Routing 14 2.4 Basics of genetic algorithms 17 CHAPTER 3 The proposed order batching approach 20 3.1 The general approach of GAs 20 3.1.1 Encoding 20 3.1.2 Initial solution 20 3.1.3 Fitness function 21 3.1.4 Reproduction (selection) mechanism 21 3.1.5 Crossover 22 3.1.6 Mutation mechanism 24 3.1.7 Stop criteria 24 3.1.8 Control parameter 25 3.2 The GA-based batching method 25 3.2.1 Encoding of solution 25 3.2.2 Produce initial solution 26 3.2.3 Define fitness function 26 3.2.4 Reproduction (selection) mechanism 26 3.2.5 Crossover mechanism 26 3.2.6 Mutation mechanism 28 3.3 The Notation of batching is used in the paper: 28 3.4 Development of mathematical batching model 29 3.4.1 The order batching model of minimizing the total travel distance 29 3.4.2 The order batching model with routing 31 CHAPTER 4 Computation experiments 34 CHAPTER 5 Conclusion 39 REFERENCES 41

    Bozer, Y.A. & Kile, J.W. (2007). Order batching in walk-and-pick order picking systems. International Journal of Production Research, 46:7, 1887–1909.
    Coyle, J.J., E.J. Bardi & C.J. Langley. (1996). The Management of Business Logistics (West: St. Paul, MN).
    Clarke, G. & Wright, W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12, 568–581.
    Hsu, C.M., Chen, K.Y., Chen, M.C. (2005). Batching orders in warehouses by minimizing travel distance with genetic algorithms. Computers in Industry, 56 (2), 169–178.
    De Koster, R., Van der Poort, E.S., Wolters, M., (1999). Efficient order batching methods in warehouses. International Journal of Production Research, 37 (7), 1479–1504.
    De Koster, R., Neuteboom, A.J. (2001). The logistics of Supermarket Chains. Elsevier, Doetinchem.
    De Koster, R. (2004). How to assess a warehouse operation in a single tour. Report, RSM Erasmus University, the Netherlands.
    De Koster, Tho Le-Duc, and Keefs Jan Roodbergen (2006). Design and control of warehouse order picking: A literature review. European Journal of Operational Research, 182, 481–501.
    De Koster, R., T. Le-Duc & K.J. Roodbergen (2007). Design and control of warehouse order picking: A literature review. European Journal of Operational Research, 182, 481-501.
    Elsayed, E.A. (1981). Algorithms for optimal material handling in automatic warehousing systems. International Journal of Production Research, 19 (5), 525–535.
    Elsayed, E.A., Stern, R.G. (1983). Computerized algorithms for order processing in automated warehousing systems. International Journal of Production Research, 21 (4), 579-586.
    Elsayed, E.A., Unal, O.I (1989). Order batching algorithms and travel-time estimation for automated storage/retrieval systems. International Journal of Production Research, 31 (3), 727-738.
    Hwang , H. & Lee, M.K. (1988). Order batching algorithms for a man-on-board automated storage and retrieval system. Engineering Costs and Production Economics, 13, 258–294.
    Hwang , H., Beak, W., Lee, M. (1988). Cluster algorithms for order picking in an automated storage and retrieval system. International Journal of Production Research, 26, 189–204.
    Hwang, H. & Kim, D.G.. (2005). Order-batching heuristics based on cluster analysis in a low-level picker-to-part warehousing system. International Journal of Production Research, 43:17, 3657-3670.
    Hall , R.W. (1993). Distance approximation for routing manual pickers in a warehouse. IIE Transactions, 25, 77-87.
    Ho, Y. –C and Tseng Y. –Y. (2006). A study on order-batching methods of order-picking in a distribution centre with two cross-aisle. International Journal of Production Research, 44:17, 3391–3417.
    Gibson, D.R. & Sharp, G.P. (1992). Order batching procedures. European Journal of Operational Research, 58 (1), 57–67.
    Goetschalckx, M., Rattliff, D.H. (1988). Order picking in an aisle. IIE Transactions, 20, 531–562.
    Pan, C.H. & Liu, S.Y. (1995). A comparative study of order batching algorithms. Omega International Journal of Management Science, 23 (6), 691–700.
    Petersen, C.G.. (1997). An evaluation of order picking routing policies. International Journal of Production Research, 17 (11), 1098–1111.
    Rosenwein, M.B. (1994). An application of cluster analysis to the problem of locating items within a warehouse. IIE Transaction, 26 (1), 101–103.
    Rosenwein, M.B. (1996). A comparison of heuristics for the problem of batching orders for warehouse selection. International Journal of Production Research, 34 (7), 657–664.
    Ruben, R.A. & Jacobs, F.R. (1999). Batch construction heuristics and storage assignment strategies for walk/ride and picking systems. Management Science, 45 (4), 575–596.
    Tompkins J.A., J.A. White, Y.A. Bozer, E.H. Frazelle & J.M.A. Tanchoco (2003). Facilities Planning. New York: John Wiley.

    QR CODE