【作者】 肖恒辉；

【导师】 齐欢；

【作者基本信息】 华中科技大学 ， 系统分析与集成， 2008， 博士

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

【Abstract】 With the large-scale and complexity of systems increasing, the large-scale complex scheduling has become one of the hotest problems. Based on the background of the project on the co-scheduling systems engineering of the the Three Gorges Dam and the Gezhouba dam, the network scheduling with the uncertainty is discussed and the methods of modeling and optimization for these networks are studied.As the Golden Channel’s gorge of the Yangtze River, the Three Gorges reach from MiaoHe to ZhongShuiMen is 59 kilometers, where is the location of the hinge of the Three Gorges Dam and the Gezhouba dam. In order to improve the navigation capability for the establishment of the double-line five-grade ship locks of the Three Gorges Dam and the three one-step ship locks of the Gezhouba Dam as one whole framework, the co-scheduling of the Three Gorges Dam and the Gezhouba dam is implemented for all the ships to pass the dams expeditely. Effective navigation on the Golden Channel’s gorge is bound to be of great benefit to the Yangtze River economically. According to the work on the scheduling problems and the experience from the administrative bureau, the more effective models and methods are presented, so as to offer the new research and methods for the scheduling of the transportation on the highway, railway, and voyage.In this dissertation, in order to make the co-scheduling as efficient as possibly and provide the design and betterment of the co-scheduling with the theoretical approaches, my research is foused on the mathematic model of co-scheduling, the strategies of co-scheduling, the rolling interval scheduling under uncertainty, arrangement outside of ship locks and the adjustment for scheduling.The main research work lies in five aspects as follows.(1) Navigation co-scheduling system is studied, and the mathematical model is set up with the definition of objective function and the corresponding restrictive conditions, and the mathematic model of co-scheduling is described as a multi-objective non-linear programming problem. Solving the Three Gorges Dam and the Gezhouba Dam co-scheduling model is based on the timetable sequence deduced from the ship sequence, in this sense, this is a scheduling problem of the time table from time aspect. The ship needs to be arranged into the two-dimensional space(arrange ships) in accordance with the timetable of the sequence (the arrangement answer includes the location information of the ships in the ship lock), that is, a bin packing problem from space aspect. The two problems are coupled as a NP-hard combinatorial optimization problem, and the actual shipping scheduling system variables in the structure is complex and precise, and optimization algorithm is unrealistic. Therefore, in view of the scheduling model objectives and constraints, the progressive optimality algorithm is designed, which is fit for the multi-stage decision-making for a method of using multi-cycle iterative optimization strategy with multi-constraint problem.(2) The best strategy is the centralized scheduling coupled with distributed scheduling. From the distribution of the five dams, they build a network. The nodes of the network are linked by the ship flow, and are bound respectively by the location of the dams. There is 38 kilometers between two dams, distributed scheduling is accepted considering the long distance between the two dams, and it is close to the scheduling at spot. Distributed scheduling is convenient to make the navigation capability maximal, and the shortcoming is that the interlinkage between the two dams is problematical to make the ships overstocked between dams. Centralized scheduling is adopted considering the short distance between the two dams, that is the united scheduling for all ship locks. The advantage of the centralized scheduling is good to the interlinkage between the two dams, and it is lack of the maximal navigation capability because of the restricted dam. By the comparison analysis of the two strategies, based on full analysis of Three Gorges-Gezhouba dam’s actual needs, the best co-scheduling of the Three Gorges Dam and the Gezhouba Dam with the area buffer and the time punishment is introduced.(3) It is chaos for ships to pass the dams by by the small data sets method in chaotic time series analyzing, predicting interval is obtained to keep the scheduling plan precise, according to the method of the the rolling scheduling with the appropriate rolling interval, the rolling interval scheduling which can satisfy the spot scheduling better is presented. By means of experiment’s analysis, illustrative results show that the the rolling interval scheduling is feasible and the the scheduling plan deduced from the algorithm is quite close to the schema in practice. The rolling interval scheduling can make the more accurate scheduling plan to instruct the spot scheduling, and can significantly improve the throughput of the ship locks.(4) With focus on the whole process of the co-scheduling to optimize the ship scheduling, a new concept of the arrangement outside of the ship locks and the adjustment for scheduling are introduced. Based on the analysis of the operation process of ships’entry into ship locks, the mathematic model with the objectives of the safety and the time for entry into ship locks is established, followed with a corresponding heuristic solution algorithm, which can heuristically educe the arrangement approach for the ships outside of the ship locks through the objectives and constraints in the model. During the spot scheduling, the adjustment for scheduling is used to optimize and meet the emergency, and it is the arrangement inside compared with the arrangement outside. By means of experiment’s analysis, illustrative results show that the arrangement outside of the ship locks and the adjustment for scheduling are feasible. Considering the time for ships’entry into ship locks and the principle of safety , two strategies can increase the operation times of ship locks, and can make the efficient scheme for ship scheduling.At last, the navigation co-scheduling system is designed and developed by the author, involving the navigation co-scheduling module and navigation information management module. Based on the mathematic model, the strategies of co-scheduling, the rolling interval scheduling under uncertainty, arrangement outside of ship locks and adjustment, the co-scheduling system has worked for two years. The results show that it is general and adaptive for co-scheduling system to make the practice and theory combined. The research on the co-scheduling systems engineering of the the Three Gorges Dam and the Gezhouba dam can solve the problems in practice, at the same time, can offer the certain methods of the network scheduling with the uncertainty.更多还原