具有容量约束的车辆路径问题算例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 个文件