The formation of multiple AUVs in a row during navigation can effectively improve energy efficiency and detection capability. Since it is difficult to assign multiple AUVs to form a row efficiently, the optimal assignment in operations research is innovatively used to solve this problem in this paper. However, due to the limited data processing capability of the AUV and its trajectory being disturbed by the current, the Hungarian method will take a long time to solve the optimal assignment. Therefore, a method of assigning multiple AUVs to form a row efficiently by processing the cost matrix is proposed. First, a cost matrix, consisting of the time cost for each AUV to reach different assigned positions, is generated. Second, the preprocessing and further processing are combined to increase the number of zeros in the generated cost matrix. Third, the space tree method considering the distribution of zeros is used to extract n independent zeros of different rows and different columns, which correspond to the optimal assignment. In order to verify the feasibility and effectiveness of the proposed method, simulations and experiments are performed to assign AUVs to form a row. The optimal assignment solved by the proposed method is more efficient than the Hungarian method in the simulations, and is accurate in the experiments. The above results show that the proposed method is feasible and effective.