आर्क रूटिंग

आर्क रूटिंग समस्याएं (एआरपी) सामान्य रूटिंग समस्याओं (जीआरपी) की श्रेणी है, जिसमें नोड रूटिंग समस्याएं (एनआरपी) भी सम्मिलित हैं। एआरपी और एनआरपी में उद्देश्य क्रमशः ग्राफ के किनारों और नोड्स को पार करना है।^[1] आर्क रूटिंग समस्याओं के उद्देश्य में कुल दूरी और समय को कम करना सम्मिलित है, जिसमें अधिकांशतः अनुपयुक्त माइलेज समय, किसी गंतव्य तक पहुंचने में लगने वाला समय, को कम करना सम्मिलित होता है। आर्क रूटिंग समस्याओं को अपशिष्ट संग्रहण, स्कूल बस मार्ग योजना, पैकेज और समाचार पत्र वितरण, सड़क पर नमक छिड़कने वाले शीतकालीन सेवा वाहन के साथ बर्फ हटाने और बर्फ हटाने के लिए प्रयुक्त किया जा सकता है।^[2] मेल, नेटवर्क रखरखाव, सफाई कर्मचारी , पुलिस और सुरक्षा गार्ड गश्त,^[1] और बर्फ़ की जुताई ^[3]^[4] रूट निरीक्षण समस्या के विपरीत आर्क रूटिंग समस्याएं एनपी-कठोरता हैं, जिन्हें बहुपद-समय में हल किया जा सकता है।

आर्क रूटिंग समस्या समाधान के वास्तविक संसार के उदाहरण के लिए, क्रिस्टीना आर. डेलगाडो सेर्ना और जोकिन पाचेको बोनरोस्त्रो ने स्पेनिश प्रांत बर्गोस माध्यमिक विद्यालय प्रणाली के सर्वश्रेष्ठ स्कूल बस मार्गों को खोजने के लिए सन्निकटन एल्गोरिदम प्रयुक्त किया था। शोधकर्ताओं ने उन मार्गों की संख्या कम कर दी जिन्हें पहले पार करने में 60 मिनट से अधिक समय लगता था। उन्होंने वाहनों की निश्चित अधिकतम संख्या के साथ सबसे लंबे मार्ग की अवधि को भी कम कर दिया था।^[5]

आर्क रूटिंग समस्याओं के सामान्यीकरण हैं जो कई मेलमैन प्रस्तुत करते हैं, उदाहरण के लिए के चीनी पोस्टमैन समस्या (केसीपीपी) है।

पृष्ठभूमि

वाहनों की कुशल शेड्यूलिंग और रूटिंग से उद्योग और सरकार को प्रत्येक वर्ष लाखों डॉलर की बचत हो सकती है।^[2]^[6] आर्क रूटिंग समस्याओं का अनुप्रयोग स्कूल बस योजना, शहरों में कूड़ा-कचरा और कचरा संग्रहण, मेलमैन और डाक सेवाओं द्वारा मेल और पैकेज वितरण, सर्दियों में सड़कों को सुरक्षित रखने के लिए सर्दियों में ग्रिटिंग और नमक बिछाना, बर्फ की जुताई और निष्कासन, मीटर रीडिंग में होता है। जिसमें रिमोट रेडियो आवृत्ति पहचान मीटर रीडिंग तकनीक, सड़क रखरखाव और सफाई, पुलिस गश्ती कार मार्ग योजना, और बहुत कुछ सम्मिलित है।

आधार

मूल रूटिंग समस्या यह है: वाहनों के बेड़े द्वारा सेवित किए जाने वाले नोड्स और/या आर्क्स का सेट दिया गया है, डिपो पर प्रारंभ होने और समाप्त होने वाले प्रत्येक वाहन के लिए मार्ग खोजते है। वाहन मार्ग बिंदुओं या नोड्स का क्रम है, जिसे वाहन को डिपो पर प्रारंभ और समाप्त होने के क्रम में पार करना होता है।^[2]

