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