WMS를 위한 이산 수학: 셀 내 상품 압축 알고리즘(1부)

이 기사에서는 창고의 여유 셀 부족 문제를 어떻게 해결했는지, 그리고 이러한 문제를 해결하기 위한 개별 최적화 알고리즘을 개발했는지 설명합니다. 최적화 문제의 수학적 모델을 어떻게 "구축"했는지, 그리고 알고리즘의 입력 데이터를 처리할 때 예상치 못한 어려움에 대해 이야기해 보겠습니다.

비즈니스에 수학을 적용하는 데 관심이 있고 5학년 수준에서 공식의 엄격한 정체성 변환을 두려워하지 않는다면 고양이에 오신 것을 환영합니다!

이 기사는 구현하는 사람들에게 유용할 것입니다. WMS-시스템, 창고 또는 생산 물류 업계에서 근무하는 사람, 비즈니스에 수학을 적용하고 기업의 프로세스를 최적화하는 데 관심이 있는 프로그래머.

입문부분

이 간행물은 창고 프로세스에서 최적화 알고리즘을 구현하는 성공적인 경험을 공유하는 일련의 기사입니다.

В 이전 기사 우리가 구현한 창고의 세부 사항을 설명합니다. WMS-시스템, 또한 구현 중에 남은 제품의 배치를 클러스터링하는 문제를 해결해야 했던 이유를 설명합니다. WMS-시스템, 그리고 우리가 그것을 어떻게 했는지.

최적화 알고리즘에 대한 기사 작성을 마쳤을 때 그 내용이 매우 큰 것으로 판명되었으므로 축적된 자료를 두 부분으로 나누기로 결정했습니다.

• 첫 번째 부분(이 기사)에서는 문제의 수학적 모델을 어떻게 "구축"했는지, 그리고 알고리즘의 입력 데이터를 처리하고 변환할 때 예상치 못한 큰 어려움에 대해 이야기하겠습니다.
• 두 번째 부분에서는 언어로 알고리즘을 구현하는 방법을 자세히 고려할 것입니다. C + +, 우리는 컴퓨터 실험을 수행하고 고객의 비즈니스 프로세스에서 이러한 "지능형 기술"을 구현하는 동안 얻은 경험을 요약할 것입니다.

기사를 읽는 방법. 이전 기사를 읽었다면 즉시 "기존 솔루션 개요" 장으로 이동할 수 있으며, 그렇지 않은 경우 해결 중인 문제에 대한 설명이 아래 스포일러에 있습니다.

고객 창고에서 해결 중인 문제에 대한 설명

프로세스의 병목 현상

2018년에는 구현 프로젝트를 완료했습니다. WMS-Chelyabinsk의 창고 "Trading House "LD"에 있는 시스템. 우리는 1개 작업장을 위해 "3C-물류: 창고 관리 20" 제품을 구현했습니다. WMS, 점주, 지게차 운전사. 평균 창고 면적은 약 4m2이고, 셀 수는 5000개, SKU 수는 4500개입니다. 창고에는 1kg에서 400kg까지 다양한 크기의 당사 자체 생산 볼 밸브가 보관되어 있습니다. FIFO에 따라 상품을 선택해야 하기 때문에 창고의 재고는 일괄적으로 저장됩니다.

창고 프로세스 자동화 계획을 설계하는 동안 우리는 최적이 아닌 재고 보관이라는 기존 문제에 직면했습니다. 크레인 보관 및 부설의 세부 사항은 하나의 단위 저장 셀에 한 배치의 품목만 담을 수 있다는 것입니다(그림 1 참조). 제품은 매일 창고에 도착하며 각 도착은 별도의 배치로 이루어집니다. 각각 별도의 셀에 저장해야 함에도 불구하고 총 1개월 동안 창고를 운영한 결과 30개의 별도 배치가 생성되었습니다. 제품은 전체 팔레트가 아닌 조각으로 선택되는 경우가 많으며 결과적으로 많은 셀의 조각 선택 영역에서 다음 그림이 관찰됩니다. 부피가 1m3 이상인 셀에는 여러 조각의 크레인이 있습니다. 세포 부피의 5~10% 미만을 차지합니다.

