आर्क रूटिंग

आर्क रूटिंग समस्याएं (एआरपी) सामान्य रूटिंग समस्याओं (जीआरपी) की एक श्रेणी है, जिसमें नोड रूटिंग समस्याएं (एनआरपी) भी शामिल हैं। एआरपी और एनआरपी में उद्देश्य क्रमशः ग्राफ के किनारों और नोड्स को पार करना है। आर्क रूटिंग समस्याओं के उद्देश्य में कुल दूरी और समय को कम करना शामिल है, जिसमें अक्सर ख़राब माइलेज समय, किसी गंतव्य तक पहुंचने में लगने वाला समय, को कम करना शामिल होता है। आर्क रूटिंग समस्याओं को अपशिष्ट संग्रहण, स्कूल बस मार्ग योजना, पैकेज और समाचार पत्र वितरण, सड़क पर नमक छिड़कने वाले शीतकालीन सेवा वाहन के साथ बर्फ हटाने और बर्फ हटाने के लिए लागू किया जा सकता है। मेल, नेटवर्क रखरखाव, सफाई कर्मचारी , पुलिस और सुरक्षा गार्ड गश्त,और बर्फ़ की जुताई।<संदर्भ नाम = डसॉल्ट 1465-1474 >Dussault, Benjamin; Golden, Bruce; Wasil, Edward (October 2014). "एकाधिक हलों के साथ डाउनहिल हल की समस्या". Journal of the Operational Research Society (in English). 65 (10): 1465–1474. doi:10.1057/jors.2013.83. ISSN 0160-5682. S2CID 36977043.</ref> रूट निरीक्षण समस्या के विपरीत आर्क रूटिंग समस्याएं एनपी-कठोरता हैं, जिन्हें बहुपद-समय में हल किया जा सकता है।

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

पृष्ठभूमि

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

आधार

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

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

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

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

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

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

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

एल्गोरिदम

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

यूलेरियन सर्किट

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

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

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

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

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

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

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

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

इतिहास

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

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

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

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

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

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

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

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

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

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

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

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

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

अनुप्रयोग

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

हिमपात हल

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

डाउनहिल जुताई की समस्या प्राथमिकता वाली जुताई की समस्या (पीपीपी) को नजरअंदाज करती है, जो इस उचित धारणा पर बनाई गई है कि यदि बर्फ बहुत गहरी है तो बर्फ का हल बिना जुताई वाली सड़क को खत्म नहीं कर सकता है। डीपीपी यह अनुमान लगाता है कि बर्फ का स्तर इतना कम है कि जिन सड़कों पर जुताई नहीं की गई है वे क्षतिग्रस्त हो सकती हैं, लेकिन बर्फ इतनी गहरी है कि कोई यातायात नहीं है। यदि सड़कों पर यातायात है, तो यह धारणा कि ऊपर की ओर हल चलाना असंभव है, अब टिकी नहीं रह सकती। डीपीपी डेडहेडेड अनप्लोस्टेड स्ट्रीट के लिए सिमुलेशन लगभग 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 में साबित किया कि के-सीपीपी निश्चित-पैरामीटर ट्रैक्टेबल है। लेखक साबित करते हैं कि के-सीपीपी एक कर्नेल को स्वीकार करता है $O(k^{2}\log(k))$ कोने और के-सीपीपी का निर्देशित संस्करण एनपी पूर्ण है।

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

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

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

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

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

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

जटिलता

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