चीनी डाकिया समस्या

चीनी डाकिया समस्या (सीपीपी) का उद्देश्य डाकिया के लिए न्यूनतम लंबाई चक्र का पता लगाना है। सीपीपी के लिए सभी किनारों को बार पार करने की आवश्यकता होती है, ग्रामीण डाकिया समस्या (आरपीपी) के लिए न्यूनतम लंबाई चक्र के साथ किनारों के सबसेट को पार करने की आवश्यकता होती है।^[1]

वाहन रूटिंग समस्याएँ/वीआरपी

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

ग्रामीण डाकिया समस्या

कुछ स्थितियों में, आवश्यक किनारों का सेट ग्राफ़ में किनारों से भिन्न होता है। इसे ग्रामीण डाकिया समस्या (आरपीपी) द्वारा प्रतिरूपित किया गया है।^[1] जहां आवश्यक किनारे किनारों की प्रणाली का उपसमूह हैं।

एल्गोरिदम

चीनी डाकिया समस्या (सीपीपी), विंडी डाकिया समस्या (डब्ल्यूपीपी), ग्रामीण डाकिया समस्या (आरपीपी), के-चीनी डाकिया समस्या (केसीपीपी), मिश्रित चीनी डाकिया समस्या (एमसीपीपी) के लिए बड़ी मात्रा में डेटा के साथ कुशल समाधान खोजना ), निर्देशित चीनी डाकिया समस्या (डीसीपीपी),^[8] डाउनहिल जुताई समस्या (डीपीपी), प्राथमिकता वाली जुताई समस्या (पीपीपी), विंडी ग्रामीण पोस्टमैन समस्या (डब्ल्यूआरपीपी) और विंडी जनरल रूटिंग समस्या (डब्ल्यूजीआरपी) के लिए ह्यूरिस्टिक (कंप्यूटर विज्ञान), शाखा और बाउंड सहित विचारशील गणितीय अवधारणाओं का उपयोग करने की आवश्यकता होती है। ब्रांच-एंड-बाउंड विधियां, पूर्णांक प्रोग्रामिंग, और हेल्ड-कार्प एल्गोरिदम जैसे ट्रैवलिंग सेल्समैन की समस्या एल्गोरिदम के अनुप्रयोग से सुधार होता है $O(n!)$ को $O(2^{n}n^{2})$ .^[9] इन एल्गोरिदम के अतिरिक्त, समस्याओं के इन वर्गों को कटिंग-प्लेन विधि, उत्तल अनुकूलन, उत्तल पतवार, लैग्रेंज गुणक और अन्य गतिशील प्रोग्रामिंग के साथ भी हल किया जा सकता है। ऐसे स्थितियों में जहां इसकी उच्च कम्प्यूटेशनल जटिलता के कारण हेल्ड-कार्प एल्गोरिथ्म को चलाना संभव नहीं है, इस तरह के एल्गोरिदम का उपयोग उचित समय में समाधान का अनुमान लगाने के लिए किया जा सकता है।^[10]

यूलेरियन परिपथ

आर्क रूटिंग समस्याओं के क्षेत्र का सबसे पहला प्रलेखित संदर्भ क्लासिक कोनिग्सबर्ग के सात पुलों कोनिग्सबर्ग के पुलों की चुनौती है, जिसे लियोनहार्ड यूलर ने असंभव सिद्ध किया था।^[4] कोनिग्सबर्ग के निवासी, जो अब कैलिनिनग्राद का भाग है, बहुत नंगा नदी पर बने सभी सात पुलों को बिना पीछे हटे या अपने कदम पीछे किए बिना पार करने का रास्ता खोजना चाहते थे, अर्थात प्रत्येक पुल को बार और केवल बार पार करना। 1736 में, यूलर ने समस्या को नोड्स और किनारों के प्रश्न तक सीमित कर दिया और दिखाया कि समस्या असंभव थी। 1873 में हियरहोल्ज़र ने क्लोज्ड परिपथ के प्रश्न पर अधिक कार्य किया था।^[4]

