An Improved Branch - and - Cut Algorithm for the Capacitated Vehicle Routing Problem
An Improved Branch - and - Cut Algorithm for the Capacitated Vehicle Routing Problem
复制标题
改进的分支割断算法解决容量车辆路径问题
DOI：
10.1287/trsc.37.2.153.15243
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
S. Hill
中科院分区：
文献类型：
--
作者：
N. Achuthan;L. Caccetta;S. Hill
能力约束车辆路径问题（CVRP）处理从一个集中的仓库到多个指定的客户位置与已知的需求的单一商品的分配。在本文中考虑的CVRP假设共同的车辆容量，固定或可变数量的车辆，并最大限度地减少所有车辆的总行驶距离的目标。本文针对这一问题提出了几种新的切割平面，并将其应用于精确的分支切割算法中。两个新的切割平面是基于一个指定的结构的最优解及其存在性。计算结果报告为1,650模拟欧几里德问题以及24个标准的文献测试问题，解决的问题范围从15- 100客户的大小。比较分析表明，所提出的方法的显着的计算效益。
The capacitated vehicle routing problem (CVRP) deals with the distribution of a single commodity from a centralized depot to a number of specified customer locations with known demands. The CVRP considered in this paper assumes common vehicle capacity, fixed or variable number of vehicles, and an objective to minimize the total distance traveled by all the vehicles. This paper develops several new cutting planes for this problem, and uses them in an exact branch-and-cut algorithm. Two of the new cutting planes are based on a specified structure of an optimal solution and its existence. Computational results are reported for 1,650 simulated Euclidean problems as well as 24 standard literature test problems; solved problems range in size from 15--100 customers. A comparative analysis demonstrates the significant computational benefit of the proposed method.