مسئله مسیریابی وابسته به زمان (TDVRP) با پایتون

وقتی یک مسیریاب، مسیر بین دو نقطه را محاسبه می‌کند، معمولاً فرض می‌کند زمان سفر بین آن‌ها ثابت است. اما در دنیای واقعی این فرض اغلب اشتباه است. مسیر میان دو نقطه در تهران، ساعت دو بامداد شاید فقط ده دقیقه طول بکشد. همان مسیر ساعت هشت صبح، وسط ترافیک سنگین، می‌تواند به پنجاه دقیقه برسد. مسئله مسیریابی وابسته به زمان (Time-Dependent Vehicle Routing Problem یا TDVRP) دقیقاً همین واقعیت را در دل مدل ریاضی وارد می‌کند.

مسئله واقعی چیست؟

در مسئله کلاسیک مسیریابی وسایل نقلیه (VRP)، هزینه سفر بین هر دو گره یک عدد ثابت است. انگار یک جدول فاصله، یک‌بار محاسبه می‌شود و تا پایان روز معتبر می‌ماند. اما وقتی ناوگان توزیع یک شرکت در ساعات مختلف روز حرکت می‌کند، این فرض واقعیت را نادیده می‌گیرد. زمان سفر واقعی بین دو نقطه، به ساعت دقیق حرکت وابسته است، نه فقط به فاصله فیزیکی.

این وابستگی چند پیامد مهم دارد. اول، دیگر نمی‌توان کوتاه‌ترین مسیر را یک‌بار برای همیشه محاسبه کرد؛ باید بدانیم کِی قرار است از آن مسیر عبور شود. دوم، ترتیب بازدید مشتری‌ها مستقیماً روی زمان رسیدن به مشتری‌های بعدی اثر می‌گذارد. سوم، یک تصمیم کوچک در ابتدای مسیر، مثلاً حرکت ده دقیقه دیرتر، می‌تواند کل برنامه روز را درگیر ترافیک سنگین کند.

برای مدل‌سازی درست این وابستگی، معمولاً یک فرض ساده‌کننده اما واقع‌بینانه به کار می‌رود: اصل عدم‌سبقت یا FIFO. این اصل می‌گوید اگر خودرویی دیرتر از خودرویی دیگر از همان نقطه حرکت کند، نباید زودتر از آن به مقصد برسد. بدون این فرض، مدل ریاضی ناپایدار و بی‌معنا می‌شود. با وجود این فرض، مدل همچنان واقعیت ترافیک شهری را به‌خوبی نشان می‌دهد.

اهمیت این موضوع

نادیده‌گرفتن وابستگی زمانی، هزینه واقعی عملیات را به‌شدت دست‌کم می‌گیرد. شرکتی که مسیرهایش را فقط بر اساس فاصله کیلومتری برنامه‌ریزی کند، در عمل با تأخیرهای مکرر و نارضایتی مشتری روبه‌رو می‌شود. شرکتی مثل یوپی‌اس (UPS) در سامانه مسیریابی ORION خود، دقیقاً با چنین چالشی دست‌وپنجه نرم می‌کند. صنعت توزیع بسته در شهرهای شلوغ، بدون در نظرگرفتن ترافیک ساعات اوج، عملاً قابل برنامه‌ریزی دقیق نیست.

این موضوع فقط به حمل‌ونقل شهری محدود نمی‌شود. شرکت‌های توزیع مواد غذایی و سرویس‌های تحویل اینترنتی هم با همین چالش روبه‌رو هستند. ناوگان‌های حمل‌ونقل بین‌شهری نیز زمان سفرشان در ساعات مختلف روز تغییر می‌کند. وقتی برنامه‌ریزی مسیر این واقعیت را نادیده بگیرد، زمان تحویل تخمینی به مشتری اغلب اشتباه از آب درمی‌آید. این خطا هم هزینه عملیاتی را بالا می‌برد و هم رضایت مشتری را کاهش می‌دهد.

فرمول‌بندی ریاضی مسئله

برای ساده‌سازی، بازه زمانی یک روز کاری را به چند دوره تقسیم می‌کنیم. دوره‌ها مثلاً عبارت‌اند از صبح زود، اوج ترافیک صبح، میانه روز، اوج ترافیک عصر و شب. در هر دوره، سرعت حرکت بین دو نقطه را تقریباً ثابت فرض می‌کنیم. زمان سفر از گره $i$ به گره $j$ را، وقتی حرکت در لحظه $\tau$ آغاز شود، با $t_{ij}(\tau)$ نشان می‌دهیم. این مقدار یک تابع پله‌ای از $\tau$ است؛ در هر دوره یک عدد ثابت دارد و در گذار بین دوره‌ها تغییر می‌کند.

