車輛路徑問題

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