This paper presents a framework for solving weather routing problems. Such a problem may be considered as: giving the model of ship dynamics and fuel consumption used for route evaluation, GIS data and weather forecast, which allow to check any route leg for safety, providing the set of routes and satisfying some optimality criteria (e.g. minimal routing time, minimal fuel consumption, specified time of arrival and so on). From the authors’ point of view, the searching of such routes may consist of the following steps: 1. Generation of a set of feasible routes, which are “close” to some extent to desired ones; 2. Modification of the feasible routes set by applying some transformations to previously found routes; 3. Fine tuning of route parameters according to search criteria; and 4. Selection of best routes. Several discrete algorithms, proposed for step 1, are compared, so one can chose an appropriate one. Algorithms presented for steps 2 and 3 may be considered as a way of softening the space/time discretization side effects. To compare the efficiency of such algorithms, some common quality measures are presented.