LUOJIA985784554的个人博客分享 http://blog.sciencenet.cn/u/LUOJIA985784554

博文

【汇总】车辆路径问题中常用的测试集

已有 2873 次阅读 2019-11-21 10:30 |系统分类:科研笔记

车辆路径问题中用来检验算法性能(这里所说的算法主要是精确算法和启发式算法)的测试集是基于传统的带容量限制的车辆路径问题(CVRP)。

第一个,由Augerat等人在群里1995年提出的ABP,以及分别在1969、1994、1979年由Christofides and Eilon,Fisher,Christofides、Mingozzi and Toth提出的E,F,M,也就是常说的ABEFMP测试集。

由于提出时间早,所以几乎所有的精确实算法都是用这6类例子进行测试。这个测试集里面90%以上的例子中的客户数量都没有超过100,但是有几个例子用当时非常流行的分支定界法也没能得到最优解。在2006年Fukasawa提出Branch-Cut-Price算法能够求解出高达100个客户点的案例,但是还剩下M系列里面的三个:M-n151-k12,M-n200-k16,M-n200-k17,这3个M系列的案例是到了这几年才解出来。Martinelli(2014)和Ropke(2012)求解出了M-n151-k12,Pecin,Pessoa,Poggi and Uchoa(2014)提出的算法解决了M-n200-k16,M-n200-k17。

Rochat and Taillard(1995)提出的启发式算法其实已经能够得到最优解,除了有一个带199个客户的案例,跟最优解相比差了0.012%。

第二个,由Golden等人在1998年提出的测试集,客户数目介于240-483之间,也能较好地验证算法。

第三个,由Uchoa等人在2014年提出的测试集,客户数目介于100-1000之间,维数更大,客户点的位置及需求、车场的位置更贴近实际情况。因此,对于算法的要求更高。



https://blog.sciencenet.cn/blog-3421244-1206979.html

上一篇:求解优化问题常用的搜索方法
收藏 IP: 116.236.75.*| 热度|

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-9-19 12:45

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部