三峡工程两坝联合通航调度的混合模拟退火算法 - 控制理论与应用.pdf

25 4 Vol. 25 No. 4 2008 8 Control Theory Applications Aug. 2008 :2008 , , (1. , 430074; 2. , 430074) : 5, , . , , NP-hard, , , , (DFS), Metropolis. . . : ; ; ; : TP18 : A Hybrid simulated annealing algorithm on navigation co-scheduling to the two dams of the three gorges project ZHANG Xiao-pan , QI Huan , YUAN Xiao-hui (1. Institute of System Engineering, Huazhong University of Science and Technology, Wuhan Hubei 430074, China; 2. School of Hydropower and Information Engineering, Huazhong University of Science and Technology, Wuhan Hubei 430074, China) Abstract: A mixed-integer nonlinear programming model is proposed to improve the transportation capacity of the 5 locks in the Three Gorges Dam and the Gezhouba Dam. Since the model is a large scale and NP-hard combinational optimization problem in the real navigation environment, a hybrid simulated annealing algorithm is employed to search the suboptimal solution composed of a lockage timetable and a ship scheduling, The search starts by trimming the existing lockage timetable based on heuristic rules; the result is then used to compute the ship scheduling by the depth-first-search (DFS) algorithm. The obtained solution is finally updated by the Metropolis rule. The experimental test in real naviga- tion conditions shows that the algorithm is more desirable than the original heuristic approach. This algorithm has been successfully put in the real navigation co-scheduling system for operation.