🍿 🚴 🖌️ WMS के लिए असतत गणित: कोशिकाओं में सामान को संपीड़ित करने के लिए एल्गोरिथ्म (भाग 2) 💶 🎺 💤

लेख में, हम वर्णन करेंगे कि हमने कोशिकाओं में शेष माल के इष्टतम संपीड़न के लिए एक एल्गोरिदम कैसे विकसित किया। हम आपको बताएँगे कि फ्रेमवर्क चिड़ियाघर पर्यावरण के आवश्यक मेटाहॉरलिस्टिक्स का चयन कैसे करें: वर्जित खोज, आनुवंशिक एल्गोरिथ्म, चींटी कॉलगर्ल, आदि।

हम एल्गोरिथम के संचालन समय और सटीकता का विश्लेषण करने के लिए एक कम्प्यूटेशनल प्रयोग करेंगे। ग्राहक की व्यावसायिक प्रक्रियाओं में "स्मार्ट प्रौद्योगिकियों" के अनुकूलन और कार्यान्वयन की इस समस्या को हल करने में प्राप्त मूल्यवान अनुभव को हम संक्षेप में प्रस्तुत करते हैं।

लेख उन लोगों के लिए उपयोगी होगा जो बुद्धिमान प्रौद्योगिकियों को लागू करते हैं, गोदाम या उत्पादन रसद उद्योग में काम करते हैं, साथ ही प्रोग्रामर जो व्यवसाय में गणित के अनुप्रयोगों और उद्यम में प्रक्रिया अनुकूलन में रुचि रखते हैं।

परिचयात्मक भाग

यह प्रकाशन लेखों की श्रृंखला को जारी रखता है जिसमें हम गोदाम प्रक्रियाओं में अनुकूलन एल्गोरिदम को लागू करने में अपने सफल अनुभव को साझा करते हैं। पिछले प्रकाशन:

कैसे एक लेख पढ़ने के लिए। यदि आप पिछले लेख पढ़ते हैं, तो आप तुरंत "समस्या को हल करने के लिए एक एल्गोरिथ्म का विकास" अध्याय पर आगे बढ़ सकते हैं, यदि नहीं, तो बिगाड़ने में हल की जाने वाली समस्या का वर्णन नीचे है।

ग्राहक के गोदाम में हल की जाने वाली समस्या का विवरण

प्रक्रिया अड़चन

2018 में, हमने चेल्याबिंस्क में एलडी ट्रेडिंग हाउस कंपनी के गोदाम में एक डब्ल्यूएमएस प्रणाली शुरू करने के लिए एक परियोजना बनाई। 20 नौकरियों के लिए उत्पाद "1C- लॉजिस्टिक्स: वेयरहाउस मैनेजमेंट 3" पेश किया: WMS ऑपरेटर, स्टोरकीपर, फोर्कलिफ्ट ड्राइवर। गोदाम में औसतन लगभग 4 हजार एम 2 है, कोशिकाओं की संख्या 5000 है और एसकेयू 4500 की संख्या है। 1 किलोग्राम से 400 किलोग्राम तक विभिन्न आकारों के हमारे अपने उत्पादन के बॉल वाल्व गोदाम में संग्रहीत हैं। FIFO और "इन-लाइन" उत्पाद प्लेसमेंट (नीचे स्पष्टीकरण) की बारीकियों के अनुसार माल का चयन करने की आवश्यकता के कारण गोदाम में इन्वेंटरी को बैचों के संदर्भ में संग्रहीत किया जाता है।

गोदाम प्रक्रियाओं के लिए स्वचालन योजनाओं को डिजाइन करते समय, हमें स्टॉक के गैर-इष्टतम भंडारण की मौजूदा समस्या का सामना करना पड़ा। स्टैकिंग और क्रेन का भंडारण, जैसा कि हमने पहले ही कहा है, "पंक्ति" बारीकियों। यही है, सेल में उत्पादों को एक के ऊपर एक पंक्तियों में ढेर किया जाता है, और एक टुकड़े पर एक टुकड़ा डालने की क्षमता अक्सर अनुपस्थित होती है (वे बस गिर जाती हैं, और वजन छोटा नहीं होता है)। इस वजह से, यह पता चला है कि एक बैच का केवल एक नामकरण एक टुकड़ा भंडारण इकाई में हो सकता है;

उत्पाद रोजाना गोदाम में पहुंचते हैं और प्रत्येक आगमन एक अलग बैच होता है। कुल मिलाकर, गोदाम संचालन के 1 महीने के परिणामस्वरूप, 30 अलग-अलग लॉट बनाए जाते हैं, इस तथ्य के बावजूद कि प्रत्येक को एक अलग सेल में संग्रहीत किया जाना चाहिए। सामानों को अक्सर पूरे पैलेट में नहीं, बल्कि टुकड़ों में चुना जाता है, और परिणामस्वरूप, टुकड़ा चयन क्षेत्र में, कई कोशिकाओं में निम्न चित्र देखा जाता है: 1 m3 से अधिक की मात्रा वाले सेल में क्रेन के कई टुकड़े होते हैं जो सेल वॉल्यूम के 5-10% से कम होते हैं (चित्र 1 देखें)। )।

अंजीर 1. एक सेल में कई टुकड़ों की तस्वीर

भंडारण क्षमता के उप-अपनाने के चेहरे पर। आपदा के पैमाने की कल्पना करने के लिए, मैं आंकड़ों का हवाला दे सकता हूं: गोदाम के संचालन के विभिन्न अवधियों में औसतन ऐसी कोशिकाओं की 100 और 300 कोशिकाओं के बीच की कमी होती है। चूंकि गोदाम अपेक्षाकृत छोटा है, इसलिए गोदाम के लोडिंग सीज़न में यह कारक "संकीर्ण गर्दन" बन जाता है और स्वीकृति और शिपमेंट की गोदाम प्रक्रियाओं को रोक देता है।

किसी समस्या को हल करने का विचार

