题名

儲位指派問題之全域最佳化方法

并列篇名

A Global Optimization Approach for Storage Location Assignment Problems

DOI

10.29416/JMS.201801_25(1).0002

作者

蔡榮發(Jung-Fa Tsai)；彭磊義(Lei-Yi Peng)；林明華(Ming-Hua Lin)；陳俐穎(Li-Ying Chen)

关键词

儲位指派 ； 二次指派問題 ； 線性化技術 ； Storage Location Assignment ； Quadratic Assignment Problem ； Linearization

期刊名称

管理與系統

卷期/出版年月

25卷1期（2018 / 01 / 01）

页次

29 - 59

内容语文

繁體中文
中文摘要

儲位指派問題所探討的是在物流中心內，如何將貨品指派到適合的儲位放置，使得滿足所有訂單需求的總揀貨距離可以達到最小。本研究將儲位指派問題建構成一個二次指派問題，此類問題屬於NP-Hard問題，其複雜性高而不容易求得其全域最佳解。因此很多不同的啟發式演算法被開發出來快速地求解此問題，但這些啟發式方法都無法保證求解品質。本研究以Nyberg and Westerlund (2012)針對二次指派問題所提出線性化技術為基礎，加入特殊序列集合第一型之改良方法來減少模型中的二元變數，以提昇二次指派問題全域最佳解的求解效率。在實證分析中，本研究將所提出的方法用在求解物流中心儲位指派問題的真實案例，並和實務上常用的EIQ分析法做比較。在兩種不同揀貨路徑下，分析結果顯示所提出的方法皆可以達到較小的總揀貨距離。對物流中心而言，揀貨程序是最勞力密集及花費成本的運作，透過最佳的儲位指派來降低總揀貨距離，可藉由改善揀貨作業的效率來增進物流中心的運作績效。
英文摘要

