At maritime navigation, building an effective route assumes several difficulties. When the problem area is large, seaway is complex and according to natural reasons it varies in time, strict route building methods may be ineffective because they require too much time. The paper describes a method for building an optimal route for a vessel by utilising parallel genetic algorithm. Descriptions for both the genetic algorithm that builds the result route and the heuristic method that generates a single route are given.