بهینه سازی سیستم برداشت سفارش چند دوره ای و مسیریابی چند سفره ‏برداشت کننده ها با ‏‎ ‎هدف حداقل سازی مجموع دیرکرد ‏

فرهادی سرتنگی, مرتضی; حسین زاده کاشان, علی; حاله, حسن; کاظمی, ابوالفضل

doi:10.22105/dmor.2021.294310.1441

نوع مقاله : مقاله پژوهشی - کاربردی

نویسندگان

¹ گروه مهندسی صنایع، دانشکده مهندسی صنایع و مکانیک، واحد قزوین، دانشگاه آزاد اسلامی ، قزوین، ایران.

² دانشکده مهندسی صنایع و سیستم ها، دانشگاه تربیت مدرس، تهران، ایران.

³ گروه مهندسی صنایع، دانشکده فنی و مهندسی ، گلپایگان، ایران.

https://doi.org/10.22105/dmor.2021.294310.1441

چکیده

هدف: برداشت سفارش، یکی از فرایندهای درونی لجستیکی مبتنی بر نیروی کار و هزینه شناخته‌شده است. برداشت سفارش در قالب مسئله پاسخ به سفارش مشتری، به‌منظور جمع‌آوری مجموعه‌ای از سفارش‌ها در کوتاه‌ترین زمان ممکن در انبار تعریف می‌گردد. لذا هدف این تحقیق فراهم نمودن یک مبنای علمی و هم‌زمان کاربردی با در نظر گرفتن الزامات و محدودیت‌هایی است که سطح قابل قبولی از عملکرد را در سیستم‌های برداشت سفارش به ارمغان آورد. این امر از طریق ساخت یک مدل برنامه‌ریزی عدد صحیح و هم‌چنین طراحی روش حل متناسب با ساختار مسئله صورت می‌گیرد.
روش‌شناسی پژوهش: ابتدا با مرور ادبیات در حوزه برداشت سفارش دانش کافی در سطح عملیاتی حاصل‌شده است و با تأکید بر محدودیت‌های واقعی اقدام به مدل‌سازی ریاضی از طریق یکپارچه نمودن دسته‌بندی سفارش‌ها و مسیریابی برداشت کننده‌ها، شده است. پس از بررسی صحت مدل و حل آن از طریق نرم‌افزار GAMS، به دلیل ماهیت مسئله که از نوع سخت است، مسئله از طریق یک الگوریتم کارا که نسخه گروه‌بندی الگوریتم قهرمانی در لیگ‌های ورزشی است، حل‌شده و مقایسات صورت پذیرفته است. برای استفاده از این الگوریتم از اپراتورهای منطبق با ساختار خاص مسئله که هدف آن تخصیص سفارش‌ها (اقلام) به برداشت کننده‌ها ‌(گروه‌ها) است استفاده می‌شود.
یافته ها: ارائه یک مدل برنامه‌ریزی عدد صحیح چند دوره‌ای برای مسیریابی چند سفره برداشت کنندگان با فرض وجود قابلیت باز پر سازی انبار و دسترسی محدود به برداشت کنندگان. برای نمونه مسائل با ابعاد بزرگ، از الگوریتم قهرمانی در لیگ‌های ورزشی استفاده‌شده است. نتایج بر قابلیت مؤثر و کارایی این الگوریتم برای حل نمونه مسائل بزرگ اشاره دارد.
اصالت/ارزش‌افزوده علمی: مسئله برداشت سفارش چند دوره‌ای و مسیریابی چند سفره برداشت کنندگان نخستین بار در این مقاله مدنظر قرارگرفته است. زیرابه علت محدود بودن تعداد برداشت کنندگان، این مهم می‌بایست در مدل‌سازی مدنظر قرار گیرد. فرض بازپرسازی نیز نخستین بار در این مقاله موردتوجه قرارگرفته و مدل‌سازی آن صورت گرفته است. بدین ترتیب سفارش‌ها در طول زمان، طی دوره‌های مختلف وارد انبار می‌شوند و در موقعیت از پیش تعیین‌شده قرار می‌گیرند. وجود بازه زمانی برای دسترسی به برداشت کننده‌ها‌ در هر دوره و مدل‌سازی آن نیز نخستین بار در این مقاله موردبررسی قرارگرفته است. درنهایت، تابع هدف حداقل سازی مجموع دیرکرد است که هم‌راستا با نیاز صنایع تولیدی است. در خصوص روش حل نیز یک الگوریتم قهرمانی در لیگ‌های ورزشی با در نظر گرفتن ساختار مسئله (که منطبق بر ساختار مسائل گروه‌بندی است) ارائه‌شده است و عملگرهای تولید جواب نیز برای حفظ شدنی بودن جواب، توسعه ‌یافته‌اند.

