考虑多人相互影响的舰船通道最短路径规划

摘要

Path planning in ship channel network with consideration of mutual influence between persons can be taken as a shortest path problem in time-dependent network. Travel times of each crew member in all sections must be calculated to get the shortest path. Global dynamic optimal path algorithm together with genetic section time algorithm is developed. Effectiveness of the proposed method is demonstrated with the help of the theory of the least time path in the time-dependent network.%将时间维引入既定舰船通道网络，把考虑多人相互影响的动态最优路径规划问题转化为时间依赖网络中的最优路径搜索问题。首先，论文的算法为所有人员随机生成走行路径，为了预测网络中的弧（路段）的走行时间，按人员速度从慢到快的顺序依次计算并记录人员到达路径中的各路段首节点的时刻，先记录到的人员将成为后记录到的人员的动态障碍。然后，将遗传算法与网络中弧的走行时间预测方法相结合，借助遗传算法的个体多样性天然地解决了人员走行任意性问题，因而获得了全局动态最优路径算法，并仿真计算了两人以及三人的最短时间路径；经与不考虑人员间相互影响时获得的最优路径相比较，论文的算法获得了人员遇到障碍时（或跟行或绕行）的最优走行路径。最后，借助时间依赖网络中的最优路径充要条件定理，说明了算法的有效性。