跳至內容

車輛路徑問題

維基百科,自由的百科全書

車輛路徑問題(VRP)是一個組合優化整數規劃問題英語Integer_programming(回答了「為了交付給定的一組客戶,車輛車隊的最佳路線集是什麼?」)。它概括了眾所周知的旅行推銷員問題(TSP)。它最初出現在1959年George Dantzig和John Ramser的論文中[1]。這篇論文首先編寫了算法,並將其應用於汽油交付。通常,這個問題的背景是將位於中央倉庫的貨物交付給已經訂購此類貨物的客戶。 VRP的目標是最小化總路由成本。 1964年,Clarke和Wright使用一種稱為儲蓄算法的有效貪婪方法改進了Dantzig和Ramser的方法。

參考資料

[編輯]
  1. ^ Dantzig, George Bernard; Ramser, John Hubert. The Truck Dispatching Problem (PDF). Management Science. October 1959, 6 (1): 80–91 [2019-07-02]. doi:10.1287/mnsc.6.1.80. (原始內容存檔 (PDF)於2013-11-12).