车辆路径问题

维基百科,自由的百科全书
跳到导航 跳到搜索

车辆路径问题(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).