基于图论的舰船通道路线优化

Optimization of Passage Route in Ship Based on Graph Theory

舰船通道长期以来主要依据规范和工程经验设计,设计质量很大程度受设计师能力的影响。文章讨论图论在舰船通道路线优化设计中的应用。首先从图论的原理出发,阐述舰船通道路线优化设计的依据,参考人群流量理论提出路权的计算方法;以船舶通道网络为研究对象,以行程时间最短为优化目标,利用经典的Floyd算法确定最短路径。对某舰艇两层甲板的通道网络实例进行优化并编程实现算法,对优化结果进行分析并提出进一步开展优化的设想。

The passage design of a ship was always based on regulation and engineering experience, and the quality of design ahnost relied on the ability of a designer. The application of graph theory in the optimization of route selection was discussed. According to the graph theory, the theory basis of the route selection optimization and the method of calculating the weight of passage with flow theory were presented. Then taking the passage system as the research ohject by optimization, we found the shortest path based on the Floyd algorithm, and the method was applied to optimize the plan of route selection on two decks of a ship and the algorithm was programmed. The result of optimization was discussed and the expectation of further work was also considered.