CARP问题的构造型启发式算法研究

第39卷 第3期2011年5月河南师范大学学报(自然科学版)JournalofHenanNormalUniversity(NaturalScienceEdition) Vol.39 No.3 May.2011 文章编号:1000-2367(2011)03-0148-05

CARP问题的构造型启发式算法研究

李庆华,林 丹

(天津大学理学院,天津300072)

摘 要:全面综述了国内外用于求解容量约束弧路径问题(CARP问题)的构造型启发式算法的研究现状,指

出了构造型启发式算法与元启发式算法相比而言的优点所在.将求解算法分为3类并且分别进行简要介绍,最后展望了构造型启发式算法的研究前景.

关键词:CARP问题;构造型启发式算法;综述

中图分类号:TP301.6;N945.15文献标志码:A

容量约束弧路径问题(CapacitatedArcRoutingProblem,CARP问题)是一个典型的组合优化问题.它在现实中具有非常广泛的应用.例如城市垃圾清理,冬季撒盐道路等现实应用均能够抽象为CARP问题.基于上述原因,CARP问题在近年来受到越来越多研究者的关注.

在过去的20年时间里,许多研究者分别从不同角度对CARP问题作了大量的分析建模并提出了优秀的解决方案,其中有不少已经投入到了实际应用中并取得了良好的效益.例如:Beltrami和Bodin为纽约的垃圾回收应用设计的规划系统[1],Eglese和Li[2]设计的兰开夏(英格兰西北部之州)道路除冰问题的方案等.国内对CARP问题的研究目前仅仅处于起步和探索阶段.

目前,国内外求解CARP问题的方法[3]主要有精确算法和近似算法.CARP问题是1981年Golden等[4]最早提出的,并由他们证明该问题是NP hard问题.甚至连找到一个费用是最优解的3/2倍的可行解,都是一个NP hard问题.因此精确算法很少能够解决现实生活中大规模的CARP问题.以构造型启发式方法与元启发式方法为代表的近似方法更加适用于实际中出现的弧路径问题实例.21世纪之前,CARP问题的大部分研究工作均集中于利用构造型启发式算法作为解决方案从而以较少的计算资源为代价迅速得到一个可被接受的解[5].进入21世纪之后,研究者们开始转而考虑利用更多的计算资源换取质量更好的解,并将研究精力转移到元启发式方法的应用上.虽然元启发式提高了解的质量,但是构造型启发式方法还是有其独特的优点的[6].近年来,又有不少研究者投入到构造型启发式的研究当中来.

本文将CARP问题的求解视为解决聚类和排序两个子问题.基于CARP问题的这种特性,将构造型启发式算法可分为3类.

1 CARP问题介绍

经典CARP问题可以定义为:给定一个连通图,其中若干边需要某种服务.有一个车队以网络中的某个特殊点作为车场,车队中的所有车辆假定是同一车型的,由该车队中的每辆车提供相关服务.每条边均必须由一辆车提供服务,且服务需要一次完成.所有边均允许被经过任意多次.每辆车从车场出发并且在服务完成之后再回到车场,所经过的路径上的服务需求量之和不超过车辆的容量.

在实际生活的应用中CARP问题有很多派生的问题.经典的CARP问题是定义在无向图上的.由于实际应用中必须考虑单向道和并行道,所以派生出定义在有向图和和混合图上的CARP问题.按车场数目分,有单车场和多车场问题;按车辆类型分,有单车型和多车型问题;按优化目标分,有单目标问题和多目标问题.

收稿日期:2010 12 25,,,[7]

你可能喜欢

  • 英语四级新题型
  • 英文影评
  • 语文说课
  • 小学四年级数学小数
  • 认识钟表课件
  • 入党申请书范文
  • 认识钟表教案

CARP问题的构造型启发式算法研究相关文档

最新文档

返回顶部