Эффективное решение задачи коммивояжёра на случайно распределённых данных

Аннотация

В данном исследовании мы представляем метод и его реализации для задачи коммивояжёра применительно к матрицам с равномерным случайным распределением стоимостей путей. Метод представляет собой модификацию метода ветвей и границ с использованием специфических эвристик. Обсуждаются генерация данных и валидация, использованные в этом исследовании.

Математическое изучение решаемой задачи, вероятно, можно считать завершённым ещё в 1970-х годах; ещё раньше был описан подход к её решению в виде метода ветвей и границ. Цель данной статьи — описать такую эвристическую реализацию метода ветвей и границ, которая с вероятностью, близкой к единице, даёт оптимальное решение случайной задачи за приемлемое время. Случайными мы называем такие варианты задачи, в которых каждая ячейка матрицы коммивояжёра для конкретного экземпляра задачи представляет собой реализацию равномерно распределённой случайной величины. Важно отметить, что подходы к эвристическому решению случайного варианта существенно отличаются от подходов к геометрическим и псевдогеометрическим вариантам.

По нашему мнению, мы достигли поставленной цели: максимальное время получения решения для 100 случайных экземпляров задачи размерности 99 не превысило 2 минут, при этом точное решение находилось всегда; последнее было подтверждено тем, что метод ветвей и границ всегда доводился до завершения. В статье мы даём краткое описание использованных для этого эвристик, важнейшей из которых является построение так называемой последовательности правых подзадач.