그림 1. 셀의 여러 조각 사진

스토리지 용량이 최적으로 사용되지 않는 것은 분명합니다. 재난의 규모를 상상하기 위해 수치를 제시할 수 있습니다. 평균적으로 창고 운영의 다양한 기간 동안 "미소" 잔고를 가진 1m3 이상의 부피를 가진 100~300개의 셀이 있습니다. 창고가 상대적으로 작기 때문에 창고 성수기에는 이 요인이 "병목 현상"을 일으키고 창고의 인수 및 배송 프로세스를 크게 지연시킵니다.

문제 해결 아이디어

아이디어가 생겼습니다. 날짜가 가장 가까운 남은 음식 묶음은 하나의 단일 묶음으로 줄여야 하며, 통일된 배치가 포함된 남은 음식은 하나의 셀에 촘촘하게 함께 배치해야 하며, 하나의 셀에 공간이 충분하지 않은 경우 여러 셀에 배치해야 합니다. 남은 음식의 전체 양. 이러한 "압축"의 예가 그림 2에 나와 있습니다.

그림 2. 세포 내 잔류물을 압축하는 방식

이를 통해 새 상품을 배치하는 데 사용되는 점유 창고 공간을 크게 줄일 수 있습니다. 창고 용량이 과부하된 상황에서는 이러한 조치가 매우 필요합니다. 그렇지 않으면 새 상품을 수용할 여유 공간이 충분하지 않아 창고 배치 및 보충 프로세스가 중단될 수 있으며 결과적으로 접수 및 배송이 중단됩니다. 이전에는 WMS 시스템을 구현하기 전에는 이러한 작업을 수동으로 수행했는데, 이는 셀에서 적절한 잔액을 검색하는 과정이 상당히 길기 때문에 비효율적이었습니다. 이제 WMS 시스템의 도입으로 프로세스를 자동화하고 속도를 높이며 지능적으로 만들기로 결정했습니다.

이러한 문제를 해결하는 과정은 2단계로 나뉩니다.

• 첫 번째 단계에서는 압축 날짜가 가까운 배치 그룹을 찾습니다(이 작업 전용). 이전 기사);
• 두 번째 단계에서는 각 배치 그룹에 대해 셀에 남아 있는 제품의 가장 컴팩트한 배치를 계산합니다.

현재 기사에서는 알고리즘의 두 번째 단계에 중점을 둘 것입니다.

기존 솔루션 검토

우리가 개발한 알고리즘에 대한 설명으로 넘어가기 전에 이미 시장에 존재하는 시스템에 대한 간략한 개요를 살펴보는 것이 좋습니다. WMS, 유사한 최적의 압축 기능을 구현합니다.

우선, “1C: Enterprise 8. WMS Logistics.”라는 제품에 주목할 필요가 있습니다. 4C가 소유하고 복제하며 1세대에 속하는 창고 관리 XNUMX" WMS-AXELOT에서 개발한 시스템. 이 시스템은 서로 다른 제품을 하나의 공통 셀에 통합하도록 설계된 압축 기능을 요구합니다. 이러한 시스템의 압축 기능에는 ABC 클래스에 따라 셀의 상품 배치를 수정하는 등의 다른 가능성도 포함되어 있다는 점을 언급할 가치가 있지만 이에 대해서는 다루지 않겠습니다.

1C : Enterprise 8. WMS Logistics 시스템의 코드를 분석하면. 창고 관리 4"(이 부분의 기능이 열려 있음)를 통해 다음과 같은 결론을 내릴 수 있습니다. 잔여 압축 알고리즘은 다소 원시적인 선형 논리를 구현하며 "최적의" 압축에 대해서는 말할 수 없습니다. 당연히 정당의 클러스터링을 제공하지 않습니다. 이러한 시스템을 구현한 몇몇 고객은 압축 계획의 결과에 대해 불만을 토로했습니다. 예를 들어 실제로 압축하는 동안 다음과 같은 상황이 자주 발생했습니다. 100개. 남은 물품을 한 셀에서 1개가 있는 다른 셀로 이동할 계획입니다. 시간 소비 측면에서는 그 반대를 수행하는 것이 최적이지만.