यूलेरियन परिपथ पर कार्य 1 जुलाई, 1953 को साइंटिफिक अमेरिकन के साथ लोकप्रिय हुआ था।^[11] इस कार्य को मेगु गुआन द्वारा बढ़ाया गया था, जिसे शांगटुन नॉर्मल कॉलेज में क्वान मेई-को के नाम से भी जाना जाता है। मेगु गुआन को बंद परिपथ का निर्धारण करने के बजाय अलग प्रश्न में रूचि थी। गुआन ने ग्राफ़ के प्रत्येक किनारे को कम से कम बार पार करने वाली न्यूनतम लंबाई का पता लगाने के लिए कार्य किया था। गुआन ने 1962 में अपने लक्ष्य का वर्णन किया था: डाकिये को डाकघर लौटने से पहले अपने निर्दिष्ट क्षेत्र को कवर करना होता है। समस्या डाकिया के लिए न्यूनतम पैदल दूरी का पता लगाने की है।^[4]

समस्या प्रकार

आर्क रूटिंग समस्याएं (एआरपी) उनके लक्ष्य और अनुमान में भिन्न होती हैं। चूँकि, ये सभी एनपी कठिन माने जाते हैं।

अप्रत्यक्ष ग्रामीण डाकिया समस्या

इस समस्या का नाम डाकिया और उसके द्वारा चुने गए किसी भी क्रम में डाक वितरित करने की उसकी चुनौती के नाम पर रखा गया है, किन्तु समय या यात्रा की दूरी जैसी उसकी निवेश को कम करते हुए। इसे कभी-कभी अप्रत्यक्ष चीनी डाकिया समस्या भी कहा जाता है। अप्रत्यक्ष ग्रामीण डाकिया समस्या (यूआरपीपी) का लक्ष्य उस मार्ग की कुल निवेश को कम करना है जो पूरे नेटवर्क को मैप करता है, या अधिक विशिष्ट स्थितियों में, ऐसा मार्ग जो हर किनारे को मैप करता है जिसके लिए सेवा की आवश्यकता होती है। यदि पूरे नेटवर्क को मैप किया जाना है, जिससे पूरे नेटवर्क को मैप करने वाले मार्ग को कवरिंग टूर कहा जाता है। ऐसे स्थिति में जहां केवल कुछ किनारों को मैप करने की आवश्यकता होती है, समस्या का उद्देश्य उस मार्ग को हल करना है जो मांगों को अनुकूलित करता है, गैर-आवश्यक मार्गों में न्यूनतम संख्या में पार करता है।^[12]

अप्रत्यक्ष कैपेसिटेटेड आर्क रूटिंग समस्या

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

इतिहास

यूआरपीपी को पहली बार 1974 में प्रस्तुत किया गया था और जन कैरेल लेनस्ट्रा और अलेक्जेंडर रिन्नॉय कान द्वारा इसे एनपी-हार्ड समस्या सिद्ध किया गया था। यूसीएआरपी को यूआरपीपी से प्राप्त किया जा सकता है, और इस प्रकार यह एनपी-हार्ड भी है। 1981 में, कंप्यूटर वैज्ञानिकों की और जोड़ी, गोल्डन और वोंग, यह सिद्ध करने में कामयाब रही कि यूआरपीपी के लिए .5 सन्निकटन प्राप्त करना भी एनपी-कठिन था। 2000 में, ड्रोर ने विभिन्न आर्क रूटिंग समस्याओं का वर्णन करते हुए पुस्तक प्रकाशित की थी।

विंडी डाकिया समस्या और वेरिएंट

