ابعاد
با مجموعه‌ها، منظم بمانید
ذخیره و طبقه‌بندی محتوا براساس اولویت‌های شما.
حل‌کننده مسیریابی از شیئی به نام بعد استفاده می‌کند تا مقادیری را که در طول مسیر وسیله نقلیه جمع می‌شوند، مانند زمان سفر یا اگر وسیله نقلیه در حال تحویل گرفتن و تحویل است، کل وزنی که حمل می‌کند، ردیابی کند. اگر یک مشکل مسیریابی شامل چنین کمیتی باشد، چه در قیود یا تابع هدف، باید یک بعد برای مشخص کردن آنها تعریف کنید.
این بخش نحوه تعریف و استفاده از ابعاد را توضیح می دهد.
نمونه هایی از ابعاد
در اینجا چند نمونه از ابعاد از بخش های قبلی آورده شده است.
مثال 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 در بخش مرجع ببینید.
جز در مواردی که غیر از این ذکر شده باشد،محتوای این صفحه تحت مجوز Creative Commons Attribution 4.0 License است. نمونه کدها نیز دارای مجوز Apache 2.0 License است. برای اطلاع از جزئیات، به خطمشیهای سایت Google Developers مراجعه کنید. جاوا علامت تجاری ثبتشده Oracle و/یا شرکتهای وابسته به آن است.
تاریخ آخرین بهروزرسانی 2024-08-26 بهوقت ساعت هماهنگ جهانی.
[null,null,["تاریخ آخرین بهروزرسانی 2024-08-26 بهوقت ساعت هماهنگ جهانی."],[[["\u003cp\u003eRouting solver uses \u003cem\u003edimensions\u003c/em\u003e to track quantities like travel time or load along a vehicle's route, essential for constraints and objective functions.\u003c/p\u003e\n"],["\u003cp\u003eDimensions are defined using the \u003ccode\u003eAddDimension\u003c/code\u003e method, specifying parameters like callback index, slack, capacity, and whether the cumulative value starts at zero.\u003c/p\u003e\n"],["\u003cp\u003eSlack variables represent waiting times at locations, crucial for problems with time window constraints like VRPTW.\u003c/p\u003e\n"],["\u003cp\u003e\u003ccode\u003eAddDimensionWithVehicleCapacity\u003c/code\u003e allows defining dimensions with varying capacities for different vehicles, unlike \u003ccode\u003eAddDimension\u003c/code\u003e which assumes uniform capacity.\u003c/p\u003e\n"],["\u003cp\u003eTwo key variable types within dimensions: \u003cem\u003etransit variables\u003c/em\u003e representing quantity changes at each step and \u003cem\u003ecumulative variables\u003c/em\u003e representing the total accumulated quantity at each location.\u003c/p\u003e\n"]]],["The routing solver utilizes *dimensions* to track accumulating quantities along vehicle routes, such as travel time or carried weight. To define a dimension, the `AddDimension` method is used, requiring inputs like `callback_index`, `slack_max`, `capacity`, `fix_start_cumul_to_zero`, and `dimension_name`. `AddDimensionWithVehicleCapacity` handles varying capacities per vehicle. Slack variables represent waiting times at locations and are computed using transit and cumulative variables. Dimensions are essential for enforcing constraints and defining the objective function in routing problems.\n"],null,["# Dimensions\n\nThe routing solver uses an object called a *dimension* to keep track of\nquantities that accumulate along a vehicle's route, such as the travel time or,\nif the vehicle is making pickups and deliveries, the total weight it is carrying\n. If a routing problem involves such a quantity, either in the constraints or\nthe objective function, you need to define a dimension to specify them.\n\nThis section explains how to define and use dimensions.\n\nExamples of dimensions\n----------------------\n\nHere are a couple of examples of dimensions from previous sections.\n\n- The [VRPTW example](/optimization/routing/cvrptw) creates a dimension to track\n each vehicle's cumulative travel time. The solver uses the dimension to enforce\n the constraint that a vehicle can only visit a location within the location's\n time window.\n\n- The [CVRP example](/optimization/routing/cvrp) creates a dimension for the\n *demands* (e.g., weights or volumes of packages to be picked up), which tracks\n the cumulative load the vehicle is carrying along its route.\n The solver uses the dimension to enforce the constraint that a vehicle's load\n can't exceed its capacity.\n\nThe examples below define a dimension for the VRPTW using the\n[`AddDimension`](/optimization/reference/constraint_solver/routing/RoutingModel#AddDimension)\nmethod. \n\n### Python\n\n```python\nrouting.AddDimension(\n callback_index,\n slack_max,\n capacity,\n fix_start_cumul_to_zero,\n dimension_name)\n```\n\n### C++\n\n```c++\nrouting.AddDimension(\n callback_index,\n slack_max,\n capacity,\n fix_start_cumul_to_zero,\n dimension_name)\n```\n\n### Java\n\n```java\nrouting.addDimension(\n callbackIndex,\n slackMax,\n capacity,\n fixStartCumulToZero,\n dimensionName)\n```\n\n### C#\n\n```c#\nrouting.AddDimension(\n callbackIndex,\n slackMax,\n capacity,\n fixStartCumulToZero,\n dimensionName)\n```\n\nThe `AddDimension` method has the following inputs:\n\n- `callback_index`: The index for the callback that returns the quantity. The index, which is the solver's internal reference to the callback, is created by methods such as `RegisterTransitCallback` or `RegisterUnitaryTransitCallback`.\n- `slack_max`: Maximum for the *slack* , a variable used to represent waiting times at the locations. See [slack variables](#slack_variables) below for details. If the problem doesn't involve waiting time, you can usually set `slack_max` to 0.\n- `capacity`: Maximum for the total quantity accumulated along each route. Use `capacity` to create constraints like those in the [CVRP](/optimization/routing/cvrp). If your problem doesn't have such a constraint, you can set `capacity` to a value that is sufficiently large to impose no restrictions on the routes ---for example, the sum of all entries of the matrix or array used to define the callback.\n- `fix_start_cumulative_to_zero`: Boolean value. If true, the cumulative value of the quantity starts at 0. In most cases, this should be set to `True`. However, for the [VRPTW](/optimization/routing/cvrptw) or problems with [resource constraints](/optimization/routing/cvrptw_resources), some vehicles may have to start after time 0 due to time window constraints, so you should set `fix_start_cumulative_to_zero` to `False` for these problems.\n- `dimension_name`: String for the name for the dimension, such as `'Distance'`, which you can use to access the variables elsewhere in the program.\n\nThe CVRP program creates a slightly different type of dimension using the\n[`AddDimensionWithVehicleCapacity`](/optimization/reference/constraint_solver/routing/RoutingModel#AddDimensionWithVehicleCapacity)\nmethod. This method takes an array of capacities, with one entry for each vehicle.\n(In contrast, `AddDimension` takes a single value for `capacity`, so all\nvehicles are assumed to have the same capacity.)\n\nSee the [`RoutingModel`](/optimization/reference/constraint_solver/routing/RoutingModel)\nreference page for other methods that create dimensions.\n\nThe section\n[Save the solution time windows to a list or array](/optimization/routing/vrptw#get-cumulative-data)\npresents functions that save the cumulative data in a dimension in a list or array.\n\nSlack variables\n---------------\n\nHere's an example that illustrates slack variables for a problem involving\ntravel time. Suppose that\na vehicle goes from location i to location j in one step of its route, and that:\n\n- The vehicle's cumulative travel time at i is 100 minutes.\n- The vehicle's cumulative travel time at j is 200 minutes.\n- The travel time from i to j is 75 minutes.\n\nThe vehicle can't leave location i immediately upon arrival, or its cumulative\ntime at location j would be 175. Instead, vehicle must wait for 25 minutes at\nlocation i before departing; in other words, the slack at location i is 25.\n\nYou need to allow slack in a VRPTW because vehicles may have to wait before\nvisiting a location, due to time window constraints. In a problem like this, set\n`slack_max` to the maximum amount of time you want to allow vehicles to wait at\na location before proceeding to the next location. If it doesn't matter how long\nthey wait, just set `slack_max` to a very large number.\n\nFor the CVRP, on the other hand, the change in the accumulated load from `i` to\n`j` always equals the demand at `i`, so there is no slack. For problems like\nthis, you can set `slack_max` to 0.\n\nNext, we'll give the formal definition of slack. Internally, a dimension stores\ntwo types of variables related to quantities that accumulate along routes:\n\n- *Transit variables* : The increase or decrease of the quantity at each step of a route. If `i -\u003e j` is one step in a route, the transit variable is either the `i`, `j` entry of the transit matrix (for a transit callback), or simply the callback value at location i (if the callback depends on just one location).\n- *Cumulative variables* : The total accumulated quantity at each location. You can access the cumulative variable at location i by `dimension_name.CumulVar(i)`. For an example, see the [time window constraints](/optimization/routing/vrptw#time_window_constraints) in the VRPTW example.\n\nAssuming that a vehicle goes from location `i` to location `j` in one step, the\nslack is related to these variables as follows: \n\n```\nslack(i) = cumul(j) - cumul(i) - transit(i, j)\n```\n\n\u003cbr /\u003e\n\nFor more details about dimensions, see\n[`RoutingDimension`](/optimization/reference/constraint_solver/routing/RoutingDimension)\nin the reference section."]]
