Ship Lock Scheduling Method of Three Gorges Based on Improved Ant Colony and Surplus Rectangle Fill Algorithm

In order to improve the navigation capacity of ship lock of Three Gorges and relieve the backlog of ships, an optimal algorithm for ship lock scheduling is proposed, which integrates improved ant colony algorithm and surplus rectangle fill algorithm. First, the average waiting time of ships and the average utilization rate of lock chamber area is treated as the objective function, the mathematical model of ship lock scheduling problem is constructed. Second, considering the navigation rules of the Three Gorges Dam and the attributes of ships, the concept of ship weight is introduced to determine the ship entry sequence. The global search ability of the algorithm is improved by the pheromone update strategy for the optimal lock chamber arrangement and the path transfer strategy combining adaptive selection and dynamic adjustment. For each iteration the lock chamber arrangement is implemented by the surplus rectangle fill algorithm in order to improve the local search ability. Finally, the actual data of ship lock in the Three Gorges dam is used to verify the performance of the proposed algorithm, and compared with the manual arrangement strategy and CPLEX solution results. The waiting time of the proposed algorithm is reduced by 10.26 % and 2.62%, and utilization rate of ship lock is increased by 8.42 % and 7.31%, respectively. The results show that the proposed algorithm has good performance for ship lock scheduling.