यह विचार आया कि: अवशेषों के बैचों को निकटतम तारीखों के साथ एक एकल बैच में लाया जाए और ऐसे अवशेषों को एक एकीकृत बैच के साथ एक सेल में एक साथ रखा जाए, या कई में यदि अवशेषों की पूरी संख्या को समायोजित करने के लिए एक में पर्याप्त जगह नहीं है। इस तरह के "संपीड़न" का एक उदाहरण चित्र 2 में दिखाया गया है।

अंजीर। २। सेल कंप्रेशन स्कीम

यह आपको कब्जे वाले गोदाम की जगह को काफी कम करने की अनुमति देता है, जिसका उपयोग नए रखे गए सामानों के लिए किया जाएगा। गोदाम क्षमता को ओवरलोड करने की स्थिति में, ऐसा उपाय अत्यंत आवश्यक है, अन्यथा नए सामान रखने के लिए बस पर्याप्त खाली जगह नहीं हो सकती है, जिससे प्लेसमेंट और पुनःपूर्ति की गोदाम प्रक्रियाओं में एक डाट पैदा होगा और परिणामस्वरूप, स्वीकृति और शिपमेंट के लिए एक डाट। पहले, डब्ल्यूएमएस प्रणाली के कार्यान्वयन से पहले, इस तरह के एक ऑपरेशन को मैन्युअल रूप से किया गया था, जो प्रभावी नहीं था, क्योंकि कोशिकाओं में उपयुक्त अवशेषों को खोजने की प्रक्रिया काफी लंबी थी। अब, WMS सिस्टम की शुरुआत के साथ, उन्होंने इस प्रक्रिया को स्वचालित करने, इसे गति देने और इसे बुद्धिमान बनाने का निर्णय लिया।

इस समस्या को हल करने की प्रक्रिया को 2 चरणों में विभाजित किया गया है:

पहले चरण में, हम उन दलों के समूह पाते हैं जो संकुचित होने की तारीख में करीब हैं (यह इस समर्पण कार्य के लिए पहला लेख है );
दूसरे चरण में, बैचों के प्रत्येक समूह के लिए हम कोशिकाओं में उत्पाद अवशेषों के सबसे कॉम्पैक्ट प्लेसमेंट की गणना करते हैं।

वर्तमान लेख में, हम समाधान प्रक्रिया के दूसरे चरण के विवरण के साथ समाप्त करते हैं और सीधे अनुकूलन एल्गोरिथ्म पर विचार करते हैं।

समस्या को हल करने के लिए एक एल्गोरिथ्म का विकास

अनुकूलन एल्गोरिथ्म के प्रत्यक्ष विवरण के साथ आगे बढ़ने से पहले, इस तरह के एल्गोरिथ्म के विकास के मुख्य मानदंडों के बारे में कहना आवश्यक है, जो कि डब्ल्यूएमएस प्रणाली को लागू करने के लिए परियोजना के हिस्से के रूप में निर्धारित किए गए थे।

सबसे पहले, एल्गोरिथ्म को समझना आसान होना चाहिए। यह एक प्राकृतिक आवश्यकता है, क्योंकि यह माना जाता है कि एल्गोरिथ्म को भविष्य में ग्राहक की आईटी सेवा द्वारा समर्थित और विकसित किया जाएगा, जो अक्सर गणितीय सूक्ष्मता और ज्ञान से दूर होता है।
दूसरे, एल्गोरिथ्म तेज होना चाहिए। गोदाम में लगभग सभी सामान संपीड़न प्रक्रिया में शामिल हैं (यह लगभग 3,000 आइटम हैं) और प्रत्येक उत्पाद के लिए लगभग 10x100 की आयाम समस्या को हल करना आवश्यक है।
तीसरा, एल्गोरिथ्म इष्टतम के करीब समाधान की गणना करना चाहिए।
चौथा, एल्गोरिथ्म के डिजाइन, कार्यान्वयन, डिबगिंग, विश्लेषण और आंतरिक परीक्षण का समय अपेक्षाकृत छोटा है। यह एक आवश्यक आवश्यकता है, क्योंकि इस कार्य के लिए प्रोजेक्ट बजट सीमित था ।

यह कहने योग्य है कि आज तक, गणितज्ञों ने एकल-स्रोत कैपेसिटेड सुविधा स्थान समस्या समस्या को हल करने के लिए कई प्रभावी एल्गोरिदम विकसित किए हैं। उपलब्ध एल्गोरिदम की मुख्य किस्मों पर विचार करें।

सबसे कुशल एल्गोरिदम में से कुछ तथाकथित लैगरेंज विश्राम के दृष्टिकोण पर आधारित हैं। एक नियम के रूप में, ये बल्कि जटिल एल्गोरिदम हैं जो किसी ऐसे व्यक्ति के लिए समझना मुश्किल है जो असतत अनुकूलन की सूक्ष्मता में डूबा नहीं है। जटिल के साथ "ब्लैक बॉक्स", लेकिन ग्राहक के लैग्रेग छूट के प्रभावी एल्गोरिदम के अनुरूप नहीं था।

काफी प्रभावी मेटाह्यूरिस्ट्स हैं (यहां क्या मेटाह्यूरिस्ट्स पढ़ा जाता है , यहां क्या पढ़ा जाता है ), उदाहरण के लिए, जेनेटिक एल्गोरिदम, सिम्युलेटेड एनेलिंग एल्गोरिदम, एंट कॉलोनी एल्गोरिदम, टैबू सर्च एल्गोरिदम और अन्य (रूसी में ऐसे मेटाह्यूरिस्टिक्स का अवलोकन यहां पाया जा सकता है )। लेकिन इस तरह के एल्गोरिदम ग्राहक को पहले ही संतुष्ट कर चुके हैं, क्योंकि:

उन समस्याओं के समाधान की गणना करने में सक्षम, जो इष्टतम के बहुत करीब हैं।
समझने के लिए पर्याप्त, आगे समर्थन, डिबग और परिष्कृत।
वे जल्दी से एक समस्या के समाधान की गणना कर सकते हैं।