또한, 셀에 남은 물품을 압축하는 기능은 해외에서도 많이 선언되고 있습니다. WMS-시스템이지만 불행하게도 우리는 알고리즘의 효율성(영업 비밀)에 대한 실제 피드백이 없으며 논리의 깊이(독점 폐쇄 소스 소프트웨어)에 대한 아이디어도 없기 때문에 판단할 수 없습니다.

문제의 수학적 모델 검색

문제 해결을 위한 고품질 알고리즘을 설계하려면 먼저 이 문제를 수학적으로 명확하게 공식화하는 것이 필요하며, 이것이 우리가 할 일입니다.

세포가 많다 , 일부 상품의 잔해가 포함되어 있습니다. 다음에서는 그러한 세포를 기증자 세포라고 부르겠습니다. 나타내자 셀 안의 물품 부피 $.

한 배치의 단 하나의 제품 또는 이전에 클러스터로 결합된 여러 배치를 말하는 것이 중요합니다(읽기: 이전 기사) 이는 상품 보관 및 보관의 특성 때문입니다. 다양한 제품이나 다양한 배치 클러스터는 자체적인 별도의 압축 절차를 실행해야 합니다.

세포가 많다 , 기증자 세포의 잔류물이 잠재적으로 배치될 수 있습니다. 우리는 이러한 셀을 컨테이너 셀이라고 더 부르겠습니다. 이는 창고에 있는 자유 셀이거나 다양한 기증자 셀일 수 있습니다. . 항상 넉넉하다 부분집합이다 .

각 셀에 대해 많은 사람들로부터 용량 제한이 설정되었습니다. , dm3 단위로 측정됩니다. 3dm10은 한 변의 길이가 XNUMXcm인 정육면체인데, 창고에 보관된 제품의 양이 꽤 크기 때문에 이 경우에는 이 정도의 구분만으로도 충분합니다.

최단 거리의 행렬이 주어지면 각 셀 쌍 사이의 미터 단위 어디에서 и 세트에 속한다 и 각각.

나타내자 셀에서 물품을 이동하는 데 드는 "비용" 세포로 . 나타내자 컨테이너를 선택하는 데 드는 "비용" 다른 세포의 잔여물을 그 세포로 옮기는 것입니다. 값이 얼마나 정확하고 어떤 측정 단위로 계산되는지 и 우리는 더 고려할 것입니다 (입력 데이터 준비 섹션 참조). 지금은 그러한 값이 값에 정비례한다고 말하는 것으로 충분합니다 и 각각.

로 나타내다 나머지가 셀에 있는 경우 값 1을 취하는 변수 컨테이너로 옮겼습니다 , 그렇지 않으면 0입니다. 다음으로 나타내자 컨테이너가 있는 경우 값 1을 취하는 변수 남은 상품을 포함하고 그렇지 않으면 0입니다.

임무는 다음과 같다: 너무 많은 컨테이너를 찾아야 합니다. 따라서 기능을 최소화하기 위해 기증자 세포를 용기 세포에 "부착"합니다.

제한을 받고 있는

전체적으로 문제에 대한 해결책을 계산할 때 우리는 다음을 위해 노력합니다.

• 첫째, 저장 용량을 절약하기 위해;
• 둘째, 점주들의 시간을 절약하기 위해서입니다.

마지막 제한은 우리가 선택하지 않은 컨테이너로 상품을 이동할 수 없으므로 선택에 대한 "비용"이 발생하지 않음을 의미합니다. 이 제한은 또한 셀에서 컨테이너로 이동되는 상품의 양이 컨테이너의 용량을 초과해서는 안 된다는 것을 의미합니다. 문제를 해결한다는 것은 일련의 컨테이너를 의미합니다. 및 기증자 세포를 용기에 부착하는 방법.

