維度

路徑解析器會使用名為「維度」的物件來追蹤車輛路徑上累積的量，例如路程時間；如果車輛提供自取與外送，則會記錄其總重量。如果轉送問題涉及限制數量或目標函式，就必須定義維度來指定。

本節將說明如何定義和使用維度。

維度範例

以下幾個範例說明瞭前幾個小節的維度。

  • VRPTW 範例會建立維度，以追蹤每輛車的累計交通時間。解題工具使用這項維度來強制執行限制，是車輛只能造訪地點時間範圍內的某個地點。

  • CVRP 範例會建立需求的維度 (例如要挑選的重量或包裹數量)，用於追蹤車輛在路線上所累積的累計負載。解析器會使用這項維度來強制執行車輛負載無法超過容量的限制。

以下範例使用 AddDimension 方法定義 VRPTW 的維度。

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：傳回數量的回呼索引。索引是解題工具的內部參照，用來建立 RegisterTransitCallback 或 RegisterUnitaryTransitCallback 等方法。
  • slack_max：slack 的最大值，它是表示位置等待時間的變數。詳情請參閱下方的「精簡變數」一節。 如果該問題不會等候等候時間，您通常可以將 slack_max 設為 0。
  • capacity：沿每條路線所累積的總量上限。 使用 capacity 來建立類似 CVRP 的限制。如果您的問題沒有這類限制，您可以將 capacity 設為夠大的值，使該路徑不受任何限制，例如用於定義回呼的矩陣或陣列的所有總和。
  • fix_start_cumulative_to_zero：布林值。如為 true，數量的累計值為 0。在大多數情況下，應設為 True。不過，對於 VRPTW 或資源限制的問題，由於時間限制，某些車輛可能需要在時間 0 之後才啟動，因此您應針對這些問題將 fix_start_cumulative_to_zero 設為 False。
  • dimension_name：維度名稱的字串，例如 'Distance'，可用於存取程式其他位置。

CVRP 程式使用 AddDimensionWithVehicleCapacity 方法建立稍微不同類型的維度。這個方法使用容量陣列，每輛車一個項目。(相較之下，AddDimension 使用 capacity 的單一值，因此會假設所有車輛都擁有相同的容量)。

如要瞭解建立維度的其他方法，請參閱 RoutingModel 參考資料頁面。

「將解決方案時間範圍儲存至清單或陣列」一節說明函式，可將累計資料儲存在清單或陣列中的維度中。

Slack 變數

以下範例說明行程時間相關問題的精簡變數。假設車輛從路線的某個步驟從位置 i 到位置 j，並且：

  • 車輛在 i 的累計行駛時間為 100 分鐘。
  • 車輛在 j 時的累計行駛時間為 200 分鐘。
  • 從 i 到 j 的交通時間為 75 分鐘。

車輛無法在抵達後立即離開 i 地點，或者在 j 地點所累積的累計值為 175。相反地，車輛必須在位置 i 等待 25 分鐘，之後就會離開；換句話說， 地點 i 的時差是 25。

基於時間限制，車輛必須允許進入 VRPTW，因為你可能需要等待一段時間才能造訪位置資訊。在這類問題中，將 slack_max 設為您想要允許車輛等待特定地點最多的時間，然後再前往下一個位置。如果請款時間限制，只要將 slack_max 設定為非常大的數字即可。

另一方面，對 CVRP 而言，從 i 變更為 j 的累積負載變化，一定會等於 i 的需求，所以不會有變化。對於這類問題，您可以將 slack_max 設為 0。

接下來，我們將提供正式的 Sack 定義。維度會在內部儲存與路徑累積數量相關的兩種變數：

  • 大眾運輸變數：路線中的每個步驟增減量。如果 i -> j 是路線中的一個步驟，大眾運輸變數可以是大眾運輸矩陣的 i 和 j 項目 (用於大眾運輸回呼)，或者只是位於位置 i 的回呼值 (如果回呼僅依附於一個位置)。
  • 累計變數：每個地點的總累計數量。您可以利用 dimension_name.CumulVar(i) 存取位置 i 的累計變數。如需範例，請參閱 VRPTW 範例中的時間範圍限制。

假設您在一個步驟中，從某個地點從 i 定位到 j 位置，這個堆疊會與下列變數相關：

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

如要進一步瞭解維度，請參閱參考資料部分中的 RoutingDimension 一節。