● 摘要
合理利用和调度水资源，不仅是社会发展的重大需要，更是国民经济发展亟待解决的问题，这已成为世界各国关注的难点和热点问题。修建大型水利工程能够有效地对水资源进行合理调节和配置，满足人民生活和生产的需要。随着物流运输的快速发展，车辆路径问题越来越受到企业和行业的重视，也一直是国际学术界研究的热点。中国国家发改委和葛洲坝集团针对大型水利工程的场地布置、车辆调度和运输方案等问题进行了专门立项研究。本论文以发改委和葛洲坝集团的重大项目为基础，利用计算机仿真、运筹学和启发式算法等技术或方法，将大型水利工程与车辆路径问题相结合，对车辆路径问题和最短路径问题进行了深入的研究，形成了科学、合理的车辆行驶方案，保证了工程的顺利开展，并达到了节约工程施工成本、缩短工程建设工期等目的。论文以大型水利工程中车辆路径问题和最短路径问题为研究对象，以对其进行科学合理的组织管理为研究目标，并在综合分析其特点的基础上，研究了周期性带时间窗的车辆路径问题、多车场多车型车辆路径问题、动态车辆路径问题以及基于复杂交通网络的最短路径问题等，并讨论了解决这些问题的相关启发式算法。主要研究成果归纳如下：(1) 提出了解决带时间窗周期性车辆路径问题的基于模式匹配的混合遗传算法。将大型水利工程与车辆路径问题相结合，研究了带时间窗周期性车辆路径问题。在分析PVRPTW特点的基础上，构建其图论模型和数学模型，提出了基于模式匹配的混合遗传算法解决PVRPTW问题。这种方法是基于种群的混合启发式算法，它将基于集合的邻域搜索与种群进化机制的遗传算法相结合，以提高解的质量。混合算法在基于种群的搜索能力和基于邻域的搜索空间上提供了方法，该算法在搜索空间寻找可行解的能力也有一定的改进。(2) 提出了解决多车场多车型车辆路径问题的改进的变邻域搜索算法。综合分析了多车场多车型带时间窗车辆路径问题特点，构建了图论模型和数学模型，提出了改进的变邻域搜索算法解决改问题，并对变邻域搜索算法的适应度函数、初始可行解、抖动过程、局部搜索等方面均做了改进。其中，在抖动过程中引入插入和交换两种邻域结构来实现抖动操作，局部搜索中用2-opt和Or-opt联合作为局部搜索算子。改进后的算法在局部最优解和全局最优解方面都取得了较好的收敛效果。(3) 提出了求解动态车辆路径问题的基于爬山算法的混合粒子群算法。研究了动态环境下动态需求的带时间窗的车辆路径问题问题。从实际应用需求出发，综合考虑车辆、客户、路况等方面存在的不确定因素，从全局静态和局部动态的角度对DVRPTW进行全面地讨论，建立了考虑实时交通信息和服务水平，满足车辆、路网容量、车场运作成本的数学模型；提出了基于爬山算法的混合粒子群算法求解大型水利工程的动态车辆路径问题，并通过仿真实验验证模型和算法的正确性。(4) 提出了求解复杂网络的最短路径问题的改进的蚁群算法。在分析大型水利工程施工系统构成的基础上，重点研究了物料运输问题。构建了动态复杂网络和土石方平衡的联合优化模型，采用全局和局部信息素更新的方法改进了蚁群算法，并提出了基于改进的蚁群算法求解大型水利工程复杂网络的最短路径问题。改进后的蚁群算法在求解最优化、求解时间和收敛性上都得到了不同程度的提高。(5) 构建了大型水利工程车辆路径决策管理系统。将提出的解决大型水利工程的模型与算法和实际的工程项目相结合，进行了案例研究，并构建了大型水利工程车辆路径决策系统。以某大型水利工程的实际施工为例，研究了车辆路径决策系统的结构、功能，并利用计算机仿真技术，实现了路径决策系统；给出了车辆调度、道路规划以及工程优化的最佳方案。该系统为施工单位、决策管理部门以及一线的工作人员提供了技术保障和智力支持。