车辆路径问题

车辆路径问题（VRP）是一个组合优化和整数规划问题（英语：Integer_programming）（回答了“为了交付给定的一组客户，车辆车队的最佳路线集是什么？”）。它概括了众所周知的旅行推销员问题（TSP）。它最初出现在1959年George Dantzig和John Ramser的论文中^[1]。这篇论文首先编写了算法，并将其应用于汽油交付。通常，这个问题的背景是将位于中央仓库的货物交付给已经订购此类货物的客户。 VRP的目标是最小化总路由成本。 1964年，Clarke和Wright使用一种称为储蓄算法的有效贪婪方法改进了Dantzig和Ramser的方法。