मिनीका द्वारा प्रस्तावित विंडी पोस्टमैन समस्या मार्ग निरीक्षण समस्या का प्रकार है जिसमें इनपुट अप्रत्यक्ष ग्राफ है, किन्तु जहां प्रत्येक किनारे को दूसरी दिशा में पार करने की तुलना में इसे दिशा में पार करने के लिए अलग निवेश हो सकती है।^[13] निर्देशित और अप्रत्यक्ष ग्राफ़ के समाधान के विपरीत, यह एनपी-पूर्ण है।^[14]^[15] दिशा में यात्रा करने की निवेश तब अधिक होती है जब हवा आपके चेहरे की ओर चल रही हो, उस समय की तुलना में जब हवा आपकी पीठ की ओर हो, और यही विंडी पोस्टमैन समस्या नाम की उत्पत्ति है। सड़क को दिशा में पार करने में जो कार्य करना पड़ता है, वह तेज़ हवा वाले दिन में सड़क को दूसरी दिशा में पार करने में लगने वाले कार्य से भिन्न होता है।^[8]

विंडी पोस्टमैन समस्या आर्क रूटिंग समस्या (एआरपी) है जिसमें विशेष स्थिति के रूप में मिश्रित चीनी पोस्टमैन समस्या एमसीपीपी सम्मिलित है।^[16]

समस्या को निम्नलिखित विधि से परिभाषित किया जा सकता है: दो गैर-नकारात्मक निवेशों के साथ अप्रत्यक्ष और जुड़े ग्राफ G=(V,E) को देखते हुए $c_{i,j}$ और $c_{j,i}$ प्रत्येक किनारे से जुड़ा हुआ $\{i,j\}\in E$ क्रमशः i से j और j से i तक इसे पार करने की निवेश के अनुरूप, डब्ल्यूपीपी को प्रत्येक किनारे को कम से कम बार पार करते हुए G पर न्यूनतम निवेश का दौरा खोजना है।^[16] यह समस्या मिनीका द्वारा प्रस्तुत की गई थी। डब्ल्यूपीपी सामान्य रूप से एनपी-पूर्ण है और यदि जी यूलेरियन है, तो बहुपद समय में हल किया जा सकता है, यदि जी में प्रत्येक चक्र के दो विपरीत अभिविन्यासों की निवेश समान है या यदि जी श्रृंखला-समानांतर ग्राफ है। विंडी रूरल पोस्टमैन प्रॉब्लम (डब्ल्यूआरपीपी) डब्ल्यूपीपी का सामान्यीकरण है जिसमें ग्राफ़ के सभी किनारों को पार नहीं किया जाना है, किन्तु आवश्यक किनारों के दिए गए सबसेट में से केवल उन किनारों को पार करना है। उदाहरण के लिए, कुछ ग्रामीण सड़कों को पार करने के लिए डाकिया की आवश्यकता नहीं होती है और खड़ी पहाड़ियों पर कुछ सड़कों पर नीचे जाने की तुलना में ऊपर जाने में अधिक समय लगता है।^[10]

विंडी रूरल पोस्टमैन प्रॉब्लम (डब्ल्यूआरपीपी) डब्ल्यूपीपी का सामान्यीकरण है जिसमें ग्राफ़ के सभी किनारों को पार नहीं किया जाना है, किन्तु आवश्यक किनारों के दिए गए सबसेट में से केवल उन किनारों को पार करना है। उदाहरण के लिए, कुछ ग्रामीण सड़कों को पार करने के लिए डाकिया की आवश्यकता नहीं होती है और खड़ी पहाड़ियों पर कुछ सड़कों पर नीचे जाने की तुलना में ऊपर जाने में अधिक समय लगता है।^[10] एक अप्रत्यक्ष ग्राफ पर विचार करें $G=\{E,V\}$ दो निवेशों के साथ $c_{ij}$ और $c_{ji}$ किनारे को पार करने की निवेश से जुड़ा हुआ $(i,j)$ क्रमशः i और j से प्रारंभ करते हुए। जी घुमावदार ग्राफ है और हम किनारों के उपसमुच्चय, या गणितीय प्रतीकों $E_{R}\subseteq E$ में रुचि रखते हैं, .