मेटाह्यूरिस्टिक्स का उपयोग करने का निर्णय लिया गया। अब यह सिंगल-सोर्स कैपेसिटिव फैसिलिटी लोकेशन प्रॉब्लम को हल करने के लिए मशहूर मेटाह्यूरिस्टिक्स के बड़े "चिड़ियाघर" में से एक "फ्रेमवर्क" चुनने के लिए बना रहा। कई लेखों की समीक्षा करने के बाद, जिन्होंने विभिन्न मेटाह्यूरिस्टिक्स की प्रभावशीलता का विश्लेषण किया, हमारी पसंद जीआरएएसपी एल्गोरिथ्म पर गिर गई, क्योंकि अन्य मेटह्योरिस्टिक्स की तुलना में इसने समस्या के गणना किए गए समाधानों की सटीकता पर अच्छे परिणाम दिखाए, सबसे तेज़ और सबसे महत्वपूर्ण में से एक था। और पारदर्शी तर्क।

जीआरएएसपी एल्गोरिथ्म की योजना एकल-स्रोत कैपेसिटेड सुविधा स्थान समस्या कार्य के संबंध में लेख में विस्तार से वर्णित है। एल्गोरिथ्म की सामान्य योजना इस प्रकार है।

स्टेज 1. एक लालची यादृच्छिक एल्गोरिथ्म द्वारा समस्या के लिए कुछ संभव समाधान उत्पन्न करें।
स्टेज 2. पड़ोस में कई स्थानों में स्थानीय खोज एल्गोरिदम का उपयोग करके चरण 1 में परिणामी समाधान में सुधार करें।
यदि स्टॉप स्थिति पूरी हो गई है, तो एल्गोरिथ्म को पूरा करें, अन्यथा चरण 1 पर जाएं। सभी समाधानों के बीच सबसे कम कुल लागत के साथ समाधान एल्गोरिदम का परिणाम होगा।

एल्गोरिथ्म को रोकने के लिए स्थिति पुनरावृत्तियों की संख्या पर एक साधारण प्रतिबंध या समाधान में किसी भी सुधार के बिना पुनरावृत्तियों की संख्या पर प्रतिबंध हो सकती है।

एल्गोरिथ्म की सामान्य योजना का कोड