کلیدواژه‌ها

20.1001.1.25385097.1401.7.1.6.1

موضوعات

مدل‌های زمان‌بندی

عنوان مقاله [English]

Optimization of a multi-period order picking and multi-trip order-picker routing to minimize total tardiness

نویسندگان [English]

Morteza Farhadi Sartangi ¹
Ali Husseinzadeh Kashan ²
Hassan Haleh ³
Abolfazl Kazemi ¹

¹ Department of Industrial Engineering, Faculty of Industrial and Mechanical Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran.

² Faculty of Industrial and Systems Engineering, Tarbiat Modares University, Tehran, Iran.

³ Department of Industrial Engineering, Faculty of Technology and Engineering, Golpayegan, Iran.

چکیده [English]

Purpose: Order picking operation is one of the most well-known labor and cost intensive internal logistics processes. Withdrawal of the order in response to customer need is defined in order to collect a set of orders from storage zone in the shortest possible time. The purpose of this research is to provide a scientific and practical basis considering the constraints that enforce to achieve an acceptable level of performance in order picking systems. This is done by building a Mixed Integer Linear Programming (MILP) formulation and developing an adapted solution method suited to the structure of the problem
Methodology: First, by reviewing the literature in the field of order picking systems, sufficient knowledge has been obtained at the operational level, and with emphasis on warehouse management constraints, a MILP formulation is proposed by integrating order batching and picker routing. After validating the model and solving it through GAMS software, due to the nature of the problem, which is an NP-hard type, the problem is solved with an efficient algorithm, which is a grouping version of the league championship algorithm, and the results are compared. To develop the algorithm, operators are fit to the specific structure of the problem, i.e., the assignment of orders (items) to order pickers (groups)
Findings: Developing a multi-period MILP formulation for multi-trip picker routing, assuming for the first time the possibility of product replenishment and limited access to pickers. For large-scale problem instances, the league championship algorithm is used. The results indicate the effective capability and efficiency of this algorithm for solving large test problem instances.
Originality/Value: The issue of multi-period order picking and multi-trip routing of pickers is considered for the first time ‎in this paper. Because of the limited number of pickers, this must be taken into account in modeling. ‎The assumption of product replenishment is also considered for the first time in this article and its ‎modeling has been done. In this way, orders enter the warehouse over time, during different periods, ‎and are placed in a predetermined positions. The limited access to pickers in each period is also ‎discussed for the first time in this paper. Finally, the objective function of minimizing the total ‎tardiness, which is in line with the needs of the industry, is also introduced in this paper. Regarding the ‎solution method, a league championship metaheuristic algorithm is presented which takes into ‎account the problem structure (which corresponds to the structure of grouping problems) and ‎solution generation operators have been developed to maintain the new solution.‎

کلیدواژه‌ها [English]

Order batching
Picker routing
Multi-period
Multi-trip routing
League championship algorithm

مراجع

Briant, O., Cambazard, H., Cattaruzza, D., Catusse, N., Ladier, A. L., & Ogier, M. (2020). An efficient and general approach for the joint order batching and picker routing problem. European journal of operational research, 285(2), 497-512. https://doi.org/10.1016/j.ejor.2020.01.059

Cano, J. A., Correa-Espinal, A. A., & Gómez-Montoya, R. A. (2020). Mathematical programming modeling for joint order batching, sequencing and picker routing problems in manual order picking systems. Journal of King Saud university-engineering sciences, 32(3), 219-228. https://doi.org/10.1016/j.jksues.2019.02.004

Cergibozan, Ç., & Tasan, A. S. (2019). Order batching operations: an overview of classification, solution techniques, and future research. Journal of intelligent manufacturing, 30(1), 335-349. https://doi.org/10.1007/s10845-016-1248-4

Cheng, C. Y., Chen, Y. Y., Chen, T. L., & Yoo, J. J. W. (2015). Using a hybrid approach based on the particle swarm optimization and ant colony optimization to solve a joint order batching and picker routing problem. International journal of production economics, 170, 805-814. https://doi.org/10.1016/j.ijpe.2015.03.021

