چند سالی است که گوگل ابزاری را برای تأمین زیرساخت حل مسأله در حوزه تحقیق در عملیات و بهینه سازی ریاضی ارائه کرده است. Google OR-Tools یک نرم افزار متن‌باز برای بهینه سازی ترکیبیاتی (Combinatorial optimization) است که توسط گوگل پیاده‌سازی شده و در دسترس عموم قرار گرفته است. Google OR Tools تلاش می‌کند تا پاسخ مسائل مورد نظر را از گستره وسیع پاسخ‌های ممکن پیدا کند. در ادامه به معرفی این سرویس و شیوه استفاده از آن می‌پردازیم.
معرفی OR-Tools: این سرویس چیست و چه می‌کند؟!
براساس معرفی که خود گوگل درباره این سرویس ارائه داده است، مثال‌هایی از مسأله‌هایی که OR-Tools می‌تواند به حل آنها کمک کند این ها است:
- مسیریابی: در این مسأله، مسیر بهینه برای ناوگان حمل و نقل که اقدام به دریافت و تحویل محموله‌های موردنظر می‌کنند مورد بررسی قرار می‌گیرد. معمولا محدودیت‌های قابل توجهی هم در این مسأله مسیریابی وسائل نقلیه (Vehicle routing) درنظر گرفته می‌شود. مثلا اینکه ظرفیت یک کامیون چقدر باشد یا اینکه همه محموله‌ها باید طی یک بازه زمانی معیّن به مقصد برسد.
- زمان‌بندی: در مسأله زمان‌بندی (Scheduling) تلاش می‌شود تا برنامه زمانی بهینه برای مجموعه پیچیده‌ای از کارها یافته شود. در این بین محدودیت‌هایی نظیر روابط بین کارها و تعداد ثابت یا متناهی ماشین‌ها یا منابع پردازش کارها نیز وجود خواهد داشت.
- بسته‌بندی: در مسائل بسته‌بندی یا Bin packing به دنبال چیدمان آیتم‌ها یا اشیای مختلف با سایزهای گوناگون در تعداد ثابتی بسته با حداکثر ظرفیت هستیم.
در اغلب موارد، جواب های ممکن (نقاط شدنی) متعدد و زیادی برای مسائلی نظیر مسائل فوق وجود دارد. به همین دلیل، پردازش و جستجو در میان این حجم از پاسخ‌های شدنی برای یک کامپیوتر دشوار و طولانی خواهد بود. به‌منظور غلبه بر این مشکل، سرویس OR-Tools گوگل با استفاده از الگوریتم‌های به‌روز و مناسب تلاش می‌کند تا مجموعه جستجو را محدود کرده و بتواند پاسخ بهینه یا نزدیک به بهینه را بیابد.
شاخه‌های بهینه‌سازی مورد توجه Google OR-Tools
برنامه‌ریزی ریاضی با محدودیت
مجموعه‌ای از روش‌ها برای یافتن پاسخ‌های شدنی (feasible solutions) در یک مسأله بهینه‌سازی با محدودیت (مثلا یک اتاق یا کلاس که نمی‌تواند همزمان به دو رویداد یا برنامه اختصاص یابد؛ یا فاصله تا محصولات زراعی در یک مزرعه باید کمتر از طول ابزار آب‌رسانی باشد و یا تعداد ضبط همزمان برنامه تلویزیونی حداکثر باید پنج تا باشد) پوشش داده می‌شود.
برنامه‌ریزی خطی و عدد صحیح مختلط
ابزار بهینه‌سازی خطی Glop مقدار بهینه تابع هدف خطی را تحت محدودیت‌های خطی می‌یابد. از جمله معروف‌ترین مدل‌های این مسائل می‌توان به تخصیص افراد به شغل‌ها یا یافتن بهترین ترکیب تخصیص منابع با درنظر گرفتن کمترین هزینه اشاره کرد. Glop و نرم‌افزار بهینه‌سازی عدد صحیح مختلط از جمله این ابزارها هستند که توسط گوگل پوشش داده شده‌اند.
مسیریابی وسیله نقلیه
در مواجهه با مسائل مسیریابی، یک کتابخانه تخصصی برای شناسایی و یافتن بهترین مسیر تحت محدودیت‌های مسأله مسیریابی توسعه یافته است.
الگوریتم‌های شبکه و گراف
زیرساخت این سرویس گوگل به‌منظور یافتن کوتاه‌ترین مسیر در گراف‌ها یا جریان‌های با کمترین هزینه یا سایر مسائل شبکه و گراف آماده شده است.
برای کار با Google OR Tools از کجا شروع کنیم؟
سرویس OR-Tools گوگل با زبان ++C نوشته شده است اما می‌توان در پایتون، جاوا یا #C نیز از آن استفاده کرد. پس از مدل سازی مسأله در زبان دلخواه، می‌توانیم با استفاده از ابزارهای مختلفی نظیر Gurobi و CPLEX (که تجاری یا غیر رایگان هستند) یا SCIP و GLPK و Google’s GLOP و CP-SAT (که متن‌باز هستند) به سراغ حل مسأله برویم. برای شروع کار در هریک از زبان‌های تحت پوشش، می‌توانید از لینک‌های زیر استفاده کنید:
- پیاده‌سازی OR-Tools در زبان ++C
- پیاده‌سازی OR-Tools در زبان Python
- پیاده‌سازی OR-Tools در زبان Java
- پیاده‌سازی OR-Tools در زبان #C
به‌طور خاص برای نصب در پایتون می‌توانید از دستور زیر در مسیر pip استفاده کنید:
python -m pip install --upgrade --user ortools
پی نوشت: رفرنس تصویر این پست، اینجا است.