최적화 문제의 이러한 공식화는 새로운 것이 아니며 지난 세기 80년대 초반부터 많은 수학자에 의해 연구되어 왔습니다. 외국 문헌에는 적절한 수학적 모델에 대한 두 가지 최적화 문제가 있습니다. 단일 소스 용량 시설 위치 문제 и 다중 소스 용량 시설 위치 문제 (나중에 작업의 차이점에 대해 이야기하겠습니다). 수학 문헌에서 이러한 두 가지 최적화 문제의 공식화는 기업의 지상 위치 측면에서 공식화되므로 "시설 위치"라는 이름이 붙었습니다. 대부분의 경우 이는 전통에 대한 찬사입니다. 처음으로 이러한 조합 문제를 해결해야 할 필요성이 물류 분야, 주로 지난 세기 50년대 군산업 부문에서 나왔기 때문입니다. 기업 위치 ​​측면에서 이러한 작업은 다음과 같이 공식화됩니다.

• 잠재적으로 제조업 기업을 유치할 수 있는 도시(이하 '제조도시'라 함)는 한정되어 있습니다. 각 제조 도시마다 기업을 설립하는 데 드는 비용과 기업의 생산 능력에 대한 제한이 명시되어 있습니다.
• 클라이언트가 실제로 위치한 도시(이하 클라이언트 도시)는 한정되어 있습니다. 각 고객 도시에 대해 제품 수요량이 지정됩니다. 단순화를 위해 기업이 생산하고 고객이 소비하는 제품은 단 하나뿐이라고 가정하겠습니다.
• 도시-제조업체와 도시-고객의 각 쌍에 대해 제조업체에서 고객에게 필요한 양의 제품을 전달하는 데 드는 운송 비용의 가치가 지정됩니다.

다음을 수행하려면 사업체를 개설할 도시와 그러한 사업체에 고객을 연결하는 방법을 찾아야 합니다.

• 기업 개업에 드는 총 비용과 운송 비용은 최소화되었습니다.
• 개방형 기업에 배정된 고객의 수요량은 해당 기업의 생산 능력을 초과하지 않았습니다.

이제 이 두 가지 고전적 문제의 유일한 차이점을 언급할 가치가 있습니다.

• 단일 소스 용량 시설 위치 문제 – 클라이언트는 단 하나의 개방형 시설에서만 공급됩니다.
• 다중 소스 용량 시설 위치 문제 – 클라이언트는 동시에 여러 개방 시설에서 공급을 받을 수 있습니다.

두 문제 사이의 이러한 차이는 언뜻 보기에는 중요하지 않지만 실제로는 이러한 문제의 완전히 다른 조합 구조로 이어지며 결과적으로 문제를 해결하기 위한 완전히 다른 알고리즘이 생성됩니다. 작업 간의 차이점은 아래 그림에 나와 있습니다.

그림 3. a) 다중 소스 용량 시설 위치 문제

그림 3. b) 단일 소스 용량 시설 위치 문제

두 작업 모두 -어려움, 즉 입력 데이터 크기의 시간 다항식에서 이러한 문제를 해결할 정확한 알고리즘이 없습니다. 간단히 말해서, 문제 해결을 위한 모든 정확한 알고리즘은 옵션을 완전히 검색하는 것보다 빠르긴 하지만 기하급수적으로 작동합니다. 임무 이후로 -어려운 경우 대략적인 경험적 방법, 즉 최적에 매우 가까운 솔루션을 지속적으로 계산하고 매우 빠르게 작동하는 알고리즘만 고려합니다. 그러한 작업에 관심이 있다면 여기에서 러시아어로 된 좋은 개요를 찾을 수 있습니다.

세포 내 상품의 최적 압축 문제에 대한 용어로 전환하면 다음과 같습니다.

• 고객 도시는 기증자 세포입니다 남은 상품으로,
• 제조 도시 - 컨테이너 셀 , 다른 셀의 나머지 부분이 배치되도록 가정됩니다.
• 운송 비용 - 시간 비용 기증자 세포에서 물품의 양을 옮기는 점주 컨테이너 셀에 ;
• 사업 개시 비용-컨테이너 선택 비용 , 컨테이너 셀의 부피와 동일 , 자유 볼륨을 저장하기 위한 특정 계수를 곱합니다(계수 값은 항상 > 1입니다)(입력 데이터 준비 섹션 참조).

문제에 대한 잘 알려진 고전적 솔루션과의 유추를 그린 후에는 솔루션 알고리즘의 아키텍처 선택이 좌우되는 중요한 질문에 대답해야 합니다. 기증자 셀에서 나머지를 이동하는 것은 하나만 가능합니다. 하나의 컨테이너만(Single-Source), 아니면 나머지를 여러 컨테이너 셀(Multi-Source)로 이동할 수 있습니까?