यदि डब्ल्यूआरपीपी में अतिरिक्त बाधा सम्मिलित है कि शिखरों के निश्चित सेट का दौरा किया जाना चाहिए $V_{R}\subseteq V$ समस्या विंडी जनरल रूटिंग समस्या (डब्ल्यूजीआरपी) में बदल जाती है। बेनावेंट ने डब्ल्यूआरपीपी के लिए पूर्णांक रैखिक प्रोग्रामिंग फॉर्मूलेशन और विभिन्न अनुमान और निचली सीमाएं प्रस्तावित कीं थी। ^[9]

बेनावेंट एट अल ने मध्यम आकार के ग्राफ़ पर निचली सीमा से 1% से अधिक विचलन के साथ कुछ सेकंड में डब्ल्यूआरपीपी को हल करने के लिए उपयोग की जाने वाली कई अनुमानी विधियों का मूल्यांकन प्रकाशित किया था। उन्होंने स्कैटर सर्च एल्गोरिदम के साथ इसमें सुधार किया जिससे अंतर 0.5% तक कम हो गया था। स्कैटर सर्च ने ऐसे समाधान ढूंढे जो सैकड़ों नोड्स और हजारों किनारों वाले नेटवर्क पर प्रयुक्त होने पर 2% से कम विचलित हुए थे।^[9]

वास्तविक संसार के अनुप्रयोगों में, ऐसे कई वाहन हैं जो चल सकते हैं, जो मिन-मैक्स के-वाहन विंडी ग्रामीण पोस्टमैन समस्या (एमएम के-डब्ल्यूआरपीपी) नामक सामान्यीकरण की ओर ले जाता है। न्यूनतम-अधिकतम के-वाहन विंडी रूरल पोस्टमैन प्रॉब्लम (एमएम के-डब्ल्यूआरपीपी) को इस प्रकार परिभाषित किया गया है: विंडी ग्राफ दिया गया है $G=\{V,E\}$ , विशिष्ट शिखर, $1\in V$ , डिपो का प्रतिनिधित्व करते हुए, आवश्यक किनारों का उपसमूह $E_{R}\subseteq E$ , और वाहनों की निश्चित संख्या K, एमएम के-डब्ल्यूआरपीपी में वाहनों के लिए K टूर का सेट इस तरह से खोजना सम्मिलित है कि प्रत्येक टूर डिपो पर प्रारंभ और समाप्त हो और प्रत्येक आवश्यक किनारे की सेवा बिल्कुल वाहन द्वारा की जाए। इसका उद्देश्य वाहनों के लिए संतुलित मार्गों का सेट खोजने के लिए सबसे लंबे दौरे की लंबाई को कम करना है। न्यूनतम-अधिकतम उद्देश्यों के साथ रूटिंग समस्याओं के कुछ वास्तविक जीवन अनुप्रयोग हैं स्कूल बस रूटिंग (डेलगाडो और पाचेको 2001), ग्राहकों को समाचार पत्रों की डिलीवरी (एप्पलगेट एट अल। 2002) और अपशिष्ट संग्रह (लैकोमे एट अल। 2004)।^[10]

सर्वोत्तम एमएम के डब्ल्यूआरपीपी एल्गोरिथ्म 2 और 3 वाहनों के साथ न्यूनतम समाधान के बहुत निकट था, औसतन 0.4% से कम। 4 और 5 वाहनों पर अंतर बढ़कर लगभग 1.00% और 1.60% हो जाता है।

