車輛路線

最常見的最佳化工作之一是「車輛路線」，而其目標是為造訪一組地點的車隊找到最佳路線。通常，「最佳」表示距離或費用最少的路線。以下列舉幾個轉送問題的範例：

  • 某間包裹配送公司想指派路線給司機提供外送服務。
  • 某間有線電視公司想指派路徑給技術人員進行住宅服務通話。
  • 一間共乘公司想指派路線給司機上下車，

最常見的轉送問題是旅遊銷售人員問題 (TSP)：找出需要造訪不同地點的客戶並返回起點的銷售專員最快的路線。TSP 能以圖表表示，其中節點對應位置，邊緣 (或弧形) 則代表在不同位置之間直接移動。舉例來說，下圖顯示只有四個位置的 TSP，並分別標示為 A、B、C 和 D。任意兩個地點之間的距離，由緊接在兩個地點邊緣的數字組成。

Tsp 動畫

計算所有可能路線的距離後，您可以看到最短路線為 ACDBA，總距離為 35 + 30 + 15 + 10 = 90。

地點越多，問題就越難。上例中只有六個路徑。但如果有十個位置 (沒有計算起點)，則路徑數為 362880。因此，如果是 20 個地點，該號碼則會跳至 2432902008176640000。 對所有可能路徑進行詳盡搜尋可保證可以找到最短，但對於位置較小的位置集，這會是局部計算的。如果是較大型的問題，系統需要最佳化技巧才能對解決方案空間進行智慧搜尋，並找到最佳 (或近乎最佳) 解決方案。

較籠統的 TSP 版本是車輛的路由問題 (VRP) 中有多個車輛。在大多數情況下，VRP 都有限制，例如車輛可能隨攜帶物品的重量或容量上限，或者駕駛人員可能需要在特定時間範圍內造訪地點。

OR-Tools 可以解決多種 VRP 類型，包括：

解決車輛路線問題的限制

車輛的路由問題本質上就越來越難理解：解決這些問題所需的時間會隨著問題規模而急劇成長。對於明顯較大的問題，可能需要 OR-Tools (或任何其他轉送軟體) 數年才能找到最佳解決方案。因此，OR-Tools 有時會傳回良好 但並不理想的解決方案。如要尋找更好的解決方案 請變更解題工具的搜尋選項如需範例，請參閱變更搜尋策略。