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