آموزش OR-Tools در پایتون
این صفحه نقطهٔ شروع یادگیری OR-Tools به زبان فارسی است: اینکه OR-Tools چیست، از چه بخش‌هایی تشکیل شده، کِی باید سراغ آن رفت و به چه ترتیبی یاد گرفت. همهٔ آموزش‌های سایت که با OR-Tools و CP-SAT نوشته شده‌اند، این‌جا بر اساس نوع مسئله دسته‌بندی شده‌اند؛ با تمرکز بر زنجیرهٔ تأمین، مهندسی صنایع و لجستیک.
OR-Tools چیست؟
OR-Tools مجموعه‌ای متنباز از گوگل برای حل مسائل بهینه‌سازی ترکیبیاتی است؛ مسائلی که در آن‌ها باید از میان تعداد بسیار زیادی انتخاب گسسته بهترین را پیدا کرد. پرسش‌هایی مثل «کدام کار اول انجام شود؟»، «هر خودرو به کدام مشتری‌ها سر بزند؟» یا «انبار جدید کجا ساخته شود؟» دقیقاً از این نوع هستند.
هستهٔ OR-Tools با C++ نوشته شده و از پایتون، جاوا و #C قابل استفاده است. در این سایت همهٔ آموزش‌ها با پایتون هستند، چون برای یادگیری و نمونه‌سازی سریع‌ترین مسیر است و همان کد را می‌توان مستقیم در پروژهٔ واقعی به کار برد.
اجزای OR-Tools
OR-Tools یک سالور واحد نیست، بلکه چند ابزار تخصصی کنار هم است. دانستن اینکه هر مسئله را باید به کدام بخش سپرد، نیمی از کار است:
| بخش | برای چه مسائلی |
|---|---|
| CP-SAT | زمانبندی، تخصیص، برنامهریزی نیروی انسانی، پازل‌ها و بیشتر مسائل گسسته با قیود منطقی |
| Routing Library | مسئلهٔ فروشندهٔ دوره‌گرد (TSP) و مسیریابی وسایل نقلیه (VRP) با ظرفیت، پنجرهٔ زمانی و چند انبار |
| Linear Solver | برنامهریزی خطی و عدد صحیح (LP و MILP) از طریق یک رابط واحد برای سالورهای مختلف |
| الگوریتم‌های گراف | کوتاه‌ترین مسیر، بیشینه‌جریان، جریان با کمترین هزینه و مسئلهٔ تخصیص |
در عمل، CP-SAT پرکاربردترین بخش است و بیشتر آموزش‌های این سایت هم بر آن تکیه دارند. CP-SAT بارها در مسابقهٔ بین‌المللی سالورهای برنامهریزی محدودیت (MiniZinc Challenge) رتبهٔ اول را کسب کرده است.
OR-Tools یا Pyomo؟
این دو رقیب هم نیستند، بلکه مکمل‌اند. OR-Tools در مسائل گسسته و ترکیبیاتی می‌درخشد: زمانبندی، مسیریابی و تخصیص. Pyomo یک زبان مدلسازی جبری است که مدل را جدا از سالور تعریف میکند و برای مسائل پیوسته و غیرخطی، مثل پخش بار بهینهٔ AC در شبکهٔ برق، انتخاب طبیعی‌تری است.
به همین دلیل در این سایت، بیشتر آموزش‌های زنجیرهٔ تأمین و زمانبندی با OR-Tools نوشته شده‌اند و آموزش‌های سیستم قدرت با Pyomo (برای نمونه چه مسائلی به AC-OPF نیاز دارند؟). اگر می‌خواهید با طرف دیگر هم آشنا شوید، سه روش عملی استفاده از Solverها در Pyomo شروع خوبی است. در برخی یادداشت‌ها مثل تخصیص اسکله بندر: کدام کشتی، کجا و کِی پهلو بگیرد؟ همان مسئله با هر دو رویکرد حل شده تا تفاوتشان را ببینید.
نصب و شروع کار
نصب OR-Tools تنها با یک دستور انجام میشود: pip install ortools. سالور CP-SAT داخل همین بسته است و برخلاف بسیاری از ابزارهای بهینه‌سازی، نیازی به نصب جداگانهٔ سالور یا تهیهٔ لایسنس ندارید.
اگر نمی‌خواهید چیزی روی سیستم خود نصب کنید، می‌توانید همهٔ آموزش‌ها را در Google Colab اجرا کنید.
مسیر یادگیری OR-Tools
چهار مرحله، از مدلسازی تا پروژهٔ واقعی. هر مرحله روی مرحلهٔ قبل ساخته میشود.
-
مدلسازی ریاضی را یاد بگیرید
قبل از هر ابزاری باید بتوانید یک مسئلهٔ واقعی را به متغیر تصمیم، تابع هدف و قید تبدیل کنید. این مهارت بین همهٔ سالورها مشترک است.
-
CP-SAT را با پازل‌ها تمرین کنید
پازل‌ها کوچک‌ترین مسائل گسسته‌ای هستند که همهٔ مفاهیم CP-SAT را دارند: متغیر بولی، قیود منطقی، AllDifferent و پیدا کردن همهٔ جواب‌ها.
- حل همه جواب‌ها با OR-Tools یادداشت
- حل پازل تقویم با OR-Tools یادداشت
- حل پازل Domino Fit با OR-Tools یادداشت
-
زمانبندی و تخصیص صنعتی
متغیرهای بازه‌ای (Interval)، قید NoOverlap و منابع تجمعی قلب مسائل زمانبندی تولید و خدمات هستند؛ جایی که CP-SAT از بیشتر سالورهای MILP قوی‌تر عمل میکند.
-
مسیریابی و پروژههای واقعی
کتابخانهٔ Routing برای TSP و VRP با پنجرهٔ زمانی، ظرفیت و چند انبار طراحی شده است. در این مرحله مدل را به داده و سناریوی واقعی وصل می‌کنید.
آموزش‌های OR-Tools بر اساس نوع مسئله
هر آموزش یک مسئلهٔ واقعی را از تعریف تا پیاده‌سازی و تحلیل نتایج دنبال میکند. اگر مدلتان جواب نمی‌دهد، راهنمای عیب‌یابی مدل غیرقابل‌اجرا را ببینید.
زمانبندی تولید و خدمات
چه کاری، روی کدام ماشین یا توسط چه کسی، و در چه زمانی انجام شود. از خط تولید تا اسکلهٔ بندر و کادر پرواز.
- آشپزخونه بزنیم؟ زمانبندی تحویل با CP-SAT
آشنایی با مسئله زمانبندی تولید کارگاهی (Job Shop Scheduling) و حل آن با ابزار متنباز OR-Tools در پایتون.
- زمانبندی تولید در کارخانه با ظرفیت روزانه‌ی متغیر: یک مسئله‌ی زمانبندی منابع محدود
وقتی هر سفارش باید چند روز پیاپی کوره را اشغال کند و ظرفیت روزانه‌ی کارخانه هم روز به روز فرق دارد، مسئله دیگر یک زمانبندی ساده نیست. با CP-SAT این مسئله را مدل و حل می‌کنیم.
- تخصیص اسکله بندر: کدام کشتی، کجا و کِی پهلو بگیرد؟
مسئله تخصیص اسکله (Berth Allocation Problem) و مدلسازی ریاضی آن برای کاهش زمان انتظار کشتی‌ها در بنادر با ابزارهای متنباز پایتون.
- زمانبندی خدمه پرواز: چینش کادر پرواز در آسمان
مسئله ز‌وج سازی خدمه پروازی (Crew Pairing Problem) و مدلسازی آن به‌عنوان یک مسئله پوشش/افراز مجموعه برای کاهش هزینه‌های عملیاتی خطوط هوایی.
- زمانبندی رادیوتراپی: تعیین تقویم درمان
چگونه بهینه‌سازی ریاضی می‌تواند روز شروع درمان رادیوتراپی را طوری به بیمار پیشنهاد دهد که ظرفیت پذیرش پرستاران در تمام جلسات آینده، حتی با احتساب مرخصی‌ها، همیشه کافی بماند.
- زمانبندی بازرسی قصابی‌ها با OR-Tools
مدلسازی و حل مسئله زمانبندی بازرسی قصابی‌ها با OR-Tools در پایتون؛ یک مثال عملی از Task Scheduling و تخصیص بهینه بازرس‌ها.
- زمانبندی کارکنان فروشگاه با متغیر باینری در CP-SAT
ساخت گام‌به‌گام یک مدل زمانبندی شیفت فروشگاهی با CP-SAT در OR-Tools، از متغیرهای بولی و قید صلاحیت نقش تا تابع هدف عدالت در توزیع شیفت‌ها.
- آموزش کامل CP-SAT در OR-Tools: مرجع فارسی زمانبندی با پایتون
راهنمای کامل و فارسی سالور CP-SAT از OR-Tools برای زمانبندی: از متغیر بازه‌ای و قید عدم‌تداخل تا جاب‌شاپ، RCPSP و بهینه‌سازی عملکرد حل، با کد پایتون کامل.
- زمانبندی شیفت کارکنان با CP-SAT در OR-Tools
چگونه با CP-SAT در OR-Tools جدول شیفت کارکنان را می‌بندیم که هم پوشش هر شیفت تضمین شود و هم درخواست‌های مرخصی تا حد ممکن رعایت شوند.
مسیریابی و لجستیک
طراحی مسیر ناوگان توزیع با محدودیت ظرفیت، زمان و ترافیک؛ هستهٔ عملیات لجستیک در زنجیرهٔ تأمین.
- مسئله مسیریابی تعمیم‌یافته (GVRP): وقتی فقط یک نقطه از خوشه کافی است
آشنایی کاملاً کلی با مسئله مسیریابی تعمیم‌یافته وسایل نقلیه (GVRP)، جایی که گره‌ها در خوشه‌هایی دسته‌بندی می‌شوند و ویزیت یک نماینده از هر خوشه کافی است، با کاربردهایی از حمل‌ونقل تا توزیع دارو و واکسن.
- مسئله مسیریابی وابسته به زمان (TDVRP) با پایتون
مسئله مسیریابی وابسته به زمان (Time Dependent VRP): چرا وقتی هزینه سفر به ساعت حرکت بستگی دارد، حل مسئله چند برابر پیچیده‌تر میشود.
- پاکسازی آوار پس از بلایا: مسیریابی کمانی به‌جای مسیریابی گرهی
چرا پاکسازی جاده‌های پر از آوار بعد از زلزله یا سیل، یک مسئله مسیریابی کمانی است نه مسیریابی معمول بین نقاط، و چطور با بهینه‌سازی می‌توان آن را حل کرد.
- بازبرنامه‌ریزی پویای مسیر: سیستم مسیریابی زمان‌واقعی برای سفارش‌های جدید
طراحی و پیاده‌سازی یک سیستم مسیریابی پویای وسایل نقلیه (Dynamic VRP) که با رسیدن سفارش جدید یا تغییر داده، فقط مسیر باقی‌مانده ناوگان را در زمان کوتاه به‌روزرسانی میکند.
مکانیابی و تخصیص
تصمیم‌های راهبردی زنجیرهٔ تأمین: انبار، مرکز توزیع یا ایستگاه خدمت کجا ساخته شود و هر مشتری به کدام تخصیص یابد.
- مکانیابی انبار: کجا بسازیم که هزینه کمتر شود؟
آشنایی با مسئله مکانیابی تسهیلات (Facility Location) در زنجیره تأمین و حل آن با ابزارهای متنباز پایتون.
- مکانیابی ایستگاه آمبولانس با پایتون
آشنایی با مسئله مکانیابی پوششی حداکثری (Maximum Covering Location Problem) برای استقرار آمبولانس و ایستگاه‌های اورژانس، و حل آن با ابزارهای متنباز پایتون.
برنامهریزی محدودیت با پازل
راه سریع و سرگرم‌کننده برای درک منطق CP-SAT؛ همان تکنیک‌هایی که بعداً در زمانبندی و تخصیص به کار می‌روند.
- حل همه جواب‌ها با OR-Tools
آموزش پیدا کردن همه جواب‌های یک مدل با Constraint Programming در OR-Tools؛ همراه با یک مثال ساده و قابل اجرا در Python برای درک enumerate کردن جواب‌ها.
- حل پازل تقویم با OR-Tools
فرمولاسیون و کدنویسی پازل تقویم با Constraint Programming و OR-Tools؛ نمونه‌ای آموزشی برای تبدیل یک مسئله منطقی به مدل ریاضی قابل حل.
- حل پازل Domino Fit با OR-Tools
حل پازل Domino Fit با فرمولاسیون ریاضی، Constraint Programming و کدنویسی Python در OR-Tools؛ نمونه‌ای کاربردی برای یادگیری مدلسازی CP.
- حل پازل Tiling با OR-Tools
فرمولاسیون ریاضی و پیاده‌سازی پازل کاشی‌کاری روی شبکه با Python و CP-SAT در OR-Tools؛ از تعریف ترکیب‌ها تا قیود پوشش و حل مدل.
- حل پازل Patches لینکدین با پایتون
چگونه پازل محبوب Patches در لینکدین (نسخه‌ای از Shikaku ژاپنی) را با Constraint Programming و OR-Tools به‌صورت خودکار حل کنیم.
عیب‌یابی مدل
وقتی سالور می‌گوید مسئله جواب شدنی ندارد، باید بدانید کدام قید مقصر است.
- مدل غیرقابل‌اجرا: چطور قید مقصر را پیدا کنیم؟
معرفی روش‌های تشخیص هسته‌ی تناقض در مدلهای بهینه‌سازی غیرقابل‌اجرا (Infeasible) و پیاده‌سازی آن با OR-Tools CP-SAT در پایتون.
- خطای MODEL_INVALID در CP-SAT: از لاگ سالور تا پیدا کردن باگ
یک کد CP-SAT با باگ پنهان را اجرا می‌کنیم، خطای MODEL_INVALID می‌گیریم، لاگ سالور را فعال و خط‌به‌خط تفسیر می‌کنیم و راه پیشگیری را یاد می‌گیریم.
آموزش‌های دیگر OR-Tools
- نجات غذا: مسیریابی مازاد فروشگاه‌ها به بانک غذا
چگونه بهینه‌سازی مسیریابی و زمانبندی می‌تواند مازاد سالم فروشگاه‌ها را پیش از فاسد شدن به بانک‌های غذا و خیریه‌ها برساند.
- ۲۰ میکرودرس بهینه‌سازی با پایتون — هر کدام یک مسئله، یک ساعت
فهرست کامل ۲۰ میکرودرس مستقل بهینه‌سازی ترکیبی با پایتون و OR-Tools؛ هرکدام یک مسئله‌ی واقعی را در حدود یک ساعت آموزش می‌دهد، بدون نیاز به دوره‌ی قبلی یا میکرودرس‌های دیگر.
- لجستیک انتقال عضو پیوندی: مسیریابی در مسابقه با زمان
چگونه بهینه‌سازی مسیر و انتخاب وسیله نقلیه به رقابت با پنجره زمانی حیات عضو پیوندی کمک میکند.
دوره‌های OR-Tools
برای یادگیری ساختاریافته و پروژه‌محور، این دوره‌ها کل مسیر را با تمرین و پشتیبانی پوشش می‌دهند.
- آموزش مسیریابی وسایل نقلیه (VRP) با پایتون و OR-Tools
دوره پروژه‌محور VRP در پایتون با OR-Tools و CP-SAT؛ ۲۰ پروژه عملی از TSP و CVRP تا VRPTW و مسیریابی خودروی الکتریکی.
- دوره جامع بهینه‌سازی سیستمهای سلامت با پایتون
دوره جامع و پروژه‌محور بهینه‌سازی در حوزه سلامت و درمان با Python و OR-Tools؛ ۲۰ پروژه عملی از تخصیص تخت بیمارستان تا امداد پهپادی به مناطق آسیب‌دیده.
پرسش‌های رایج دربارهٔ OR-Tools
آیا OR-Tools رایگان است؟
بله. OR-Tools متنباز و با مجوز Apache 2.0 منتشر میشود، بنابراین استفاده از آن در پروژههای دانشگاهی و تجاری رایگان است و نیازی به خرید لایسنس سالور ندارد.
برای یادگیری OR-Tools چه پیشنیازی لازم است؟
آشنایی مقدماتی با پایتون و مفاهیم پایهٔ مدلسازی ریاضی کافی است. اگر مدلسازی برایتان تازه است، ابتدا از گام اول مسیر یادگیری همین صفحه شروع کنید.
CP-SAT با سالورهای MILP مثل Gurobi چه فرقی دارد؟
CP-SAT فقط با متغیرهای صحیح و بولی کار میکند و ترکیبی از برنامهریزی محدودیت، SAT و برنامهریزی خطی است. در مسائل زمانبندی و ترکیبیاتی معمولاً بسیار قوی است، اما برای مدلهای پیوسته یا غیرخطی مناسب نیست.
آیا OR-Tools برای مسائل واقعی صنعتی کافی است؟
بله. OR-Tools در سیستمهای عملیاتی واقعی مسیریابی و زمانبندی استفاده میشود. نکتهٔ اصلی در مسائل بزرگ، مدلسازی درست و تنظیم زمان و پارامترهای جستوجوی سالور است.
تازه شروع کرده‌اید؟ از مدلسازی ریاضی و اهمیت آن برای برنامه‌نویسی شروع کنید.
پروژهٔ OR-Tools دارید؟
برای مشاوره در مدلسازی و پیاده‌سازی مسائل زمانبندی، مسیریابی و زنجیرهٔ تأمین با @pypyid در تلگرام در تماس باشید.