डसॉल्ट एट अल और बेनावेंट एट अल के अनुसार, मेटाह्यूरिस्टिक्स मल्टी-ऑब्जेक्टिव सिमुलेटिंग एनीलिंग एल्गोरिदम (एमओएसए) डब्ल्यूआरपीपी पर लगाए गए विभिन्न बाधाओं को हल कर सकता है। डब्ल्यूआरपीपी महत्वपूर्ण आर्क रूटिंग समस्या है जो एकल-वाहन आर्क रूटिंग की कई समस्याओं को सामान्य बनाती है। गणित के वास्तविक अनुप्रयोगों में, समाधान जो सभी वाहनों के मार्ग की कुल निवेश और सबसे लंबे दौरे की लंबाई को कम करता है, उत्तम है। ऐसे स्थान पर रहना कठिन है जहां आपका पैकेज सदैव घंटों देर से आता है।^[8] हमें इस धारणा से प्रारंभ करनी चाहिए कि ग्राहकों को सेवा प्रदान करने के लिए विशिष्ट मापनीय क्षमता वाले कई वाहन, अचूक अनंत क्षमता वाले वाहन की तुलना में अधिक यथार्थवादी हैं। रब्बानी एट. अल ने यांग एट अल द्वारा विकसित कोयल खोज के बहुउद्देश्यीय विकास का उपयोग करके मोसा एल्गोरिदम और मॉडल के प्रदर्शन को मापा गया था।^[17] इसे बहुउद्देश्यीय कुक्कू खोज के रूप में भी जाना जाता है और इसे एम.ओ.सी.एस द्वारा संक्षिप्त किया गया है।^[8] उन्होंने निष्कर्ष निकाला कि मोसा विधियाँ एम.ओ.सी.एस विधियों की तुलना में अधिक कुशल थीं। भविष्य में अन्य मेटा-ह्यूरिस्टिक विधियों के साथ तुलना पर शोध किया जा सकता है, जिसमें गैर-प्रभुत्व वाली सॉर्टिंग जेनेटिक एल्गोरिदम (एनएसजीए-), बहुउद्देश्यीय कण झुंड अनुकूलन एल्गोरिदम (एमओपीएसओ) और बहुउद्देश्यीय साम्राज्यवादी प्रतिस्पर्धी एल्गोरिदम सम्मिलित हैं।

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

विंडी पोस्टमैन समस्या के लिए एंजेल कॉर्बेरन द्वारा शाखा और कट एल्गोरिदम प्रकाशित किया गया था। एल्गोरिदम विषम-कट असमानता उल्लंघनों में हेरफेर करने के लिए अनुमानी और स्पष्ट विधियों पर आधारित है।^[16]

अनुप्रयोग

चीनी पोस्टमैन समस्या में विभिन्न संयोजक समस्याओं को कम कर दिया गया है, जिसमें समतल ग्राफ में अधिकतम कटौती और अप्रत्यक्ष ग्राफ में न्यूनतम-माध्य लंबाई परिपथ खोजना सम्मिलित है।^[18]

हिमपात हल

सर्दियों में सामान्य प्रश्न यह होता है कि मार्गों के किस समूह की मार्ग लंबाई सबसे छोटी (न्यूनतम) अधिकतम है? सामान्यतः, इसका मूल्यांकन ग्राफ़ के साथ आर्क रूटिंग समस्या के रूप में किया जाता है। किसी सड़क पर यात्रा करने में लगने वाला समय, जिसे डेडहेड टाइम के रूप में जाना जाता है, सड़कों से बर्फ हटाने (या मेल पहुंचाने या पैकेज छोड़ने) में लगने वाले समय से तेज़ होता है। बर्फ की जुताई के लिए आर्क रूटिंग प्रयुक्त करते समय और तथ्यों जिस पर विचार किया जाना चाहिए वह यह तथ्य है कि खड़ी सड़कों पर ऊपर की ओर जुताई करना या तो कठिन है या असंभव है। उद्देश्य ऐसा मार्ग है जो खड़ी सड़कों पर चढ़ने से बचाता है जो स्थान प्राप्त करने के लिए डेडहेड समय को अधिकतम करके कार्य को तेजी से पूरा करता है। इसे अनुमानी एल्गोरिदम के साथ तैयार किया गया था जो डसॉल्ट, गोल्डन और वासिल द्वारा निचली सीमा का अनुमान लगाता है। Cite error: Invalid <ref> tag; invalid names, e.g. too many यह डाउनहिल प्लो प्रॉब्लम (डीपीपी) है। हिम दल नीचे की ओर हल चलाना और ऊपर की ओर मृत पहाड़ी पर हल चलाना पसंद करते हैं। यह समस्या मानती है कि स्थितियाँ इतनी गंभीर हैं कि सड़कें बंद हैं और कोई यातायात नहीं है।

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

