带容量限制的弧路径规划问题(CARP)在日常生活中的应用是非常普遍的(比如:城市洒水车路线的规划、垃圾回收车路线的规划等),有效的解决CARP问题并将其投入实际应用对于节约经济成本,提高社会生产效率有着非常重大的意义。而在实际应用中,比较常见的CARP问题都是在标准CARP问题的基础上进行了不同程度地扩展,比如:服务的车辆具有多种容量限制的CARP问题(MVCARP)、车辆具有多个停车场的CARP问题(MDCARP)等。目前,国际上对标准CARP和MVCARP的研究已比较成熟,但对MDCARP的研究还很少。MDCARP问题为NP难题,用普通的精确算法很难求得实用的解,因此有效的解决方法一般都是以启发式算法思想为基础。由于遗传算法具有良好的全局收敛性,并且在求解组合优化问题上有着优良的效果,因此作者在本文中将主要以遗传算法为工具来对MDCARP问题进行研究。在对MDCARP问题的研究中,设计了两种求解方法来解决不同类型的MDCARP问题:对于要求发车场和收车场为同一个车场的MDCARP问题(封闭式MDCARP)采用转化为单车场MVCARP问题的方法进行求解,对于发车场和收车场没有限制的MDCARP问题(开放式MDCARP)采用多个车场同时优化法进行求解。另外,本文对一种特殊的MDCARP问题CLARPIF也提出了一种有效的求解方法。本文对具有多种车型的MDCARP问题(包括封闭式MDCARP和开放式MDCARP,及一种特殊的MDCARP问题CLARPIF)进行了研究,其主要贡献有如下几个方面:①在对标准CARP问题和MVCARP问题的数学模型进行研究和分析的基础上,确定了封闭式MDCARP问题所采用的数学模型,并提出了开放式MDCARP问题的数学模型。②对于封闭式MDCARP问题,首先通过服务弧到车场的归并将MDCARP问题转化为多个单车场MVCARP问题,然后用已有的求解单车场MVCARP问题的HEGA算法进行求解,并在求解过程中,采用模拟退火算法对各个车场的边界弧进行动态调整,从而形成了求解封闭式MDCARP问题的HGAC算法。③对于开放式MDCARP问题,采用多个车场同时优化的方法,对HEGA算法的种群结构、局部搜索策略进行较大改进,并增加了保证车辆服务连续性措施,从而构造了求解开放式MDCARP问题的HGAO算法。④为MDCARP问题的研究提供了四组不同规模的测试数据集,在这四组数据集上分别对本文提出的求解封闭式MDCARP问题的HGAC算法和开放式MDCARP问题的HGAO算法进行了有效性测试,取得了良好的效果。⑤对于一种特殊的MDCARP问题CLARPIF进行了研究,基于已有HEGA算法设计了解决CLARPIF问题的HGAIF算法。在两个国际标准测试集上对该算法的性能与VNS算法等国际上已有算法进行对比测试,验证了该算法的有效性。本文研究的主要目的在于解决应用中常见的MDCARP问题,对于此问题,以洒水车路线规划为应用背景,并考虑了各种复杂的交通限制条件,因而具有一定的适用价值。另外,对于一类特殊的MDCARP问题CLARPIF以垃圾回收车路线规划为应用背景,没有考虑复杂的交通限制条件,与实际应用还有一定距离。