The paper presents an extended version of the author’s Evolutionary Sets of Safe Ship Trajectories method. The method plans safe tracks of all ships involved in an encounter including speed reduction maneuvers, if necessary, and taking into account Rule 10 of COLREGS, which specifies ships’ behavior within Traffic Separation Schemes governed by IMO. The paper focuses on the evaluation phase of the evolutionary process and shows how fitness function is designed to compare various possible tracks as well as to assess the quality of a final solution. The impact of the fitness function on the method’s results is illustrated by examples.