हमने मालवाहक के लिए माल का चयन कैसे किया

नमस्कार। हमारा नाम इल्या बश्तानोव (डेवलपर, टूचका - तोचका ) और तात्याना वोरोनोवा (डेटा विश्लेषक, 2 एम सेंटर ) है। और हम परिवहन के लिए माल का चयन करने के कार्य के तकनीकी कार्यान्वयन के बारे में बात करना चाहते हैं।

समस्या का सार इस प्रकार है। गोदाम में ऐसे सामान हैं जिन्हें शहर ए से शहर बी तक ले जाने की आवश्यकता है। हम मान सकते हैं कि केवल सामान के वजन को ध्यान में रखा जाता है, और उनके आकार कम या ज्यादा मानक (यूरो पैलेट) होते हैं। एक वाहक जो पासिंग कार्गो लेना चाहता है, वह जितना संभव हो उतना ले जाना चाहता है, लेकिन वजन और पैकेज की संख्या द्वारा सीमित है। उसके लिए गोदाम में उपलब्ध सामानों में से बहुत से वेरिएंट तैयार करना आवश्यक है।

इस मामले में व्यापार के लिए हल किए गए कार्य:

1. वाहनों को यथासंभव कुशलता से लोड करें और जिससे परिवहन राजस्व बढ़े।
2. उपयोगकर्ता (FIFO सिद्धांत सहित) के लिए स्वीकार्य समय में वितरण समस्या को हल करने के लिए।

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

कलन विधि

यह कार्य क्लासिक बैकपैक पैकिंग समस्या का एक प्रकार है । बैकपैक की समस्या एनपी-पूर्ण है । इस तरह की समस्याओं को बहुपद समय में हल नहीं किया जा सकता है, हालांकि गणितीय रूप से यह अभी तक साबित नहीं हुआ है। इसका अर्थ है कि सटीक एल्गोरिदम, जैसे कि वैरिएंट या इसकी अनुकूलित किस्मों की संपूर्ण खोज, व्यवहार में काम नहीं करते हैं, क्योंकि उनमें जटिलता है$$$O(2^n)$। अनुमानित तरीके सर्वोत्तम समय के लिए समाधान प्रदान करते हैं। उदाहरण के लिए, लालची एल्गोरिथ्म मानता है कि जब तक संभव हो तब अधिकतम भारी भार बैग में डाल दिया जाता है। इसकी जटिलता छँटाई की जटिलता से अधिक नहीं है$$$(O(n * log n))$, लेकिन परिणाम इष्टतम से दूर हो सकता है। अभी भी आनुवांशिक एल्गोरिदम का एक वर्ग है जो सीमित समय में अच्छे परिणाम देते हैं, लेकिन वे गैर-नियतात्मक हैं, जो हमारे मामले में बार-बार कॉल जारी करने के लिए अलग-अलग विकल्प देगा, ग्राहक और वाहक को समझाना मुश्किल होगा। नतीजतन, चुनाव अनुमानित तरीकों पर गिर गया, जो बहुपद समय में गारंटी सटीकता के साथ परिणाम देता है।

तो हमारे पास:

• वजन के साथ वजन $$$w_1,w_2,... , w_n$
• माल के कुल वजन पर सीमा $$$W_\max$
• कार्गो की सीमा $$$Q_\max$

अधिक से अधिक कुल वजन वाले सामानों का एक उपसमूह ढूंढना आवश्यक है जो बाधाओं को संतुष्ट करता है।

विचार यह है कि उनके भार को कम करके और लालची एल्गोरिथ्म को लागू करके माल की विविधता को कम किया जाए। इस मामले में, अनुमानित समाधान पूरी तरह से बहुपद समय में पाया जाता है, अर्थात, गारंटीकृत सटीकता के साथ एक समाधान$$$1- \varepsilon$ में एक बहुपद होने के साथ जटिलता प्राप्त की $$$n$तथा $$$\varepsilon$।

एल्गोरिथ्म के इनपुट पर, हमारे पास एक प्लेट होती है जिसमें सामान के गोल वजन और प्रत्येक वजन के लिए सीटों की संख्या होती है। लालची एल्गोरिथ्म का उपयोग करते हुए, हम कुल वजन के लिए स्टाइलिंग विकल्प प्राप्त करने की कोशिश करते हैं$$$W_\max,$ $$$W_\max-1,$$$$W_\max-2,$$$$…,$$$$0$। ऐसा करने के लिए, लक्ष्य कुल वजन सेट करें, चक्र में हम शेष भार से अधिकतम भार कार्गो का चयन करते हैं ताकि लक्षित वजन कम न हो। यदि अधिकतम स्वीकार्य राशि तक पहुँच गया है$$$Q_\max$चक्र समाप्त होता है। परिणामस्वरूप संयोजन एक अस्थायी सरणी में संग्रहीत होते हैं।

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

टेस्ट

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

दो परीक्षण वातावरण का उपयोग किया गया था: परीक्षण विकसित करने के लिए एक डेस्कटॉप और वास्तविक के समान परिस्थितियों में परीक्षण के लिए एक सर्वर।

