ขนาด
จัดทุกอย่างให้เป็นระเบียบอยู่เสมอด้วยคอลเล็กชัน
บันทึกและจัดหมวดหมู่เนื้อหาตามค่ากำหนดของคุณ
ตัวแก้โจทย์การกำหนดเส้นทางใช้ออบเจ็กต์ที่เรียกว่ามิติข้อมูลเพื่อติดตาม
ปริมาณที่สะสมบนเส้นทางของยานพาหนะ เช่น เวลาที่ใช้ในการเดินทาง หรือ
หากยานพาหนะใช้ขนส่งสินค้าและนำส่ง น้ำหนักรวมที่ใช้บรรทุก
ที่ใช้เวลาเพียง 2 นาที ถ้าปัญหาการกำหนดเส้นทางเกี่ยวข้องกับจำนวนดังกล่าว ทั้งในข้อจำกัดหรือ
ฟังก์ชันวัตถุประสงค์ คุณจะต้องกำหนดมิติข้อมูลเพื่อระบุมิติข้อมูล
ส่วนนี้จะอธิบายวิธีกำหนดและใช้มิติข้อมูล
ตัวอย่างของมิติข้อมูล
ต่อไปนี้เป็นตัวอย่างมิติข้อมูล 2-3 ข้อจากส่วนก่อนหน้า
ตัวอย่าง VRPTW สร้างมิติข้อมูลเพื่อติดตาม
ระยะเวลาเดินทางสะสมของยานพาหนะแต่ละคัน เครื่องมือแก้โจทย์ใช้มิติข้อมูลเพื่อบังคับใช้
ข้อจำกัดที่ว่ายานพาหนะสามารถเข้าชมได้เฉพาะสถานที่ภายใน
กรอบเวลา
ตัวอย่าง CVRP จะสร้างมิติข้อมูลสำหรับ
ความต้องการ (เช่น น้ำหนักหรือปริมาณบรรจุภัณฑ์ที่จะรับ) ซึ่งติดตาม
น้ำหนักบรรทุกสะสมที่พาหนะใช้อยู่บนเส้นทาง
เครื่องมือแก้โจทย์คณิตใช้มิติข้อมูลเพื่อบังคับใช้ข้อจำกัดเกี่ยวกับน้ำหนักบรรทุกของยานพาหนะ
ต้องไม่เกินจากความจุ
ตัวอย่างด้านล่างกำหนดมิติข้อมูลสำหรับ VRPTW โดยใช้
AddDimension
Python
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)
Java
routing.addDimension(
callbackIndex,
slackMax,
capacity,
fixStartCumulToZero,
dimensionName)
C#
routing.AddDimension(
callbackIndex,
slackMax,
capacity,
fixStartCumulToZero,
dimensionName)
เมธอด AddDimension มีอินพุตต่อไปนี้
callback_index: ดัชนีสำหรับ Callback ที่แสดงจำนวน
ดัชนี ซึ่งเป็นการอ้างอิงภายในของตัวแก้โจทย์กับ Callback จะสร้างขึ้นโดย
เช่น RegisterTransitCallback หรือ RegisterUnitaryTransitCallbackslack_max: ค่าสูงสุดสำหรับ slack ซึ่งเป็นตัวแปรที่ใช้แทนการรอ
ในสถานที่ต่างๆ โปรดดูตัวแปร Slack ด้านล่างสำหรับ
รายละเอียด
หากปัญหาไม่จำเป็นต้องมีเวลารอ คุณก็มักจะตั้งค่า slack_max ได้
เป็น 0capacity: ค่าสูงสุดสำหรับปริมาณทั้งหมดสะสมตลอดเส้นทางแต่ละเส้นทาง
ใช้ capacity เพื่อสร้างข้อจำกัดแบบเดียวกับที่มีอยู่ใน
CVRP ถ้าปัญหาของคุณไม่มี
คุณสามารถตั้งค่า capacity เป็นค่าที่ใหญ่พอที่จะ
ไม่มีข้อจำกัดเกี่ยวกับเส้นทาง เช่น ผลรวมของทุกเส้นทาง
ของเมทริกซ์หรืออาร์เรย์ที่ใช้กำหนด Callbackfix_start_cumulative_to_zero: ค่าบูลีน หากจริง ค่าสะสม
ของจำนวนเริ่มต้นที่ 0 ในกรณีส่วนใหญ่ ควรตั้งค่านี้เป็น True
แต่สำหรับ VRPTW หรือปัญหาเกี่ยวกับ
ข้อจำกัดด้านทรัพยากร ยานพาหนะบางคัน
อาจต้องเริ่มต้นหลังจากเวลา 0 เนื่องจากข้อจำกัดด้านกรอบเวลา คุณจึงควร
ตั้งค่า fix_start_cumulative_to_zero เป็น False สำหรับโจทย์เหล่านี้dimension_name: สตริงสำหรับชื่อของมิติข้อมูล เช่น 'Distance'
ซึ่งคุณสามารถใช้เพื่อเข้าถึงตัวแปรต่างๆ ในโปรแกรม
โปรแกรม CVRP จะสร้างมิติข้อมูลประเภทที่แตกต่างกันเล็กน้อยโดยใช้
AddDimensionWithVehicleCapacity
วิธีการนี้รองรับความจุหลากหลาย โดยมี 1 รายการสำหรับยานพาหนะแต่ละคัน
(ในทางตรงกันข้าม AddDimension จะใช้ค่าเดียวสำหรับ capacity ดังนั้น
โดยให้ถือว่ามีความจุเท่ากัน)
โปรดดูRoutingModel
สำหรับวิธีการอื่นๆ ที่สร้างมิติข้อมูล
ส่วน
บันทึกกรอบเวลาของโซลูชันลงในรายการหรืออาร์เรย์
แสดงฟังก์ชันที่บันทึกข้อมูลสะสมในมิติข้อมูลในรายการหรืออาร์เรย์
ตัวแปรของ Slack
ด้านล่างนี้เป็นตัวอย่างที่แสดงให้เห็นตัวแปร Slack สำหรับปัญหาที่เกี่ยวข้องกับ
ระยะเวลาเดินทาง สมมติว่า
ยานพาหนะแล่นจากตำแหน่ง i ไปยังตำแหน่ง j ในขั้นตอนใดขั้นตอนหนึ่งของเส้นทาง และ
- ระยะเวลาเดินทางสะสมของยานพาหนะที่ i คือ 100 นาที
- ระยะเวลาเดินทางสะสมของยานพาหนะที่ j คือ 200 นาที
- เวลาเดินทางจาก i ไป j คือ 75 นาที
รถไม่สามารถออกจากตำแหน่งได้ในทันทีเมื่อมาถึงหรือสะสมอยู่
เวลาที่สถานที่ j จะเป็น 175 แต่จะต้องรอเป็นเวลา 25 นาทีที่
สถานที่ i ก่อนออกเดินทาง พูดอีกอย่างคือ ตำแหน่งที่ไม่ปกติ i อายุ 25 ปี
คุณต้องอนุญาตให้รถหย่อนลงใน VRPTW เนื่องจากยานพาหนะอาจต้องรอก่อน
เยี่ยมชมสถานที่เนื่องจากข้อจำกัดด้านเวลา ในโจทย์แบบนี้ ให้ตั้งค่า
slack_max เป็นระยะเวลาสูงสุดที่คุณต้องการอนุญาตให้ยานพาหนะรอ
ก่อนไปที่ตำแหน่งถัดไป หากไม่สำคัญว่าใช้เวลาเท่าใด
ก็แค่ตั้งค่า slack_max ให้มีตัวเลขจำนวนมากเลย
ในทางกลับกัน สำหรับ CVRP การเปลี่ยนแปลงของโหลดสะสมจาก i เป็น
j จะเท่ากับความต้องการที่ i เสมอ จึงไม่มีความหลวม สำหรับปัญหา เช่น
ตัวเลือกนี้ตั้งค่า slack_max เป็น 0 ได้
ถัดไป เราจะให้คำจำกัดความอย่างเป็นทางการของ Slack ตัวเลือกภายใน ที่เก็บมิติข้อมูล
ตัวแปร 2 ประเภทที่เกี่ยวข้องกับปริมาณที่สะสมตามเส้นทาง ได้แก่
- ตัวแปรขนส่งสาธารณะ: การเพิ่มขึ้นหรือลดลงของปริมาณในแต่ละขั้นตอนของ
เส้นทาง
ถ้า
i -> j คือขั้นตอนเดียวในเส้นทาง ตัวแปรการขนส่งจะเป็น i
j ของเมทริกซ์การขนส่งสาธารณะ (สำหรับการเรียกกลับของการขนส่งสาธารณะ) หรือเรียกง่ายๆ ว่า
ค่า Callback ที่ตำแหน่ง i (หาก Callback ขึ้นอยู่กับสถานที่ตั้งเพียงแห่งเดียว)
- ตัวแปรสะสม: ปริมาณสะสมทั้งหมดของสถานที่แต่ละแห่ง คุณ
สามารถเข้าถึงตัวแปรสะสมในตำแหน่ง i โดย
dimension_name.CumulVar(i) ตัวอย่างเช่น ดูที่
ข้อจำกัดด้านกรอบเวลา
ในตัวอย่าง VRPTW
สมมติว่ายานพาหนะเดินทางจากตำแหน่ง i ไปยังตำแหน่ง j ในขั้นตอนเดียว
slack เกี่ยวข้องกับตัวแปรเหล่านี้ดังนี้
slack(i) = cumul(j) - cumul(i) - transit(i, j)
ดูรายละเอียดเพิ่มเติมเกี่ยวกับมิติข้อมูลได้ที่
RoutingDimension
ในส่วนการอ้างอิง
เนื้อหาของหน้าเว็บนี้ได้รับอนุญาตภายใต้ใบอนุญาตที่ต้องระบุที่มาของครีเอทีฟคอมมอนส์ 4.0 และตัวอย่างโค้ดได้รับอนุญาตภายใต้ใบอนุญาต Apache 2.0 เว้นแต่จะระบุไว้เป็นอย่างอื่น โปรดดูรายละเอียดที่นโยบายเว็บไซต์ Google Developers Java เป็นเครื่องหมายการค้าจดทะเบียนของ Oracle และ/หรือบริษัทในเครือ
อัปเดตล่าสุด 2024-08-29 UTC
[null,null,["อัปเดตล่าสุด 2024-08-29 UTC"],[[["\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."]]
