Рассматривается одна из актуальных и ключевых задач транспортной отрасли — задача планирования маршрутов следования транспортных средств. Для многих приложений данная задача может быть описана и формализована как задача коммивояжера (англ. Traveling Salesman Problem, TSP), которая заключается в поиске для коммивояжера оптимального маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В общем случае при планировании таких маршрутов приходится решать множественную задачу коммивояжера (англ. Multiple Traveling Salesman Problem, MTSP), допускающую более одного коммивояжера и более одного депо — пункта их базирования, в котором начинаются и заканчиваются маршруты. MTSP как задача комбинаторной оптимизации относится к классу NP-трудных задач. В настоящей статье излагается эвристический метод ее решения на основе геопространственной кластеризации исходного множества го родов. Сначала рассматривается MTSP с одним депо. Дается двухиндексная математическая формализация данной задачи и излагается метод Миллера—Такера—Землина, сводящий ее к задаче целочисленного линейного программирования. Обсуждаются метаэвристические методы решения MTSP. Рассматривается более сложная задача — MTSP с несколькими депо. Излагается кластерный двухэтапный метод решения данной задачи — метод CFRS ("Cluster First — Route Second"), позволяющий свести ее к семейству MTSP с одним депо. Здесь на первом этапе осуществляется геопространственная кластеризация городов, для которой возможно использовать различные методы кластеризации, включая метод K-средних. На втором этапе для каждого построенного кластера осуществляется выбор депо для его обслуживания и строятся маршруты объезда всех городов данного кластера. Обсуждается методология кластеризации как эффективный инструмент решения MTSP.

Приводится числовой пример авиационной логистики — маршрутизация полетов группы БПЛА.