ابعاد

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

این بخش نحوه تعریف و استفاده از ابعاد را توضیح می دهد.

نمونه هایی از ابعاد

در اینجا چند نمونه از ابعاد از بخش های قبلی آورده شده است.

  • مثال VRPTW یک بعد برای ردیابی زمان تجمعی سفر هر وسیله نقلیه ایجاد می کند. حل کننده از بعد برای اعمال محدودیت استفاده می کند که یک وسیله نقلیه فقط می تواند از یک مکان در پنجره زمانی مکان بازدید کند.

  • مثال CVRP ابعادی را برای تقاضاها ایجاد می کند (به عنوان مثال، وزن یا حجم بسته هایی که باید برداشت شوند)، که بار تجمعی را که وسیله نقلیه در مسیر خود حمل می کند ردیابی می کند. حل کننده از بعد برای اعمال محدودیت استفاده می کند که بار یک وسیله نقلیه نمی تواند از ظرفیت آن بیشتر شود.

مثال های زیر با استفاده از روش AddDimension یک بعد برای VRPTW تعریف می کنند.

پایتون 

routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)

C++ 

routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)

جاوا 

routing.addDimension(
    callbackIndex,
    slackMax,
    capacity,
    fixStartCumulToZero,
    dimensionName)

سی شارپ

routing.AddDimension(
    callbackIndex,
    slackMax,
    capacity,
    fixStartCumulToZero,
    dimensionName)

متد AddDimension دارای ورودی های زیر است:

  • callback_index : شاخصی برای تماس برگشتی که مقدار را برمی گرداند. ایندکس که مرجع داخلی حل کننده به پاسخ به تماس است، با روش هایی مانند RegisterTransitCallback یا RegisterUnitaryTransitCallback ایجاد می شود.
  • slack_max : حداکثر برای slack ، متغیری که برای نمایش زمان انتظار در مکان‌ها استفاده می‌شود. برای جزئیات بیشتر به متغیرهای Slack زیر مراجعه کنید. اگر مشکل شامل زمان انتظار نیست، معمولاً می توانید slack_max روی 0 تنظیم کنید.
  • capacity : حداکثر برای مقدار کل انباشته شده در هر مسیر. از capacity برای ایجاد محدودیت هایی مانند محدودیت های موجود در CVRP استفاده کنید. اگر مشکل شما چنین محدودیتی ندارد، می‌توانید capacity روی مقداری تنظیم کنید که به اندازه‌ای بزرگ باشد که هیچ محدودیتی در مسیرها اعمال نکند - به عنوان مثال، مجموع تمام ورودی‌های ماتریس یا آرایه مورد استفاده برای تعریف بازگشت تماس.
  • fix_start_cumulative_to_zero : مقدار بولی. اگر درست باشد، مقدار تجمعی کمیت از 0 شروع می شود. در بیشتر موارد، این مقدار باید روی True تنظیم شود. با این حال، برای VRPTW یا مشکلات مربوط به محدودیت‌های منابع ، برخی از وسایل نقلیه ممکن است به دلیل محدودیت‌های پنجره زمانی مجبور شوند بعد از زمان 0 شروع به کار کنند، بنابراین باید fix_start_cumulative_to_zero را برای این مشکلات روی False تنظیم کنید.
  • dimension_name : رشته ای برای نام بعد، مانند 'Distance' ، که می توانید از آن برای دسترسی به متغیرها در جاهای دیگر برنامه استفاده کنید.

برنامه CVRP با استفاده از روش AddDimensionWithVehicleCapacity یک نوع بعد کمی متفاوت ایجاد می کند. این روش مجموعه ای از ظرفیت ها را با یک ورودی برای هر وسیله نقلیه می گیرد. (در مقابل، AddDimension یک مقدار واحد برای capacity می گیرد، بنابراین همه وسایل نقلیه ظرفیت یکسانی دارند.)

برای سایر روش هایی که ابعاد ایجاد می کنند، صفحه مرجع RoutingModel را ببینید.

بخش Save the solution time windows to a list or array توابعی را ارائه می دهد که داده های تجمعی را در یک بعد در یک لیست یا آرایه ذخیره می کند.

متغیرهای Slack

در اینجا یک مثال آورده شده است که متغیرهای شل را برای مشکلی که مربوط به زمان سفر است نشان می دهد. فرض کنید یک وسیله نقلیه در یک مرحله از مسیر خود از مکان i به مکان j می رود و این:

  • زمان سفر تجمعی وسیله نقلیه در i 100 دقیقه است.
  • زمان سفر تجمعی وسیله نقلیه در j 200 دقیقه است.
  • زمان سفر از i تا j 75 دقیقه است.

وسیله نقلیه نمی‌تواند بلافاصله پس از ورود، مکان i را ترک کند، یا زمان تجمعی آن در مکان j 175 خواهد بود. در عوض، خودرو باید قبل از حرکت 25 دقیقه در مکان i منتظر بماند. به عبارت دیگر، سستی در مکان i 25 است.

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

از طرف دیگر، برای CVRP، تغییر در بار انباشته از i به j همیشه برابر با تقاضا در i است، بنابراین هیچ سستی وجود ندارد. برای چنین مشکلاتی می توانید slack_max روی 0 تنظیم کنید.

در مرحله بعد، ما به تعریف رسمی Slack می پردازیم. در داخل، یک بعد دو نوع متغیر مربوط به مقادیری را که در طول مسیرها جمع می شوند ذخیره می کند:

  • متغیرهای ترانزیت : افزایش یا کاهش مقدار در هر مرحله از مسیر. اگر i -> j یک مرحله در مسیر باشد، متغیر انتقال یا ورودی i ، j ماتریس ترانزیت (برای یک تماس برگشتی) یا به سادگی مقدار پاسخ به تماس در مکان i است (اگر پاسخ تماس فقط به یک مکان بستگی دارد. ).
  • متغیرهای تجمعی : کل مقدار انباشته شده در هر مکان. شما می توانید با dimension_name.CumulVar(i) به متغیر تجمعی در محل i دسترسی پیدا کنید. برای مثال، محدودیت‌های پنجره زمانی را در مثال VRPTW ببینید.

با فرض اینکه یک وسیله نقلیه در یک مرحله از مکان i به مکان j می رود، سستی به صورت زیر به این متغیرها مربوط می شود:

slack(i) = cumul(j) - cumul(i) - transit(i, j)

برای جزئیات بیشتر در مورد ابعاد، RoutingDimension در بخش مرجع ببینید.