int computeProblemSolution(int **aCellsData, int **aMatDist, int cellsNumb, int **aMatSolution, int **aMatAssignmentSolution) { //       //  int     .      WMS   3  ( .,    10 ),         // aMatSolutionIteration -    : // [i][0]  , [i][1]     , [i][2]             // [i][3]        int **aMatSolutionIteration = new int*[cellsNumb]; for (int count = 0; count < cellsNumb; count++) aMatSolutionIteration[count] = new int[4]; // aMatAssignmentSolutionIteration -     . [i][j] = 1 -  j   i, 0    int **aMatAssignmentSolutionIteration = new int*[cellsNumb]; for (int count = 0; count < cellsNumb; count++) aMatAssignmentSolutionIteration[count] = new int[cellsNumb]; const int maxIteration = 10; int iter = 0, recordCosts = 1000000; //    ,      int totalDemand = 0; for (int i = 0; i < cellsNumb; i++) totalDemand += aCellsData[i][1]; while (iter < maxIteration) { //     setValueIn2Array(aMatAssignmentSolutionIteration, cellsNumb, cellsNumb, 0); //    setClearSolutionArray(aMatSolutionIteration, cellsNumb, 4); //      int *aFreeContainersFitnessFunction = new int[cellsNumb]; //   ,       findGreedyRandomSolution(aCellsData, aMatDist, cellsNumb, aMatSolutionIteration, aMatAssignmentSolutionIteration, aFreeContainersFitnessFunction, false); //         improveSolutionLocalSearch(aCellsData, aMatDist, cellsNumb, aMatSolutionIteration, aMatAssignmentSolutionIteration, totalDemand); //     (      ) bool feasible = isSolutionFeasible(aMatSolutionIteration, aCellsData, cellsNumb); //    ,    if (feasible == false) { getFeasibleSolution(aCellsData, aMatDist, cellsNumb, aMatSolutionIteration, aMatAssignmentSolutionIteration); } //        ,  ,          int totalCostsIteration = getSolutionTotalCosts(aMatSolutionIteration, cellsNumb); if (totalCostsIteration < recordCosts) { recordCosts = totalCostsIteration; copy2Array(aMatSolution, aMatSolutionIteration, cellsNumb, 3); } iter++; } delete2Array(aMatSolutionIteration, cellsNumb); delete2Array(aMatAssignmentSolutionIteration, cellsNumb); return recordCosts; }

आइए हम चरण 1 में लालची यादृच्छिक यादृच्छिक एल्गोरिदम के अधिक विस्तार से विचार करें। यह माना जाता है कि शुरुआत में एक भी सेल-कंटेनर का चयन नहीं किया जाता है।

चरण 1. वर्तमान में चयनित प्रत्येक कंटेनर सेल के लिए, मान की गणना की जाती है $F_ {i} ^ {'}$ लागत सूत्र
$F_ {i} ^ {'} = \ frac {F_ {i}} {N},$
जहाँ $F_ {i} ^ {'}$ - एक कंटेनर चुनने की लागत की मात्रा $मैं$ और से माल ले जाने के लिए कुल लागत $एन$ कोशिकाएं जो अभी तक किसी भी कंटेनर में कंटेनर से जुड़ी नहीं हैं $मैं$ । ऐसा $एन$ कोशिकाओं का चयन किया जाता है ताकि उनमें माल की कुल मात्रा कंटेनर की क्षमता से अधिक न हो $मैं$ । डोनर कोशिकाओं को क्रमिक रूप से एक कंटेनर कंटेनर में स्थानांतरित करने के लिए चुना जाता है $मैं$ कंटेनर में माल की मात्रा को स्थानांतरित करने की बढ़ती लागत के क्रम में $मैं$ । जब तक कंटेनर की क्षमता पार नहीं हो जाती तब तक सेल का चयन किया जाता है।
चरण 2. सेट किया हुआ $आर$ समारोह मूल्य के साथ कंटेनर $एफ$ दहलीज मूल्य से अधिक नहीं $\ min (F) \ cdot (1 + ए)$ जहाँ $एक$ हमारे मामले में यह 0.2 है।
चरण 3. सेट से बेतरतीब ढंग से $आर$ कंटेनर का चयन किया जाता है $मैं$ । $एन$ कोशिकाओं को पहले कंटेनर में चुना गया था $मैं$ चरण 1 में, वे अंत में इस तरह के कंटेनर को सौंपा जाता है और लालची एल्गोरिथ्म की गणना में आगे भाग नहीं लेते हैं।
चरण 4. यदि सभी दाता कोशिकाओं को कंटेनरों को सौंपा जाता है, तो लालची एल्गोरिथ्म अपना काम करना बंद कर देता है, अन्यथा यह चरण 1 पर वापस चला जाता है।

प्रत्येक पुनरावृत्ति में यादृच्छिक एल्गोरिदम इस तरह से समाधान का निर्माण करने की कोशिश करता है कि समाधानों की गुणवत्ता के बीच संतुलन होता है, साथ ही साथ उनकी विविधता भी। निर्णय लेने के लिए इन दो आवश्यकताओं को एल्गोरिथ्म के सफल संचालन के लिए महत्वपूर्ण शर्तें हैं, क्योंकि:

यदि समाधान खराब गुणवत्ता के हैं, तो चरण 2 में बाद में सुधार महत्वपूर्ण परिणाम नहीं देगा, यहां तक कि खराब समाधान में सुधार करने के बाद से, हम अक्सर बहुत खराब गुणवत्ता वाले समाधान प्राप्त करेंगे;
यदि सभी समाधान अच्छे हैं, लेकिन समान हैं, तो स्थानीय खोज प्रक्रिया एक ही समाधान में परिवर्तित हो जाएगी, यह किसी भी तरह से एक तथ्य नहीं है कि इष्टतम। इस आशय को स्थानीय न्यूनतम मार कहा जाता है और इसे हमेशा टाला जाना चाहिए।

लालची यादृच्छिक एल्गोरिथ्म कोड

 void findGreedyRandomSolution(int **aCellsData, int **aMatDist, int cellsNumb, int **aMatSolutionIteration, int **aMatAssignmentSolutionIteration, int *aFreeContainersFitnessFunction, bool isOldSolution) { //     int numCellsInSolution = 0; if (isOldSolution) { //     ,   aFreeContainersFitnessFunction //  numCellsInSolution ,       for (int i = 0; i < cellsNumb; i++) { for (int j = 0; j < cellsNumb; j++) { if (aMatAssignmentSolutionIteration[i][j] == 1) numCellsInSolution++; } } } //  ,        aFreeContainersFitnessFunction,     // [i][j] = 1,   j    i, 0  int **aFreeContainersAssigntCells = new int*[cellsNumb]; for (int count = 0; count < cellsNumb; count++) aFreeContainersAssigntCells[count] = new int[cellsNumb]; while (numCellsInSolution != cellsNumb) { setValueIn2Array(aFreeContainersAssigntCells, cellsNumb, cellsNumb, 0); //    //               setFreeContainersFitnessFunction(aCellsData, aMatDist, cellsNumb, aFreeContainersFitnessFunction, aFreeContainersAssigntCells); //   ,    //       ,          int selectedRandomContainer = selectGoodRandomContainer(aFreeContainersFitnessFunction, cellsNumb); //          aMatSolutionIteration[selectedRandomContainer][0] = selectedRandomContainer; aMatSolutionIteration[selectedRandomContainer][1] = 0; aMatSolutionIteration[selectedRandomContainer][2] = aCellsData[selectedRandomContainer][2]; for (int j = 0; j < cellsNumb; j++) { if (aFreeContainersAssigntCells[selectedRandomContainer][j] == 1) { aMatAssignmentSolutionIteration[selectedRandomContainer][j] = 1; aMatSolutionIteration[selectedRandomContainer][1] += aCellsData[j][1]; aMatSolutionIteration[selectedRandomContainer][2] += aMatDist[selectedRandomContainer][j]; aMatSolutionIteration[selectedRandomContainer][3] = 0; aFreeContainersFitnessFunction[j] = 10000; numCellsInSolution++; } } } delete2Array(aFreeContainersAssigntCells, cellsNumb); delete[] aFreeContainersFitnessFunction; } void setFreeContainersFitnessFunction(int **aCellsData, int **aMatDist, int cellsNumb, int *aFreeContainersFitnessFunction, int **aFreeContainersAssigntCells) { //  ,        i // [0][k] -      , [1][k] -   int **aCurrentDist = new int*[2]; for (int count = 0; count < 2; count++) aCurrentDist[count] = new int[cellsNumb]; for (int i = 0; i < cellsNumb; i++) { // 10000 -      ,        if (aFreeContainersFitnessFunction[i] >= 10000) continue; //       int containerCurrentVolume = aCellsData[i][1]; //      int containerCosts = aCellsData[i][2]; //  -,    i int amountAssignedCell = 0; setCurrentDist(aMatDist, cellsNumb, aCurrentDist, i); for (int j = 0; j < cellsNumb; j++) { int currentCell = aCurrentDist[1][j]; if (currentCell == i) continue; if (aFreeContainersFitnessFunction[currentCell] >= 10000) continue; if (aCellsData[i][0] < containerCurrentVolume + aCellsData[currentCell][1]) continue; aFreeContainersAssigntCells[i][currentCell] = 1; containerCosts += aCurrentDist[0][j]; containerCurrentVolume += aCellsData[currentCell][1]; amountAssignedCell++; } //           (     ) if (aCellsData[i][1] > 0) { aFreeContainersAssigntCells[i][i] = 1; amountAssignedCell++; } //       1 (     ),       //           1. //          .      ,     //     (   )            . //         (     ),        //   ,             . if (amountAssignedCell > 1) amountAssignedCell *= 10; if (amountAssignedCell > 0) aFreeContainersFitnessFunction[i] = containerCosts / amountAssignedCell; else aFreeContainersFitnessFunction[i] = 10000; } delete2Array(aCurrentDist, 2); } int selectGoodRandomContainer(int *aFreeContainersFitnessFunction, int cellsNumb) { int minFit = 10000; for (int i = 0; i < cellsNumb; i++) { if (minFit > aFreeContainersFitnessFunction[i]) minFit = aFreeContainersFitnessFunction[i]; } int threshold = minFit * (1.2); // 20 %      //       int *aFreeContainersThresholdFitnessFunction = new int[cellsNumb]; int containerNumber = 0; for (int i = 0; i < cellsNumb; i++) { if (threshold >= aFreeContainersFitnessFunction[i] && aFreeContainersFitnessFunction[i] < 10000) { aFreeContainersThresholdFitnessFunction[containerNumber] = i; containerNumber++; } } int randomNumber = rand() % containerNumber; int randomContainer = aFreeContainersThresholdFitnessFunction[randomNumber]; delete[] aFreeContainersThresholdFitnessFunction; return randomContainer; }

चरण 1 में "शुरू" समाधान का निर्माण होने के बाद, एल्गोरिथ्म चरण 2 तक पहुंचता है, जहां इस तरह के एक पाया समाधान का सुधार किया जाता है, जहां स्वाभाविक रूप से सुधार का मतलब कुल लागत को कम करना है। चरण 2 में स्थानीय खोज एल्गोरिदम का तर्क निम्नानुसार है।

चरण 1. वर्तमान समाधान के लिए $एस$ सभी "पड़ोसी" समाधान किसी प्रकार के पड़ोस के अनुसार निर्मित होते हैं $N1$ । $एन 2$ ,, ... $एन 5$ और प्रत्येक "पड़ोसी" समाधान के लिए, कुल लागत के मूल्य की गणना की जाती है।
चरण 2. यदि पड़ोसी समाधानों के बीच एक बेहतर समाधान था $S1$ मूल समाधान की तुलना में $एस$ तो $एस$ बराबर माना $S1$ और एल्गोरिथ्म चरण 1 में आगे बढ़ता है। अन्यथा, यदि पड़ोसी समाधानों के बीच मूल एक से बेहतर कोई समाधान नहीं था, तो पड़ोस का दृष्टिकोण पहले से नहीं माना जाने वाले नए में बदल जाता है, और एल्गोरिथ्म चरण 1 में आगे बढ़ता है। यदि पड़ोस के सभी उपलब्ध विचारों पर विचार किया जाता है, लेकिन असफल रहा मूल की तुलना में बेहतर समाधान ढूंढना, एल्गोरिथ्म अपने काम को समाप्त करता है।

परिवेश के दृश्य क्रमिक रूप से निम्नलिखित स्टैक से चुने गए हैं:

$N1$ ।

$एन 2$ ।

$एन 3$ ।

$एन 4$ ।

$एन 5$ । आसपास के क्षेत्र के दृश्य 2 प्रकारों में विभाजित हैं: पहला प्रकार (पड़ोस)

$N1$ ।

$एन 2$ ।

$एन 3$ ), जहां कई कंटेनर नहीं बदलते हैं, लेकिन दाता कोशिकाओं को संलग्न करने के लिए केवल विकल्प बदलते हैं; दूसरा प्रकार (पड़ोस)

$एन 4$ ।

$एन 5$ ), जहां न केवल कंटेनरों में कोशिकाओं को जोड़ने के लिए विकल्प बदलते हैं, बल्कि स्वयं कई कंटेनर भी होते हैं।

हम निरूपित करते हैं

$| J |$ - सेट में तत्वों की संख्या

$जे$ । पहले प्रकार के पड़ोस के लिए चित्रण विकल्प नीचे दिए गए हैं।

अंजीर। 7. पड़ोस

$N1$

परिवेश

$N1$ (या पड़ोस में बदलाव ): कंटेनर में केवल एक दाता सेल के लगाव को बदलकर मूल से अलग समस्या को हल करने के लिए सभी विकल्प हैं। आस-पड़ोस का आकार कोई और नहीं

$| J |$ विकल्प।

अंजीर। 8. पड़ोस

$एन 2$

N1 के पड़ोस में स्थानीय खोज एल्गोरिदम का कोड

 void findBestSolutionInNeighborhoodN1(int **aCellsData, int **aMatDist, int cellsNumb, int **aMatSolutionIteration, int **aMatAssignmentSolutionIteration, int totalDemand, bool stayFeasible) { //        int recordDeltaCosts, recordCell, recordNewContainer, recordNewCosts, recordNewPenalty, recordOldContainer, recordOldCosts, recordOldPenalty; do { recordDeltaCosts = 10000; int totalContainersCapacity = 0; for (int i = 0; i < cellsNumb; i++) if (aMatSolutionIteration[i][1] > 0) totalContainersCapacity += aCellsData[i][0]; //   - for (int j = 0; j < cellsNumb; j++) { //   ,     j int currentContainer; for (int i = 0; i < cellsNumb; i++) { if (aMatAssignmentSolutionIteration[i][j] == 1) { currentContainer = i; break; } } //   ,     j (  ) int numbAssignedCells = 0; if (aMatSolutionIteration[j][0] >= 0) { for (int i = 0; i < cellsNumb; i++) { if (aMatAssignmentSolutionIteration[j][i] == 1) { numbAssignedCells = i; } } } else { numbAssignedCells = 0; } //    j        ,     j,       //     ""           ,     if (j == currentContainer && numbAssignedCells > 1) { continue; } //         int currentTotalContainersCapacity = totalContainersCapacity - aCellsData[currentContainer][0]; //  ,   ,        j    int currentCosts = aMatDist[currentContainer][j]; //        j         ,      if (aMatSolutionIteration[currentContainer][1] - aCellsData[j][1] == 0) currentCosts += aCellsData[currentContainer][2]; //        j        ,      int currentPenelty = getPenaltyValueForSingleCell(aCellsData, aMatSolutionIteration, currentContainer, j, 0); currentCosts += currentPenelty; for (int i = 0; i < cellsNumb; i++) { if (i == currentContainer) continue; if (stayFeasible) { if (max(0, aMatSolutionIteration[i][1]) + aCellsData[j][1] > aCellsData[i][0]) continue; } else { if (currentTotalContainersCapacity + aCellsData[i][0] < totalDemand) continue; } //     int newCosts = aMatDist[i][j]; //      if (aMatSolutionIteration[i][0] == -1) newCosts += aCellsData[i][2]; //        int newPenalty = getPenaltyValueForSingleCell(aCellsData, aMatSolutionIteration, i, j, 1); newCosts += newPenalty; int deltaCosts = newCosts - currentCosts; if (deltaCosts < 0 && deltaCosts < recordDeltaCosts) { recordDeltaCosts = deltaCosts; recordCell = j; recordNewContainer = i; recordNewCosts = newCosts; recordNewPenalty = newPenalty; recordOldContainer = currentContainer; recordOldCosts = currentCosts; recordOldPenalty = currentPenelty; } } } //   ,       if (recordDeltaCosts < 0) { //             aMatSolutionIteration[recordOldContainer][1] -= aCellsData[recordCell][1]; aMatSolutionIteration[recordOldContainer][2] -= recordOldCosts; if (aMatSolutionIteration[recordOldContainer][1] == 0) aMatSolutionIteration[recordOldContainer][0] = -1; aMatSolutionIteration[recordOldContainer][3] -= recordOldPenalty; aMatAssignmentSolutionIteration[recordOldContainer][recordCell] = 0; //             aMatSolutionIteration[recordNewContainer][1] += aCellsData[recordCell][1]; aMatSolutionIteration[recordNewContainer][2] += recordNewCosts; if (aMatSolutionIteration[recordNewContainer][0] == -1) aMatSolutionIteration[recordNewContainer][0] = recordNewContainer; aMatSolutionIteration[recordNewContainer][3] += recordNewPenalty; aMatAssignmentSolutionIteration[recordNewContainer][recordCell] = 1; //checkCorrectnessSolution(aCellsData, aMatDist, aMatAssignmentSolutionIteration, aMatSolutionIteration, cellsNumb); } } while (recordDeltaCosts < 0); }

परिवेश

$एन 2$ (या स्वैप पड़ोस): समस्या को हल करने के लिए सभी विकल्प होते हैं जो दाता कोशिकाओं के एक जोड़े के लिए कंटेनरों के लगाव के पारस्परिक विनिमय द्वारा मूल एक से भिन्न होते हैं। आस-पड़ोस का आकार कोई और नहीं

$| J | ^ 2$ विकल्प।

अंजीर। 9. पड़ोस

$एन 3$

परिवेश

$एन 3$ : समस्या को हल करने के लिए सभी विकल्प हैं, जो एक जोड़ी कंटेनरों के लिए सभी कोशिकाओं के लगाव के पारस्परिक प्रतिस्थापन द्वारा मूल एक से भिन्न होते हैं। आस-पड़ोस का आकार कोई और नहीं

$| I |$ विकल्प।

दूसरे प्रकार के पड़ोस को निर्णयों के "विविधीकरण" के एक तंत्र के रूप में माना जाता है, जब पहले प्रकार के "करीब" पड़ोस की खोज करके सुधार प्राप्त करना पहले से ही असंभव है।

अंजीर। 10. पड़ोस

$एन 4$

परिवेश

$एन 4$ : समस्या को हल करने के लिए सभी विकल्प हैं जो समाधान से एक कंटेनर सेल को हटाकर मूल से अलग हैं। डोनर कोशिकाएं जो इस तरह के कंटेनर से जुड़ी हुई थीं जिन्हें परिवहन की लागत को कम करने और कंटेनर की क्षमता को पार करने के लिए जुर्माना को कम करने के लिए समाधान से अन्य कंटेनरों से जोड़ा गया था। आस-पड़ोस का आकार कोई और नहीं

$| I |$ विकल्प।

अंजीर। 11. पड़ोस

$एन 5$

परिवेश

$एन 5$ : समस्या को हल करने के लिए सभी विकल्प होते हैं जो एक कंटेनर से कोशिकाओं को अलग करके और ऐसे कोशिकाओं को एक खाली कंटेनर में एक मनमाने ढंग से एक जोड़ी कंटेनर के लिए संलग्न करके मूल एक से भिन्न होते हैं। आस-पड़ोस का आकार कोई और नहीं

$| I | ^ 2$ विकल्प।

लेख के लेखकों का कहना है कि, कम्प्यूटेशनल प्रयोगों के परिणामों के आधार पर, सबसे अच्छा विकल्प पहले "पहले प्रकार के पड़ोस" के लिए खोज करना है, और फिर "दूर" पड़ोस की खोज करना है।

ध्यान दें कि लेख के लेखक प्रत्येक कंटेनर की क्षमता पर प्रतिबंधों को ध्यान में रखे बिना आसपास के क्षेत्र में एक खोज करने की सलाह देते हैं। इसके बजाय, यदि कंटेनर की क्षमता पार हो गई है, तो समाधान की कुल लागत में "सकारात्मक" कुछ सकारात्मक राशि जोड़ें, जो अन्य समाधानों की तुलना में इस तरह के समाधान के आकर्षण को बिगाड़ देगा। केवल प्रतिबंध कंटेनरों की कुल मात्रा पर रखा गया है, अर्थात्, दाता कोशिकाओं से परिवहन किए गए माल की कुल मात्रा कंटेनरों की कुल क्षमता से अधिक नहीं होनी चाहिए। प्रतिबंधों को हटाने का काम किया जाता है क्योंकि यदि प्रतिबंधों को ध्यान में रखा जाता है, तो अक्सर पड़ोस में एक भी स्वीकार्य समाधान नहीं होगा और स्थानीय खोज एल्गोरिदम अपने काम को शुरू करने के तुरंत बाद समाप्त कर देगा, बिना कोई सुधार किए। चित्र 12 प्रत्येक कंटेनर की क्षमता पर ध्यान दिए बिना स्थानीय खोज अभियान का एक उदाहरण दिखाता है।

अंजीर। 12. प्रत्येक कंटेनर की क्षमता पर ध्यान दिए बिना स्थानीय खोज का कार्य

इस आंकड़े में, यह माना जाता है कि कुछ दाता कोशिकाओं से लाल और हरे रंग के अवशेष दूसरे को छोड़कर किसी अन्य कंटेनर में जाने के लिए फायदेमंद नहीं हैं। इसका मतलब यह है कि समाधान का और सुधार असंभव है, क्योंकि समस्या के किसी अन्य नए संभव समाधान से, जहां क्षमता पर प्रतिबंध का सम्मान किया जाता है, परिवहन लागत के मामले में मूल से भी बदतर होगा। जैसा कि आप देख सकते हैं, 2 पुनरावृत्तियों के लिए एल्गोरिथ्म एक व्यवहार्य समाधान को मूल से बहुत बेहतर बनाता है, इस तथ्य के बावजूद कि पहला पुनरावृत्ति अतिरिक्त क्षमता के साथ एक अवैध समाधान बनाता है।

ध्यान दें कि किसी समाधान की अयोग्यता के लिए "जुर्माना" पेश करने का यह तरीका असतत अनुकूलन में काफी आम है और अक्सर इसका उपयोग एल्गोरिदम जैसे कि आनुवंशिक एल्गोरिदम, वर्जित खोज, आदि में किया जाता है।

स्थानीय खोज एल्गोरिथ्म पूरा होने के बाद, यदि पाया गया समाधान अभी भी अस्वीकार्य है, अर्थात, कंटेनर क्षमता की सीमाएं कहीं अधिक हो गई हैं, तो हमें समाधान को एक स्वीकार्य रूप में लाना होगा, जहां कंटेनर क्षमता पर सभी प्रतिबंधों का सम्मान किया जाता है। समाधान की अपर्याप्तता को हल करने के लिए एल्गोरिथ्म इस प्रकार है।

चरण 1. शिफ्ट और स्वैप के पड़ोस पर एक स्थानीय खोज करें। इस मामले में, संक्रमण केवल उन निर्णयों में किया जाता है जो "ठीक" की मात्रा को कम करते हैं। यदि जुर्माना में कमी संभव नहीं है, तो कम कुल लागत के साथ एक समाधान चुना जाता है। यदि स्थानीय खोज से और सुधार संभव नहीं है, तो चरण 2 पर जाएं, अन्यथा, यदि परिणामस्वरूप समाधान मान्य है, तो एल्गोरिथ्म को पूरा करें।
चरण 2. यदि समाधान अभी भी अस्वीकार्य है, तो प्रत्येक कंटेनर से जहां क्षमता की अधिकता थी, दाता कोशिकाओं को माल की बढ़ती मात्रा के क्रम में अलग किया जाता है जब तक कि क्षमता पर प्रतिबंध पूरा नहीं होता है। इस तरह की अलग कोशिकाओं के लिए, एल्गोरिथम के सभी चरण, पहले से शुरू होते हैं, इस तथ्य के बावजूद दोहराया जाता है कि उपलब्ध चयनित कंटेनरों का सेट और शेष कोशिकाओं को उनके पास संलग्न करने का तरीका तय हो गया है और उन्हें बदला नहीं जा सकता है। ध्यान दें कि इस तरह के चरण 2, जैसा कि कम्प्यूटेशनल प्रयोग दिखाता है, को बहुत कम प्रदर्शन करने की आवश्यकता होती है।

कम्प्यूटेशनल प्रयोग और एल्गोरिथ्म दक्षता का विश्लेषण

GRASP एल्गोरिथ्म C ++ में स्क्रैच से लागू किया गया था, क्योंकि हमें लेख में वर्णित एल्गोरिदम के लिए स्रोत कोड नहीं मिला था। प्रोग्राम कोड को जी-ओ 2 अनुकूलन विकल्प के साथ जी ++ का उपयोग करके संकलित किया गया था।

विजुअल स्टूडियो प्रोजेक्ट कोड GitHub पर उपलब्ध है । ग्राहक द्वारा पूछी गई एकमात्र चीज बौद्धिक संपदा, व्यापार रहस्य आदि के कारणों में से कुछ सबसे जटिल स्थानीय खोज प्रक्रियाओं को हटाना था।

GRASP एल्गोरिदम का वर्णन करने वाले लेख में , इसकी उच्च दक्षता बताई गई थी, जहां दक्षता से इसका मतलब यह है कि यह दृढ़ता से इष्टतम के बहुत करीब समाधानों की गणना करता है, और यह कि यह बहुत जल्दी काम करता है। इस तरह के GRASP एल्गोरिथ्म की वास्तविक प्रभावशीलता को सत्यापित करने के लिए, हमने अपना कम्प्यूटेशनल प्रयोग किया। समस्या का इनपुट डेटा हमारे द्वारा एक समान वितरण के साथ अनियमित रूप से उत्पन्न किया गया था। एल्गोरिदम द्वारा गणना किए गए समाधानों की तुलना इष्टतम समाधानों से की गई थी, जिनकी गणना लेख में प्रस्तावित सटीक एल्गोरिदम द्वारा की गई थी। इस तरह के एक सटीक एल्गोरिथ्म के स्रोत संदर्भ द्वारा GitHub पर स्वतंत्र रूप से उपलब्ध हैं। कार्य का आयाम, उदाहरण के लिए, 10x100 का मतलब होगा कि हमारे पास 10 दाता कोशिकाएं और 100 कंटेनर कोशिकाएं हैं।

गणना निम्नलिखित विशेषताओं के साथ एक व्यक्तिगत कंप्यूटर पर की गई थी: सीपीयू 2.50 गीगाहर्ट्ज, इंटेल कोर i5-3210M, 8 जीबी रैम, ऑपरेटिंग सिस्टम विंडोज 10 (x64)।

		GRASP		GRASP, %
550	50	0,08	1,22	0,2
1050	50	0,14	3,75	0,4
10100	50	0,55	15,81	1,4
10200	25	2,21	82,73	1,8
20100	25	1,06	264,15	2,3
20200	25	4,21	797,39	2,7

तालिका 3. जीआरएएसपी एल्गोरिदम और सटीक एल्गोरिदम के संचालन समय की तुलना

तालिका 3 से देखी जा सकती है, जीआरएएसपी एल्गोरिदम वास्तव में इष्टतम समाधानों के करीब की गणना करता है, और समस्या के आयाम में वृद्धि के साथ, एल्गोरिथ्म समाधानों की गुणवत्ता थोड़ी बिगड़ती है। यह प्रयोग के परिणामों से भी देखा जा सकता है कि जीआरएएसपी एल्गोरिथ्म काफी तेज है, उदाहरण के लिए, यह 0.5 सेकंड में औसतन 10x100 आयाम की समस्या को हल करता है। यह अंत में ध्यान देने योग्य है कि हमारे कम्प्यूटेशनल प्रयोग के परिणाम लेख के परिणामों के अनुरूप हैं ।

उत्पादन में एल्गोरिथ्म चल रहा है

एक कम्प्यूटेशनल प्रयोग में एल्गोरिथ्म विकसित होने, डिबग करने और परीक्षण करने के बाद, इसे संचालन में लगाने का समय आ गया। एल्गोरिथ्म C ++ में लागू किया गया था और एक DLL में रखा गया था जो 1C एप्लिकेशन से मूल प्रकार के बाहरी घटक के रूप में जुड़ा हुआ था । बाहरी घटकों 1 सी के बारे में पढ़ें और कैसे ठीक से विकसित करें और उन्हें 1 सी आवेदन से कनेक्ट करें । "1C: वेयरहाउस मैनेजमेंट 3" कार्यक्रम में, एक प्रसंस्करण फॉर्म विकसित किया गया था जिसमें उपयोगकर्ता अवशिष्ट को कंप्रेस्ड करने के लिए प्रक्रिया शुरू कर सकता है, जिसमें उसे जरूरत है कि मापदंडों के साथ। फॉर्म का स्क्रीनशॉट नीचे दिखाया गया है।

चित्र 13। परिशिष्ट 1C में शेष राशि के "संपीड़न" के लिए प्रक्रिया का रूप: वेयरहाउस प्रबंधन 3

उपयोगकर्ता प्रपत्र में अवशेषों के लिए संपीड़न मापदंडों का चयन कर सकता है

संपीड़न मोड: बैचों के क्लस्टरिंग के साथ (पहला लेख देखें) और इसके बिना।
वेयरहाउस, जिन कोशिकाओं में संपीड़न करना आवश्यक है। एक कमरे में विभिन्न संगठनों के लिए कई गोदाम हो सकते हैं। बस ऐसी स्थिति हमारे ग्राहक के साथ थी।
साथ ही, उपयोगकर्ता दाता सेल से कंटेनर में स्थानांतरित माल की मात्रा को अंतःक्रियात्मक रूप से समायोजित कर सकता है और आइटम को संपीड़न के लिए सूची से हटा सकता है, यदि किसी कारण से वह चाहता है कि वह संपीड़न प्रक्रिया में भाग न ले।

निष्कर्ष

लेख के अंत में मैं इस तरह के अनुकूलन एल्गोरिथ्म की शुरूआत के परिणामस्वरूप प्राप्त अनुभव को संक्षेप में प्रस्तुत करना चाहता हूं।

. : , , . - :
1. , ;
2. .
( ), , . «», - . , , . , , , - , .
, ( ), . , , . , . . , .
:
1. .
2. .
3. . , .
4. . , . , , , , .
5. , . ( ) . , .
6. .

और, मुझे लगता है, सबसे महत्वपूर्ण बात। एंटरप्राइज़ में अनुकूलन प्रक्रिया को अक्सर सूचनाकरण प्रक्रिया के पूरा होने के बाद पालन करना चाहिए। प्रारंभिक सूचना के बिना अनुकूलन का बहुत कम उपयोग होता है , क्योंकि डेटा प्राप्त करने के लिए कहीं नहीं है और एल्गोरिथम के समाधान डेटा को लिखने के लिए कहीं नहीं है। मुझे लगता है कि मध्यम और बड़े घरेलू उद्यमों के अधिकांश ने स्वचालन और सूचना के लिए बुनियादी जरूरतों को बंद कर दिया है और प्रक्रिया अनुकूलन के अधिक "ठीक-ट्यूनिंग" के लिए तैयार हैं।

इसलिए, हम सूचना प्रणाली के कार्यान्वयन के बाद अभ्यास करते हैं, यह ईआरपी, डब्ल्यूएमएस, टीएमएस, आदि हो। छोटा अतिरिक्त करें। उन प्रक्रियाओं को अनुकूलित करने के लिए परियोजनाएं जिन्हें ग्राहक के लिए समस्याग्रस्त और महत्वपूर्ण के रूप में सूचना प्रणाली के कार्यान्वयन के दौरान पहचाना गया था। मुझे लगता है कि यह एक आशाजनक अभ्यास है जो आने वाले वर्षों में गति प्राप्त करेगा।

, ,
, .

WMS के लिए असतत गणित: कोशिकाओं में सामान को संपीड़ित करने के लिए एल्गोरिथ्म (भाग 2)