Проблема масштабирования TSP
Задача коммивояжера (TSP) остается одной из самых сложных в комбинаторной оптимизации. Точное решение больших экземпляров требует экспоненциальных вычислительных ресурсов. Традиционные методы спарсификации (упрощения) графов опираются на фиксированные эвристики, которые не учитывают уникальную геометрическую структуру каждого конкретного экземпляра задачи, что приводит к либо избыточному сохранению данных, либо потере качества решения.
Решение: GES-TSP
Авторы Tianfeng Chen и Xianyue Li предлагают метод Graph Edge Sparsification (GES). Это подход, основанный на машинном обучении, который адаптируется к структуре входных данных. Метод интегрирует геометрическую информацию и технологии комбинаторной оптимизации для генерации оптимального разреженного графа для каждого конкретного случая. Это позволяет значительно уменьшить размер графа перед запуском алгоритмов поиска пути.
Ключевые метрики эффективности
Эксперименты проводились на стандартных наборах данных MATILDA и TSPLIB. Результаты демонстрируют беспрецедентный баланс между скоростью и точностью:
| Набор данных | Доля удаленных ребер (Pruning Rate) | Отклонение от оптимума (Gap) | Примечание |
|---|---|---|---|
| MATILDA | до 95% | менее 1% | Высокая плотность графов |
| TSPLIB (крупные экземпляры) | более 99% | менее 1% | Экстремальное сжатие |
Значение для индустрии
Способность удалять более 99% ребер при сохранении качества решения ниже 1% открывает путь к решению задач TSP невиданного ранее масштаба. Метод демонстрирует сильную способность к обобщению (generalization), что делает его применимым к различным типам логистических и маршрутных задач, где критичны вычислительные затраты и время отклика.
Источник: arXiv cs.AI ↗