Capacitated arc routing problem
ریاضی میں، کیپسیٹیٹڈ آرک روٹنگ مسئلہ (سی اے آر پی) وہ ہے جس میں غیر ہدایت شدہ کناروں اور ہدایت شدہ آرکس کے ساتھ مخلوط گراف کے کم از کم گراف/سفر کے فاصلے کے ساتھ مختصر ترین دورے کو تلاش کرنا ہے جو گراف کے ساتھ ساتھ حرکت کرنے والی اشیاء کے لیے صلاحیت کی رکاوٹوں کو دیکھتے ہیں جو برف کے پلورز، اسٹریٹ سویپنگ مشینوں، یا سرمائی گریٹرز، یا صلاحیت کی رکاوٹوں کے ساتھ دیگر حقیقی دنیا کی اشیاء کی نمائندگی کرتے ہیں۔ یہ پابندی اس وقت کے لیے لگائی جا سکتی ہے جب گاڑی مرکزی ڈپو سے دور ہو، یا طے شدہ کل فاصلہ، یا مختلف وزن کے عوامل کے ساتھ دونوں کا مجموعہ ہو۔ سی اے آر پی کے بہت سے مختلف تغیرات ہیں جو کتاب آرک روٹنگ میں بیان کیے گئے ہیں: مسائل، طریقے، اور ایپلی کیشنز بذریعہ اینجل کوربرن اور گلبرٹ لاپورٹے۔ سی اے آر پی کو حل کرنے میں مختصر ترین راستے کو مؤثر طریقے سے تلاش کرنے کے لیے گراف تھیوری، آرک روٹنگ، آپریشنز ریسرچ، اور جغرافیائی روٹنگ الگورتھم کا مطالعہ شامل ہے۔ سی اے آر پی این پی ہارڈ آرک روٹنگ کا مسئلہ ہے۔ سی اے آر پی کو کنویکس ہلز سمیت مشترکہ اصلاح کے ساتھ حل کیا جا سکتا ہے۔ بڑے پیمانے پر کیپسیٹیٹڈ آرک روٹنگ کا مسئلہ (ایل ایس سی اے آر پی) کیپسیٹیٹڈ آرک روٹنگ کے مسئلے کی ایک قسم ہے جو سینکڑوں کناروں اور نوڈس پر لاگو ہوتا ہے تاکہ حقیقی طور پر بڑے پیچیدہ ماحول کی تقلید اور نمونہ بنایا جا سکے۔ حوالہ جات گراف تھیوری