论文部分内容阅读
带有容量约束的弧路径问题(Capacitated Arc Routing Problem, CARP)产生于交通运输服务系统，是弧路径问题(Arc Routing Problem, ARP)的一种特殊情况，因其可应用于如城市垃圾回收、街道清扫、邮件投递、结冰路面撒盐及路面维护等实际问题，故近年来得到了广泛的研究。本文所研究的有补给点及多装载的容量约束弧路径问题（Capacitated Arc Routing Problem with Refill Points and Multipleloads, CARP-RP-ML），由于考虑具有能多次给服务车(Service Vehicle, SV)提供原料补给的补给车辆(Refill Vehicle, RV),因此属于容量约束弧路径问题的一种推广形式。该类问题是NP-hard问题，传统的算法如精确算法，下界法都因自身缺陷而不能很好地解决这类问题，然而遗传算法作为一种启发式算法因其内在的自学习性、并行性、稳定性等强大优点已被证明能很好地解决容量约束弧路径问题。本文以CARP-RP-ML为研究对象，在广泛查阅国内外文献的基础上，深入研究该问题的求解方法，提出了求解CARP-RP-ML问题的分割启发式算法和遗传算法，为CARP问题推广形式的求解提供了借鉴与参考，主要研究工作和成果如下：1．对CARP问题及其推广形式进行了描述，并引入了有补给点的多装CARP问题(CARP-RP-ML),并给出该问题的数学模型，在归纳总结已有方法的基础上，设计相应算法解决该问题。2．本文根据CARP-RP-ML问题的特性，提出一种分割启发式算法来求得两类车的最短路径及问题的可行解，其中设计的分割算法在满足容量约束的条件下对随机排序的所有需求弧进行分割，以所能达到的补给点为分割点，计算出两个连续补给点间两类不同类型的车辆总费用，记录并保存从车场到当前补给点的最小费用，直到所有需求弧服务完毕。3．基于分割算法，文章利用遗传算法极强的鲁棒性和内在并行机制等优点进一步求得问题的近似最优解。但由于基本遗传算法在求解过程中易限于局部最优，因此采用局部搜索作为其变异算子来进一步扩大搜索空间。数值试验结果表明，遗传算法在该类问题的表现优于所设计的分割启发式算法，说明遗传算法能更有效地求解CARP-RP-ML问题。