[국내논문]의류 인터넷 쇼핑몰에서 브랜드를 고려한 상품 입고 및 재배치 방법 연구 An Efficient Heuristic for Storage Location Assignment and Reallocation for Products of Different Brands at Internet Shopping Malls for Clothing원문보기
의류 인터넷 쇼핑몰들은 판매 상품의 포장과 배송을 위한 상품 창고를 운영하고 있다. 상품들은 동일 브랜드끼리 상자에 담긴 후 선반에 일렬로 보관된다. 상품의 반출 및 상품 관리의 편의상, 상자들은 동일 브랜드끼리 묶여져 선반에 진열되어 있어야 한다. 따라서, 새로운 상품들이 입고될 경우 상품들은 동일 브랜드끼리 상자에 담긴 후 선반 위에 있는 기존 상자들 중에서 동일 브랜드의 상자 옆에 배치되어야 한다. 그런데, 선반 위의 빈 곳이 새로 입고되는 상자를 넣을 수 있을 만큼 충분하지 않다면, 옆의 다른 브랜드의 상자들을 옆으로 밀어서 공간을 확보한 후 새로운 상자를 배치함으로써 동일 브랜드 상자끼리 붙어있도록 해야 한다. 우리의 문제는 이와 같이 새로운 상품을 입고할 때 동일 브랜드의 상자들끼리 붙어 있도록 하면서 다른 브랜드의 상자를 옆으로 옮길 경우, 그 횟수를 최소화하는 것이다. 이 문제의 최적해를 구하기 위해서 우리는 이 문제를 우선 정수계획법으로 모형화하였다. 그런데, 정수계획법 문제는 분기한정법(Branch and Bound) 기법으로 해결하여야 하나, 그 경우 문제해결 시간이 너무 오래 걸리는 문제가 발생한다. 따라서, 본 연구에서는 위 재배치 문제를 할당 문제(Assignment Problem)로 완화하여 모형화함으로써 만족할만한 준최적해를 구하는 방법론을 제시하고, 실험에 의하여 그 타당성을 검토하였다. 또한, 이 방법론 하에서 실제 의류 인터넷 쇼핑몰의 컴퓨팅 환경을 고려할 때 해결 가능한 문제의 최대 크기를 도출하고, 그 크기 이내에서 입고 계획을 생성하는 시스템을 구현하였다.
의류 인터넷 쇼핑몰들은 판매 상품의 포장과 배송을 위한 상품 창고를 운영하고 있다. 상품들은 동일 브랜드끼리 상자에 담긴 후 선반에 일렬로 보관된다. 상품의 반출 및 상품 관리의 편의상, 상자들은 동일 브랜드끼리 묶여져 선반에 진열되어 있어야 한다. 따라서, 새로운 상품들이 입고될 경우 상품들은 동일 브랜드끼리 상자에 담긴 후 선반 위에 있는 기존 상자들 중에서 동일 브랜드의 상자 옆에 배치되어야 한다. 그런데, 선반 위의 빈 곳이 새로 입고되는 상자를 넣을 수 있을 만큼 충분하지 않다면, 옆의 다른 브랜드의 상자들을 옆으로 밀어서 공간을 확보한 후 새로운 상자를 배치함으로써 동일 브랜드 상자끼리 붙어있도록 해야 한다. 우리의 문제는 이와 같이 새로운 상품을 입고할 때 동일 브랜드의 상자들끼리 붙어 있도록 하면서 다른 브랜드의 상자를 옆으로 옮길 경우, 그 횟수를 최소화하는 것이다. 이 문제의 최적해를 구하기 위해서 우리는 이 문제를 우선 정수계획법으로 모형화하였다. 그런데, 정수계획법 문제는 분기한정법(Branch and Bound) 기법으로 해결하여야 하나, 그 경우 문제해결 시간이 너무 오래 걸리는 문제가 발생한다. 따라서, 본 연구에서는 위 재배치 문제를 할당 문제(Assignment Problem)로 완화하여 모형화함으로써 만족할만한 준최적해를 구하는 방법론을 제시하고, 실험에 의하여 그 타당성을 검토하였다. 또한, 이 방법론 하에서 실제 의류 인터넷 쇼핑몰의 컴퓨팅 환경을 고려할 때 해결 가능한 문제의 최대 크기를 도출하고, 그 크기 이내에서 입고 계획을 생성하는 시스템을 구현하였다.
An Internet shopping mall for clothing operates a warehouse for packing and shipping products to fulfill its orders. All the products in the warehouse are put into the boxes of same brands and the boxes are stored in a row on shelves equiped in the warehouse. To make picking and managing easy, boxes...
An Internet shopping mall for clothing operates a warehouse for packing and shipping products to fulfill its orders. All the products in the warehouse are put into the boxes of same brands and the boxes are stored in a row on shelves equiped in the warehouse. To make picking and managing easy, boxes of the same brands are located side by side on the shelves. When new products arrive to the warehouse for storage, the products of a brand are put into boxes and those boxes are located adjacent to the boxes of the same brand. If there is not enough space for the new coming boxes, however, some boxes of other brands should be moved away and then the new coming boxes are located adjacent in the resultant vacant spaces. We want to minimize the movement of the existing boxes of other brands to another places on the shelves during the warehousing of new coming boxes, while all the boxes of the same brand are kept side by side on the shelves. Firstly, we define the adjacency of boxes by looking the shelves as an one dimensional series of spaces to store boxes, i.e. cells, tagging the series of cells by a series of numbers starting from one, and considering any two boxes stored in the cells to be adjacent to each other if their cell numbers are continuous from one number to the other number. After that, we tried to formulate the problem into an integer programming model to obtain an optimal solution. An integer programming formulation and Branch-and-Bound technique for this problem may not be tractable because it would take too long time to solve the problem considering the number of the cells or boxes in the warehouse and the computing power of the Internet shopping mall. As an alternative approach, we designed a fast heuristic method for this reallocation problem by focusing on just the unused spaces-empty cells-on the shelves, which results in an assignment problem model. In this approach, the new coming boxes are assigned to each empty cells and then those boxes are reorganized so that the boxes of a brand are adjacent to each other. The objective of this new approach is to minimize the movement of the boxes during the reorganization process while keeping the boxes of a brand adjacent to each other. The approach, however, does not ensure the optimality of the solution in terms of the original problem, that is, the problem to minimize the movement of existing boxes while keeping boxes of the same brands adjacent to each other. Even though this heuristic method may produce a suboptimal solution, we could obtain a satisfactory solution within a satisfactory time, which are acceptable by real world experts. In order to justify the quality of the solution by the heuristic approach, we generate 100 problems randomly, in which the number of cells spans from 2,000 to 4,000, solve the problems by both of our heuristic approach and the original integer programming approach using a commercial optimization software package, and then compare the heuristic solutions with their corresponding optimal solutions in terms of solution time and the number of movement of boxes. We also implement our heuristic approach into a storage location assignment system for the Internet shopping mall.
An Internet shopping mall for clothing operates a warehouse for packing and shipping products to fulfill its orders. All the products in the warehouse are put into the boxes of same brands and the boxes are stored in a row on shelves equiped in the warehouse. To make picking and managing easy, boxes of the same brands are located side by side on the shelves. When new products arrive to the warehouse for storage, the products of a brand are put into boxes and those boxes are located adjacent to the boxes of the same brand. If there is not enough space for the new coming boxes, however, some boxes of other brands should be moved away and then the new coming boxes are located adjacent in the resultant vacant spaces. We want to minimize the movement of the existing boxes of other brands to another places on the shelves during the warehousing of new coming boxes, while all the boxes of the same brand are kept side by side on the shelves. Firstly, we define the adjacency of boxes by looking the shelves as an one dimensional series of spaces to store boxes, i.e. cells, tagging the series of cells by a series of numbers starting from one, and considering any two boxes stored in the cells to be adjacent to each other if their cell numbers are continuous from one number to the other number. After that, we tried to formulate the problem into an integer programming model to obtain an optimal solution. An integer programming formulation and Branch-and-Bound technique for this problem may not be tractable because it would take too long time to solve the problem considering the number of the cells or boxes in the warehouse and the computing power of the Internet shopping mall. As an alternative approach, we designed a fast heuristic method for this reallocation problem by focusing on just the unused spaces-empty cells-on the shelves, which results in an assignment problem model. In this approach, the new coming boxes are assigned to each empty cells and then those boxes are reorganized so that the boxes of a brand are adjacent to each other. The objective of this new approach is to minimize the movement of the boxes during the reorganization process while keeping the boxes of a brand adjacent to each other. The approach, however, does not ensure the optimality of the solution in terms of the original problem, that is, the problem to minimize the movement of existing boxes while keeping boxes of the same brands adjacent to each other. Even though this heuristic method may produce a suboptimal solution, we could obtain a satisfactory solution within a satisfactory time, which are acceptable by real world experts. In order to justify the quality of the solution by the heuristic approach, we generate 100 problems randomly, in which the number of cells spans from 2,000 to 4,000, solve the problems by both of our heuristic approach and the original integer programming approach using a commercial optimization software package, and then compare the heuristic solutions with their corresponding optimal solutions in terms of solution time and the number of movement of boxes. We also implement our heuristic approach into a storage location assignment system for the Internet shopping mall.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
따라서 본 문제에서는 셀의 배치 형태를 일렬로 늘어선 1차원의 배열로 파악하고, 동일 브랜드의 상자끼리 묶는 것도 이 1차원 배열 상에서 묶이도록 한다<그림 1>. 그러면, 본 연구문제의 목표는 새로 상품 상자를 입고할 때 1차원의 각 셀에 동일 브랜드의 상품 상자끼리 묶이도록 상품 상자들을 배치하되, 그때 상품 상자의 총 이동 횟수를 최소화 하는 것이 된다.
이 상품 상자를 X라고 하고, X상자의 브랜드를 B라고 하자. 그리고 X를 각 빈 셀에 배치할 경우의 비용을 생각해 보자. 예를 들어, B 브랜드의 상자들이 배치된 셀들의 바로 옆의 셀에 X를 배치할 경우 같은 브랜드의 상자끼리 묶기 위한 특별한 재배치 비용은 없다.
본 연구에서는 의류 인터넷 쇼핑몰에서 주문 상품의 반출을 용이하게 하기 위한 상품의 배치를 정하는 문제를 해결하고자 하였다. 상품 반출 빈도, 상품 크기나 무게 등을 기준으로 하는 SKU의 위치를 정하는 기존 연구들과는 달리, 브랜드 별로 상품을 묶어 유지하는 것이 기준이 된다는 점에서 본 연구의 문제는 기존 문제와 다른 새로운 유형의 문제라고 할 수 있다.
주어진 컴퓨팅 환경 하에서 기대 가능한 시간내에 이 문제를 풀기 위해서는 이 문제를 다른 각도에서 모형화 할 필요가 있다. 이를 위하여 상품 상자의 배치 방법을 빈 셀(상자가 배치되지 않은 셀)의 관점에서 생각해보자.
제안 방법
또한 창고관리자가 셀의 배치 형태를 1차원 배열로 파악하여 동일 브랜드 셀의 시작점부터 끝점까지의 두 가지 값을 기억하여 상자들을 기억하고 관리하는 것이 간편하다. 따라서 본 문제에서는 셀의 배치 형태를 일렬로 늘어선 1차원의 배열로 파악하고, 동일 브랜드의 상자끼리 묶는 것도 이 1차원 배열 상에서 묶이도록 한다<;그림 1>. 그러면, 본 연구문제의 목표는 새로 상품 상자를 입고할 때 1차원의 각 셀에 동일 브랜드의 상품 상자끼리 묶이도록 상품 상자들을 배치하되, 그때 상품 상자의 총 이동 횟수를 최소화 하는 것이 된다.
완화된 할당문제 모형의 해의 타당성을 검토하기 위하여 상용 패키지에 의해 푼 원래의 정수계획법 모형의 해와 수송문제 알고리즘에 의해 푼 완화된 할당문제 모형의 해를 비교 실험하였다. 실제적인 비교를 위해서는 셀의 수 7,000개, 브랜드 수 60개인 문제를 풀어서 비교해야 하지만 원래의 정수계획법 모형의 경우 상용 패키지가 풀 수 없으므로, 상용 패키지가 풀 수 있는 한계 내에서 셀수가 2,000, 2,500, 3,000, 3,500 및 4,000개, 브랜드 수가 17, 21, 25, 30 및 34개인 각각의 경우에 대해서 임의의 문제를 20개씩 생성하여 그 속도 및 최적해를 비교하였다. 실험에서 사용한 셀의 수 및 브랜드의 수는 실제 문제의 셀 수 7,000개 및 브랜드 수 60개에 비례하여 결정하였다.
완화된 할당문제 모형의 해의 타당성을 검토하기 위하여 상용 패키지에 의해 푼 원래의 정수계획법 모형의 해와 수송문제 알고리즘에 의해 푼 완화된 할당문제 모형의 해를 비교 실험하였다. 실제적인 비교를 위해서는 셀의 수 7,000개, 브랜드 수 60개인 문제를 풀어서 비교해야 하지만 원래의 정수계획법 모형의 경우 상용 패키지가 풀 수 없으므로, 상용 패키지가 풀 수 있는 한계 내에서 셀수가 2,000, 2,500, 3,000, 3,500 및 4,000개, 브랜드 수가 17, 21, 25, 30 및 34개인 각각의 경우에 대해서 임의의 문제를 20개씩 생성하여 그 속도 및 최적해를 비교하였다.
대상 데이터
실제적인 비교를 위해서는 셀의 수 7,000개, 브랜드 수 60개인 문제를 풀어서 비교해야 하지만 원래의 정수계획법 모형의 경우 상용 패키지가 풀 수 없으므로, 상용 패키지가 풀 수 있는 한계 내에서 셀수가 2,000, 2,500, 3,000, 3,500 및 4,000개, 브랜드 수가 17, 21, 25, 30 및 34개인 각각의 경우에 대해서 임의의 문제를 20개씩 생성하여 그 속도 및 최적해를 비교하였다. 실험에서 사용한 셀의 수 및 브랜드의 수는 실제 문제의 셀 수 7,000개 및 브랜드 수 60개에 비례하여 결정하였다.
성능/효과
그런데, LINDO, CPLEX 등 상용 최적화 패키지를 이용하여 문제 해결 시간을 검토해 보았을 때, 실제 의류 인터넷 쇼핑몰이 갖고 있는 컴퓨팅 환경인 2GHz CPU를 장착한 윈도우 XP PC에서 브랜드의 개수 43개, 셀의 수 5,000개 이내일 경우 약 4분 이내에 풀지만, 그 이상이 되면 풀지 못하는 것을 확인할 수 있었다( 참조).
이런 관점에서 문제의 크기가 커질 수로 완화문제가 정수계획법 모형에 비해 훨씬 짧은 시간 내에 해를 도출해 낼 수 있음을 알 수 있으며, 이러한 사실은 <표 2>를 통해서도 간접적으로나마 확인할 수 있다. 또한 실험결과 셀이 4,000개 일때 정수계획법이 완화문제에 비해 약 65초의 시간이 더 걸리지만, 움직여야 하는 상자의 개수가 약 2개 정도 늘어난 것에 대해 쇼핑몰의 입고 담당자는 상자 2개를 움직이는 데 수 십초이면 충분하며, 이러한 값의 차이는 셀의 개수가 늘어남에 따라 더욱 커질 것이라는 점에서 완화문제에 의한 해를 만족스럽게 받아들였다.
복잡성 측면에서 할당모형 문제는 최적해를 보장하는 앞의 정수계획법 문제보다 풀기 쉬운 것이 자명하다. 또한, 실제 창고에서 빈 셀의 개수가 전체 셀의 20～30% 이내로 유지되는 점을 고려하면 정수계획법 문제의 셀의 수가 7,000개, 변수 개수가 420,000개에 이르는 데 반하여, 할당모형 문제의 빈 셀의 수는 약 1,400～2,100개, 변수의 개수는 신규 입고 상자의 개수가 60개 일때 약 84,000～126,000개 정도로 현저히 문제의 크기도 줄어드는 것을 알 수 있다. 실제로 의류 인터넷 쇼핑몰 컴퓨팅 환경 하에서 브랜드의 개수 약 60개, 셀의 개수 약 7,000개의 문제를 할당모형 문제로 모형화하여 풀어보았을 때 약 10초 이내에 해를 찾아주는 것을 확인할 수 있었다.
<표 2>를 보면 먼저 속도 측면에서 문제 크기 별로 20개 문제를 푼 평균 시간이 정수계획법 모형의 경우 7.1, 10.55, 14.65, 20.4, 66.15초 등으로 기하급수적으로 증가하는 모습을 보이는데 반하여, 완화된 할당문제 모형의 경우 0.35, 0.25, 0.65, 0.95, 1.6초 등으로 정수계획법 모형에 비해 현저히 작으면서, 문제의 크기가 커질 때 상대적으로 적게 증가하는 것을 볼 수가 있다<;그림 5>.
40%로 증가한 것을 볼 수 있다<그림 6>. 이것은 평균 약 6.45%의 비율로 총비용이 증가한 것을 나타내며, 완화된 할당문제 모형이 정수계획법 모형에 비해 현저히 빠른 시간 내에 해를 구하며, 특히 정수계획법 문제가 셀 수 7,000개짜리 실제 문제를 풀지 못하는 것을 고려하면 상당히 만족스러운 것으로 평가되었다.
최적해의 측면에서 20개 문제의 평균 비용이 정수계획법 모형의 23.5, 35.7, 37.2, 45.4, 44.55 등의 최적값에 비하여 완화된 할당문제 모형의 경우 24.5, 37.7, 40.6, 50.2, 46.2 등으로 각각 104.30%, 105.27%, 109.20%, 110.07%, 103.40%로 증가한 것을 볼 수 있다<;그림 6>. 이것은 평균 약 6.
이렇게 얻어진 할당 문제 모형은 그 특성상 선형계획법 패키지에 의해서 빠른 시간 내에 풀릴 수 있으며, 또한 문제의 크기가 빈 셀의 수에 비례하므로 창고내 전체 셀의 크기가 커져도 원래의 최적화 모형과 달리 문제의 크기가 심각히 커지지 않는 다는 장점이 있다. 한편, 할당 문제로 완화된 모형은 최적해를 보장하지 못하는 문제가 있으나, 실험 결과 그 해가 충분히 만족스러운 것으로 판단되었다. 현재 이 방법론을 구현한 의류창고 입출고 관리 시스템이 ㈜아이에프네트워크의 패션플러스 쇼핑몰에 구축되어 사용되고 있다.
질의응답
핵심어
질문
논문에서 추출한 답변
주문 상품반출에 관한 주요 연구과제는 무엇인가?
주문된 상품들을 창고에서 꺼내는 과정을 효율화하기 위하여 주문 상품반출(Order picking)에 관한 기존 연구들은 크게 두 가지 측면에서 접근하고 있다. 하나는 재고 상품(SKU, Stock keeping unit)을 창고의 특정 위치에 배치(assign)하는 배치문제이며, 다른 하나는 SKU들의 배치가 주어진 상태에서 각 주문 상품을 반출하기 위해 창고를 돌아다니고, 상품 정보를 파악하거나, 기타 필요한 행동들을 하기 위해 소요되는 시간을 최소화하기 위해 유사한 주문끼리 묶는(Order batching) 문제이다(Brynzer, 1996; Koster et al., 2007).
주문묶음 문제는 무엇을 최소화하는 문제인가?
주문묶음(Order batching) 문제는 창고 내 상품 적재 선반의 배치 및 이에 따른 복도의 위치와 길이 등을 고려하여 주문 상품반출 지시서에 따른 한번의 작업동안 반출자(Order picker)가 움직여야 하는 동선의 길이의 평균을 최소화하는 문제로 모형화되며, 이러한 모형은 일반적으로 풀기가 매우 어려운 문제로 알려져 있다. 따라서, 지금까지의 연구들은 주로 주어진 상황을 고려하여 만족스러운 시간 내에 만족스러운 해를 찾아내는 휴리스틱의 개발에 초점을 맞추어 왔다.
의류 인터넷 쇼핑몰 상품 창고에서 상품들은 어떻게 보관되는가?
의류 인터넷 쇼핑몰 상품 창고에서 상품들은 동일 브랜드끼리 상자에 담긴 후 선반에 일렬로 보관된다. 상품 관리의 편의상, 상자들은 동일 브랜드끼리 묶여져 선반에 진열되어 있어야 한다.
참고문헌 (23)
Brynzer, H. and M. I. Johansson, "Storage location assignment：Using the product structure to reduce order picking times", Int. Journal of Production Economics, Vol.46-47(1996), 595-603.
Elsayed, E. A. and O. I. Unal, "Order batching algorithms and travel-time estimation for automated storage/retrieval systems", Int. Journal of Production Research, Vol.27, No.7(1989), 1097-1114.
Goetschalckx, M. and H. D. Ratliff, "An efficient algorithm to cluster order picking items in a wide aisle", Engineering Costs and Production Economics, Vol.13, No.4(1988), 263-271.
Goetschalckx, M. and R. Wei, "Bibliography on Order Picking Systems, Vol.1：1985-1992", 1994. Available on line at : www2.isye.gatech.edu/～mgoetsch/bibpick.ps, accessed May, 2010.
Graves, Stephen C., Warren H. Hausman, and LeRoy B. Schwarz, "Storage-Retrieval Interleaving in Automatic Warehousing Systems", Management Science, Vol.23, No.9(1977), 935-945.
Hausman, Warren H., LeRoy B. Schwarz, and Stephen C. Graves, "Optimal Storage Assignment in Automatic Warehousing Systems", Management Science, Vol.22, No.6(1976), 629-638.
Heragu, S. S., L. Du, R. J. Mantel, and P. C. Schuur, "Mathematical model for warehouse Design and Product Allocation", International Journal of Production Research, Vol.43, No.2(2005), 327-338.
Heskett, J. L., "Cube-per-order index-A key to warehouse stock location", Transportation and Distribution Management, Vol.3, No.1(1963), 27-31.
Jewkes, Elizabeth, Chulung Lee, and Ray Vickson, "Product Location, Allocation and Server Home based Location for an Order Picking Line with Multiple Servers", Computers and Operations Research, Vol.31(2004), 623-636.
Jane, Chin Chia, "Storage location assignment in a distribution center", International Journal of Physical Distribution and Logistics Management, Vol.30, No.1(2000), 55-71.
Koster, Rene de, Tho Le-Duc, and Kees Jan Roodbergen, "Design and Control of Warehouse Order Picking：A Literature Review", European Journal of Operations Reseach, Vol.182(2007), 481-501.
Knuth, D. E., The Art of Computer Programming 3rd Edition, Volume 1 Fundamental Algorithms, Addison-Wesley, New York, NY, 1997.
Le-Duc, T. and R.(M.) B. M. De Koster, "Travel Distance Estimation and Storage Zone Optimization in a 2-block Class-based Storage Strategy Warehouse", International Journal of Production Research, Vol.43, No.17(2005), 3561-3581.
Little, T. D. C. and D. Venkatesh, "Popularity-Based Assignment of Movies to Storage Devices in a Video-on-Demand System", MCL Technical Report, 05-01-1994, 1994.
Malmborg, C. J. and B. Krishnakumar, "Optimal Storage Assignment Policies for Multiaddress Warehousing Systems", IEEE Transactions on Systems, Man, and Cybernetics, Vol.19, No.1(1989), 197-204.
Merkuryev, Y., A. Burinskiene, and G. Merkuryeva, "Warehouse Order Picking Process", In: Merkuryev, Yuri, Galina Merkuryeva, Miquel Angel Piera, and Antoni Guasch(Eds.) Simulation-Based Case Studies in Logistics: Education and Applied Research, Springer, London, 2009, 147-165.
Muralidharan, B., R. J. Linn, and R. Pandit, "Shuffling heuristics for the storage location assignment in an AS/RS", Int. Journal of Production Research, Vol.33, No.6(1995), 1661-1672.
Petersen, C. G., "An evaluation of order picking routing policies", International Journal of Operations and Production Management, Vol.17, No.11(1997), 1098-1111.
Petersen, C. G. and Schmenner R. W., An evaluation of routing and volume-based storage policies in an order picking operation, Decision Sciences, Vol.30, No.2(1999), 481-501.
Roodbergen, K. J., Layout and routing methods for warehouses. Erasmus Research Institute of Management, Erasmus University, Rotterdam, 2001.
White, J. A. and H. D. Kinney, "Storage and Warehousing", In Handbook of Industrial Engineering, Chapter 10.4, G. Salvendy(ed.), John Wiley and Sons, New York, NY, 1982.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.