실제로 문제에 대한 두 가지 공식이 모두 발생한다는 점은 주목할 가치가 있습니다. 아래에는 이러한 각 설정에 대한 모든 장단점이 나와 있습니다.

문제 변형	옵션의 장점	옵션의 단점
단일 소스	이 문제 변형을 사용하여 계산된 상품 이동 작업: 상점 주인의 통제가 덜 필요합니다(한 셀에서 모든 것을 가져오고 모든 것을 다른 컨테이너 셀에 넣음). 이는 다음과 같은 위험을 제거합니다. "셀에 넣기" 작업을 수행할 때 상품 수량을 다시 계산할 때 오류; 재계산된 수량을 TSD에 입력하는 중 오류가 발생했습니다. "셀에 넣기" 작업을 수행할 때 상품 수를 다시 계산하고 TSD에 입력하는 데 시간이 필요하지 않습니다.
다중 소스	이 버전의 문제를 사용하여 계산된 압축은 일반적으로 "단일 소스" 옵션을 사용하여 계산된 압축에 비해 10-15% 더 컴팩트합니다. 그러나 기증자 세포의 잔기 수가 적을수록 밀도의 차이도 작아집니다.	이 문제 변형을 사용하여 계산된 상품 이동 작업: 점주 측에서 더 큰 통제가 필요하므로(계획된 각 컨테이너 셀로 이동된 상품 수량을 다시 계산해야 함), 이를 통해 상품 수량을 다시 계산하고 TSD에 데이터를 입력할 때 오류가 발생할 위험이 없습니다. 셀에 넣기” 작업 "셀에 넣기" 작업 수행 시 상품 개수를 다시 계산하는 데 시간이 걸립니다. "셀에 넣기" 작업을 수행할 때 "오버헤드"(중지, 팔레트로 이동, 컨테이너 셀의 바코드 스캔)에 시간이 걸립니다. 때때로 알고리즘은 이미 적합한 제품을 보유하고 있는 다수의 컨테이너 셀 간에 거의 완전한 팔레트의 수량을 "분할"할 수 있는데, 이는 고객의 관점에서 받아들일 수 없는 일입니다.

표 1. 단일 소스 및 다중 소스 옵션의 장단점

단일 소스 옵션에는 더 많은 장점이 있고 기증자 세포의 잔여물 수가 적을수록 문제의 두 변형에 대해 계산된 압축 압축 정도의 차이가 더 작다는 사실을 고려하여 우리의 선택은 다음과 같습니다. 단일 소스 옵션 소스.

다중 소스 옵션에 대한 솔루션도 발생한다고 말할 가치가 있습니다. 이를 해결하기 위한 효과적인 알고리즘이 많이 있으며, 그 중 대부분은 여러 전송 문제를 해결하는 데 사용됩니다. 효율적인 알고리즘뿐만 아니라 우아한 알고리즘도 있습니다. 예를 들어, 여기에.

입력 데이터 준비

문제 해결을 위한 알고리즘 분석 및 개발을 시작하기 전에 어떤 데이터를 어떤 형식으로 입력으로 제공할지 결정해야 합니다. 기증자 셀에 남아 있는 제품의 양과 컨테이너 셀의 용량에는 문제가 없습니다. 이는 사소하기 때문입니다. 이러한 수량은 m3 단위로 측정되지만 컨테이너 셀 사용 비용과 이동 비용 매트릭스가 전부는 아닙니다. 정말 간단해요!

먼저 계산을 살펴보겠습니다. 물건을 옮기는 데 드는 비용 기증자 세포에서 컨테이너 세포로. 우선, 이동 비용을 계산할 측정 단위를 결정하는 것이 필요합니다. 가장 확실한 두 가지 옵션은 미터와 초입니다. "순수한" 미터로 여행 비용을 계산하는 것은 의미가 없습니다. 이를 예를 통해 보여드리겠습니다. 세포를 보자 첫 번째 계층인 셀에 위치 30미터 떨어져 있으며 두 번째 층에 위치합니다.

