具有容量约束的车辆路径问题算例CVRP

本页面列举一些比较有名的CVRP算例数据及其优化方案。

Augerat 等研究得 CVRP的三类数据集
数据集A:
   算例: 27个文件
   优化方案: 20个文件
   部分问题图表: 6个文件
　

数据集B:
 算例: 23个文件
 优化方案: 19个文件

数据集P:
  算例数据: 24 files

注：

Augerat的CVRP数据集是最基本的数据集，初始条件是：有1个车场，n个需求点（客户）和容量相同的k辆车，n个需求点的地理位置用二维坐标表示，每个需求点需要车辆从车场运送的特定数量的相同产品。

优化目标：

   所排出的车辆运行距离最短；

数据集A、B、P本质上是相同的，数据集的结构也是相同的，可以采取统一类型的解法进行求解。

Breedam研究的CVRP数据集
  Breedam文件结构说明
   车辆容量等于50的数据集 (G2, 60个数据文件)

   车辆容量等于100的数据集 (G1, 60个数据文件)

   车辆容量等于200的数据集 (G3, 60个数据文件)

   Breedam基准数据集的最优解

注：Breedam数据集同Augerat数据集的异同：

（1）相同点：（a）均为有1个车场，n个需求点（客户）和容量相同的k辆车，n个需求点的地理位置用二维坐标表示；

       （b）每个需求点需要从车场运送特定数量的产品

（2）不同点：（a）Breedam数据集中每个需求点的需求数量均为10个，而Augerat数据集中每个需求点的需求数量不一定相等。

       （b）Breedam数据集的扩展性比较强，可以扩展为：哪个节点是装载点，哪个节点时卸载点。

Christofides和Eilon研究的CVRP数据集
  他们研究的CVRP中顾客数量分布在13个到101个之间，每个问题中的车辆数量也会不同。
    算例数据: 15个数据文件
    优化方案: 9个文件

注：数据集基本同Breedam和Augerat的数据集，只是节点间的距离直接给出，而非给出节点的X、Y坐标。

Fisher研究的CVRP数据集
  Fisher研究了3个算例，分别为：45个顾客和4辆车、72个顾客和4辆车、135个顾客和7辆车。
    算例数据: 3个数据文件
    优化方案: 3个文件

Christofides, Mingozzi和Toth研究的CVRP数据集
   下面列举的数据集为N.Christofides, A.Mingozzi, P.Toth and C.Sandi编辑的“Combinatorial optimization”, John Wiley, Chichester 1979书籍中11章的14个测试问题。
    算例数据: 14个数据文件

Rinaldi和Yarrow研究的CVRP数据集
   一个数据集，48个顾客和容量为15的车辆。

Taillard研究的CVRP数据集
    算例数据:Taillard提出了12个算例，顾客数量从75到385个。
    优化方案：

Golden, Wasil, Kelly 和Chao研究的CVRP数据集
   他们研究得算例有20个大规模的VRP问题，顾客数量从200到480个，部分算例对每个路径的最大长度进行了限制，算例的最优解可以从Prins的论文中获得。

   优化方案：New best solutions for the benchmark of Golden et al.

TSPLIB（旅行商问题库）

   算例数据: 14 个文件
   优化方案: 14 个文件