एक अप्रत्यक्ष ग्राफ पर विचार करते हुए $G=\{V,A\}$ जहाँ $V$ शीर्षों और नोड्स का सेट है और $A$ चापों का समुच्चय है. प्रत्येक चाप द्वारा दर्शाया गया है $(v_{i},v_{j})$ इसकी चार निवेशें हैं: $c_{ij}^{+}$ , से जुताई की निवेश के रूप में परिभाषित किया गया है $v_{i}$ को $v_{j}$ , $c_{ji}^{+}$ , से जुताई की निवेश $v_{j}$ को $v_{i}$ , $c_{ij}^{-}$ , से डेडहेडिंग की निवेश $v_{i}$ को $v_{j}$ , और $c_{ji}^{-}$ , से डेडहेडिंग की निवेश $v_{j}$ को $v_{i}$ . सेटअप यह मानता है $v_{j}$ अधिक ऊंचाई है $v_{i}$ , जो कथन की ओर ले जाता है: $c_{ij}^{+}\gg c_{ji}^{+}\gg c_{ij}^{-}\geq c_{ji}^{-}$ . व्यवहार में, ढलान पर जुताई का समय ऊपर की ओर जाने वाली जुताई की तुलना में दोगुना कुशल है और डेडहेडिंग का समय जुताई की तुलना में दोगुना कुशल है। एल्गोरिदम खोजता है $k$ प्रत्येक मार्ग डिपो पर प्रारंभ और समाप्त होगा $v_{0}$ , चाप को दो बार जोतें क्योंकि सड़क के बायीं ओर और दायीं ओर जुताई के लिए दो पास लगते हैं।

सबसे अच्छा समाधान अधिकतम मार्ग लंबाई को कम करना होगा। डसॉल्ट, गोल्डन और वासिल ने ऐसा एल्गोरिदम पाया जो 80 से अधिक परीक्षण रनों में निचली सीमा 5.5% से अधिक नहीं था। जैसे-जैसे मॉडल की जटिलता बढ़ती गई, विचलन बढ़ता गया क्योंकि जैसे-जैसे मॉडल बढ़ता है, अनुकूलित सन्निकटन की तुलना में अधिक अअनुकूलित सन्निकटन होते हैं। डसॉल्ट एट पर सुधार। अल के डीपीपी एल्गोरिदम में यू-टर्न और बाएं हाथ के मोड़ बनाने, या सीधे चौराहे पर जाने के लिए दंड हो सकता है, जो क्रमशः अतिरिक्त समय लेता है और बर्फ को चौराहे के बीच में धकेलता है। (द डायरेक्टेड रूरल पोस्टमैन प्रॉब्लम विद टर्न पेनल्टी प्रॉब्लम देखें, जिसे अधिकांशतः नीचे डीआरपीपी-टीपी के रूप में जाना जाता है)।

के-चीनी डाकिया समस्या (के-सीपीपी)

के-चीनी पोस्टमैन को इस प्रकार कहा जा सकता है: जुड़े हुए किनारे-भारित ग्राफ जी और पूर्णांक पी और के को देखते हुए, तय करें कि क्या कम से कम के बंद रास्ते हैं जैसे कि जी का प्रत्येक किनारा उनमें से कम से कम में समाहित है और वॉक में किनारों का कुल वजन अधिकतम p है? के-सीपीपी का समाधान प्राप्त करने की प्रक्रिया एनपी पूर्ण है। गुटिन, म्यूसियासिया और येओ ने 2013 में सिद्ध किया कि के-सीपीपी निश्चित-पैरामीटर ट्रैक्टेबल है।^[19] लेखक सिद्ध करते हैं कि के-सीपीपी कर्नेल $O(k^{2}\log(k))$ को स्वीकार करता है कोने और के-सीपीपी का निर्देशित संस्करण एनपी पूर्ण है।

