Abstract: To better plan the ship route in the marine construction waters where lies a great risk for maritime navigation, this paper established a mathematical model with the shortest route length possible as the objective function and non-navigable regional and ship steering angle as the constrained equation route planning, focusing on the specific methods as solutions. To this end, we first split the free navigable area into several convex polygons through link lines by graph theory, then connected their midpoints in the construction waters two by two to form the Maklink route network and, based on this network, used the two-stage optimization method for solution, in which Dijkstra algorithm was used to first find the initial route free of danger and then ant colony algorithm to optimize the route mentioned above so as to get the most desirable one with shortest length and smallest steering angle.

Key words: traffic and transportation engineering, construction waters, route design, Maklink graph, Dijkstra algorithm, ant colony algorithm

摘要： 海上施工水域是船舶在航行中风险较大的区域，为了解决船舶在施工水域中的船舶航线规划问题，建立了以航线总长度最短为目标函数，以不可航行区域和船舶转向角等为约束方程的航线规划数学模型。在建立航线规划的数学模型的基础上，重点研究了模型求解的具体方法。在求解施工水域航线规划的数学模型时，首先利用图论的方法将可自由航行区域通过链接线将其拆分为若干个凸多边形。其次将链接线的中点两两相连，形成海上施工水域中的Maklink航线网络。然后再采用两阶段优化方法求解，第1阶段利用Dijkstra算法求解出能够避开所有危险区域的初始航线；第2阶段利用蚁群算法，对初始航线进行优化。最后通过蚁群算法的优化，求得了航线总长度更短而且转向角更小的最优航线。

关键词: 交通运输工程, 施工水域, 航线设计, Maklink图, Dijkstra算法, 蚁群算法