Stacker crane problem
संयोजन अनुकूलन में, स्टेकर क्रेन समस्या एक अनुकूलन समस्या है जो यात्रा करने वाले विक्रेता की समस्या से निकटता से संबंधित है। इसके निवेश में एक मीट्रिक स्थान में अंकों के क्रमबद्ध जोड़े का संग्रह होता है, और लक्ष्य इन बिंदुओं को न्यूनतम कुल लंबाई के चक्र में जोड़ना है जिसमें सभी जोड़े शामिल होते हैं, जो एक दूसरे के साथ लगातार उन्मुख होते हैं। यह इन डिलीवरी के समय पर बाधाओं के बिना एक सरल रूप में एक स्टेकर क्रेन, निर्माण क्रेन या (ड्रेज में) एक ट्रक द्वारा माल के व्यक्तिगत भार के पिकअप और डिलीवरी को निर्धारित करने की समस्याओं का मॉडल बनाता है। इसे मिश्रित ग्राफ के संदर्भ में एक समतुल्य सूत्रीकरण के साथ प्रस्तुत किया गया था, जिसमें निर्देशित किनारों के साथ इनपुट जोड़े और अनिर्दिष्ट किनारों को उनकी दूरी का प्रतिरूपण किया गया था। फ्रेडरिकसन और अन्य। इसके निर्माण का श्रेय डैनियल जे. रोसेनक्रांट्ज़ के व्यक्तिगत संचार को दिया जाता है। स्टेकर क्रेन समस्या को मीट्रिक स्थानों में यात्रा करने वाले विक्रेता की समस्या के सामान्यीकरण के रूप में देखा जा सकता हैः यात्रा करने वाले विक्रेता की समस्या के किसी भी उदाहरण को स्टेकर क्रेन समस्या के एक उदाहरण में बदला जा सकता है, जिसमें यात्रा करने वाले विक्रेता के उदाहरण में प्रत्येक बिंदु के लिए एक जोड़ी होती है। दूसरी दिशा में, स्टेकर क्रेन समस्या को असममित यात्रा विक्रेता समस्या के एक विशेष मामले के रूप में देखा जा सकता है, जहां असममित यात्रा विक्रेता समस्या के बिंदु एक स्टेकर क्रेन उदाहरण के जोड़े हैं और एक जोड़ी से दूसरी जोड़ी तक की दूरी को पहले जोड़ी के वितरण बिंदु से, उसके पिकअप बिंदु के माध्यम से, दूसरे जोड़ी के वितरण बिंदु तक की दूरी के रूप में लिया जाता है। क्योंकि यह यात्रा करने वाले विक्रेता की समस्या को सामान्य करता है, यह उसी कम्प्यूटेशनल जटिलता को विरासत में प्राप्त करता हैः यह एन. पी.-कठोर है, और कम से कम अनुमानित करने के लिए कठिन है। यात्रा करने वाले विक्रेता की समस्या के लिए क्रिस्टोफाइड्स एल्गोरिथ्म पर आधारित एक अनुमानित एल्गोरिथ्म 9/5 के अनुमानित अनुपात के भीतर स्टेकर क्रेन समस्या के समाधान का अनुमान लगा सकता है। उपयोग किए गए धागे की कुल मात्रा को कम करने के लिए एक कढ़ाई पैटर्न के पीछे की ओर डिजाइन करने की समस्या स्टेकर क्रेन समस्या से निकटता से संबंधित है, लेकिन यह इसके प्रत्येक जोड़े के बिंदुओं (पैटर्न के सामने की ओर दिखाई देने वाले टांके के सिरों) को किसी भी दिशा में पार करने की अनुमति देता है, बजाय इसके कि एक सुसंगत दिशा में सभी जोड़े से गुजरने के लिए ट्रेवर्सल की आवश्यकता हो। यह यात्रा करने वाले विक्रेता की समस्या से समान परिवर्तन द्वारा एन. पी.-कठोर है, और 2 के अनुमानित अनुपात के भीतर अनुमानित किया जा सकता है। स्टेकर क्रेन समस्या का एक अन्य रूप, जिसे डायल-ए-राइड समस्या कहा जाता है, एक वाहन को अपने मार्ग के किसी भी बिंदु पर कुछ संख्या में भार रखने की अनुमति देते हुए पिकअप और डिलीवरी का संग्रह करने के लिए न्यूनतम मार्ग के लिए कहता है। संदर्भ यात्रा विक्रेता समस्या