Large-scale capacitated arc routing problem
লার্জ-স্কেল ক্যাপাসিটেড আর্ক রাউটিং প্রবলেম (এল. এস. সি. এ. আর. পি) হল ক্যাপাসিটেড আর্ক রাউটিং সমস্যার একটি রূপ যা বড় স্কেলে জটিল আর্ক রাউটিং সমস্যার মডেল তৈরি করতে 300 বা তার বেশি প্রান্ত জুড়ে থাকে। ইয়ি মেই এবং অন্যান্য। একটি সমবায় সহ-বিবর্তন অ্যালগরিদম ব্যবহার করে বড় আকারের ক্যাপাসিটেড আর্ক রাউটিং সমস্যা সমাধানের জন্য একটি অ্যালগরিদম প্রকাশ করেছে। এলএসসিএআরপি একটি বিভাজন এবং জয় অ্যালগরিদমের মাধ্যমে সমাধান করা যেতে পারে যা পচন বন্ধ করার পথে প্রয়োগ করা হয়। এলএসসিএআরপি একটি পুনরাবৃত্ত স্থানীয় অনুসন্ধানের মাধ্যমেও সমাধান করা যেতে পারে যা অন্যান্য পদ্ধতির উপরের এবং নীচের সীমানায় উন্নতি করে। ডেনমার্কে বর্জ্য সংগ্রহের জন্য একটি এলএসসিএআরপি অ্যালগরিদম প্রয়োগ করা হয়েছে যার নাম ফাস্ট-সিএআরপি। অ্যালগরিদমটি প্রায়শই টাইম ক্যাপাসিটেড আর্ক রাউটিং সমস্যা হিসাবেও উল্লেখ করা হয় যা প্রায়শই টিসিএআরপি হিসাবে উল্লেখ করা হয়। টিসিএআরপি যুক্তিসঙ্গত সময়ের মধ্যে একটি মেটা-হিউরিস্টিক দিয়ে সমাধান করা যেতে পারে। টিসিএআরপি প্রায়শই দেখা দেয় যখন আয়তনের সীমাবদ্ধতা প্রযোজ্য হয় না উদাহরণস্বরূপ মিটার রিডিং ঝাং এট আল। রুট ক্লাস্টারিং এবং সার্চ হিউরিস্টিক নামে লার্জ-স্কেল মাল্টি-ডিপো সি. এ. আর. পি (এল. এস. এম. ডি. সি. এ. আর. পি) নামে একটি সাধারণীকরণ সমাধান করার জন্য একটি মেটা-হিউরিস্টিক তৈরি করেছিলেন। 2017 সালে এল. এস. সি. এ. আর. পি-র জন্য এক্সটেনশন স্টেপ এবং স্ট্যাটিস্টিক্যাল ফিল্টারিং ফর লার্জ-স্কেল সি. এ. আর. পি (ই. এস. এম. এ. ই. এন. এস) নামে একটি অ্যালগরিদম তৈরি করা হয়েছিল। এল. এস. সি. এ. আর. পি একটি হায়ারার্কিক্যাল ডিকম্পোসিশন অ্যালগরিদম সহ একটি বড় আকারের ক্যাপাসিটেড যানবাহন রাউটিং সমস্যায় প্রসারিত করা যেতে পারে। এল. এস. সি. ভি. আর. পি স্থানীয় অনুসন্ধানের উপর ভিত্তি করে একটি বিবর্তনীয় পদ্ধতির মাধ্যমে সমাধান করা যেতে পারে। এল. এস. সি. ভি. আর. পি-র সমাধান সমন্বিত সাপোর্ট ভেক্টর মেশিন এবং এলোমেলো বন পদ্ধতির মাধ্যমে করা যেতে পারে। সিমুলেটেড অ্যানিলিংয়ের উপর ভিত্তি করে এল. এস. সি. এ. আর. পি সমাধান করার জন্য একটি অ্যালগরিদম তৈরি করেছিলেন অ্যাকোর্সি এবং অন্যান্যরা। তথ্যসূত্র গ্রাফ তত্ত্ব