• 다음에서 이동 в 이사하는 것보다 비싸다 в , 두 번째 층(바닥에서 1,5-2m)에서 내려가는 것이 두 번째 층으로 올라가는 것보다 쉽기 때문에 거리는 동일하지만;
• 1개를 이동합니다. 세포에서 나온 물건 в 10개를 옮기는 것보다 쉬울 거예요. 동일한 제품이지만 거리는 동일합니다.

이동 비용을 초 단위로 고려하는 것이 좋습니다. 이를 통해 계층 차이와 이동된 상품 수량의 차이를 모두 고려할 수 있기 때문입니다. 초 단위의 이동 비용을 계산하려면 이동 작업을 기본 구성 요소로 분해하고 각 기본 구성 요소의 실행에 대한 시간을 측정해야 합니다.

셀에서하자 움직임 PC. 컨테이너에 담긴 물품 . 하자 – 창고 내 작업자의 평균 이동 속도(m/초로 측정) 허락하다 и – 일회성 작업의 평균 속도는 각각 4dm3(직원이 작업을 수행할 때 창고에서 한 번에 가져가는 평균 볼륨)에 해당하는 상품 볼륨에 대해 취하고 적용합니다. 허락하다 и take 및 put 작업이 각각 수행되는 셀의 높이입니다. 예를 들어, 첫 번째 층(바닥)의 평균 높이는 1m, 두 번째 층은 2m 등입니다. 그러면 이동 작업을 완료하는 데 걸리는 총 시간을 계산하는 공식은 다음과 같습니다. 다음:

표 2는 보관 물품의 특성을 고려하여 창고 직원이 수집한 각 기본 작업의 실행 시간에 대한 통계를 보여줍니다.

작업의 이름	지정	평균
창고를 돌아다니는 작업자의 평균 속도		1,5 m / s
4회 작업의 평균 속도(제품 용량 3dmXNUMX의 경우)		2,4 초

표 2. 창고 운영을 완료하는 데 걸리는 평균 시간

이사비용 계산방법을 결정했습니다. 이제 계산 방법을 알아내야 합니다. 컨테이너 셀 선택 비용. 여기의 모든 것은 이사 비용보다 훨씬 더 복잡합니다. 그 이유는 다음과 같습니다.

• 첫째, 비용은 세포의 부피에 직접적으로 의존해야 합니다. 기증자 세포에서 옮겨진 동일한 부피의 잔류물은 큰 용기보다 작은 부피의 용기에 넣는 것이 더 좋습니다. 단, 그러한 부피가 두 용기에 완전히 들어맞으면 됩니다. 따라서 컨테이너 선택에 드는 총 비용을 최소화함으로써 셀에 제품을 배치하는 후속 작업을 수행하기 위해 선택 영역의 "부족한" 여유 저장 용량을 절약하려고 노력합니다. 그림 4는 잔류물을 크고 작은 용기로 옮기는 옵션과 후속 창고 운영에서 이러한 운반 옵션의 결과를 보여줍니다.
• 둘째, 원래 문제를 해결하려면 총 비용을 정확히 최소화해야 하며 이는 이동 비용과 컨테이너 선택 비용의 합이므로 입방 미터 단위의 셀 부피는 어떻게든 초와 연결되어야 합니다. 이는 결코 사소한 일이 아닙니다.

쌀. 4. 남은 음식을 다양한 용량의 용기로 옮기는 옵션.

그림 4는 후속 상품을 배치하는 두 번째 단계에서 더 이상 컨테이너에 맞지 않는 남은 음식의 양을 빨간색으로 보여줍니다.

컨테이너를 선택하기 위한 입방미터 비용을 문제에 대한 계산된 솔루션에 대한 다음 요구 사항을 이동하기 위한 비용(초)과 연결하는 데 도움이 됩니다.

• 제품을 담는 용기 용기의 총 수가 감소하는 경우 어떤 경우에도 기증 용기의 잔액을 용기 용기로 옮겨야 합니다.
• 컨테이너의 부피와 이동에 소요되는 시간 사이의 균형을 유지해야 합니다. 예를 들어 이전 솔루션과 비교하여 문제에 대한 새로운 솔루션의 경우 볼륨 증가는 크지만 시간 손실은 작습니다. , 그러면 새로운 옵션을 선택해야 합니다.

