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

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

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

CARP एनपी-कठोरता |एनपी-हार्ड आर्क रूटिंग समस्या है।

CARP को उत्तल पतवार सहित संयोजन अनुकूलन के साथ हल किया जा सकता है।

बड़े पैमाने पर कैपेसिटेटेड आर्क रूटिंग समस्या (एलएससीएआरपी) कैपेसिटेटेड आर्क रूटिंग समस्या का एक प्रकार है जो बड़े जटिल वातावरणों को वास्तविक रूप से अनुकरण और मॉडल करने के लिए सैकड़ों किनारों और नोड्स पर लागू होता है।