आर्क रूटिंग

आर्क रूटिंग समस्याएं (एआरपी) सामान्य रूटिंग समस्याओं (जीआरपी) की एक श्रेणी है, जिसमें नोड रूटिंग समस्याएं (एनआरपी) भी शामिल हैं। एआरपी और एनआरपी में उद्देश्य क्रमशः ग्राफ के किनारों और नोड्स को पार करना है। आर्क रूटिंग समस्याओं के उद्देश्य में कुल दूरी और समय को कम करना शामिल है, जिसमें अक्सर ख़राब माइलेज समय, किसी गंतव्य तक पहुंचने में लगने वाला समय, को कम करना शामिल होता है। आर्क रूटिंग समस्याओं को अपशिष्ट संग्रहण, स्कूल बस मार्ग योजना, पैकेज और समाचार पत्र वितरण, सड़क पर नमक छिड़कने वाले शीतकालीन सेवा वाहन के साथ बर्फ हटाने और बर्फ हटाने के लिए लागू किया जा सकता है। मेल, नेटवर्क रखरखाव, सफाई कर्मचारी , पुलिस और सुरक्षा गार्ड गश्त,और बर्फ़ की जुताई।<संदर्भ नाम = डसॉल्ट 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$