فرض کنید $x_{ijk}$ متغیر دودویی باشد که اگر خودرو $k$ مستقیماً از $i$ به $j$ برود، برابر یک است. متغیر $\tau_i^k$ زمان شروع خدمت‌رسانی خودرو $k$ در گره $i$ را نشان می‌دهد. اگر $s_i$ زمان خدمت در گره $i$ باشد، رابطه کلیدی مدل به‌صورت زیر نوشته می‌شود:

$$\tau_j^k \ge \tau_i^k + s_i + t_{ij}(\tau_i^k) - M (1 - x_{ijk})$$

این قید می‌گوید وقتی خودرو $k$ از $i$ به $j$ می‌رود، زمان رسیدن به $j$ از زمان خروج $i$ کمتر نیست. به این زمان، مدت سفر وابسته به لحظه خروج هم اضافه می‌شود. عدد بزرگ $M$ وقتی قید را خنثی می‌کند که $x_{ijk}$ صفر باشد؛ یعنی آن دو گره پشت‌سرهم بازدید نشده‌اند.

قید دیگری که باید رعایت شود، پنجره زمانی مجاز هر مشتری است:

$$e_j \le \tau_j^k \le l_j \qquad \forall j, k$$

در این رابطه، $e_j$ و $l_j$ به‌ترتیب زودترین و دیرترین زمان مجاز شروع خدمت در گره $j$ هستند. تابع هدف معمولاً کمینه‌کردن مجموع زمان کل سفر همه خودروها، یا کمینه‌کردن تعداد خودروهای لازم است. گاهی هم ترکیبی وزن‌دار از این دو معیار در نظر گرفته می‌شود.

چرا حل این مدل دشوار است؟

مسئله مسیریابی وسایل نقلیه، حتی در حالت ساده و بدون وابستگی زمانی، از نوع NP-سخت است. افزودن وابستگی زمانی، فضای جست‌وجو را پیچیده‌تر هم می‌کند. علت این است که هزینه هر قوس دیگر یک عدد ثابت نیست؛ به زمان عبور از آن قوس بستگی دارد. زمان عبور هم خودش نتیجه تصمیم‌های قبلی مسیر است. این وابستگی متقابل، محاسبه دقیق هزینه هر مسیر کاندید را کندتر می‌کند.

به همین دلیل، سالورهای دقیق فقط برای نمونه‌های کوچک قابل‌استفاده‌اند. برای مسائل واقعی با ده‌ها یا صدها مشتری، روش‌های فراابتکاری و جست‌وجوی محلی گزینه عملی‌تری هستند. یکی از این روش‌ها، جست‌وجوی همسایگی بزرگ (Large Neighborhood Search) است. این روش بخشی از مسیر فعلی را خراب می‌کند. سپس همان بخش را، با در نظر گرفتن هزینه وابسته به زمان، دوباره بازسازی می‌کند. این چرخه خراب‌کردن و بازسازی، بارها تکرار می‌شود تا جواب بهتری پیدا شود.

نکته دیگری که باید در نظر گرفت، ناپیوستگی تابع $t_{ij}(\tau)$ در مرز دوره‌هاست. اگر خودرویی درست در مرز دو دوره از یک گره حرکت کند، باید مشخص شود کدام سرعت اعمال می‌شود. معمولاً قرارداد می‌شود که سرعت لحظه دقیق حرکت، معیار محاسبه است، نه سرعت لحظه رسیدن.

ظرفیت کار آکادمیک و پژوهشی

TDVRP یکی از زیرشاخه‌های فعال پژوهش در حوزه مسیریابی است. یک مسیر باز، ترکیب وابستگی زمانی با عدم‌قطعیت است. یعنی زمان سفر در هر دوره، به‌جای یک عدد قطعی، یک توزیع احتمال باشد. مسیر دوم، ترکیب این مدل با مسیریابی آلاینده (Pollution-Routing) است تا هم زمان و هم میزان انتشار کربن هم‌زمان کمینه شوند. مسیر سوم، یادگیری خودِ تابع $t_{ij}(\tau)$ از داده‌های واقعی ترافیک است. این کار به‌جای فرض‌کردن یک تابع پله‌ای ساده انجام می‌شود و مدل‌سازی ریاضی را با یادگیری ماشین پیوند می‌دهد.

زمینه چهارم، مقایسه عملکرد روش‌های فراابتکاری مختلف روی نمونه‌های استاندارد TDVRP است. بسیاری از این نمونه‌ها در مقالات مرجع این حوزه منتشر شده‌اند. این نمونه‌ها بستر خوبی برای مقایسه الگوریتم جدید با نتایج موجود فراهم می‌کنند. زمینه پنجم هم ترکیب TDVRP با وسایل نقلیه برقی است. در این حالت، هم زمان سفر و هم مصرف باتری به ساعت حرکت وابسته‌اند. این زمینه‌ها، گزینه‌های مناسبی برای پایان‌نامه یا مقاله در حوزه تحقیق در عملیات هستند.

