Адаптивный эвристический солвер для обобщенной задачи коммивояжера с ограничениями предшествования

Обобщенная задача коммивояжера с ограничениями предшествования (PCGTSP) — специальная версия известной обобщенной задачи коммивояжера (GTSP), обладающей широким спектром значимых приложений в исследовании операций. Несмотря на практическую значимость, результаты в области проектирования, реализации и численного тестирования алгоритмов для этой задачи до сих пор остаются достаточно редкими. В данной работе, по всей видимости, впервые предлагается комплекс эвристических алгоритмов, высокая эффективность которого подтверждается результатами численных экспериментов на постановках из публичного репозитория PCGTSPLIB. Предлагаемый комплекс основан на методологии адаптивного поиска в больших окрестностях и онлайн-обучения в классе элементарных эвристик и является недавно предложенной библиотеки глобального поиска (GLNS) для задачи GTSP без ограничений предшествования. Для обеспечения воспроизводимости полученных численных результатов исходные коды реализаций всех предложенных алгоритмов предоставлены авторами в свободном доступе.