НАУКА и ОБРАЗОВАНИЕ

Файл статьи: SE-BMSTU...o310.pdf (1692.93Кб)

УДК 658.5

Россия,  МГТУ им. Н.Э. Баумана

Статья посвящена под-задаче маршрутизации сборщиков заказов в процессе комплектования заказов на складе и является второй статьей в цикле «Процесс комплектования заказов на складе». Приводятся аналогии задачи маршрутизации сборщиков заказов с задачей коммивояжера, выявлены различия между стандартной формулировкой задачи коммивояжера и задачей маршрутизации сборщиков заказов, приведена частная, штейнеровская, формулировка задачи коммивояжера. Планировка склада с типовым заказом представляется в виде графа, часть вершин которого обязательна к посещению, а часть — нет. Описывается оптимальный алгоритм Рэтлиффа-Розенталя решения задачи маршрутизации сборщиков заказов для одноблочных складов. т.е. складов с двумя поперечными проходами, определяются семь эквивалентных классов частичных маршрутных подграфов и пять перемещений, используемых для получения оптимального маршрутного подграфа сборщика заказов. Приводятся расширение алгоритма Рэтлиффа-Розенталя на случай многоблочных складов, а также причины, по которым в большинстве случаев применение точных оптимальных алгоритмов заменяется использованием эвристических методов. Приводится алгоритмическое описание следующих семи эвристик маршрутизации сборщиков заказов: S-образной, с возвратами, серединной, с захождением на наибольший интервал, последовательная, составная и комбинированная, а также модификация комбинированной эвристики. Сравнение эффективности эвристических метод маршрутизации сборщиков заказов для одно- и двухблочных складов представлено в следующей статье цикла «Процесс комплектования заказов на складе».