پیاده‌سازی با پایتون

خبر خوب این است که پیاده‌سازی این مدل نیازی به نرم‌افزار گران‌قیمت ندارد. کتابخانه متن‌باز OR-Tools گوگل، ماژول مسیریابی اختصاصی دارد که دقیقاً برای این نوع مسائل ساخته شده است. به‌جای یک ماتریس فاصله ثابت، می‌توان یک تابع بازگشتی (callback) تعریف کرد. این تابع، زمان سفر را بر اساس زمان فعلی خودرو در مسیر محاسبه می‌کند.

ایده کلی این است که یک بعد زمانی (Time Dimension) به مدل اضافه می‌شود. این بعد، زمان تجمعی رسیدن هر خودرو به هر گره را دنبال می‌کند. سپس تابع هزینه قوس، به‌جای یک عدد ثابت، از همین مقدار زمان تجمعی استفاده می‌کند. این مقدار برای انتخاب دوره ترافیکی مناسب و سرعت متناظرش به کار می‌رود. برای کار با داده‌های ورودی مثل مختصات مشتری‌ها و پنجره‌های زمانی، کتابخانه pandas گزینه راحتی است. با آن می‌توان این داده را از یک جدول ساده اکسل خواند.

اسکلت اولیه این مدل در OR-Tools به این شکل آغاز می‌شود:

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

def time_dependent_transit(from_index, to_index):
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    current_time = routing.GetDimensionOrDie("Time").CumulVar(from_index)
    period = time_period(current_time)  # تعیین دوره ترافیکی بر اساس زمان جاری
    return travel_time_matrix[period][from_node][to_node]

manager = pywrapcp.RoutingIndexManager(num_locations, num_vehicles, depot)
routing = pywrapcp.RoutingModel(manager)

ادامه تعریف بعد زمانی، قیدهای پنجره زمانی و تابع هدف، به همین شیوه روی همین مدل اضافه می‌شوند.

پس از حل مدل، می‌توان با NetworkX مسیر نهایی هر خودرو را روی نقشه شهر رسم کرد. زمان رسیدن تخمینی به هر مشتری را هم می‌توان کنار همان نقشه نوشت. این تصویرسازی، ارزیابی کیفیت جواب را برای تیم عملیات بسیار ساده‌تر می‌کند. مقایسه جواب TDVRP با جواب VRP معمولی روی همان داده هم نشان می‌دهد نادیده‌گرفتن ترافیک چقدر هزینه واقعی را دست‌کم می‌گیرد.

سوالات متداول

تفاوت TDVRP با مسئله مسیریابی معمولی (VRP) چیست؟

در VRP معمولی، زمان سفر بین هر دو نقطه یک عدد ثابت است. در TDVRP، این زمان به ساعت دقیق حرکت وابسته است و طبق اصل FIFO تغییر می‌کند.

آیا OR-Tools به‌طور پیش‌فرض وابستگی زمانی را پشتیبانی می‌کند؟

به‌صورت مستقیم نه. اما می‌توان یک تابع بازگشتی سفارشی برای هزینه قوس تعریف کرد؛ با افزودن یک بعد زمانی، این وابستگی به مدل اضافه می‌شود.

برای یادگیری ساخت این نوع مدل‌های مسیریابی از کجا شروع کنم؟

دوره مسیریابی و بهینه‌سازی زنجیره تأمین با پایتون دقیقاً همین نوع مسائل را گام‌به‌گام پوشش می‌دهد. برای پیاده‌سازی این مدل روی داده واقعی ناوگان خودتان هم می‌توانید از طریق صفحه مشاوره با ما تماس بگیرید.

جمع‌بندی

مسئله مسیریابی وابسته به زمان، یک گام واقع‌بینانه فراتر از VRP کلاسیک است. در این یادداشت دیدیم چرا فرض ثابت‌بودن زمان سفر در دنیای واقعی اشتباه است. دیدیم چطور اصل FIFO مدل ریاضی را پایدار نگه می‌دارد و چرا این وابستگی، حل دقیق مسئله را دشوارتر می‌کند. دیدیم چطور با افزودن یک بعد زمانی به مدل OR-Tools، این واقعیت بدون نیاز به ابزار گران‌قیمت پیاده‌سازی می‌شود.

اگر می‌خواهید مبانی مدل‌سازی ریاضی را پیش از این مسائل پیچیده‌تر مرور کنید، یادداشت مدل‌سازی ریاضی و اهمیت آن شروع خوبی است. برای اجرای این کدها بدون نصب چیزی روی سیستم خودتان هم، راهنمای Google Colab مفید خواهد بود.