This study proposes a method to determine the optimal number of information exchange messages in the Distributed Local Search Algorithm for ship collision avoidance. The cost of determining a ship’s movement is defined as the sum of the collision risk between ships and the cost of reaching the destination. This total cost is used to set the maximum allowable cost, which in turn defines the upper limit for message exchanges. In the experiments, the number of ships varied from 2 to 20, and changes in the maximum cost and the number of message exchanges were recorded. The number of message exchanges was capped at 5 in all cases. Experimental results using AIS data demonstrated that an upper limit of 25 message exchanges successfully ensured collision avoidance for 5 ships, while an upper limit of 50 exchanges was effective for 10 ships.