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

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

CARP के कई भिन्न प्रकार हैं जिसे एंजेल कॉर्बेरन और गिल्बर्ट लापोर्टे की पुस्तक आर्क रूटिंग: प्रॉब्लम्स, मेथड्स, एंड एप्लिकेशन में दर्शाया गया हैं।

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

CARP, एनपी-कठोर चाप मार्ग समस्या है।

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

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