घन उपयोग और बिन पैकिंग

स्टैकिंग: हर ट्रेलर में 3D ज्यामिति

उत्तरी अमेरिका में एक मानक पैलेट 48 इंच बाय 40 इंच (GMA पैलेट) है। यह लॉजिस्टिक्स ज्यामिति की मौलिक इकाई है।

घन उपयोग मापता है कि आप एक स्थान को कितनी कुशलता से भरते हैं: वास्तविक उत्पाद वॉल्यूम को उपलब्ध वॉल्यूम से विभाजित। एक ट्रेलर जो वजन में भरा हुआ है लेकिन वॉल्यूम में आधा खाली है, खराब घन उपयोग है। एक ट्रेलर जो छत तक पैक है, उत्कृष्ट घन उपयोग है।

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

इंटरलॉकिंग (पिनव्हील) स्टैकिंग: वैकल्पिक परतें 90 डिग्री घुमाई जाती हैं। बहुत अधिक स्थिर लेकिन किनारों पर खाली स्थान बनाता है, पैलेट फुटप्रिंट का 5-15% बर्बाद करता है।

कंटेनर लोडिंग वास्तविक ज्यामितीय चुनौती है: विभिन्न आकारों के आयताकार बॉक्स को एक 40-फुट शिपिंग कंटेनर में फिट करना (आंतरिक आयाम लगभग 39'5" x 7'8" x 7'10")। यह 3D बिन पैकिंग है: कंप्यूटर विज्ञान में क्लासिक NP-कठिन समस्याओं में से एक। कोई भी एल्गोरिथ्म बड़े उदाहरणों के लिए उचित समय में इष्टतम समाधान की गारंटी नहीं दे सकता है।

व्यवहार में, लॉजिस्टिक्स कंपनियां अनुमानी दृष्टिकोण का उपयोग करती हैं: सबसे बड़ी वस्तुएं पहले, स्टैकिंग ऊंचाई से पहले फर्श क्षेत्र को भरें, अनलोडिंग दक्षता के लिए गंतव्य के आधार पर वस्तुओं को समूहित करें।

पैलेट लोडिंग दक्षता

आपको 12 इंच लंबे, 10 इंच चौड़े और 8 इंच ऊंचे बॉक्स को एक मानक 48" x 40" पैलेट पर लोड करने की आवश्यकता है। अधिकतम स्टैक ऊंचाई 48 इंच है।

रूट अनुकूलन मुश्किल क्यों हो जाता है

ट्रैवलिंग सेल्समैन समस्या (TSP)

मान लीजिए आपको 10 ग्राहकों को देखना होगा और अपने डिपो पर लौटना होगा। सबसे छोटा मार्ग क्या है? यह ट्रैवलिंग सेल्समैन समस्या है: गणित और कंप्यूटर विज्ञान में सबसे अधिक अध्ययन की जाने वाली समस्याओं में से एक।

कठिनाई संयोजन विस्फोट है। N स्टॉप के लिए, (N-1)!/2 अद्वितीय मार्ग हैं (2 से विभाजित क्योंकि दक्षिणावर्त और वामावर्त समान दूरी हैं)।

- 5 स्टॉप: 12 मार्ग: मिलीसेकंड में सभी को चेक करें

- 10 स्टॉप: 181,440 मार्ग: कंप्यूटर के लिए अभी भी प्रबंधनीय

- 15 स्टॉप: 43.6 बिलियन मार्ग: घंटों लगते हैं

- 20 स्टॉप: 60.8 क्वाड्रिलियन मार्ग: सदियां लगती हैं

- 50 स्टॉप: अवलोकनीय ब्रह्मांड में परमाणुओं से अधिक मार्ग

TSP NP-कठिन है: कोई ज्ञात एल्गोरिथ्म इसे बहुपद समय में हल नहीं कर सकता है। जैसे-जैसे N बढ़ता है, सटीक समाधान असंभव हो जाते हैं और हमें अनुमान का उपयोग करना चाहिए: एल्गोरिथ्म जो अच्छे (लेकिन गारंटीकृत इष्टतम नहीं) समाधान जल्दी खोजते हैं।