ग्रामीण डाकिया समस्या (आरपीपी) और सामान्यीकरण

ग्रामीण डाकिया समस्या (आरपीपी) कुछ मार्गों को अनिवार्य और पूर्ण बनाती है किन्तु ग्राफ को पार करने वाले व्यक्ति को विशेष दिशा में नहीं जाना पड़ता है। आरपीपी एनपी हार्ड और पूर्ण है, उसी तरह जैसे केसीपीपी, डीपीपी, पीपीपी, एनपी हार्ड हैं। बेनेवेंट ने डायरेक्टेड रूरल पोस्टमैन प्रॉब्लम विद टर्न पेनल्टीज़ (डीआरपीपी-टीपी) नामक इसके सामान्यीकरण का अध्ययन किया था।^[20] बेनेवेंट के एल्गोरिदम ने डीआरपीपी-टीपी को असममित यात्रा सेल्समैन समस्या (एटीएसपी) में परिवर्तित करके समाधान का अनुमान लगाया गया था।

ह्यूरिस्टिक्स और एल्गोरिदम

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

एक बार प्री-प्रोसेसिंग हो जाने के बाद, समस्या को उत्तल पतवार समस्या में सामान्यीकृत किया जा सकता है, जिसके किनारे पतवार के बिंदु होते है। उत्तल पतवार समस्या को रैखिक प्रोग्रामिंग या उत्तल पतवार एल्गोरिदम के माध्यम से हल किया जा सकता है, किन्तु उत्तल पतवार खोजने की प्रक्रिया घातीय समस्या है।

प्री-प्रोसेसिंग पूरी होने के बाद यूआरपीपी को हल करने के विधियों में इंटीजर प्रोग्रामिंग और ब्रांच और कट|ब्रांच और कट पद्धति सम्मिलित है।^[21]

जटिलता

यह विभिन्न आर्क रूटिंग समस्याओं के लिए कम्प्यूटेशनल जटिलताओं की सूची है।

सीपी वैरिएंट	मौलिक जटिलता	अनुमान	पैरामीट्रिज्ड जटिलता
अनिर्दिष्ट	$O(\|V\|^{3})$ -समय एल्गोरिथ्म^[22]
निर्देशित	$O(\|V\|^{3})$ -समय एल्गोरिथ्म^[22] $O((\|E\|-\|V\|)\|V\|^{2})$ -समय एल्गोरिथ्म^[23]
मिश्रित	एन पी-सम्पूर्ण^[24] $O(\|V\|^{3})$ -यदि प्रत्येक शीर्ष पर सम डिग्री हो तो समय हल किया जा सकता है^[22]	$O(\max\{\|V\|^{3},\|A\|(\max\{\|A\|,\|E\|\})^{2}\})$ -time factor 3/2^[25]	$O(2^{\|E\|}\cdot \|V\|^{3})$ -समय एल्गोरिथ्म^[26] एफपीटी में \|ए\| के संबंध में^[26] एक्सपी में ट्रीविड्थ के संबंध में^[27]
विंडी	एनपी-पूर्ण^[28] कुछ विशेष स्थितियों में पी^[28]^[29]	कारक 3/2^[30]
k-पदानुक्रमित	एनपी-पूर्ण^[31] $O(k\|V\|^{4})$ -यदि प्राथमिकता संबंध रैखिक हो तो समय पर हल किया जा सकता है
मिन-सम के पोस्टमैन	$O(\|V\|^{3})$ -पोस्ट ऑफिस वर्टेक्स के साथ समय एल्गोरिथ्म,^[32] अन्यथा एनपी-पूर्ण^[33]		एफपीटी में पोस्ट ऑफिस वर्टेक्स के बिना के के संबंध में^[34]
न्यूनतम-अधिकतम k डाकिए	एनपी-पूर्ण^[35]	$O(\|V\|^{3})$ -समय कारक(2-1/के)<रेफरी नाम= फ्रेडरिकसन 178-193 />