三峡工程两坝联合通航调度的混合模拟退火算法

对三峡大坝和葛洲坝的一共5座船闸进行统一的船舶通航调度管理,是提高长江三峡水域航运能力的关键,然而其优化调度算法还缺乏必要的研究.本文首先提出了该问题的混合整数非线性规划模型,在实际通航调度环境中,该模型属于强NP-hard复杂度的大规模组合优化问题,因此设计了一种混合模拟退火算法来搜索次优化调度方案,该算法将解分解为闸次时间表和船舶调度计划两部分,在搜索过程中用启发式规则对闸次时日表进行调整,然后用深度优先搜索(DFS)算法根据闸次时间表求解船舶调度计划,最后根据Metropolis规则对当前解进行更新.针对实际通航数据的测试结果表明其优化效果明显优于原有的启发式算法.目前该算法已经成功地应用于实际的两坝联合通航调度系统中.

Hybrid simulated annealing algorithm on navigation co-scheduling to the two dams of the three gorges project

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.