CP variant	Classical complexity	Approximation	Parametrized complexity
Undirected	$O(|V|^{3})$-time algorithm
Directed	$O(|V|^{3})$-time algorithm $O((|E|-|V|)|V|^{2})$-time algorithm
Mixed	NP-complete $O(|V|^{3})$-time solvable if each vertex has even degree	$O(\max\{|V|^{3},|A|(\max\{|A|,|E|\})^{2}\})$-time factor 3/2	$O(2^{|E|}\cdot |V|^{3})$-समय एल्गोरिथ्म एफपीटी में |ए| के संबंध में एक्सपी में ट्रीविड्थ के संबंध में
हवादार	एनपी-पूर्ण कुछ विशेष मामलों में पी	कारक 3/2
k-पदानुक्रमित	एनपी-पूर्ण $O(k|V|^{4})$-यदि प्राथमिकता संबंध रैखिक हो तो समय पर हल किया जा सकता है
मिन-सम के पोस्टमैन	$O(|V|^{3})$-पोस्ट ऑफिस वर्टेक्स के साथ समय एल्गोरिथ्म, अन्यथा एनपी-पूर्ण		एफपीटी में पोस्ट ऑफिस वर्टेक्स के बिना के के संबंध में
न्यूनतम-अधिकतम k डाकिए	एनपी-पूर्ण<रेफरी नाम= फ्रेडरिकसन 178-193 >Frederickson, Greg N.; Hecht, Matthew S.; Kim, Chul E. (May 1978). "कुछ रूटिंग समस्याओं के लिए सन्निकटन एल्गोरिदम". SIAM Journal on Computing. 7 (2): 178–193. doi:10.1137/0207017. ISSN 0097-5397. S2CID 7562375.</ref>	$O(|V|^{3})$-समय कारक(2-1/के)<रेफरी नाम= फ्रेडरिकसन 178-193 />

आर्क रूटिंग वेरिएंट की सूची

Problem	Abbreviation	Description	Output Notes	Examples
Arc Routing Problem	ARP	Determine a least-cost traversal of a specified arc subset of a graph, with or without constraints.		Seven Bridges of Konigsberg
Chinese Postman Problem	CPP	undirected graph G with Vertices V and weighted edges E	Traverse every edge at least once with minimal cost	"A mailman has to cover his assigned segment before returning to the post office. The problem is to find the shortest walking distance for the mailman."
Rural Postman Problem	RPP	undirected graph G with Vertices V and weighted edges E	Traverse a subset of the edges E at least once with minimum cost
Directed Rural Postman Problem	DRPP
Rural Postman Problem with Turn Penalties	RPP-TP, RPPTP
Windy Postman Problem	WPP
Windy Rural Postman Problem	WRPP
Street Sweeper Problem	SPP
m-Plowing Problem	m-PP
Capacitated Plow Problem	C-PP
Downhill Plow Problem	DPP
Downhill Plow Problem with Turn Penalties	DPP-TP
Rural Downhill Plow Problem with Turn Penalties	RDPP-TP
Capacitated Arc Routing Problem	CARP
k-Plow Windy Rural Postman Problem	k-WRPP
Min-Max Downhill Plow Problem with Multiple Plows	MM k-DPP
Min-Max Windy Rural Postman Problem	MM k-WRPP
Plowing with Precedence Problem	PPP
Min-Max Extended Downhill Plow Problem	MM k-DPPE
Capacitated Chinese Postman Problem	CCPP
Directed Chinese Postman Problem	DCPP
Directed Rural Postman Problem	DRPP
Extended Capacitated Arc Routing Problem	ECARP
Hierarchical Chinese Postman Problem	HCPP
Mixed Capacitated Arc Routing Problem	MCARP
Mixed Chinese Postman Problem	MCPP
Stacker Crane Problem	SCP	Certain arcs must be traversed at least once in one direction but can be traversed as many times in the other direction
Traveling Salesman Problem	TSP
Undirected Capacitated Arc Routing Problem	UCARP
Undirected Rural Postman Problem	URPP
Vehicle Routing Problem	VRP
Min-Max Multiple-Depot Rural Postman Problem	MMMDRPP
Generalized Vehicle Routing Problem	GVRP

बाहरी संबंध

• Arc Routing Problems Search page at Lancaster University
• Trends in Arc Routing

यह भी देखें

• मार्ग निरीक्षण समस्या
• वाहन रूटिंग की समस्या
• ट्रैवलिंग सेल्समैन की समस्या
• यूलेरियन पथ
• कैपेसिटेटेड आर्क रूटिंग समस्या
• ग्राफ सिद्धांत समस्याओं की सूची
• स्नो प्लो रूटिंग समस्या
• चीनी डाकिया समस्या जटिलता सूची