【作者】 张晓盼；

【导师】 齐欢；

【作者基本信息】 华中科技大学 ， 系统工程， 2007， 博士

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

【Abstract】 The navigation 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 improved 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 Communications. But because the distance between the Three Gorges Dam and the downstream Gezhouba Dam is less than 40km, it’s 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 both 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 two 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 combining a 2D packing model for the berth problem in lock chamber. It’s a strong NP-hard combinational optimization model, so there isn’t accurate algorithm with reasonable computation for the huge scale navigation co-scheduling.Thus a hybrid approximate optimization algorithm is designed for the static co-scheduling, which converts the optimization on the timetable of ships to the 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 algorithm 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 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 algorithms 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 because of the random of navigation and system status the scheduling in a rolling horizon is usually carried out partly and re-scheduled when the deviation of prediction is too remarkable from the real environment. In the single machine or parallel machines category of job shop scheduling, the re-scheduling can occur in all machines synchronously since there is only one service station. But in the navigation co-scheduling, there are multi service stations within different input and output environment, so we designed an asynchronous policy to improve the flexibility and decrease the computation when re-scheduling.At the end of the thesis the real navigation management system involving the navigation co-scheduling sub-system and navigation information management sub-system is introduced. In the navigation co-scheduling sub-system, the optimization algorithm is used obtaining the scheduling plan within a long period. The long period scheduling have both characteristics of RHP and global static scheduling but with multi optimization objectives. As the RHP method can only deal with the problems whose objectives can be separated by the scheduling unit, we combine the RHP and hybrid algorithm for the long period multi objectives optimal co-scheduling. At present the combinational algorithm has been put into use of the real system and obtained comparatively good effect which is recognized by the navigation scheduling experts.更多还原