마지막 요구 사항부터 시작하겠습니다. '균형'이라는 모호한 단어를 명확히 하기 위해 창고 직원을 대상으로 설문조사를 실시하여 다음과 같은 사실을 알아냈습니다. 볼륨의 컨테이너 셀이 있게 해주세요. , 기증자 세포에서 남은 물품의 이동이 할당되고 해당 이동의 총 시간은 다음과 같습니다. . 동일한 기증자 셀의 동일한 양의 상품을 다른 컨테이너에 배치하기 위한 몇 가지 대체 옵션이 있습니다. 각 배치에는 자체 추정치가 있습니다. 어디에서 < и 어디에서 >.

질문이 제기됩니다. 볼륨의 최소 이득은 얼마입니까? 주어진 시간 손실 값에 대해 허용 가능 ? 예를 들어 설명해 보겠습니다. 처음에는 유해를 1000dm3(1m3) 용량의 용기에 담을 예정이었고 이송 시간은 70초였습니다. 잔여물을 500dm3 용량과 130초의 시간으로 다른 용기에 담을 수 있는 옵션이 있습니다. 질문: 60dm500의 여유 부피를 절약하기 위해 점주가 상품을 옮기는 데 추가로 3초의 시간을 할애할 준비가 되어 있습니까? 창고 직원을 대상으로 한 설문 조사 결과를 바탕으로 다음 다이어그램이 작성되었습니다.

쌀. 5. 작동 시간 차이의 증가에 따른 최소 허용량 절감량의 의존성 다이어그램

즉, 추가 시간 비용이 40초라면 볼륨 증가가 최소 500dm3 이상인 경우에만 이를 사용할 준비가 된 것입니다. 의존성에 약간의 비선형성이 있음에도 불구하고 추가 계산을 단순화하기 위해 수량 간의 의존성은 선형이며 부등식으로 설명된다고 가정합니다.

아래 그림에서는 컨테이너에 상품을 넣는 다음과 같은 방법을 고려합니다.

쌀. 6. 옵션 (a): 용기 2개, 총 부피 400 dm3, 총 시간 150초.

쌀. 6. 옵션 (b): 용기 2개, 총 부피 600 dm3, 총 시간 190초.

쌀. 6. 옵션 (c): 용기 1개, 총 부피 400 dm3, 총 시간 200초.

컨테이너를 선택하는 옵션 (a)가 원래 옵션보다 더 선호됩니다. 왜냐하면 부등식은 (800-400)/10>=150-120이며 이는 40 >= 30을 의미합니다. 옵션 (b)는 원래 옵션보다 덜 선호됩니다. option , 부등식이 성립하지 않기 때문에: (800-600)/10>=190-150 이는 20 >= 40을 의미합니다. 그러나 옵션 (c)는 그러한 논리에 맞지 않습니다! 이 옵션을 더 자세히 고려해 보겠습니다. 한편으로 부등식 (800-400)/10>=200-120은 부등식 40 >= 80이 충족되지 않음을 의미하며, 이는 볼륨의 증가가 시간의 큰 손실만큼 가치가 없음을 시사합니다.

그러나 반면에 이 옵션 (c)에서는 점유된 전체 부피를 줄일 뿐만 아니라 점유된 셀 수도 줄입니다. 이는 위에 나열된 문제에 대한 계산 가능한 솔루션을 위한 두 가지 중요한 요구 사항 중 첫 번째입니다. 분명히, 이 요구 사항이 충족되기 시작하려면 부등식의 왼쪽에 양의 상수를 추가해야 합니다. , 이러한 상수는 컨테이너 수가 감소하는 경우에만 추가하면 됩니다. 이를 상기시켜 드리겠습니다. 컨테이너가 있을 때 1과 같은 변수입니다. 선택됨, 컨테이너인 경우 0 선택되지 않은. 나타내자 – 초기 솔루션의 많은 컨테이너 및 – 새로운 솔루션에는 많은 컨테이너가 있습니다. 일반적으로 새로운 부등식은 다음과 같습니다.

위의 불평등을 변환하면, 우리는 다음을 얻습니다:

