本節說明轉送器的幾個選項。
搜尋限制
搜尋限制達到特定限制時就會終止解題工具,例如時間長度上限或找到的解決方案數量。您可以透過解析器的搜尋參數設定搜尋限制。如需範例,請參閱時間限制。
下表說明最常見的搜尋限制。
姓名 | 類型 | 預設 | 說明 |
---|---|---|---|
solution_limit
|
int64 | kint64max | 請限制搜尋期間產生的解決方案數量。 |
time_limit.seconds
|
int64 | kint64max | 限制搜尋使用時間:以秒為單位。 |
lns_time_limit.seconds
|
int64 | 100 | 限制搜尋秒數的時間: 每個區域搜尋的完成搜尋。 |
第一個解決方案策略
第一個解決方案策略是解題工具用來找出初始解決方案的方法。下表列出 first_solution_strategy
的選項。
選項 | 說明 |
---|---|
AUTOMATIC
|
讓解析器根據要解決的模型,偵測要使用的策略。 |
PATH_CHEAPEST_ARC
|
從路徑「start」節點開始,將節點連線至產生最便宜路徑區隔的節點,然後疊代新增至路徑中的最後一個節點來擴充路徑。 |
PATH_MOST_CONSTRAINED_ARC
|
與 PATH_CHEAPEST_ARC 類似,但 rca 是以比較的選取器進行評估,且會先採用限制最嚴格的弧形。如要將選取器指派給轉送模型,請使用 ArcIsMoreConstrainedThanArc() 方法。 |
EVALUATOR_STRATEGY
|
與 PATH_CHEAPEST_ARC 類似,但 Arc 費用是以傳遞至 SetFirstSolutionEvaluator() 的函式來評估。 |
SAVINGS
|
儲蓄演算法 (Clarke 和 Wright)。參考資料:Clarke, G. 和 Wright, J.W. 「Schedule of the Vehicle from a Central Depot to a Number of Delivery Point》(從中央車站到中央,車輛的站點號碼), |
SWEEP
|
掃瞄演算法 (Wren & Holliday)。參考 Anthony Wren & Alan Holliday 電腦安排安排行程,從單程或多輛庫到現場載運點 研究中心 (1970-1977),第 23 號,第 33 號 (9 月、1972),第 333-344 頁。 |
CHRISTOFIDES
|
Christofides 演算法 (實際上是將 Christoithes 演算法的變化版本,盡可能使用最大值比對結果),但無法保證 3/2 因公制旅遊專員所提出的估計值。可藉由擴充路線來補充一般車輛路線模型,直到無法插入節點。參考 Nicos Christoithes 針對旅遊旅客問題推出新的經驗法則分析,報告 388,義大利工業管理學院 CMU 1976 報告。 |
ALL_UNPERFORMED
|
停用所有節點。只有在節點為選用的情況下,才能尋找解決方案 (屬於限制限制的阻塞限制元素)。 |
BEST_INSERTION
|
透過將最便宜的節點插入最便宜的位置,以便建構解決方案;插入費用取決於轉送模型的全域成本函式。自 2012 年起,只有包含選用節點的模型 (費用有限), |
PARALLEL_CHEAPEST_INSERTION
|
透過將最便宜的節點插入最便宜的節點,以反覆建構解決方案,插入費用取決於弧形成本函式。比 BEST_INSERTION 快。 |
LOCAL_CHEAPEST_INSERTION
|
反覆地建立解決方案,並把每個節點插入最便宜的位置,不過費用會因弧形成本函式而異。從 PARALLEL_CHEAPEST_INSERTION 做為插入作業的節點之間的差異;這裡的節點會依建立順序而異。比 PARALLEL_CHEAPEST_INSERTION 快。 |
GLOBAL_CHEAPEST_ARC
|
反覆連結兩個節點,建立最便宜的路徑區隔。 |
LOCAL_CHEAPEST_ARC
|
選取含有未繫結後續運算器的第一個節點,然後將節點連線至產生最便宜路徑區隔的節點。 |
FIRST_UNBOUND_MIN_VALUE
|
選取第一個含有未繫結嘗試的節點,並連線至第一個可用的節點。這相當於與 ASSIGN_MIN_VALUE 結合的 CHOOSE_FIRST_UNBOUND 策略 (cf. tt_solver.h)。 |
搜尋狀態
您可以使用轉送模型的 status
方法傳回搜尋狀態。以下是列印搜尋狀態的 Python 程式碼:
print("Solver status: ", solver.status())
這會輸出具有下列含義的整數:
值 | 說明 |
---|---|
0 |
ROUTING_NOT_SOLVED :問題尚未解決。 |
1 |
ROUTING_SUCCESS :問題已成功解決。 |
2
|
ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED :呼叫 RoutingModel.Solve() 後成功解決問題,前提是尚未達到本機最佳化。將時間拉長一點,有助於改善解決方案。 |
3 |
ROUTING_FAIL :找不到問題的解決方案。 |
4 |
ROUTING_FAIL_TIMEOUT :尋找解決方案前已達時間上限 |
5 |
ROUTING_INVALID :模型、模型參數或旗標無效。 |
6 |
ROUTING_INFEASIBLE :經證實無法解決的問題。 |
區域搜尋選項
下表列出本機搜尋策略 (也稱為中繼) 的選項。如需設定這些選項的範例,請參閱變更搜尋策略。
選項 | 說明 |
---|---|
AUTOMATIC |
讓解析器選取新式。 |
GREEDY_DESCENT |
接受改善 (減少成本) 區域搜尋點,直到達到當地最小值。 |
GUIDED_LOCAL_SEARCH |
使用引導式本地搜尋跳脫本地極簡錯誤。(cf. 引導式搜尋) 這類內容,通常是最適合用於路線規劃的子類別。 |
SIMULATED_ANNEALING |
使用模擬模擬功能將逸出當地最小值插入 (cf. Simulated Annealing)。 |
TABU_SEARCH |
使用 Tab 鍵搜尋來逸出本機的最小值 (cf. Tabu Search)。 |
GENERIC_TABU_SEARCH |
針對定位目標值使用 Tab 鍵搜尋,以逸出本機最小值。 |
傳播控制
姓名 | 類型 | 預設 | 說明 |
---|---|---|---|
use_full_propagation
|
布林值 | 是 | 在轉送模型中使用全面傳播限制 (而非僅使用光傳播)。只有在使用深度優先搜尋,或需要強力傳播的模式來確定次要變數的值時,才需要進行完整傳播。在大多數情況下,將這項設定變更為 true 會降低搜尋速度,並增加所有記憶體的記憶體用量。 |