随着系统规模和复杂程度的不断增加,大规模复杂的调度问题已经成为热门的研究课题,本文以“三峡-葛洲坝水利枢纽通航调度系统工程”项目为工程背景,对具有不确定性的网络调度问题进行了探讨,并对这类调度问题的建模和优化进行了研究。长江三峡河段(庙河至中水门)全长59公里,是三峡-葛洲坝梯级枢纽所在的航道,这是长江“黄金水道”的咽喉部分。三峡-葛洲坝梯级枢纽是一个有机的整体,要充分发挥该水域的航运能力就必须对两坝的通航设施(包括三峡大坝的双线五级船闸和葛洲坝的三线单级船闸)和所有过坝船舶实行统一的通航调度管理。三峡-葛洲坝联合通航调度能有效发挥“黄金水道”咽喉部分的通航能力,这将为我国长江航运带来重大的经济效益。本论文借鉴了调度问题上已有的研究工作和通航部门的调度经验,对具体的系统工程问题提出了全面有效的模型和方法,进而为交通运输中的公路、铁路、航空、航运的调度提供了新的思路和研究方法。为了高效实施两坝联合通航调度,以及为三峡-葛洲坝水利枢纽通航调度系统的设计和改进提供理论依据,文本工作着力于联合通航调度的数学模型、联合通航调度的调度策略、不确定性下的滚动时窗调度、闸外编排和计划调整等问题的研究。本文的主要研究工作如下:(1)研究了联合通航调度系统,建立了数学模型,定义了目标函数和相应的约束条件,本文将联合调度系统的数学模型归结为一个多目标规划问题。求解三峡--葛洲坝两坝联合调度模型就是根据船舶流序列生成时间表序列,从这个意义上看,这是个时间上的scheduling问题。由于船舶需要编排到船闸之中,根据时间表序列对二维空间(船闸闸室)进行排档(排档结果包括船舶在船闸内的位置信息),即空间上的bin packing问题。二者耦合在一起是一个非常复杂的组合优化问题,具有强NP-hard的复杂度,并且在实际的通航调度系统中变量结构相当复杂,因此精确优化算法是不现实的,针对调度模型的目标和约束条件本文采用逐步最优化算法POA(Progressive Optimality Algorithm),它是求解多阶段决策问题的一种方法,采用多层循环迭代寻优的策略,适合于多约束的时间表问题的求解。(2)设计了两坝联合调度最优策略。从船闸的分布来看,五个船闸构成一类网络结构,这类网络系统之间通过船舶流来连接,三峡两线船闸和葛洲坝三个船闸又因地理位置而分别绑定。两坝间距为38公里,距离“不近”也“不远”。从两坝之间距离“不近”来看,调度策略归结可为分坝调度,其特点是两坝分坝调度,其性质接近船闸的现场调度,因此其优点可以尽量发挥两坝的分坝通过能力,其缺点是两坝间衔接不够,通常会使得两坝间船舶大量积压;从两坝之间距离“不远”来看,调度策略归结可为集中调度,即统一编制调度计划,其优点是计划衔接和两坝间衔接合理,其缺点是受通过能力小的一坝约束,使得整体通过能力受到影响。本文正是针对两种调度模式进行比较分析,根据调度实际情况,引入了两坝间的面积缓冲和待闸时间的惩罚,得出了两坝联合调度最优策略—集中协调结合两坝分坝实施的策略。(3)提出了滚动时窗调度。本文通过混沌时间序列分析的小数据量方法对船舶的历史过闸数据进行计算,得出了船舶过闸的混沌特性,根据混沌时间序列的短期预报方法,获得了能保证调度计划准确性的预测时窗范围。借鉴滚动调度的思想,根据混沌时间序列预报提供的参考时窗,设计了滚动时窗调度。通过实验分析,结果表明滚动时窗调度切实可行,合适时窗的滚动调度得出的过闸计划和船舶的实际过闸记录更为接近,因此滚动时窗调度可以生成更准确的调度计划来指导船舶的现场调度。(4)从全流程调度来看,为了优化船舶现场调度,本文提出了闸外编排和计划调整的概念。分析了船舶在进闸调度中的操作流程,考虑了调度的安全性和船舶进闸耗时,建立了闸外编排的数学模型,设计了相应的启发式求解算法,将模型的目标和约束条件通过启发式方法生成船舶在闸外的排序法则。在现场调度中,计划调整的操作主要用来帮助现场船舶调度的优化和应急,相对闸外编排而言,计划调整是一种闸内编排。通过实验表明闸外编排和计划调整切实可行,考虑了船舶进闸时间和安全性原则,可以提高日开闸次数,可以生成安全高效的进闸方案。最后本文介绍了作者作为项目负责人设计和开发的长江三峡通航管理局的“三峡—葛洲坝水利枢纽通航调度系统工程应用软件开发项目(包括系统软件)”。在实际的航运调度管理系统中包括计划编制子系统和信息管理子系统,本章从系统设计和实现的角度给出了系统的体系结构和工程应用。结合了联合通航调度模型、调度策略和算法、滚动时窗调度,以及闸外编排和计划调整这些理论的联合调度系统,经过两年的正式运行检验,表明调度系统及其相应的调度模型与调度策略具有很好的普适性,很好地实现了理论和工程实践相结合。研究三峡—葛洲坝水利枢纽通航调度问题解决了工程应用中的实际问题,也为这类带有不确定性的网络调度问题提供了一定的研究方法。