论文部分内容阅读
容量约束弧路径问题(Capacitated Arc Routing Problem,CARP)产生于交通运输服务系统,是弧路径问题(Arc Routing Problem,ARP)的一种特殊情况,因其可应用于如城市垃圾回收、街道清扫、邮件投递、结冰路面撒盐及路面维护等实际问题,故近年来得到了广泛的研究。本文主要研究此问题的一种新的扩展类型,即带有收益的无向容量约束弧路径问题(UCARPP)。此问题与传统的弧路径问题最大的区别就是不必对网络中所有的客户弧进行服务,每条客户弧有收益、遍历时间、需求三个属性值,服务车队在满足容量及时间限制的前提下,对部分客户弧进行服务,目标使总收益值最大。该类问题是NP-hard问题,传统的算法如精确算法、下界法都因自身缺陷而不能很好地解决这类问题,而变邻域搜索算法(VNS)作为一种元启发式算法因其内在的简单高效、通用性强等优点有希望很好地解决UCARPP问题。 本文以UCARPP为研究对象,在广泛查阅国内外文献的基础上,深入研究该问题的求解方法,提出了求解UCARPP问题的分割启发式算法和变邻域搜索算法,为CARP问题推广形式的求解提供了借鉴与参考,主要研究工作和成果如下: 1、对CARP问题及其推广形式进行了描述,并引入了带有收益的无向容量约束弧路径问题(UCARPP),并给出该问题的数学模型,在归纳总结已有方法的基础上,设计相应算法解决该问题。 2、本文根据UCARPP问题的特性,提出一种分割启发式算法来获得初始解,加快程序运行速度,同时加大算法寻优能力。 3、运用六种邻域结构进行广域搜索,其中针对邻域结构的选择设计了旋轮法。数值试验结果表明,分割算法提高了算法的效率,六种邻域结构的设计避免了早 期陷入局部最优,该算法能有效解决一定规模的UCARPP问题,为实际应用奠定了基础。