이를 바탕으로 총 비용을 계산하는 공식이 있습니다. 문제에 대한 몇 가지 해결책:

하지만 이제 질문이 생깁니다.: 그러한 상수는 어떤 값을 가져야 합니까? ? 분명히 그 값은 문제 해결을 위한 첫 번째 요구 사항을 항상 충족할 수 있을 만큼 충분히 커야 합니다. 물론 상수 값을 103 또는 106으로 간주할 수 있지만 저는 그러한 "마법의 숫자"를 피하고 싶습니다. 창고 운영 수행의 세부 사항을 고려하면 그러한 상수 값에 대한 몇 가지 근거 있는 수치 추정을 계산할 수 있습니다.

하자 – 한 구역 ABC의 창고 셀 사이의 최대 거리는 우리의 경우 100m와 같습니다. – 창고 내 컨테이너 셀의 최대 부피는 1000dm3입니다.

가치를 계산하는 첫 번째 방법 . 첫 번째 계층에 2개의 컨테이너가 있고 그 안에 상품이 이미 물리적으로 위치해 있는 상황, 즉 컨테이너 자체가 기증자 셀이고 상품을 동일한 셀로 이동하는 데 드는 비용이 당연히 0인 상황을 생각해 보겠습니다. 그러한 상수 값을 찾는 것이 필요합니다. , 남은 음식을 항상 용기 1에서 용기 2로 옮기는 것이 유리할 것입니다. 값을 대체합니다. и 위에 주어진 부등식에서 우리는 다음을 얻습니다:

다음에서

위의 공식에 기본 작업을 수행하는 데 소요되는 평균 시간 값을 대입하면 다음과 같습니다.

가치를 계산하는 두 번째 방법 . 다음과 같은 상황을 생각해 보자. 물품을 컨테이너 1로 옮길 계획인 기증자 세포. – 기증자 세포로부터의 거리 컨테이너 1에. 이미 상품이 들어 있고 나머지 모든 상품을 수용할 수 있는 볼륨인 컨테이너 2도 있습니다. 세포. 단순화를 위해 기증자 세포에서 컨테이너로 이동된 상품의 양이 동일하고 같다고 가정합니다. . 그러한 상수 값을 구하는 것이 필요합니다. , 여기서 모든 나머지 부분의 배치는 컨테이너 2에 셀을 넣는 것이 다른 컨테이너에 넣는 것보다 항상 더 수익성이 높습니다.

우리가 얻는 불평등의 변화

수량의 가치를 '강화'하기 위해 , 다음과 같이 가정해보자 = 0. 창고 잔액을 압축하는 절차에 일반적으로 포함되는 평균 셀 수는 10입니다. 알려진 수량 값을 대체하면 다음과 같은 상수 값이 있습니다.

각 옵션에 대해 계산된 가장 큰 값을 취합니다. 이것이 수량의 값이 됩니다. 주어진 창고 매개변수에 대해. 이제 완전성을 위해 총 비용 계산 공식을 적어 보겠습니다. 실현 가능한 솔루션을 위해 :

이제 결국 엄청난 노력 입력 데이터를 변환함으로써 모든 입력 데이터가 원하는 형태로 변환되었으며 최적화 알고리즘에 사용할 준비가 되었다고 말할 수 있습니다.

결론

실습에서 알 수 있듯이 알고리즘에 대한 입력 데이터를 준비하고 변환하는 단계의 복잡성과 중요성은 종종 과소평가됩니다. 이 기사에서 우리는 고품질의 지능적으로 준비된 입력 데이터만이 알고리즘에 의해 계산된 결정을 클라이언트에게 진정으로 가치 있게 만들 수 있다는 것을 보여주기 위해 이 단계에 특히 많은 관심을 기울였습니다. 예, 많은 파생 공식이 있었지만 카타 이전에도 경고했습니다 :)

다음 기사에서는 이전 2개의 출판물이 의도한 것이 무엇인지(이산 최적화 알고리즘)에 대해 마침내 설명하겠습니다.

기사를 준비했습니다
프로젝트 부서의 프로그래머인 Roman Shangin은
First Bit 회사, 첼랴빈스크

출처 : habr.com