Работа посвящена проблеме планирования маршрутов судов на акваториях с интенсивным движением. В условиях насыщенного трафика навигационная безопасность может быть обеспечена только при координации движения судов и реализации ими определенной схемы движения. В статье рассматривается задача планирования маршрута таким образом, чтобы он соответствовал практике судоходства, сложившейся в конкретном районе. Предлагаемый в работе метод планирования маршрутов основан на кластеризации данных о движении судов. Выделенные кластеры представляют собой области в трех- или четырехмерном фазовом пространстве с близкими значениями скоростей и курсов судов, на основе которых формируется граф возможных маршрутов. Особенностью подхода к построению графа является уменьшение числа вершин и ребер за счет моделирования выделенных кластеров охватывающими многоугольниками. В работе показано, что во многих случаях могут использоваться не только вогнутые, но и выпуклые многоугольники, что может дополнительно уменьшить мощность графа. В статье дается метрика расстояния между точками в фазовом пространстве, по которой ведется кластеризация данных, обсуждаются проблемы выбора параметров метрики и алгоритма кластеризации. Отмечается перспективность использования алгоритма DBSCAN. Работа сопровождается расчетами планируемых маршрутов судов на данных реальной акватории (Сангарский пролив). Приводятся результаты кластеризации данных о движении, выделения местоположения кластеров путем построения охватывающих многоугольников, вычисления маршрута судна. Отмечается, что рассматриваемая задача может быть актуальна в контексте перспективного развития автономного судовождения. В этом случае рассчитанный маршрут судна будет соответствовать движению других судов, находившихся на акватории ранее. Это позволит снизить вероятность возникновения опасных ситуаций при движении автономного судна в общем судопотоке.