多车场车辆弧路径问题(MDARP:Multiple Depot Arc Routing Problem)与我们熟悉的车辆路径问题(VRP)的最大区别就在于:VRP中的需要进行服务的是一系列点,而MDARP中需要进行服务的则是一系列边,且有数个车场,车辆可以从每个车场出发最终返回到原车场。目前,对车辆路径问题的研究主要是针对VRP,对于多车场的VRP(Multiple Depot Vehicle Routing Problem:MDVRP)的研究也取得了一定的成果,但是对于大规模的MDARP研究,据所查文献资料来看,目前采用进化计算方法对大规模的MDARP研究还没有相关报导,而只有少量文献对ARP的研究。MDARP在我们的日常生活中也有一些应用的实例,如道路清洁,垃圾回收,输电线路检测等,我们可以借鉴ARP和MDVRP的研究方法对MDARP的进行研究,以解决一些实际问题。对于MDARP问题的研究,本文做的主要工作和获得的研究成果如下:①本文采用双层遗传算法对MDARP进行求解,利用了遗传算法的生物进化机制,对问题的解进行全局搜索,从而寻求满意解。生物学已经证明,“近亲繁殖”不利于群体的健康发展,在同一种群的不同群体之间,交换越深入,后代会越优秀。因此,在双层遗传算法中,除了各子种群内部个体(内层遗传算子)之间进行遗传操作外,我们在各个父种群间(外层遗传算子)也进行类似的遗传操作,以加强群体间的信息交换,改善寻优能力。②对MDARP的数学模型进行探讨,借鉴MDVRP的数学模型构造了MDARP的数学模型,并在模型计算的基础上,针对传统遗传算法编码表达能力不够直观的缺点,本文对染色体编码机制和种群结构进行了改进,设计出了既反映多车场服务组合关系又能反映路径信息的新的编码方式——“双层整数编码方式”,其中外层遗传算法用来确定车场与服务弧的优化组合,内层遗传算法用来最终求解所有的车辆路径,不仅提高了编码方式的表达能力,而且编码码串长度显著下降,避免二进制编码产生的不可行解,提高了选择计算能力。③借鉴整数编码遗传交叉算子在函数求极值进化算子设计方面的经验,结合本文的遗传算子特点,在内层遗传算子进化过程中引入了初始种群生成策略和多样性染色体交叉、增强型染色体邻域搜索等遗传算子进化策略,克服了由于传统遗传算法的随机性所带来的早熟收敛、稳定性差等缺点,使算法达到了良好的收敛性与稳定性。④针对MDARP问题,结合本文提出的双层遗传算法,以某城区洒水车行驶路线为原型,对不同车场数目、不同服务边数量的几种情形进行实验测试,得到了合理的科学的车辆安排方案,比现行的车辆安排方案节省总路程20%以上,并提高了安排效率,验证了本文提出的双层遗传算法的正确性与合理性。基于双层遗传算法的MDARP的研究综合了车辆路径优化领域与遗传算法领域的研究成果,提出具有可扩展性、实时性、稳定性特点的路径优化机制,解决了车场数量和服务对象数量变化车辆安排困难的矛盾,开辟了MDARP的研究新途径。