1. Коробков Е.В. Процесс комплектования заказов на складе. Обзор // Наука и образование. МГТУ им. Н . Э . Баумана . Электрон . журн . 2015. № 3. С. 153-183. DOI: 10.7463/0315.0763161
2. Lawler E.L., Lenstra J.K., Kan A.R., Shmoys D.B. The Travelling Salesman Problem: A Guided Tour of Combinational Optimization. Vol. 3. New York, NY: Wiley, 1985. 476 p.
3. Ratliff H.D., Rosenthal A.S. Order-Picking in a Rectangular Warehouse: A Solvable Case of the Traveling Salesman Problem // Operations Research. 1983. Vol. 31, no. 3. P. 507-521. DOI: 10.1287/opre.31.3.507
4. Roodbergen K.J., de Koster R. Routing Order Pickers in a Warehouse with a Middle Aisle // European Journal of Operational Research. 2001. Vol. 133, no. 1. P. 32-43. DOI: 10.1016/S0377-2217(00)00177-6
5. Gademann N., Velde S. Order Batching to Minimize Total Travel Time in a Parallel-Aisle Warehouse // IIE Transactions. 2005. Vol. 37, no. 1. P. 63–75. DOI: 10.1080/07408170590516917
6. De Koster R., Roodbergen K.J., van Voorden R. Reduction of Walking Time in the Distribution Center of De Bijenkorf // In: New Trends in Distribution Logistics / ed. by M.G. Speranza. Berlin: Springer-Verlag, 2000. P. 215-234. DOI:10.1007/978-3-642-58568-5_11
7. Dekker R., de Koster R., Roodbergen K.J., van Kalleveen H. Improving Order-Picking Response Time at Ankor’s Warehouse // Interface. 2004. Vol. 34, no. 4. P. 303–313. DOI: 10.1287/inte.1040.0083
8. Petersen II C.G., Schmenner R.W. An Evaluation of Routing and Volume-Based Storage Policies in an Order Picking Operation // Decision Sciences. 1999. Vol. 30, no. 2. P. 481–501. DOI: 10.1111/j.1540-5915.1999.tb01619.x
9. Interactive Warehouse: web-site. Available at: http://www.roodbergen.com/warehouse/index.php, accessed January 2015.
10. Petersen II C.G., Aase G. A Comparison of Picking, Storage, and Routing Policies in Manual Order Picking // International Journal of Production Economics. 2004. Vol. 92, no. 1. P. 11-19. DOI: 10.1016/j.ijpe.2003.09.006
11. De Koster R., Le-Duc T., Roodbergen K.J. Design and Control of Warehouse Order Picking: A Literature Review // European Journal of Operational Research. 2007. Vol. 182, no. 2. P. 481–501. DOI:10.1016/j.ejor.2006.07.009
12. Gu J., Goetschalckx M., McGinnis L.F. Research on Warehouse Design and Performance Evaluation: A Comprehensive Review // European Journal of Operational Research. 2010. Vol. 203, no. 3. P. 539-549. DOI: 10.1016/j.ejor.2009.07.031
13. Le-Duc T., De Koster R. Travel Distance Estimation and Storage Zone Optimization in a 2-Block Class-Based Strategy Warehouse // International Journal of Production Research. 2005. Vol. 43, no. 17. P. 3561–3581. DOI: 10.1080/00207540500142894
14. Petersen II C.G. The Impact of Routing and Storage Policies on Warehouse Efficiency // International Journal of Operations and Production Management. 1999. Vol. 19, no. 10. P. 1053–1064. DOI: 10.1108/01443579910287073
15. Petersen II C.G., Aase G.R., Heiser D.R. Improving Order-Picking Performance through the Implementation of Class-Based Storage // International Journal of Physical Distribution and Logistics Management. 2004. Vol. 34, no. 7. P. 532-544. DOI: 10.1108/09600030410552230
16. De Koster R., van der Poort E.S., Wolters M. Efficient Orderbatching Methods in Warehouse // International Journal of Production Research. 1999. Vol. 37, no. 7. P. 1479-1504. DOI: 10.1080/002075499191094
17. Le-Duc T., De Koster R. Travel Time Estimation and Order Batching in a 2-Block Warehouse // European Journal of Operational Research. 2007. Vol. 176, no. 1. P. 374–388. DOI: 10.1016/j.ejor.2005.03.052
18. De Koster R., van der Poort E. Routing Orderpickers in a Warehouse: A Comparison between Optimal and Heuristic Solutions // IIE Transactions. 1998. Vol. 30, no. 5. P. 469-480. DOI: 10.1080/07408179808966487
19. Roodbergen K.J., de Koster R. Routing Methods for Warehouses with Multiple Cross Aisles // International Journal of Production Research. 2001. Vol. 39, no. 9. P. 1865-1883. DOI: 10.1080/00207540110028128
20. Hall R.W. Distance Approximations for Routing Manual Pickers in a Warehouse // IIE Transactions. 1993. Vol. 25, no. 4. P. 76–87. DOI: 10.1080/07408179308964306
21. Hwang H., Oh Y.H., Lee Y.K. An Evaluation of Routing Policies for Order-Picking Operations in Low-Level Picker-to-Part System // International Journal of Production Research. 2004. Vol. 42, no. 18. P. 3873–3889. DOI: 10.1080/00207540410001696339
22. Roodbergen K.J., Sharp G.P., Vis I.F. Designing the Layout Structure of Manual Order Picking Areas in Warehouses // IIE Transactions. 2008. Vol. 40, no. 11. P. 1032–1045. DOI: 10.1080/07408170802167639
23. Vaughan T.S. The Effect of Warehouse Cross Aisles on Order Picking Efficiency // International Journal of Production Research. 1999. Vol. 37, no. 4. P. 881–897. DOI: 10.1080/002075499191580
24. Jarvis J.M., McDowell E.D. Optimal Product Layout in an Order Picking Warehouse // IIE Transactions. 1991. Vol. 23, no. 1. P. 93-102. DOI: 10.1080/07408179108963844
25. Gray A.E., Karmarkar U.S., Seidmann A. Design and Operation of an Order-Consolidation Warehouse: Models and Application // European Journal of Operational Research. 1992. Vol. 58, no. 1. P. 14–36. DOI: 10.1016/0377-2217(92)90232-X
26. Petersen II C.G. An Evaluation of Order Picking Routeing Policies // International Journal of Operations and Production Management. 1997. Vol. 17, no. 11. P. 1098–1111. DOI: 10.1108/01443579710177860