多目标遗传算法在船闸调度中的应用

毛 星，胡少英，徐希涛 ，李宁宁

(南瑞集团(国网电力科学研究院)有限公司,江苏 南京 211000)

0 引 言

作为一个河网密度极大，最大值达12.7 km/km2、海岸线达3.2万公里的国家，水运是我国最主要的货运手段之一。当前我国水路运输不断发展，长江水运通道已超过密西西比河和莱茵河，成为世界上最繁忙、运量最大的内河运输通道。但是目前我国的货运周转量承担值只有49.77%，与发达国家的75%相比，相差悬殊。究其原因，船闸通航能力成为制约水路运输效率的最突出问题[1-2]，因此解决船闸调度过程中船舶待闸时间长、闸室利用率低等问题是提高船闸通航能力、增加航运周转量的关键[3]。

目前内河航运主要采用人工编排调度计划的调度方式，人工排船时通常选择减少单次过闸船数、降低闸室利用率的方式来缓解过闸等待时间长的问题，调度过程慢、调度水平低、缺乏科学性，而且人工排档方法太过依赖人为决策，对决策者个人的经验、知识、能力等要求很高，决策的科学性较低。因此，提高船闸通航能力的核心是采用科学有效的调度方法[4-6]。

闸室编排根据船舶报到时间和优先级别，将船舶排入闸室内，可以用二维空间上的装箱模型来描述[7-8]，是一个典型的NP完全问题[9]。目前以二维装箱模型解决船闸排档问题常见的方法有快速编排算法、贪婪算法、二维优化编排启发式算法等[10-14]，这些算法在大多数情况下能取得较高的闸室利用率，但是在编排过程中只注重局部最优选择，不进行回溯处理，很容易错过真正的最优解[15]。……