带时间约束条件的弧路径问题研究-计算机软件与理论专业论文.docx

重庆大学硕士学位论文中文摘要 重庆大学硕士学位论文 中文摘要 I I 摘 要 带时间约束条件的弧路径问题属于带容量限制弧路径优化问题（CARP）的一个扩 展，在 CARP 的基础上对某些关键路径做出了时间限制，这种扩展有着实际的应用意义， 比如在某些城市主干道中只能在某些时间段内才允许对其进行服务，这就要求在完成全 部路径规划的同时，优先保证这些路径的服务时间。在不能满足每条路径都能按照其约 束时间进行服务时，优先选择具有最小时间延误代价的路径规划方案来进行，具体延误 惩罚代价可以依据路径重要程度不同来判定，总之可以根据我们实际的需求进行约束。 本文以车辆路径问题为研究对象，综合研究了车辆路径问题的各种常用解决方法。 在较大规模的路径问题中主要是以启发式算法为主，其中以遗传算法为研究重点，遗传 算法因其全局的收敛性在解决多目标优化组合问题时有着优良的效果，其具有极强的鲁 棒性和内在的并行计算机制，特别适合于空间中复杂的多极值优化和组合优化问题，但 基本遗传算法在求解过程中容易出现早熟收敛，以及陷入局部最优解的情况。本文通过 构造种群结构，改善进化算子来避免基本遗传算法所带来的缺陷，通过提出实际规划方 案拓展了车辆路径问题和优化组合的研究领域，丰富了路径规划的理论研究成果，为车 辆路径应用领域提供了规划方案设计的借鉴与参考，本文主要的研究工作和研究成果如 下： ① 对 CARP 问题进行了描述并引入了带时间约束的 CARP 问题(CARPTC)，建立其 数学模型，在对各种求解方法的归纳与总结基础上明确了本文以遗传算法为工具，通过 对基本遗传算法的改进，解决带时间约束的 CARP 问题(CARPTC)。 ② 本文根据 CARPTC 问题的特性，提出了一种混合遗传算法 HGA-TC，该算法采 用了适合其问题的染色体编码和种群初始化方法，改进了进化算子、变异算子、适应值 计算以及适应度函数。对于带有时间限制的关键路径，采用在算法中加入时间惩罚函数， 对于没有达到时间要求的规划方案加入惩罚成本，通过遗传算法的优胜劣汰原则来选择 出具有最优适应值和最小惩罚成本的规划方案，以此来满足带有时间约束的路径规划。 ③ 引入了一些复杂限制条件，如单行道、双边同时被服务以及有坡度的路径等， 设计了一种分层遗传算法，其思想先按照某种要求或约束限制条件将整个初始种群划分 为一些子群体，在每个子群体内部分别进行独立的遗传进化操作，在适当的时候进行子 群体之间的信息交换，这样不仅可以使子种群因约束限制的减少而能以更快的效率进化 收敛迭代，还能维持种群的多样性，使其不趋于一致，达到抑制早熟现象的效果，同时 又可因种群规模有所减小而增加算法的效率。 II II ④ 根据真实道路图为 CARPTC 问题建立了数据集，设定一些重要道路的时间约束， 通过道路模拟系统实现了遗传算法对车辆路径的规划，最后得出了良好的解决方案。 本文以洒水车路径规划为研究对象，在此应用的背景中引入一些实际道路限制条 件，做出车辆行驶路线规划方案，对实际应用具有指导意义。通过优化路径方案，可以 减少以前靠人为经验来执行的浪费损耗，对建设资源节约型环境大有裨益。 关键词: 遗传算法，进化算子，服务时间约束 重庆大学硕士学位论文英文摘要 重庆大学硕士学位论文 英文摘要 PAGE PAGE IV ABSTRACT Capacitated Arc Routing Problem (CARP) with time constraints is an extension of Arc Routing Problem. On the basis of some critical paths to make the time limit, this expansion has practical significance, such as some of the main road in the city only in certain period of time for service, which requires all path planning completed in such period, while giving priority to ensuring the service time of these paths. If not each path can meet the time constraints, the minimum time delay of the path planning program should be considered. The specific costs of delay can be made based on the punishme