Capacitated arc routing problem
গণিতে, ক্যাপাসিটেড আর্ক রাউটিং প্রবলেম (সি. এ. আর. পি) হল একটি মিশ্র গ্রাফের ন্যূনতম গ্রাফ/ভ্রমণ দূরত্ব সহ অনির্দিষ্ট প্রান্ত এবং নির্দেশিত চাপের সাথে সংক্ষিপ্ততম সফর খুঁজে বের করা যা গ্রাফ বরাবর চলাচলকারী বস্তুর জন্য ক্ষমতার সীমাবদ্ধতা দেওয়া হয় যা তুষার-প্লওয়ার, স্ট্রিট সুইপিং মেশিন, বা শীতকালীন গ্রিটার, বা ক্ষমতা সীমাবদ্ধতা সহ অন্যান্য বাস্তব-বিশ্বের বস্তুর প্রতিনিধিত্ব করে। কেন্দ্রীয় ডিপো থেকে গাড়িটি কতদিন দূরে থাকবে, বা মোট যে দূরত্ব অতিক্রম করবে, বা ভিন্ন ভিন্ন ওজনের কারণ সহ দুটির সংমিশ্রণের জন্য এই সীমাবদ্ধতা আরোপ করা যেতে পারে। অ্যাঞ্জেল করবেরান এবং গিলবার্ট লাপোর্তে রচিত 'আর্ক রাউটিংঃ প্রবলেম, মেথডস, অ্যান্ড অ্যাপ্লিকেশনস "বইটিতে সিএআরপি-র বিভিন্ন বৈচিত্র্য বর্ণনা করা হয়েছে। সি. এ. আর. পি-র সমাধানে সংক্ষিপ্ততম পথটি দক্ষতার সাথে খুঁজে বের করার জন্য গ্রাফ তত্ত্ব, আর্ক রাউটিং, অপারেশন গবেষণা এবং ভৌগলিক রাউটিং অ্যালগরিদমগুলির অধ্যয়ন জড়িত। সি. এ. আর. পি হল এন. পি-হার্ড আর্ক রাউটিং সমস্যা। সিএআরপি উত্তল হুল সহ সমন্বিত অপ্টিমাইজেশনের মাধ্যমে সমাধান করা যেতে পারে। বড় মাপের ক্যাপাসিটেড আর্ক রাউটিং সমস্যা (এল. এস. সি. এ. আর. পি) ক্যাপাসিটেড আর্ক রাউটিং সমস্যার একটি রূপ যা বাস্তবসম্মতভাবে বড় জটিল পরিবেশের অনুকরণ এবং মডেল করার জন্য শত শত প্রান্ত এবং নোডের ক্ষেত্রে প্রযোজ্য। তথ্যসূত্র গ্রাফ তত্ত্ব