三峡—葛洲坝联合通航调度系统是长江三峡河段上特有的一种内河航运调度系统,三峡工程的修建大大改善了长江中上游航道的通航条件,但不可否认的是,随着长江中上游航运的日益繁忙,三峡大坝和葛洲坝必将成为这一水域的通航瓶颈,“十一五”期间,交通部计划投资一百五十亿元人民币实施的长江黄金水道建设中,重点推进的六大工程中就包括三峡过坝运输扩能(其他五项工程分别是航道治理、港口建设、船型标准化、水运保障及干支联动)。由于三峡大坝和下游的葛洲坝相距不到40公里(大约为普通船只2-4小时左右的航程),两者构成了一个有机的整体,因此要充分发挥该水域的航运能力就必须对两座大坝的通航设施(包括三峡大坝的双线五级船闸和目前尚未投入使用的升船机,以及葛洲坝的三线单级船闸)和所有过坝船只实行统一的通航调度管理,针对船舶过坝的联合通航调度是这一管理模式中的主要环节,而设计稳定高效的调度算法是实现联合通航调度稳定高效的关键。然而由于三峡工程的独特性,这一联合通航调度问题在理论和方法上都缺乏必要的研究,针对这一现状本文首先通过借鉴受到加工车间调度问题的研究成果,提出了联合通航调度问题的非线性混合整数规划模型,这一模型主要基于联合通航调度问题与柔性制造调度问题的相似性,从柔性制造调度问题的混合整数规划模型演化而来,同时结合二维packing模型描述了船舶在闸室中停泊位置的优化编排问题,该模型是一种强NP-hard复杂度的组合优化问题,因此对于大规模的航运调度来说,可行时间内的精确优化算法是不存在的。静态环境中的优化能力是对调度算法的基本要求,为了在可行的计算时间内得到稳定有效的优化性能,本文提出了一种混合优化算法将针对船舶过坝时间表的优化计算转化为针对船闸闸次时间表的优化计算。闸次时间表优化模型也是一种混合整数规划模型,我们提出的混合优化算法是一种具有启发式变换策略的随机局域搜索算法和模拟退火算法的合成,其中随机局域搜索算法针对整数型优化变量,而模拟退火算法针对实数型优化变量,基于实际通航数据的测算表明该算法优化性能稳定,并且计算速度和优化效果能够满足实际应用的需要。与上述针对的是全局静态调度问题的混合优化算法相比,更具有实用价值的是复杂环境中的动态调度算法。在加工制造领域,滚动时域方法(Rolling Horizon Procedure, RHP)在Job Shop问题的单机以及并行多机系统动态调度中取得了非常好的效果,本文借鉴这一思路,设计了基于闸次时间表优化的联合通航调度滚动时域算法,在滚动时段内采用具有启发式剪枝策略的分枝定界算法搜索最优解。静态调度模型下的测试结果表明该算法的全局优化能力和计算速度均优于全局混合优化算法。而在实际的动态调度环境中,由于系统参数和船舶航行的随机性,滚动时段内的短期计划往往只有部分能够准确执行,而当实际环境与预测值相差过大时就需要进行调度调整或者重调度,与Job Shop中的单机和并行多机系统不同的是,联合通航调度系统是一种双服务台(大坝)的串联结构,各服务台面临的输入输出环境是不同的,往往并不需要同时进行调度调整或者重调度,因此我们设计了一种异步滚动时域调度策略以提高滚动时域方法的灵活性并降低重调度的计算量。最后本文介绍了联合通航调度算法在实际的航运管理系统中的应用,现阶段调度算法主要用于长时段内的调度计划编制问题,从更大的时间跨度来看,这也是一种滚动时域调度,然而由于时域长度过大(通常为24小时),该问题以及具有了全局静态优化的性质,同时在实际系统中需要考虑的优化目标更加复杂,我们采取了利用较短时段内的滚动时域算法得到调度计划初值,然后运用全局混合优化算法进一步改进调度计划的方法。目前这一算法已经实际应用于长江三峡通航管理局的“三峡—葛洲坝水利枢纽通航调度系统”中,并取得了较好的效果,得到了调度专家们的一致认可。