সবচেয়ে সাধারণ অপ্টিমাইজেশন কাজগুলির মধ্যে একটি হল যানবাহন রাউটিং , যার লক্ষ্য হল একটি নির্দিষ্ট স্থানে পরিদর্শন করা যানবাহনের বহরের জন্য সেরা রুটগুলি খুঁজে বের করা৷ সাধারণত, "সেরা" মানে সর্বনিম্ন মোট দূরত্ব বা খরচ সহ রুট। এখানে রাউটিং সমস্যার কয়েকটি উদাহরণ রয়েছে:
- একটি প্যাকেজ ডেলিভারি কোম্পানি চালকদের ডেলিভারি করার জন্য রুট নির্ধারণ করতে চায়।
- একটি কেবল টিভি কোম্পানি প্রযুক্তিবিদদের আবাসিক পরিষেবা কল করার জন্য রুট নির্ধারণ করতে চায়।
- একটি রাইড-শেয়ারিং কোম্পানি চালকদের যাত্রী তোলা এবং নামানোর জন্য রুট নির্ধারণ করতে চায়।
সবচেয়ে বিখ্যাত রাউটিং সমস্যা হল ট্রাভেলিং সেলসপার্সন প্রবলেম (টিএসপি): একজন বিক্রয়কর্মীর জন্য সংক্ষিপ্ততম রুট খুঁজুন যাকে বিভিন্ন স্থানে গ্রাহকদের সাথে দেখা করতে হবে এবং স্টার্টিং পয়েন্টে ফিরে যেতে হবে। একটি টিএসপি একটি গ্রাফ দ্বারা প্রতিনিধিত্ব করা যেতে পারে, যেখানে নোডগুলি অবস্থানগুলির সাথে মিলে যায় এবং প্রান্তগুলি (বা আর্কস) অবস্থানগুলির মধ্যে সরাসরি ভ্রমণকে বোঝায়৷ উদাহরণ স্বরূপ, নীচের গ্রাফটি A, B, C, এবং D লেবেলযুক্ত মাত্র চারটি অবস্থান সহ একটি TSP দেখায়। যেকোনো দুটি অবস্থানের মধ্যে দূরত্ব তাদের যোগদানকারী প্রান্তের পাশের সংখ্যা দ্বারা দেওয়া হয়।
সমস্ত সম্ভাব্য রুটের দূরত্ব গণনা করে, আপনি দেখতে পারেন যে সবচেয়ে ছোট রুটটি হল ACDBA, যার জন্য মোট দূরত্ব হল 35 + 30 + 15 + 10 = 90 ।
যখন আরও অবস্থান থাকে তখন সমস্যা আরও কঠিন হয়। উপরের উদাহরণে, মাত্র ছয়টি রুট আছে। কিন্তু যদি দশটি অবস্থান থাকে (প্রারম্ভিক বিন্দু গণনা না করে), রুটের সংখ্যা হয় 362880। 20টি অবস্থানের জন্য, সংখ্যাটি 2432902008176640000-এ চলে যায়। সমস্ত সম্ভাব্য রুটের একটি সম্পূর্ণ অনুসন্ধানের মাধ্যমে সবচেয়ে ছোট পথ খুঁজে পাওয়ার নিশ্চয়তা দেওয়া হবে, তবে এটি গণনাগতভাবে। অবস্থানের ছোট সেট বাদে সকলের জন্য জটিল। বৃহত্তর সমস্যার জন্য, অপ্টিমাইজেশান কৌশলগুলি বুদ্ধিমত্তার সাথে সমাধানের স্থান অনুসন্ধান করতে এবং একটি সর্বোত্তম (বা কাছাকাছি-অনুকূল) সমাধান খুঁজে পেতে প্রয়োজন।
TSP-এর আরও সাধারণ সংস্করণ হল গাড়ির রাউটিং সমস্যা (VRP), যেখানে একাধিক যানবাহন রয়েছে। বেশিরভাগ ক্ষেত্রে, VRP-এর সীমাবদ্ধতা রয়েছে: উদাহরণস্বরূপ, যানবাহনগুলির সর্বোচ্চ ওজন বা আইটেমগুলির পরিমাণের ক্ষমতা থাকতে পারে যা তারা বহন করতে পারে, বা গ্রাহকদের অনুরোধ করা নির্দিষ্ট সময়ের মধ্যে ড্রাইভারদের অবস্থানগুলি পরিদর্শন করতে হতে পারে।
OR-Tools নিম্নলিখিতগুলি সহ অনেক ধরনের VRPs সমাধান করতে পারে:
- ভ্রমণ বিক্রয়কর্মী সমস্যা , ক্লাসিক রাউটিং সমস্যা যেখানে শুধুমাত্র একটি গাড়ি আছে।
- যানবাহন রাউটিং সমস্যা , একাধিক যানবাহনের সাথে TSP-এর সাধারণীকরণ।
- ক্ষমতার সীমাবদ্ধতা সহ VRP , যেখানে যানবাহনগুলি বহন করতে পারে এমন আইটেমগুলির জন্য সর্বাধিক ক্ষমতা রয়েছে৷
- সময় জানালা সহ VRP , যেখানে যানবাহনগুলিকে নির্দিষ্ট সময়ের ব্যবধানে অবস্থানগুলি পরিদর্শন করতে হবে৷
- সম্পদের সীমাবদ্ধতা সহ VRP , যেমন ডিপোতে যানবাহন লোড এবং আনলোড করার জন্য স্থান বা কর্মী (রুটগুলির জন্য শুরুর স্থান)।
- ড্রপ করা ভিজিট সহ VRP , যেখানে যানবাহনগুলিকে সমস্ত অবস্থানে যাওয়ার প্রয়োজন নেই, তবে বাদ দেওয়া প্রতিটি ভিজিটের জন্য অবশ্যই একটি জরিমানা দিতে হবে৷
যানবাহন রাউটিং সমস্যা সমাধানে সীমাবদ্ধতা
যানবাহন রাউটিং সমস্যাগুলি সহজাতভাবে জটিল: সেগুলি সমাধান করতে যে সময় লাগে তা সমস্যার আকারের সাথে দ্রুত বৃদ্ধি পায়। যথেষ্ট বড় সমস্যার জন্য, সর্বোত্তম সমাধান খুঁজে পেতে OR-Tools (বা অন্য কোনো রাউটিং সফ্টওয়্যার) বছর লাগতে পারে। ফলস্বরূপ, OR-Tools কখনও কখনও এমন সমাধান প্রদান করে যা ভাল, কিন্তু সর্বোত্তম নয়। একটি ভাল সমাধান খুঁজতে, সমাধানকারীর জন্য অনুসন্ধান বিকল্পগুলি পরিবর্তন করুন৷ একটি উদাহরণের জন্য অনুসন্ধান কৌশল পরিবর্তন দেখুন।