《三峡工程两坝联合通航调度算法研究》由会员分享，可在线阅读，更多相关《三峡工程两坝联合通航调度算法研究（115页珍藏版）》请在金锄头文库上搜索。
1、华中科技大学 博士学位论文 三峡工程两坝联合通航调度算法研究 姓名：张晓盼 申请学位级别：博士 专业：系统工程 指导教师：齐欢 20070601 I 摘摘 要要 三峡葛洲坝联合通航调度系统是长江三峡河段上特有的一种内河航运调度系 统，三峡工程的修建大大改善了长江中上游航道的通航条件，但不可否认的是，随 着长江中上游航运的日益繁忙，三峡大坝和葛洲坝必将成为这一水域的通航瓶颈， “十一五”期间，交通部计划投资一百五十亿元人民币实施的长江黄金水道建设中， 重点推进的六大工程中就包括三峡过坝运输扩能（其他五项工程分别是航道治理、 港口建设、船型标准化、水运保障及干支联动） 。由于三峡大坝和下游的葛洲坝
2、相距 不到 40 公里（大约为普通船只 2-4 小时左右的航程） ，两者构成了一个有机的整体， 因此要充分发挥该水域的航运能力就必须对两座大坝的通航设施（包括三峡大坝的 双线五级船闸和目前尚未投入使用的升船机，以及葛洲坝的三线单级船闸）和所有 过坝船只实行统一的通航调度管理，针对船舶过坝的联合通航调度是这一管理模式 中的主要环节，而设计稳定高效的调度算法是实现联合通航调度稳定高效的关键。 然而由于三峡工程的独特性， 这一联合通航调度问题在理论和方法上都缺乏必要 的研究，针对这一现状本文首先通过借鉴受到加工车间调度问题的研究成果，提出 了联合通航调度问题的非线性混合整数规划模型，这一模型主要基于
3、联合通航调度 问题与柔性制造调度问题的相似性，从柔性制造调度问题的混合整数规划模型演化 而来，同时结合二维 packing 模型描述了船舶在闸室中停泊位置的优化编排问题，该 模型是一种强 NP-hard 复杂度的组合优化问题，因此对于大规模的航运调度来说， 可行时间内的精确优化算法是不存在的。 静态环境中的优化能力是对调度算法的基本要求， 为了在可行的计算时间内得到 稳定有效的优化性能，本文提出了一种混合优化算法将针对船舶过坝时间表的优化 计算转化为针对船闸闸次时间表的优化计算。闸次时间表优化模型也是一种混合整 数规划模型，我们提出的混合优化算法是一种具有启发式变换策略的随机局域搜索 算法和模
4、拟退火算法的合成，其中随机局域搜索算法针对整数型优化变量，而模拟 退火算法针对实数型优化变量，基于实际通航数据的测算表明该算法优化性能稳定， II 并且计算速度和优化效果能够满足实际应用的需要。 与上述针对的是全局静态调度问题的混合优化算法相比， 更具有实用价值的是复 杂环境中的动态调度算法。 在加工制造领域， 滚动时域方法 （Rolling Horizon Procedure, RHP）在 Job Shop 问题的单机以及并行多机系统动态调度中取得了非常好的效果， 本文借鉴这一思路，设计了基于闸次时间表优化的联合通航调度滚动时域算法，在 滚动时段内采用具有启发式剪枝策略的分枝定界算法搜索最优
5、解。静态调度模型下 的测试结果表明该算法的全局优化能力和计算速度均优于全局混合优化算法。而在 实际的动态调度环境中，由于系统参数和船舶航行的随机性，滚动时段内的短期计 划往往只有部分能够准确执行，而当实际环境与预测值相差过大时就需要进行调度 调整或者重调度，与 Job Shop 中的单机和并行多机系统不同的是，联合通航调度系 统是一种双服务台（大坝）的串联结构，各服务台面临的输入输出环境是不同的， 往往并不需要同时进行调度调整或者重调度，因此我们设计了一种异步滚动时域调 度策略以提高滚动时域方法的灵活性并降低重调度的计算量。 最后本文介绍了联合通航调度算法在实际的航运管理系统中的应用， 现阶段
6、调度 算法主要用于长时段内的调度计划编制问题，从更大的时间跨度来看，这也是一种 滚动时域调度，然而由于时域长度过大（通常为 24 小时） ，该问题以及具有了全局 静态优化的性质，同时在实际系统中需要考虑的优化目标更加复杂，我们采取了利 用较短时段内的滚动时域算法得到调度计划初值，然后运用全局混合优化算法进一 步改进调度计划的方法。目前这一算法已经实际应用于长江三峡通航管理局的“三 峡葛洲坝水利枢纽通航调度系统”中，并取得了较好的效果，得到了调度专家们 的一致认可。 关键词关键词: 三峡工程，联合通航调度，滚动时域调度，混合整数规划，混合优化算法 III Abstract The navigat
7、ion co-scheduling system of the Three Gorges Dam and the Gezhouba Dam is a particular navigation scheduling system on the Three Gorges reach of the Yangtze River. The traffic on the middle and upper reaches of the Yangtze River has became busy more and more when the navigation condition has been imp
8、roved by The Three Gorges Project remarkably. So the enhancement of transportation capacity of the Three Gorges Dam has been included in the six key projects on constructing the golden-waterway of the Yangtze River, which are proposed to get 15 billion RMB investement from the Ministry of Communicat
9、ions. But because the distance between the Three Gorges Dam and the downstream Gezhouba Dam is less than 40km, its necessary to make collaborative scheduling for all locks, including two five-stair locks in the Three Gorges Dam and three single-stair locks in the Gezhouba Dam, and passage ships of b
10、oth of the two dams to improve the navigation capacity. This collaborative scheduling is called navigation co-scheduling and the feasible and effective algorithms for it is the main objective of this thesis. Because of the uniqueness of the Three Gorges Project, the navigation co-scheduling of the t
11、wo dams is lack of research both theoretically and methodologically. First of all, a mixed-integer nonlinear program (MINLP) model is proposed to describe the problem, which is evolved from the mixed-integer model of the job shop problem based on the similarity of these two scheduling problem by com
12、bining a 2D packing model for the berth problem in lock chamber. Its a strong NP-hard combinational optimization model, so there isnt accurate algorithm with reasonable computation for the huge scale navigation co-scheduling. Thus a hybrid approximate optimization algorithm is designed for the stati
13、c co-scheduling, which converts the optimization on the timetable of ships to the IV optimization on the timetable of locks. The optimization model on the timetable of locks is also a mixed-integer program model but has less variables and simpler feasible domain than the above MINLP model. Our algor
14、ithm is a hybrid of local search and simulated annealing with heuristic transform strategy, where the local search deals with the integer variables and the simulated annealing deals with the real variables. The result of test under real navigation data shows that the algorithm has good and feasible
15、effect and reasonable computation. Comparing with the static co-scheduling algorithm, the dynamic co-scheduling algorithm is thought to be more practical. Because the Rolling Horizon Procedure (RHP) has been proved to have better global optimization capacity than traditional dispatch-rule based algo
16、rithms on the dynamic job shop scheduling in the single machine or parallel machines category, we attempt to make use of RHP on the dynamic navigation co-scheduling. Our RHP method is still based on the lock timetable model and use a kind of approximate branch and bound algorithm to deal with the optimization within each rolling horizon. The tests on static co-scheduling show that the RHP method has better global optimization capacity than above hybrid algorithm. On dynamic co-scheduling be