Chen, F., Wang, H., Xie, Y., & Qi, C. (2016). An ACO-based online routing method for multiple order pickers with congestion consideration in warehouse. Journal of intelligent manufacturing, 27(2), 389-408. https://doi.org/10.1007/s10845-014-0871-1

Chen, F., Wei, Y., & Wang, H. (2018). A heuristic based batching and assigning method for online customer orders. Flexible services and manufacturing journal, 30(4), 640-685. https://doi.org/10.1007/s10696-017-9277-7

Chen, T. L., Cheng, C. Y., Chen, Y. Y., & Chan, L. K. (2015). An efficient hybrid algorithm for integrated order batching, sequencing and routing problem. International journal of production economics, 159, 158-167. https://doi.org/10.1016/j.ijpe.2014.09.029

De Koster, R., Le-Duc, T., & Roodbergen, K. J. (2007). Design and control of warehouse order picking: a literature review. European journal of operational research, 182(2), 481-501. https://doi.org/10.1016/j.ejor.2006.07.009

Falkenauer, E. (1994). A new representation and operators for genetic algorithms applied to grouping problems. Evolutionary computation, 2(2), 123-144. DOI: 10.1162/evco.1994.2.2.123

Giannikas, V., Lu, W., Robertson, B., & McFarlane, D. (2017). An interventionist strategy for warehouse order picking: evidence from two case studies. International journal of production economics, 189, 63-76. https://doi.org/10.1016/j.ijpe.2017.04.002

Glock, C. H., Grosse, E. H., Elbert, R. M., & Franzke, T. (2017). Maverick picking: the impact of modifications in work schedules on manual order picking processes. International journal of production research, 55(21), 6344-6360. https://doi.org/10.1080/00207543.2016.1252862

Henn, S. (2015). Order batching and sequencing for the minimization of the total tardiness in picker-to-part warehouses. Flexible services and manufacturing journal, 27(1), 86-114. https://doi.org/10.1007/s10696-012-9164-1

Henn, S., Koch, S., Doerner, K. F., Strauss, C., & Wäscher, G. (2010). Metaheuristics for the order batching problem in manual order picking systems. Business research, 3(1), 82-105. https://doi.org/10.1007/BF03342717

Henn, S., Koch, S., & Wäscher, G. (2012). Order batching in order picking warehouses: a survey of solution approaches. In Warehousing in the global supply chain (pp. 105-137). Springer, London. https://doi.org/10.1007/978-1-4471-2274-6_6

Henn, S., & Schmid, V. (2013). Metaheuristics for order batching and sequencing in manual order picking systems. Computers & industrial engineering, 66(2), 338-351. https://doi.org/10.1016/j.cie.2013.07.003

Ho, Y. C., & Tseng, Y. Y. (2006). A study on order-batching methods of order-picking in a distribution centre with two cross-aisles. International journal of production research, 44(17), 3391-3417. https://doi.org/10.1080/00207540600558015

Hong, S., Johnson, A. L., & Peters, B. A. (2012). Batch picking in narrow-aisle order picking systems with consideration for picker blocking. European journal of operational research, 221(3), 557-570. https://doi.org/10.1016/j.ejor.2012.03.045

Kashan, A. H. (2009, December). League championship algorithm: a new algorithm for numerical function optimization. 2009 international conference of soft computing and pattern recognition (pp. 43-48). IEEE. DOI: 10.1109/SoCPaR.2009.21

Kuhn, H., Schubert, D., & Holzapfel, A. (2021). Integrated order batching and vehicle routing operations in grocery retail–a general adaptive large neighborhood search algorithm. European journal of operational research, 294(3), 1003-1021. https://doi.org/10.1016/j.ejor.2020.03.075

Kulak, O., Sahin, Y., & Taner, M. E. (2012). Joint order batching and picker routing in single and multiple-cross-aisle warehouses using cluster-based tabu search algorithms. Flexible services and manufacturing journal, 24(1), 52-80. https://doi.org/10.1007/s10696-011-9101-8

Marchet, G., Melacini, M., & Perotti, S. (2015). Investigating order picking system adoption: a case-study-based approach. International journal of logistics research and applications, 18(1), 82-98. https://doi.org/10.1080/13675567.2014.945400

Masae, M., Glock, C. H., & Grosse, E. H. (2020). Order picker routing in warehouses: a systematic literature review. International journal of production economics, 224, 107564. https://doi.org/10.1016/j.ijpe.2019.107564