आम अनुमान:

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

- उत्तल पतवार सम्मिलन: बाहरी स्टॉप से शुरू करें (उत्तल पतवार: ज्यामितीय सीमा)। फिर आंतरिक स्टॉप को एक-एक करके सम्मिलित करें जहां वे कम से कम दूरी जोड़ते हैं।

- 2-opt सुधार: एक पूर्ण मार्ग लें और किनारों की जोड़ी को स्वैप करने का प्रयास करें। यदि दो किनारों को हटाना और अलग तरीके से पुनः कनेक्ट करना मार्ग को छोटा बनाता है, तो स्वैप को रखें। कोई सुधार न मिलने तक दोहराएं।

अनुमान बनाम सटीक समाधान

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

क्षेत्र, घनत्व, और वाहन रूटिंग समस्या

अंतिम-मील डिलीवरी: जहां ज्यामिति अर्थशास्त्र से मिलती है

अंतिम मील: वितरण केंद्र से ग्राहक के दरवाजे तक: कुल शिपिंग लागत का 40-50% खाता है। यह आपूर्ति श्रृंखला का सबसे ज्यामितीय रूप से बाध्य भाग है।

डिपो से रेडियल मार्ग: डिलीवरी ट्रक एक केंद्रीय वितरण केंद्र से बाहर निकलते हैं। प्रत्येक ट्रक के मार्ग को एक कॉम्पैक्ट भौगोलिक क्षेत्र को कवर करना चाहिए: कोई भी दो ट्रक एक-दूसरे के क्षेत्र को पार नहीं करने चाहिए।

डिलीवरी घनत्व सब कुछ निर्धारित करता है। एक घने शहरी क्षेत्र में, एक ट्रक एक 8-घंटे की शिफ्ट में 150 डिलीवरी कर सकता है। ग्रामीण क्षेत्रों में, एक ही ट्रक 20-30 का प्रबंधन कर सकता है। ज्यामितीय कारण: शहरी स्टॉप एक-दूसरे के पास हैं (स्टॉप के बीच छोटी ड्राइव) जबकि ग्रामीण स्टॉप दूर हैं।

क्षेत्र-आधारित रूटिंग सेवा क्षेत्र को भौगोलिक क्लस्टर में विभाजित करता है। प्रत्येक क्षेत्र को एक वाहन को सौंपा जाता है। अच्छे क्षेत्र कॉम्पैक्ट (मोटे तौर पर गोलाकार या वर्गाकार) और सन्निहित (कोई अंतराल या अलग-थलग जेब नहीं) हैं। लक्ष्य: कुल दूरी को कम करना जबकि प्रत्येक मार्ग को समय/क्षमता सीमा के तहत रखना।

वाहन रूटिंग समस्या (VRP) TSP को कई वाहनों के लिए सामान्यीकृत करता है। एक डिपो, N ग्राहकों, और K ट्रकों (प्रत्येक क्षमता और समय बाधाओं के साथ) को देखते हुए, ग्राहकों को ट्रकों को असाइन करें और कुल दूरी को कम करने के लिए प्रत्येक ट्रक के मार्ग को अनुक्रम करें। VRP भी NP-कठिन है।

एक अच्छी तरह से डिज़ाइन किया गया क्षेत्र मानचित्र मार्ग बनाता है जहां प्रत्येक ड्राइवर के पथ एक कॉम्पैक्ट ज्यामितीय आकार बनाते हैं: डिपो से एक सांख्यिक वृत्त या पालि। यदि आप एक मार्ग देखते हैं जो अपने आप को पार करता है या दूसरे ड्राइवर के क्षेत्र के साथ ओवरलैप होता है, तो रूटिंग अक्षम है।

क्षेत्र डिजाइन

एक डिलीवरी कंपनी एक शहर के केंद्र में एक डिपो से संचालित होती है। उनके पास 4 ड्राइवर हैं और 200 डिलीवरी एक मोटे तौर पर गोलाकार सेवा क्षेत्र में 10-मील की त्रिज्या में बिखरी हुई हैं।