آموزش جامع بهینهسازی و مسیریابی (VRP) در Python
۳ تیر ۱۴۰۵
| محیط کار: Python | سطح: مقدماتی تا تخصصی | حجم: ۲۰ پروژه + حدود ۱۰ ساعت ویدیو |
این دوره یک مسیر آموزشی پروژهمحور برای یادگیری مدلسازی و پیادهسازی مسائل مسیریابی وسیلهٔ نقلیه (VRP) و مسائل ترکیبی در Python است. دوره شامل ۲۰ پروژهٔ عملی و حدود ۱۰ ساعت ویدیوی آموزشی است، از سطح مقدماتی آغاز میشود و بهتدریج وارد مسائل تخصصیتر حملونقل و لجستیک میشود. هر پروژه با کد کامل، مستندات و دادهٔ تست آماده ارائه میشود.

بخش اول — ۱۰ پروژهٔ عمومی (مسائل ترکیبی و مدلسازی)
این بخش پایهٔ مدلسازی مسائل ترکیبی را میسازد تا برای مسائل تخصصی VRP آماده شوید. همهٔ پروژهها با کتابخانهٔ OR-Tools و حلکنندهٔ CP-SAT در Python پیادهسازی شدهاند. در هر پروژه یاد میگیرید مسئله را با سه رکن اصلی — متغیر تصمیم، تابع هدف و قیود — فرموله کنید و خروجی را تفسیر و تصویرسازی نمایید.
پروژه ۱ — حداکثر جریان در شبکه (Maximum Flow)
مسئلهٔ کلاسیک جریان بیشینه: در یک شبکهٔ جهتدار با ظرفیت روی هر یال (مثل شبکههای آب، گاز، برق یا حملونقل)، میخواهیم بیشترین جریان ممکن را از یک گره مبدأ به یک گره مقصد برسانیم. متغیر تصمیم، مقدار جریان روی هر یال است (کراندار به ظرفیت آن)، و کلید مدل، قید بقای جریان (nodal balance) است: در هر گره میانی، مجموع جریان ورودی برابر مجموع جریان خروجی است و فقط در مبدأ و مقصد، جریان تزریق/خروج داریم. تابع هدف، بیشینهکردن جریان تزریقی است. این پروژه مفهوم بنیادیِ «شبکه، گره، یال و بقای جریان» را جا میاندازد که ستون فقرات همهٔ مسائل مسیریابی است.
نکتهٔ کلیدی — قید بقای جریان (nodal balance) ستون فقرات همهٔ مسائل شبکه است؛ دقیقاً همین ایده بعداً در VRP برای حذف زیرتور با رویکرد جریان دوباره ظاهر میشود.
نکتهٔ کلیدی — کرانگذاری متغیر جریان به ظرفیت هر یال، سادهترین شکل قید ظرفیت است که در CVRP به هستهٔ کار تبدیل میشود.
پروژه ۲ — تخصیص کارگر به وظیفه (Assignment Problem)
با یک ماتریس هزینه (هزینهٔ انجام هر وظیفه توسط هر کارگر)، میخواهیم وظایف را طوری به کارگرها بدهیم که هزینهٔ کل کمینه شود. متغیر تصمیم باینری است: آیا کارگر w وظیفهٔ t را میگیرد یا نه. قیود کلیدی: هر وظیفه دقیقاً به یک کارگر برسد (AddExactlyOne) و هر کارگر حداکثر یک وظیفه بگیرد (AtMostOne). در این پروژه دو شیوهٔ ساخت تابع هدف (LinearExpr.Sum و WeightedSum) هم مقایسه میشود. پایهٔ «تخصیص» که در بسیاری از مسائل تصمیمگیری تکرار میشود.
نکتهٔ کلیدی —
AddExactlyOneوAtMostOneگویاترین راه بیان «هرکدام دقیقاً/حداکثر یکبار» هستند و خوانایی مدل را بالا میبرند.
نکتهٔ کلیدی —
LinearExpr.WeightedSumمعمولاً از ساختن دستیِ تکتک جملههای هدف، هم تمیزتر و هم سریعتر است.
پروژه ۳ — کولهپشتی و بستهبندی (Knapsack & Bin Packing)
ابتدا مسئلهٔ کولهپشتی صفر-و-یک: از میان مجموعهای از اقلام (هرکدام با ارزش و وزن)، زیرمجموعهای را انتخاب کنیم که با رعایت ظرفیت وزنی، بیشترین ارزش را بدهد. سپس مسئله به حالت چند سطل (bin) گسترش مییابد: هر قلم حداکثر در یک سطل، ظرفیت هر سطل جداگانه. اینجا با نکات مهم عملی آشنا میشوید: شکستن تقارن (symmetry breaking) برای اقلام یکسان، مدیریت اقلام با وزن صفر، تعیین محدودیت زمانی حل و تفاوت جواب OPTIMAL با FEASIBLE.
نکتهٔ کلیدی — شکستن تقارن برای اقلام هموزن و همارزش، جوابهای تکراری را حذف و حل را بسیار سریعتر میکند.
نکتهٔ کلیدی — تعیین
max_time_in_secondsو پذیرفتن جوابFEASIBLE، برخورد عملی با مسائل بزرگی است که رسیدن به جواب بهینهٔ قطعی زمانبر است.
پروژه ۴ — چیدمان میهمانان عروسی (Wedding Seating)
میهمانان را باید طوری سرِ میزها نشاند که مجموع «صمیمیت» افرادِ هممیز بیشینه شود. متغیر اصلی، تخصیص هر میهمان به یک میز است؛ اما نکتهٔ آموزشیِ مهم، متغیر کمکی «آیا دو نفر هممیزند؟» است که حاصلضرب دو متغیر باینریست و با سه قید خطی، خطیسازی رابطهٔ AND میشود. قیود: هر میهمان دقیقاً یک میز، سقف ظرفیت هر میز، و حداقل تعداد آشنا برای هر فرد سرِ میز. الگوی «خطیسازی ضرب دو باینری» در VRP و بسیاری مسائل دیگر بارها به کار میآید.
نکتهٔ کلیدی — خطیسازی ضرب دو متغیر باینری (AND) با سه قید ساده، الگویی است که در VRP، مسائل گراف و بسیاری جاهای دیگر بارها تکرار میشود.
نکتهٔ کلیدی — کمیکردن «کیفیت» (صمیمیت هممیزها) بهجای صرفِ امکانپذیری، نشان میدهد چطور یک هدف نرم را به تابع هدف تبدیل کنیم.
پروژه ۵ — زمانبندی تولید (Job-Shop Scheduling)
چند کار (job) داریم که هرکدام دنبالهای از عملیات روی ماشینهای مشخص با زمانهای معین است؛ هدف، کمینهکردن زمان کل اتمام (makespan) است. اینجا با ابزار قدرتمند متغیرهای بازهای (Interval Variables) و قید عدم همپوشانی (AddNoOverlap) روی هر ماشین آشنا میشوید و قیود ترتیب (precedence) بین عملیات یک کار را مدل میکنید. خروجی بهصورت نمودار گانت رسم میشود. این پروژه دروازهٔ ورود به مسائل زمانبندی و بُعدِ زمان است.
نکتهٔ کلیدی — متغیرهای بازهای +
AddNoOverlapراه استاندارد و بسیار کارآمد بیان «این کارها روی یک منبع همپوشانی نداشته باشند» است.
نکتهٔ کلیدی — کمینهکردن makespan نمونهٔ کلاسیک هدف min-max زمانی است که در برنامهریزی تولید همهجا دیده میشود.
پروژه ۶ — تحویل بار فرودگاه با ونها (Airport Baggage Routing)
یک مسئلهٔ واقعیِ مسیریابی وسیله نقلیه و پلِ ورود به بخش دوم: شرکتی با چند ون باید بارِ جامانده را از فرودگاه هیثرو در محدودهٔ زمانی/مسافتی مشخص به مشتریان برساند و میخواهد کمترین تعداد ون را به کار بگیرد. اینجا اولین بار همهٔ اجزای VRP کنار هم میآیند: متغیرهای یال مسیر U[i,j,c]، تخصیص مشتری به خودرو، حذف زیرتور با رویکرد جریان (flow-based subtour elimination)، محدودیت طول مسیر هر خودرو و کمینهکردن تعداد خودروهای استفادهشده. اگر این پروژه را بفهمید، وارد بخش تخصصی VRP آمادهاید.
نکتهٔ کلیدی — حذف زیرتور با رویکرد جریان (flow-based) جایگزینی برای
AddCircuitاست و برای مسائل چندخودرویی خیلی خوب مقیاس میگیرد.
نکتهٔ کلیدی — کمینهکردن تعداد خودرو یک هدف کاملاً صنعتی است؛ اینجا میبینید تصمیم «چند خودرو» و «کدام مسیر» همزمان گرفته میشوند.
پروژه ۷ — مربع جادویی (Magic Square)
یک مسئلهٔ ارضای قید (constraint satisfaction) خالص: در جدول n×n اعداد ۱ تا n² را طوری بچینید که مجموع هر سطر، هر ستون و دو قطر برابر «عدد جادویی» شود. متغیر تصمیم، مقدار عددی هر خانه است و قید کلیدی، AddAllDifferent (همهٔ خانهها متمایز) در کنار قیود تساوی مجموعهاست. این پروژه قدرت سالور CP-SAT را برای مسائلی که تابع «هدف» ندارند و فقط دنبال یک جواب شدنیاند نشان میدهد.
نکتهٔ کلیدی —
AddAllDifferentیکی از قویترین قیدهای CP است و مسائل ارضای قید را بسیار فشرده مدل میکند.
نکتهٔ کلیدی — CP-SAT حتی برای مسائل بدون تابع هدف (فقط یافتن یک جواب شدنی) هم بسیار قدرتمند است.
پروژه ۸ — بزرگترین خوشه در گراف (Maximum Clique)
در یک گراف، بزرگترین زیرمجموعه از گرهها را پیدا کنید که همگی دوبهدو به هم متصلاند. با کتابخانهٔ networkx گراف ساخته و تحلیل میشود. متغیرها: انتخاب هر گره (X[n]) و متغیر کمکیِ «هر دو گره در خوشهاند؟» که باز هم با خطیسازی AND ساخته میشود؛ قید مهم این است که اگر بین دو گره یالی نباشد، نمیتوانند همزمان در خوشه باشند. هدف، بیشینهکردن تعداد گرههای انتخابی است. تمرین عالی برای مدلسازی گراف.
نکتهٔ کلیدی — همان الگوی **خطیسازی ** دوباره به کار میآید؛ تسلط بر این الگو در سراسر دوره حیاتی است.
نکتهٔ کلیدی — استفاده از networkx برای ساخت و تحلیل گراف، مدلسازی مسائل شبکهای را بسیار سریع میکند.
پروژه ۹ — برنامهریزی تقویم درسی (Balanced Academic Curriculum)
مسئلهٔ واقعیِ BACP: چیدن درسها در تعدادی نیمسال با رعایت حداقل/حداکثر بار واحدی و حداقل/حداکثر تعداد درس در هر نیمسال، و مهمتر از همه قیود پیشنیازی: نیمسالِ یک درس باید پیش از نیمسالِ درسِ وابسته باشد. سپس نسخهٔ دومِ مدل، بار درسی را متوازن میکند با کمینهکردن اختلاف بیشترین و کمترین بار (هدف min-max). این پروژه مدلسازی «تخصیص روی بازههای زمانی + پیشنیاز + توازن بار» را میآموزد.
نکتهٔ کلیدی — قید پیشنیاز (نیمسالِ c1 پیش از نیمسالِ c2) نمونهٔ تمیزی از مدلکردن ترتیب/تقدم است که در زمانبندی همهجا لازم میشود.
نکتهٔ کلیدی — هدف min-max برای توازن بار درسی نشان میدهد چطور «بالانس بودن» را به یک هدف قابلبهینهسازی تبدیل کنیم.
پروژه ۱۰ — جانمایی بهینهٔ رباتها (Robot Placement)
N ربات را در یک صفحه طوری بچینید که کمترین فاصلهٔ بین هر جفت ربات، بیشینه شود (پخشکردن حداکثری). نکتهٔ فنیِ ویژه: چون فاصله شامل مجذور است، از add_multiplication_equality برای مدلکردن رابطهٔ غیرخطی استفاده میشود؛ و هدف، یک مسئلهٔ max-min است. نسخهٔ دومِ کد با شکستن تقارن سرعت حل را بهبود میدهد. جمعبندیِ خوبی از مدلسازی غیرخطی و اهداف بیشینهٔ کمینه.
نکتهٔ کلیدی —
add_multiplication_equalityراه مدلکردن رابطههای غیرخطی (مجذور) در CP-SAT است.
نکتهٔ کلیدی — هدف max-min (بیشینهکردن کمترین فاصله) الگوی مهمی برای مسائل «پخشکردن یا دورترین چیدمان» است.
بخش دوم — ۱۰ پروژهٔ تخصصی VRP
این بخش هستهٔ اصلی دوره است و بهصورت پلکانی، از مسئلهٔ کلاسیک فروشندهٔ دورهگرد (TSP) تا مسائل واقعیِ روزِ صنعت (مسیریابی وسیلهٔ برقی، تحویل تقسیمشده و مسیریابی موجودی-دینامیک) پیش میرود. در همهٔ پروژهها از قید بسیار قدرتمند AddCircuit در CP-SAT استفاده میشود که بهطور خودکار یک تور معتبر و بدون زیرتور میسازد.
پروژه ۱۱ — فروشندهٔ دورهگرد (TSP با AddCircuit)
نقطهٔ شروع مسیریابی: پیدا کردن کوتاهترین تورِ بازدید از همهٔ نقاط (اینجا ۱۰۰ نقطه). متغیر تصمیم، انتخاب یال (i,j) و تابع هدف، کمینهکردن مجموع مسافت است. کل مدل تقریباً با یک خط AddCircuit بسته میشود.
نکتهٔ کلیدی — قید
AddCircuitبهتنهایی تضمین میکند مسیر یک حلقهٔ کامل و بدون زیرتور باشد؛ این کار جای دهها قید دستساز (مثل MTZ) را میگیرد و مدل را بسیار تمیزتر میکند.
نکتهٔ کلیدی — با هرسکردن یالهای بلند (حذف اتصالهایی که مسافتشان از یک آستانه بیشتر است) تعداد متغیرها بهشدت کم و سرعت حل برای نمونههای بزرگ چند برابر میشود.
پروژه ۱۲ — TSP با ترتیب و انتخاب (Precedence & Selective)
سه توسعهٔ مهم روی TSP: نخست قیود ترتیب بازدید (باید نقطهٔ i قبل از j دیده شود) با کمک متغیر visit_order؛ سپس مسیر انتخابی (selective/prize-collecting) که در آن فقط زیرمجموعهای از نقاط (مثلاً حداقل ۱۵ نقطه) بازدید میشوند؛ و در نهایت یال مجازی برای بازگشت منعطف به مبدأ.
نکتهٔ کلیدی —
OnlyEnforceIfاجازه میدهد قید فقط وقتی یالی فعال است اعمال شود؛ این «قید شرطی» ابزار اصلی انتشار ترتیب و زمان در طول مسیر است.
نکتهٔ کلیدی — با گذاشتن self-loop در
AddCircuit(یعنی(i, i, انتخابنشدنگرهِ i)) بهزیبایی مدل میکنیم که یک گره از تور حذف شود — پایهٔ همهٔ مسائل مسیریابی انتخابی.
پروژه ۱۳ — مسیریابی ظرفیتدار چندخودرویی (CVRP)
نسخهٔ واقعیِ چندخودرویی: چند خودرو با ظرفیت محدود از یک انبار حرکت میکنند و باید تقاضای همهٔ مشتریان را با کمترین مسافت کل پوشش دهند. برای هر خودرو یک AddCircuit جداگانه ساخته میشود و قید ظرفیت روی جمع تقاضای مشتریان هر خودرو اعمال میگردد.
نکتهٔ کلیدی — یک حلقهٔ مستقل بهازای هر خودرو (با self-loop برای مشتریانی که آن خودرو سرویسشان نمیدهد) اجازه میدهد چند مسیر همزمان در یک مدل واحد ساخته شوند.
نکتهٔ کلیدی — شکستن تقارن (مثلاً بارِ خودرو c ≤ بارِ خودرو c+1) جوابهای تکراری و همارز را حذف میکند و زمان حل را بهشکل چشمگیری کاهش میدهد.
پروژه ۱۴ — مسیریابی چندانباره (Multi-Depot VRP)
این بار بهجای یک انبار، چند انبار داریم و باید همزمان تصمیم بگیریم هر خودرو از کدام انبار شروع کند، کدام خودروها اصلاً به کار گرفته شوند و هر مشتری به کدام مسیر برسد.
نکتهٔ کلیدی — پیوند دادن متغیر «خودرو استفاده شد؟» به انتخاب انبار و به ظرفیت (ظرفیت × used_car) روشی تمیز برای روشن/خاموش کردن خودروها و انبارهاست.
نکتهٔ کلیدی — مسیریابی چندانباره تعمیم مستقیم حالت تکانبار است و به واقعیت شبکههای توزیع بزرگ با چند مرکز پخش نزدیکتر است.
پروژه ۱۵ — تحویل تقسیمشده (Split Delivery VRP)
در SDVRP فرض «هر مشتری فقط یک بار سرویس میگیرد» کنار میرود: تقاضای یک مشتری میتواند بین چند خودرو تقسیم شود. بهجای متغیر باینریِ «سرویس داده شد»، از متغیر صحیح loadcar[i,c] (مقدار تحویل هر خودرو) استفاده میشود.
نکتهٔ کلیدی — تبدیل «سرویسدهی» از باینری به مقدارِ تحویل کلید تقسیم بار است؛ وقتی تقاضا بزرگ است یا از ظرفیت یک خودرو بیشتر میشود، همین ایده مسئله را شدنی و کارآمد میکند.
نکتهٔ کلیدی — استفاده از
AddAtLeastOneبهجایAddExactlyOneاجازه میدهد بیش از یک خودرو به یک مشتری سر بزنند.
پروژه ۱۶ — پنجرهٔ زمانی (VRPTW)
مسیریابی ظرفیتدار همراه با پنجرهٔ زمانی هر مشتری، زمان سرویس و زمان انتظار. متغیر arrival_time زمان رسیدن به هر گره را نگه میدارد و در طول مسیر منتشر میشود؛ همچنین محدودیت طول شیفت خودرو اعمال میگردد.
نکتهٔ کلیدی — انتشار زمان رسیدن در طول یالها با
OnlyEnforceIf(زمانِ j ≥ زمانِ i + سرویس + مسافت) قلب مدلسازی پنجرهٔ زمانی است.
نکتهٔ کلیدی — هرس یالهای ناممکن از نظر زمانی (اگر پنجرهٔ j پیش از باز شدن پنجرهٔ i بسته شود) اندازهٔ مدل را کم و حل را سریعتر میکند.
پروژه ۱۷ — مسیریابی خودروی برقی (EV Routing)
مسیریابی روی یک شبکهٔ جادهایِ واقعی (نه گراف کامل) با محدودیت باتری/برد: متغیر EFuel سطح شارژ را نشان میدهد که با پیمودن هر یال کم میشود و نباید از حد مجاز پایینتر برود. سپس نسخهٔ دوم ایستگاه شارژ را اضافه میکند که در آن شارژ دوباره پر میشود.
نکتهٔ کلیدی — مدلکردن سطح شارژ باتری بهصورت متغیری که با مسافت افت میکند، مفهوم «برد محدود / اضطراب برد» را مستقیماً وارد بهینهسازی میکند.
نکتهٔ کلیدی — ایستگاه شارژ یعنی گرهی که متغیر شارژ در آن بازنشانی (reset) میشود؛ همین ترفند ساده مسیرهای طولانیتر را ممکن میکند.
پروژه ۱۸ — مسیر شبکهای با ترتیب (پازل Zip لینکدین)
نگاهی سرگرمکننده و آموزنده: در یک جدول ۷×۷ فقط حرکت به خانههای مجاور مجاز است و باید همهٔ خانهها را در یک مسیر پیوسته و با رعایت ترتیب نقاط شمارهگذاریشده طی کرد (همان بازی Zip لینکدین).
نکتهٔ کلیدی — محدودکردن یالها به همسایگی شبکهای + قیود ترتیب با
visit_orderنشان میدهد چطور همان ابزارهای VRP روی پازلها و بازیها هم کار میکنند.
نکتهٔ کلیدی — با
AddCircuitو یک یال بستِ اجباری، یک مسیر همیلتونی که همهٔ خانهها را پوشش میدهد ساخته میشود.
پروژه ۱۹ — ترابری/انتقال بار (Transshipment)
ترکیب مسیریابی انتخابی با انتقال بار: مشتریانی که روی مسیر اصلی نیستند، تقاضایشان با یک یال انتقال به نزدیکترین مشتریِ روی مسیر منتقل میشود. تابع هدف، مجموع مسافت مسیر بهعلاوهٔ هزینهٔ انتقالهاست.
نکتهٔ کلیدی — پیوند متغیر انتقال به گرههای انتخابنشده (
select[i].Not()) روشی تمیز است برای اینکه «اگر مشتری بازدید نشد، حتماً از طریق انتقال پوشش داده شود».
نکتهٔ کلیدی — این مدل نشان میدهد گاهی سرویسدادن غیرمستقیم (transshipment) از کشاندن مسیر تا همهٔ نقاط ارزانتر است.
پروژه ۲۰ — مسیریابی دینامیک و موجودی (Inventory Routing)
جمعبندی دوره با پیشرفتهترین حالت: یک مسئلهٔ مسیریابی-موجودی (IRP) روی افق ۱۰ روزه. باید تصمیم بگیرید هر مشتری چه روزی بازدید شود، چه مقدار تحویل داده شود، مسافت کل کمینه شود و هیچ مشتری دچار کمبود موجودی (stockout) نشود.
نکتهٔ کلیدی — افزودن بُعد زمان (چند روز) و پویاییِ موجودی، همانجایی است که مسیریابی به مدیریت موجودی و زنجیرهٔ تأمین گره میخورد.
نکتهٔ کلیدی — تصمیمِ «چه زمانی سر بزنیم» (نه فقط «با چه مسیری») بر اساس نرخ مصرف و جلوگیری از کمبود، جوهرهٔ مسیریابی موجودی است.
مسیر پیشنهادی یادگیری VRP
| گام | موضوع | مفهوم کلیدی |
|---|---|---|
| ۱ | مسائل ترکیبی پایه | متغیر باینری، تخصیص |
| ۲ | تحلیل گراف و جریان | گره، یال، جریان |
| ۳ | VRP پایه | مسیر، حذف زیرتور |
| ۴ | CVRP | قید ظرفیت وسیله |
| ۵ | VRPTW | پنجرهٔ زمانی و زمان انتظار |
| ۶ | توسعهها | چندپایانه، pickup/delivery، سودآور |
دریافتیهای دوره
- ویدیوهای آموزشی گامبهگام (حدود ۱۰ ساعت)
- کد کامل و قابلاجرای هر ۲۰ پروژه
- مستندات و دادهٔ تست آمادهٔ هر مسئله
- ساختاری تمیز و قابلتوسعه برای پروژههای واقعی خودتان
این دوره برای چه کسانی است؟
- دانشجویان مهندسی (صنایع، کامپیوتر، عمران/حملونقل)
- مدیران و کارشناسان عملیات و لجستیک
- علاقهمندان به برنامهنویسی و بهینهسازی که میخواهند با پروژههای واقعی یاد بگیرند
پیشنیازها
آشنایی پایه با Python کافی است. آشنایی قبلی با مدلسازی مسائل بهینهسازی توصیه میشود اما الزامی نیست؛ در صورت نیاز ابتدا دوره مدلسازی مسائل بهینهسازی پیشنهاد میشود.
سوالات متداول درباره دوره
پیشنیاز این دوره چیست؟
آشنایی پایه با Python کافی است. آشنایی قبلی با مدلسازی مسائل بهینهسازی توصیه میشود اما الزامی نیست.
دوره شامل چه چیزهایی است؟
۲۰ پروژه عملی (۱۰ پروژه عمومی و ۱۰ پروژه تخصصی VRP)، حدود ۱۰ ساعت ویدیو، کد کامل، مستندات و دادههای تست آماده.
چه نوع مسائل VRP پوشش داده میشود؟
از VRP پایه تا CVRP و VRPTW، مسیریابی چندپایانه، pickup & delivery، مسیریابی سودآور و محدودیتهای مکانی و اولویتبندی.
خروجی نهایی دوره چیست؟
مجموعهای از پروژههای آماده و قابلتوسعه که پایهای برای پروژههای واقعی حملونقل و زنجیره تأمین است.
💬 سوالات و راهنمایی
سوالی درباره ثبتنام داری؟ با آیدی @pypyid در تلگرام تماس بگیرید.