Menéndez, B., Pardo, E. G., Alonso-Ayuso, A., Molina, E., & Duarte, A. (2017). Variable neighborhood search strategies for the order batching problem. Computers & operations research, 78, 500-512. https://doi.org/10.1016/j.cor.2016.01.020

Moons, S., Braekers, K., Ramaekers, K., Caris, A., & Arda, Y. (2019). The value of integrating order picking and vehicle routing decisions in a B2C e-commerce environment. International journal of production research, 57(20), 6405-6423. https://doi.org/10.1080/00207543.2019.1566668

Öncan, T. (2015). Milp formulations and an iterated local search algorithm with tabu thresholding for the order batching problem. European journal of operational research, 243(1), 142-155. https://doi.org/10.1016/j.ejor.2014.11.025

Pan, J. C. H., Shih, P. H., & Wu, M. H. (2012). Storage assignment problem with travel distance and blocking considerations for a picker-to-part order picking system. Computers & industrial engineering, 62(2), 527-535. https://doi.org/10.1016/j.cie.2011.11.001

Petersen, C. G. (1997). An evaluation of order picking routeing policies. International journal of operations & production management, 17(11), 1098-1111. https://doi.org/10.1108/01443579710177860

Petersen, Ch. G. (2000). An evaluation of order picking policies for mail order companies. Production and operations management, 9(4), 319-335. https://doi.org/10.1111/j.1937-5956.2000.tb00461.x

Petersen, C. G., & Aase, G. (2004). A comparison of picking, storage, and routing policies in manual order picking. International journal of production economics, 92(1), 11-19. https://doi.org/10.1016/j.ijpe.2003.09.006

Scholz, A., & Wäscher, G. (2017). Order batching and picker routing in manual order picking systems: the benefits of integrated routing. Central European journal of operations research, 25(2), 491-520. https://doi.org/10.1007/s10100-017-0467-x

Scholz, A., Schubert, D., & Wäscher, G. (2017). Order picking with multiple pickers and due dates–simultaneous solution of order batching, batch assignment and sequencing, and picker routing problems. European journal of operational research, 263(2), 461-478. https://doi.org/10.1016/j.ejor.2017.04.038

Tsai, C. Y., Liou, J. J., & Huang, T. M. (2008). Using a multiple-GA method to solve the batch picking problem: considering travel distance and order due time. International journal of production research, 46(22), 6533-6555. https://doi.org/10.1080/00207540701441947

Valle, C. A., Beasley, J. E., & Da Cunha, A. S. (2017). Optimally solving the joint order batching and picker routing problem. European journal of operational research, 262(3), 817-834. https://doi.org/10.1016/j.ejor.2017.03.069

Van Gils, T., Ramaekers, K., Braekers, K., Depaire, B., & Caris, A. (2018). Increasing order picking efficiency by integrating storage, batching, zone picking, and routing policy decisions. International journal of production economics, 197, 243-261. https://doi.org/10.1016/j.ijpe.2017.11.021

Wäscher, G. (2004). Order picking: a survey of planning problems and methods. In Supply chain management and reverse logistics (pp. 323-347). Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24815-6_15

Won, J., & Olafsson, S. (2005). Joint order batching and order picking in warehouse operations. International journal of production research, 43(7), 1427-1442. https://doi.org/10.1080/00207540410001733896

Žulj, I., Kramer, S., & Schneider, M. (2018). A hybrid of adaptive large neighborhood search and tabu search for the order-batching problem. European journal of operational research, 264(2), 653-664. https://doi.org/10.1016/j.ejor.2017.06.056

تصمیم گیری و تحقیق در عملیات

بهینه سازی سیستم برداشت سفارش چند دوره ای و مسیریابی چند سفره ‏برداشت کننده ها با ‏‎ ‎هدف حداقل سازی مجموع دیرکرد ‏

مراجع

مراجع

دوره 7، شماره 1
اردیبهشت 1401
صفحه 91-110

بهینه سازی سیستم برداشت سفارش چند دوره ای و مسیریابی چند سفره ‏برداشت کننده ها با ‏‎ ‎هدف حداقل سازی مجموع دیرکرد ‏

مراجع

مراجع

دوره 7، شماره 1اردیبهشت 1401صفحه 91-110

دوره 7، شماره 1
اردیبهشت 1401
صفحه 91-110