洒水车作业路线规划问题的研究与应用

洒水车作业路线规划问题的研究与应用

论文摘要

现实生活中,洒水车作业路线方案通常依靠工作经验积累由人工确定,从降低行驶成本、提高工作效率等角度考虑,这种决策方法并不科学。调查分析发现,洒水车的作业路线规划可以抽象为一类特殊的车辆路径问题进行研究,即复杂的弧对象车辆路径问题(Complicated CARP, CCARP)。本文所研究的CCARP相比一般CARP,其复杂性主要体现在:道路的多样性,有双行道、单行道、斜坡路;作业需求的多样性,有双边分别喷洒、双边同时喷洒、仅一边喷洒;根据交通状况考虑车辆的转弯限制因素;车辆载水吨位不一;道路洒水量由具体路况而定。CARP已被证明是一种NP难问题,采用精确算法已很难用于实际大规模CARP的求解,当今的主流趋势是构造运算高效的启发式算法得到其近似最优解。本文采用一种结合小生境技术的改进遗传算法求解洒水车作业路线规划问题,并在有关部门的支持协助下,开发设计了一套洒水车作业路线规划的应用系统。在对课题的研究中,本文所做的主要贡献体现在以下方面:①通过对洒水车作业进行实地调研,采集到丰富而全面的数据,综合考虑了上述多种约束条件,基于一定合理的前提和假设,对一般CARP的模型进行适当改进及扩充,建立了符合本文问题特点的数学模型。②根据建立的数学模型,通过一种改进的遗传算法求解问题。在算法的初始阶段利用一种新颖的染色体构造机制形成种群;同时为避免算法出现常见的“早熟收敛”现象,引入了隔离小生境技术,让多个种群以不同的交叉概率、变异概率,在各自生存环境中独立进化,并对种群建立了一些生存规则,控制种群的存亡;在种群的内部进化中,采用了局部搜索策略,加快种群的优化进程。③设计并开发了一套洒水车作业路线规划的应用系统,可以实现包括道路数据修改、车辆信息设置、道路转弯限制情况设置等功能。在实验环节,利用采集的真实数据进行了大量实验对比测试,找到了算法运行的一组最佳参数配置。最后利用本系统产生的最优方案与人工安排方案对比,在总里程上节省了约15.85%,且运算在较理想的时间范围内完成,充分表明了本文算法的实用性和高效性。本文首次尝试将洒水车的作业路线规划作为CARP的应用背景进行研究,并且取得了不错的研究成果。本文中所开发的应用系统以科学的方式产生作业方案,不但实现了行驶路线的经济性,也一定程度上考虑了路线划分的合理性,有助于提高部门的科学管理水平,具有很大的应用价值和推广潜力。

论文目录

  • 摘要
  • ABSTRACT
  • 1 绪论
  • 1.1 选题背景及意义
  • 1.2 弧对象车辆路径问题(CARP)的研究现状
  • 1.3 论文所做的主要工作
  • 1.4 论文的组织结构
  • 2 弧对象车辆路径问题(CARP)的概要介绍
  • 2.1 弧对象车辆路径问题(CARP)
  • 2.1.1 问题的一般定义
  • 2.1.2 问题的求解复杂性
  • 2.1.3 问题的常见约束及分类
  • 2.2 问题的一般数学模型
  • 2.3 问题求解常用的算法
  • 2.3.1 精确算法
  • 2.3.2 启发式算法
  • 2.3.3 亚启发式算法
  • 3 洒水车作业的调研情况及问题的数学模型
  • 3.1 洒水车作业与CARP 的联系
  • 3.1.1 洒水车作业的一般描述
  • 3.1.2 两者之间存在的联系
  • 3.2 洒水车作业的实地调研情况
  • 3.2.1 多种类型的洒水车辆
  • 3.2.2 多种类型的道路及相关作业约束
  • 3.2.3 转弯限制因素的考虑
  • 3.2.4 道路洒水量的不确定性
  • 3.3 问题的前提和假设
  • 3.4 问题的描述与建模
  • 3.4.1 相关的定义说明
  • 3.4.2 问题的描述
  • 3.4.3 数学模型的建立
  • 4 基于改进遗传算法的洒水车作业路线规划问题求解
  • 4.1 遗传算法概述
  • 4.2 遗传算法的收敛性与小生境技术
  • 4.2.1 遗传算法的收敛性分析
  • 4.2.2 小生境技术的相关介绍
  • 4.2.3 隔离小生境技术对收敛性的作用
  • 4.3 结合隔离小生境技术的改进遗传算法设计
  • 4.3.1 小生境的多种群进化机制和特殊染色体结构
  • 4.3.2 种群及染色体的初始化
  • 4.3.3 种群内的进化
  • 4.3.4 最优种群的解码
  • 4.3.5 路线的合理分配
  • 4.3.6 算法的执行流程
  • 4.4 算法执行的前期准备工作
  • 4.4.1 初始数据的准备
  • 4.4.2 带转弯限制的距离及前驱矩阵计算
  • 5 洒水车作业路线规划系统的设计开发与应用
  • 5.1 系统开发环境介绍
  • 5.1.1 系统开发采用的主要工具
  • 5.1.2 系统的运行环境
  • 5.2 系统总体描述
  • 5.2.1 系统特点
  • 5.2.2 原始数据的组织
  • 5.3 系统功能模块介绍
  • 5.4 算法实验结果及分析
  • 5.4.1 种群规模和进化代数对求解结果的影响
  • 5.4.2 进化期大小对求解结果的影响
  • 5.4.3 局部搜索概率对求解结果的影响
  • 5.5 系统的应用情况说明
  • 6 总结与展望
  • 6.1 研究工作总结
  • 6.2 工作展望
  • 致谢
  • 参考文献
  • 附录
  • 相关论文文献

    标签:;  ;  ;  ;  

    洒水车作业路线规划问题的研究与应用
    下载Doc文档

    猜你喜欢