Research On Algorithms Of Navigation Co-scheduling To The Two Dams Of The Three Gorges Project

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.