• देव: एचपी प्रोबुक 4740s क्लाइंट स्टेशन + 32-बिट 2 एक्स पेंटियम® ड्यूल-कोर सीपीयू E5300 @ 2.60GHz और 4 जीबी रैम, उबंटू लिनक्स 16.04, पोस्टग्रेक्यूएल 10.3।
• test: 64-bit 2 x Intel Xeon CPU E5-2673 v4 @ 2.30GHz 14 , CentOS Linux 7.4, PostgreSQL 10.3

PostgreSQL डेटाबेस में एक परीक्षण तालिका तैयार की गई थी जिसमें 20 से 800 किलोग्राम तक यादृच्छिक भार के साथ 7000 भार थे। परीक्षण के लिए, PostgreSQL से मानक pgBench उपयोगिता का उपयोग किया गया था, जिसने परीक्षण के दौरान 500 लेनदेन (प्रत्येक 50 लेनदेन के 10 कनेक्शन) किए। प्रत्येक लेनदेन ने यादृच्छिक मापदंडों के साथ एल्गोरिथ्म की एक कॉल की (10 से 1000 किग्रा वजन पर प्रतिबंध और 1 से 50 टुकड़ों से माल की संख्या पर)। सभी यादृच्छिक चर समान रूप से वितरित किए जाते हैं।

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

दूसरे एल्गोरिथ्म के लिए, प्रत्येक लेनदेन ने पोस्टग्रेक्यूएल डेटाबेस के संग्रहित फ़ंक्शन को कॉल किया, जिसने तालिका से परीक्षण डेटा पढ़ा और एल्गोरिथ्म लागू किया।

तालिका 1. मुख्य परीक्षण के परिणाम मुख्य परीक्षण



के अलावा, जिनमें से परिणाम तालिका 1 में दिखाए गए हैं, एल्गोरिथ्म 2 का एक अतिरिक्त परीक्षण किया गया था, जिसमें प्रारंभिक डेटा प्राप्त करने के लिए विभिन्न विकल्पों की तुलना की गई थी: एक डेटाबेस से, एक फ़ाइल से, यादृच्छिक सरणी पीढ़ी। यह पता चला कि 7000 भार के लिए, DBMS से स्थानीय सरणी में डेटा स्थानांतरित करने के लिए वास्तविक स्टैकिंग एल्गोरिदम की तुलना में अधिक समय की आवश्यकता होती है।

जाँच - परिणाम।

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

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

शोषण

हमेशा की तरह, जीवन ने समायोजन किया, और मुझे कार्यान्वयन को मोड़ना पड़ा।

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

प्रारंभ में, वजन उन मानों तक किया गया जो 10 किलोग्राम के गुणक हैं। ऑपरेशन के दौरान, यह स्पष्ट हो गया कि सटीकता काफ़ी हद तक ग्रस्त है, और परिणाम सामान्य ज्ञान के विपरीत शुरू होते हैं, उदाहरण के लिए, 12 और 19 किलोग्राम वजन वाले सामान की उपस्थिति में, सिस्टम पहले का चयन कर सकता है। वेयरहाउस तराजू 1 किलो की सटीकता के साथ डेटा देते हैं, और वर्तमान वॉल्यूम और लोड के लिए, तराजू के पूर्णांक मानों के लिए एल्गोरिथ्म का प्रदर्शन काफी स्वीकार्य निकला, इसलिए उन्होंने राउंडिंग से इनकार कर दिया है। भविष्य में, लदान की संख्या में वृद्धि के साथ, यह उन मानों के लिए गोलाई का उपयोग करने की योजना है जो 5 किलो के गुणक हैं।

मौजूदा डेटा वॉल्यूम और क्वेरी की तीव्रता के साथ स्टैकिंग एल्गोरिदम के संचालन के लिए ओवरहेड महत्वपूर्ण नहीं है। महत्वपूर्ण रूप से कार्गो चयन के चरण में, साथ ही साथ अन्य सिस्टम ऑपरेशन प्रक्रियाओं के लिए अधिक संसाधनों की आवश्यकता होती है।

व्यापार निष्कर्ष

प्वाइंट-पॉइंट का मिशन एक प्रभावी लॉजिस्टिक प्रक्रिया है, विशेष रूप से, भीड़ के संदर्भ में वाहन का इष्टतम उपयोग: जब न्यूनतम की परिवहन।

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

सेंटर 2 एम और टोका-टोची के विशेषज्ञों ने परिवहन प्रक्रिया में सभी प्रतिभागियों के लिए उपयुक्त एक सॉफ्टवेयर-गणितीय समाधान पाया। इसका उपयोग संघीय नेटवर्क के लिए किया जा सकता है, जिनमें से प्रत्येक बिंदु पर 7 हजार पैलेट (फुटबॉल क्षेत्र के आकार के अनुसार) 500 वाहक द्वारा अनुरोध किया जाता है और परिणाम 1 सेकंड से कम समय में प्राप्त होता है।

लेख के लेखक: इल्या बश्तानोव (i-बैश), तात्याना वोरोनोवा (tvoronova)