The storage location assignment problem focuses on appropriately locating the stock items in storage locations to minimize the total travel distance in a distribution center for fulfilling customer demand orders. This study formulates the storage location assignment problem as a quadratic assignment problem that belongs to NP-hard problems and is not easy to be globally solved due to the high complexity. Therefore, a large number of different heuristic approaches have been developed to quickly solve this kind of problems. But those approaches cannot guarantee the quality of the solution. This study bases on the linearization technique presented by Nyberg and Westerlund (2012) for solving quadratic assignment problems, and integrates the improved model for special ordered set of type 1 to reduce the number of binary variables for enhancing computational efficiency. In the empirical analysis, the proposed method is used to solve the real case of storage location assignment problem and compare the results with the commonly used EIQ analysis method. Under two different picking paths, the proposed method results in a shorter total travel distance than the EIQ analysis method. For almost every distribution center, order picking processes are the most labor-intensive and costly activity. Through an optimal storage location assignment to decrease the total travel distance, the operation performance of a distribution center can be enhanced by improving the efficiency of order picking processes.
主题分类 基礎與應用科學 > 統計
社會科學 > 財金及會計學
社會科學 > 管理學
参考文献
  1. 黃浩良、賴憲堂、吳光耀、林秀锜(2014)。醫院庫房設施佈置規劃─以苗栗某綜合醫院為例。聯大學報，11(2)，147-171。
    連結：
  2. Anstreicher, K. M.(2003).Recent Advances in the Solution of Quadratic Assignment Problems.Mathematical Programming,97(1-2),27-42.
  3. Battini, D.,Calzavara, M.,Persona, A.,Sgarbossa, F.(2015).Order Picking System Design: The Storage Assignment and Travel Distance Estimation (SA&TDE) Joint Method.International Journal of Production Research,53(4),1077-1093.
  4. Bos, J.(1993).A Quadratic Assignment Problem Solved by Simulated Annealing.Journal of Environmental Management,37(2),127-145.
  5. Brynzér, H.,Johansson, M. I.(1996).Storage Location Assignment: Using the Product Structure to Reduce Order Picking Times.International Journal of Production Economics,46-47,595-603.
  6. Burkard, R. E.,Çela, D. E.,Karisch, S.,Rendl, F.(1997).QAPLIB - A Quadratic Assignment Pproblem Library.Journal of Global Optimization,10(4),391-403.
  7. Burkard, R.,Offermann, J.(1977).Entwurf von Schreibmaschinentastaturen Mittels Quadratischer Zuordnungsprobleme.Zeitschrift für Operations Research,21(4),121-132.
  8. Cahn, A. S., “The Warehouse Problem,” Bulletin of the American Mathematical Society, Vol. 54, No. 11, 1948, pp. 1073
  9. Carlson, R. C.,Nemhauser, G. L.(1966).Scheduling to Minimize Interaction Cost.Operations Research,14(1),52-58.
  10. Caron, F.,Marchet, G.,Perego, A.(2000).Layout Design in Manual Picking System: A Simulation Approach.Integrated Manufacturing Systems,11(2),94-104.
  11. Chen, L.,Langevin, A.,Riopel, B.(2011).A Tabu Search Algorithm for the Relocation Problem in a Warehousing System.International Journal of Production Economics,129(1),147-156.
  12. Chiang, M. H. D.,Lin, C. P.,Chen, M. C.(2011).The Adaptive Approach for Storage Assignment by Mining Data of Warehouse Management System for Distribution Center.Enterprise Information Systems,5(2),219-234.
  13. Chuang, Y. F.,Lee, H. T.,Lai, Y. C.(2012).Item-associated Cluster Assignment Model on Storage Allocation Problems.Computers and Industrial Engineering,63,1171-1177.
  14. Commander, C. W.(2005).A Survey of the Quadratic Assignment Problem with Applications.Morehead Electronic Journal of Applicable Mathematics,4,1-15.
  15. Dallari, F.,Marchet, G.,Ruggeri, R.(2000).Optimization of A Man-on-board Automated Storage/Retrieval System.Integrated Manufacturing Systems,11(2),87-93.
  16. Dell'Amico M.,Díaz Díaz, J. C.,Iori, M.,Montanari, R.(2009).The Single Finger Keyboard Layout Problem.Computers & Operations Research,36,3002-3012.
  17. Dell'Amico, M.(Ed.),Maffioli, F.(Ed.),Martello, S.(Ed.)(1996).Annotated Bibliographies in Combinatorial Optimization.Chichester:Wiley.
  18. Dickey, J. W.,Hopkins, J. W.(1972).Campus Building Arrangement Using TOPAZ.Transportation Research,6,59-68.
  19. Dorigo, M.,Maniezzo, V.,Colorni, A.(1996).Ant System: Optimization by a Colony of Cooperating Agents.IEEE Transactions on System, Man, and Cybernetics - Part B,26,29-41.
  20. Drezner, Z.,Hahn, P.,Taillard, E.(2005).Recent Advances for the QAP Problem with Special Emphasis on Instances that are Difficult for Metaheuristic Methods.Annals of Operations Research,139,65-94.
  21. Du, D. Z.(Ed.),Pardalos, P.(Ed.)(1998).Combinatorial Optimization.Dordrecht:Kluwer Academic Publishers.
  22. Duman, E.,Ilhan, O.(2007).The Quadratic Assignment Problem in the Context of the Printed Circuit Board Assembly Process.Computers and Operations Research,34(1),163-179.
  23. Elshafei, A. N.(1977).Hospital Layout as a Quadratic Assignment Problem.Operations Research Quarterly,28(1),167-179.
  24. Ernst, A.,Jiang, H.,Krishnamoorthy, M.(2006).Exact Solution to Task Allocation Problem.Management Science,52(10),1634-1646.
  25. Fontana, M. E.,Nepomuceno, V. S.(2017).Multi-criteria Approach for Products Classification and Their Storage Location Assignment.International Journal of Advanced Manufacturing Technology,80,3205-3216.
  26. Frazele, E. H.,Sharp, G. P.(1989).Correlated Assignment Strategy Can Improve Any Order-picking Operation.Industrial Engineering,21,33-37.
  27. Geoffrion, A. M.,Graves, G. W.(1976).Scheduling Parallel Production Lines with Changeover Costs: Practical Application of a Quadratic Assignment/LP Approach.Operations Research,24(4),595-610.
  28. Goetschalckx, M.,Ratliff, H. D.(1988).Order picking in an Aisle.IIE Transactions,20,53-62.
  29. Grötschel, M.(1992).,Berlin:.
  30. Guo, X.,Yu, Y.,De Koster, R.(2016).Impact of Required Storage Space on Storage Policy Performance in a Unit-load Warehouse.International Journal of Production Research,54(8),2405-2418.
  31. Haghani, A.,Chen, M. C.(1998).Optimizing Gate Assignments at Airport Terminals.Transportation Research Part A: Policy and Practice,32(6),437-454.
  32. Hahn, P. and Anjos, M., Qaplib - A Quadratic Assignment Problem Library Online, University of Pennsylvania, School of Engineering and Applied Science, 2002. http://www.seas.upenn.edu/qaplib/
  33. Hall, R. W.(1993).Distance Approximations for Routing Manual Pickers in a Warehouse.IIE Transactions,25(4),76-87.
  34. Holland, J.(1975).Adaptation in Natural and Artificial Systems.Englewood:University of Michigan Press.
  35. Hsieh, S.,Tsai, K. C.(2001).A BOM Oriented Class-based Storage Assignment in an Automated Storage/Retrieval System.International Journal of Advanced Manufacturing Technology,17(9),683-691.
  36. Jünger, M.,Martin, A.,Reinelt, G.,Weismantel, R.(1994).Quadratic 0-1 Optimization and a Decomposition Approach for the Placement of Electronic Circuits.Mathematical Programming,63,257-279.
  37. Kennedy, J.,Eberhart, R.(1995).Particle Swarm Optimization.Proceedings of the 1995 IEEE International Conference on Neural Networks,Perth, Australia:
  38. Kirkpatrick, S.,Gelatt, C. D.,Vecchi, M. P.(1983).Optimization by Simulated Annealing.Science, New Series,220(4598),671-680.
  39. Koopmans, T. C.,Beckmann, M.(1957).Assignment Problems and the Location of Economic Activities.Econometrica,25,53-76.
  40. Koster, R. D.,Poort, E. V. D.(1998).Routing Order Pickers in a Warehouse: A Comparison between Optimal and Heuristic Solutions.IIE Transactions,30(5),469-480.
  41. Koster, R. D.,Tho, L.,Roodbergen, K. J.(2007).Design and Control of Warehouse Order Picking: A Literature Review.European Journal of Operational Research,182(2),481-501.
  42. Lee, M. K.(1992).A Storage Assignment Policy in a Man-on-board Automated Storage/Retrieval System.International Journal of Operations Research,30(10),2281-2292.
  43. Li, H. L.,Huang, Y. H.,Fang, S. C.(2012).A Logarithmic Method for Reducing Binary Variables and Inequality Constraints in Solving Task Assignment Problems.INFORMS Journal on Computing,25,643-653.
  44. Li, H. L.,Lu, H. C.(2009).Global Optimization for Generalized Geometric Program with Mixed Free-sign Variables.Operations Research,57,701-713.
  45. Liu, C. M.(1999).Clustering Techniques for Stock Location and Order-picking in a Distribution Center.Computer and Operations Research,26(10-11),989-1002.
  46. Liu, C. M.(2004).Optimal Storage Layout and Order Picking for Warehousing.International Journal of Operations Research,1(1),37-46.
  47. Loiola, E. M.,Abreu, N. M.,Boaventura-Netto, P. O.,Hahn, P.,Querido, T.(2007).A Survey for the Quadratic Assignment Problem.European Journal of Operational Research,176(2),657-690.
  48. Malucelli, F.(1993).Genova-Udine,University of Pisa.
  49. Manzini, R.(2006).Correlated Storage Assignment in an Order Picking System.International Journal of Industrial Engineering,13(4),384-394.
  50. Manzini, R.,Gamberi, M.,Persona, A.,Regattieri, A.(2007).Design of a Class Based Storage Picker to Product Order Picking System.International Journal of Advanced Manufacturing Technology,32(7-8),811-821.
  51. Manzini, R.,Gamberi, M.,Regattieri, A.(2005).Design and Control of Order Picking Systems.International Journal of Operations and Production Management,16(1),18-35.
  52. Miranda, G.,Luna, H. P. L.,Mateus, G. R.,Ferreira, R. P. M.(2005).A Performance Guarantee Heuristic for Electronic Components Placement Problems Including Thermal Effects.Computers and Operations Research,32,2937-2957.
  53. Mirchandani, P. B.(Ed.),Francis, R. L.(Ed.)(1991).Discrete Location Theory.John Wiley and Sons.
  54. Muppani, V. R.,Adil, G. K.(2008).Efficient Formation of Storage Classes for Warehouse Storage Location Assignment: A Simulated Annealing Approach.Omega,36(4),609-618.
  55. Muppani, V. R.,Adil, G. K.(2008).A Branch and Bound Algorithm for Class Based Storage Location Assignment.European Journal of Operational Research,189(2),492-507.
  56. Nyberg, A.,Westerlund, T.(2012).A New Exact Discrete Linear Reformulation of the Quadratic Assignment Problem.European Journal of Operational Research,220,314-319.
  57. Pan, J. C.,Wu, M.(2009).A Study of Storage assignment Problem for an Order Picking Line in a Pick-and-pass Warehousing System.Computer and Industrial Engineering,57,231-268.
  58. Pan, J. C.-H.,Shih, P. H.,Wu, M. H.,Lin, J. H.(2015).A Storage Assignment Heuristic Method based on Genetic Algorithm for A Pick-and-pass Warehousing System.Computers and Industrial Engineering,81,1-13.
  59. Pang, K. W.,Chan, H. L.(2017).Data Mining-based Algorithm for Storage Location Assignment in A Randomised Warehouse.International Journal of Production Research,55(14),4035-4052.
  60. Pardalos, P. M.(Ed.),Du, D. Z.(Ed.)(1998).Handbook of Combinatorial Optimization.Kluwer Academic Publishers.
  61. Pardalos, P. M.,Rendl, F.,Wolkowicz, H.(1994).The Quadratic Assignment Problem: A Survey of Recent Developments.DIMACS Series in Discrete Mathematics and Theoretical Computer Science,1-42.
  62. Peng, Y.,Miao, L. X.,Xue, Z. J.,Ye, B.(2015).Variable Neighborhood Search Heuristic for Storage Location Assignment and Storage/retrieval Scheduling under Shared Storage in Multi-shuttle Automated Storage/retrieval Systems.Transportation Research Part E,79,164-177.
  63. Petersen, C. G.(1997).An Evaluation of Order Picking Routing Policies.International Journal of Operations and Production Management,17(11),1098-1111.
  64. Quintanilla, S.,Pérez, Á.,Ballestín, F.,Lino, P.(2015).Heuristic Algorithms for a Storage Location Assignment Problem in a Chaotic Warehouse.Engineering Optimization,47(10),1405-1422.
  65. Rabak, C.,Sichman, J.(2003).Using A-teams to Optimize Automatic Insertion of Electronic Components.Advanced Engineering Informatics,17(2),95-106.
  66. Rasmussen, R.(2011).TSP in Spreadsheets a Fast and Flexible Tool.Omega,39(1),51-63.
  67. Ratliff, H. D.,Rosenthal, A. S.(1983).Order-picking in a Rectangular Warehouse: A Solvable Case of the Traveling Salesman Problem.Operations Research,31(3),507-521.
  68. Roodbergen, K. J.,Koster, R. D.(2001).Routing Method for Warehouse with Multiple Aisles.International Journal of Production Research,39(9),1865-1883.
  69. Rosenwein, M. B.(1994).An Application of Cluster Analysis to the Problem of Locating Items within a Warehouse.IIE Transactions,26(1),101-103.
  70. Steinberg, L.(1961).The Backboard Wiring Problem: A Placement Algorithm.SIAM Review,3,37-50.
  71. Till, J.,Engell, S.,Panek, S.,Stursberg, O.(2004).Applied Hybrid System Optimization: An Empirical Investigation of Complexity.Control Engineer Practice,12,1291-1303.
  72. Tompkins, J. A.,White, J. A.,Bozer, Y.A.,Frazelle, E. H.,Tanchoco, J. M. A.(2003).Facilities Planning.Facilities Planning, NJ:John Wiley & Sons.
  73. van den Berg, J. P.,Zijm, W. H. M.(1999).Models for warehouse Management: Classification and Examples.International Journal of Production Economics,9(1-3),519-528.
  74. van Oudheusden, D. L.,Zhu, W.(1992).Storage Layout of AS/RS Racks Based on Recurrent Orders.European Journal of Operational Research,58(1),48-56.
  75. Vielma, J. P.,Nemhauser, G. L.(2011).Modeling Disjunctive Constraints with a Logarithmic Number of Binary Variables and Constraints.Mathematical Programming,128(1),49-72.
  76. Wang, Y. Y.,Mou, S. D.,Wu, Y. H.(2016).Storage Assignment Optimization in a Multi-tier Shuttle Warehousing System.Chinese Journal of Mechanical Engineering,29(2),421-429.
  77. Xiao, J.,Zheng, L.(2010).A Correlated Storage Location Assignment Problem in a Singleblock-multi-aisles Warehouse Considering BOM Information.International Journal of Production Research,48(5),1321-1338.
  78. Xie, J.,Mei, Y.,Ernst, A. T.,Li, X. D.,Song, A.(2014).A Genetic Programming-based Hyper-heuristic Approach for Storage Location Assignment Problem.Proceedings of the 2014 IEEE Congress on Evolutionary Computation,Beijing, China:
  79. Xie, J.,Mei, Y.,Ernst, A. T.,Li, X. D.,Song, A.(2014).Scaling up Solutions to Storage Location Assignment Problems by Genetic Programming.Simulated Evolution and Learning
  80. Zhang, G. Q.,Xue, J.,Lai, K. K.(2000).A Genetic Algorithm Based Heuristic for Adjacent Paper-reel Layout Problem.International Journal of Production Research,38(14),3343-3356.
  81. 江曉柔(2013)。碩士論文(碩士論文)。國立雲林科技大學工業工程與管理研究所。
  82. 吳坤山(2005)。管理科學導論。臺北:華泰書局。
  83. 郭彥峰、馬婷、王宏濤(2008)。倉儲過程中貨位指派優化問題。包裝工程，29(11)，83-85。
  84. 陳志騰、林泓毅、張俊郁、李益銘、蕭宇倫(2015)。結合商品關聯與EIQ 方法論之IK 分析應用於儲位指派之研究。創新與經營管理學刊，6(1)，59-78。
  85. 黃若蘋(2007)。碩士論文(碩士論文)。大同大學資訊經營研究所。
  86. 鈴木震(1992)。鈴木震，「如何利用EIQ 法來進行配貨中心系統計畫」，中國生產力中心講義，民國81 年。
  87. 劉曉華、許鋒(2014)。基於Lingo軟件的醫院科室布局優化方法探討。中國醫療設備，5，112-114。
  88. 潘昭賢、陳禎祥、張明洲(2009)。基因演算法在物流中心品項儲位指派之應用。工商管理學刊，5(1)，135-150。
print cancel