周期性带容量限制弧路径问题(Periodic Capacitated Arc Routing Problem: PCARP)是当前路径优化系统中比较常见的问题,并且有着很强的应用背景,城市垃圾回收就是其最典型的例子。该问题属于带容量限制弧路径优化问题(CARP)的一个扩展。有效地解决PCARP问题并将其投入实际的应用对于节约经济成本,提高社会生产效率有着非常重大的意义。对CARP的研究在过去20多年中已引起国内外众多专家学者们的重视,并提出了许多富有成效的解决方案,但是总体上看,CARP的研究相对于我们通常所熟悉的VRP研究仍然显得还不够全面,从现有已经发表的一些文献中搜集到的解决CARP问题的方法大多数存在比较大的改进空间。对于应用中比较常见的周期性CARP问题(PCARP),国际上只有极少的专家学者对其进行研究,而国内在该领域的研究几乎处于空白状态。可见,对PCARP进行研究具有很大的发展前景。因此,在本篇论文中作者对基本PCARP和扩展PCARP进行了深入的理论研究,并提出解决这两类问题的算法。根据所查阅的文献来看,大多数都采用启发式算法或线性规划法对PCARP问题进行解决。由于遗传算法具有良好的全局收敛性,并且在求解组合优化问题上有着优良的效果,因此作者在本文中将主要以遗传算法为工具,同时为避免传统遗传算法在求解问题过程中存在的“早熟收敛”、易陷入局部极值点等不足,提出了二次单亲遗传算法与改进MA算法,并通过仿真实验验证了本文所设计算法的性能。本文对PCARP问题研究的主要贡献如下:①在对CARP问题的数学模型进行研究和分析的基础上,提出了周期性CARP问题(PCARP)的数学模型。②本文提出了一种二次单亲遗传算法(second Partheno-Genetic Algorithm:SPGA)对基本PCARP问题进行求解。针对PCARP问题的特殊性,该算法采用了适合PCARP的染色体编码与初始化方法;在染色体重组方面,借鉴了单亲遗传算法(Partheno-Genetic Algorithm:PGA)的思想,并增加了一个重组算子;最后还将基于精英种群的二次遗传思想运用于该算法中,有效地避免了传统遗传算法在解决路径优化问题中存在的“早熟收敛”、易陷入局部极值点等不足。③本文还提出了一种改进MA算法(Improved Memetic Algorithm:IMA)对扩展PCARP问题进行求解。基于扩展PCARP问题的复杂性,该算法采用了适合扩展PCARP问题的PLOX交叉算子;将MA算法中的局部搜索(Local Search:LS)进行简化以提高算法的运行效率;同时,为了得到更好的优化结果,本文改进了MA中的种群初始化方法、选择算子以及适应度函数。④为PCARP问题的研究提供了不同规模的测试数据集。在该数据集上运用本文提出的算法分别对基本PCARP与扩展PCARP问题进行测试,取得了良好的效果。本文研究的主要目的在于解决应用中常见的周期性CARP问题(PCARP),对该问题的探讨与研究不仅可以实现路径划分的合理性,而且有助于提高部门的科学管理水平,具有很大的应用价值。