Логотип HCXL Масштаб задачи
С задачей коммивояжера обычно связывают быстро нарастающую сложность для компьютера и сильный рост длительности оптимизации.
На практике, как правило, не удается предугадать, сколько времени займет оптимизация в каждом конкретном случае. На этой странице я приведу статистику вычислений задач по оптимизации в разных случаях.
Исследуем оптимизацию для задач с 30-ю и 51-м пунктами посещения.

1

Исследование оптимальных решений для задач с 30 пунктами посещения.

    Модель, которую мы создали на странице Построй маршрут, позволяет легко сгенерировать, решить задачу для 30 точек маршрута и сделать некоторые выводы о времени оптимизации.

    Для 100 случайных вариантов размещения 30 пунктов посещения (смотрите шаблон в файле «garbage_truck_route 3.xlsx») проведена оптимизация маршрута при параметре tolerance =5%. При этом оптимизация заняла
  • в 25% случаев - от менее 1 до 10 секунд,
  • в 30% случаев - от 10 до 50 секунд,
  • еще в 30% случаев - от 50 до 300 секунд,
  • в остальных 15% случаев время счета превышало 300 секунд или оптимизация не доводилась до конца для экономии времени. Причем проверка времени счета в одном из таких случаев «до упора» показала, что оптимизация не закончилась и за 6 часов. В других случаях расчет занимал в итоге 2-3 часа.
  • Вполне может быть, что стандартный для OpenSolver алгоритм линейной оптимизации COIN-OR CBC и вовсе никогда не завершит процесс оптимизации (по каким-то неизвестным нам причинам).
Скачать файл с задачей Скачать файл "garbage_truck_route 3.xlsx" (примерно 383 Кб)
    Этот файл содержит:
  • генератор произвольного набора координат для 30 пунктов посещения
  • модель решения задачи из 30 точек посещения, время расчета 2 сек
  • модель решения задачи из 30 точек посещения, время расчета 54 сек
  • модели решения задачи из 30 точек посещения, время расчета 1178 сек.
Если посмотреть на наборы точек, то предугадать, сколько времени будет просчитываться маршрут по этим наборам, практически невозможно.
Набор из 30 точек посещения. Вариант 1 Набор из 30 точек посещения. Вариант 2 Набор из 30 точек посещения. Вариант 3 Набор из 30 точек посещения. Вариант 4
Полученные маршруты для набора пунктов посещения сильно различаются по времени оптимизации (в каждом случае tolerance =5%).
Построеный маршрут из 30 точек посещения 1 варианта. Время расчета 2 сек.  Построеный маршрут из 30 точек посещения 2 варианта. Время расчета 54 сек.  Построеный маршрут из 30 точек посещения 1 варианта. Время расчета 43 сек. Построеный маршрут из 30 точек посещения 1 варианта. Время расчета 1178 сек.
Всегда могут встретиться варианты, когда солвер COIN-OR CBC не находит оптимального маршрута за разумное время. В этом случае используйте коммерческий солвер от Gurobi.com (пробную версию которого можно свободно получить на сайте компании).
Доступный через сервер NEOS оптимизатор IBM ILOG CPLEX (NEOS using CPLEX в опциях Solver Engine…) также успешно решает задачи, с которыми не справился COIN-OR CBC. Однако при этом вы столкнетесь с небольшой проблемой. Этот оптимизатор не принимает функцию =ТРАНСП(..), поэтому в 104-й строке файла ее нужно заменить на 30 ссылок на ячейки в столбце AI74: AI103, а в 71 строке нужно просто поставить единицы.

2

Исследование оптимальных решений для задач с 51 пунктом посещения.

Найти решение задачи о нахождении единого маршрута с 51 точкой посещения практически невозможно с помощью солвера от COIN-OR CBC. Однако решения с использованием солверов Gurobi или CPLEX занимает десяток секунд.

Так что в случаях, когда вам необходимо прокладывать маршруты на количество точек посещения более 30, имеет смысл задействовать коммерческие инструменты. Или что-то специально заточенное по решение «задачи коммивояжера» (traveling salesman problem или TSP, тут имеет смысл покопаться на в ресурсах TSPLIB ).
Скачать файл с задачей Скачать файл "garbage_truck_route 5.xlsx" (примерно 471 Кб)
    Этот файл содержит:
  • генератор произвольного набора координат для 51 пункта посещения
  • 3 варианта модели задач из 51 точки посещения с различным временем оптимизации
Но и в этом случае предсказать время оптимизации довольно сложно. Так время поиска решения для приведенных ниже вариантов различается в разы.
Набор из 51 точек посещения. Вариант 1 Набор из 51 точек посещения. Вариант 2
Построеные маршруты и время расчета:
Маршрут из 51 точки посещения. Вариант 1 Маршрут из 51 точки посещения. Вариант 2
Облачные решения с NEOS
Ранее я упоминал, что кроме универсальных алгоритмов, подобных описанному на странице Построй маршрут (чистая целочисленная оптимизация MILP), есть и специализированные алгоритмы, которые решают задачи коммивояжера гораздо быстрее.
Эти алгоритмы умеют решать гораздо более крупные задачи, вплоть до десятков тысяч пунктов ( TSPLIB). Так что, если оптимальное планирование действительно зависит от эффективности решения большой задачи коммивояжера, имеет смысл использовать именно специальные алгоритмы.
Несколько таких алгоритмов можно увидеть среди задач библиотеки GAMS. Довольно надежный алгоритм от незабвенного Дж. Данцига реализован в задаче №213 (tsp42, «TSP solution with subtour elimination»).
Здесь можно скачать файлик с заданием для сервера NEOS.
Скачать файл с заданием GMS Скачать файл "tspvse_tsp50.gms" (примерно 19 Кб)
  • В нем изменены только заголовок, список пунктов посещения i и данные таблицы расстояний d(i,j).
  • Данные таблицы расстояний соответствуют задаче на 51 пункт посещений из файла «garbage_truck_route 5.xlsx», время расчета 35 сек.

Задача решается сервером NEOS примерно за 2,6 секунды. Причем, получается немного другой маршрут, что видно по суммарному расстоянию: 117,64 км вместо 117,65. Правда, увидеть изменения в маршруте в графической форме не так-то просто. Сам маршрут не упорядочен и приводятся только пары пунктов, для которых установлена связь по маршруту. Вот так, как показано ниже (единичка – есть связь).

Решение, которое вы получите из NEOS:
Иллюстрация решения Neos В файле «garbage_truck_route 5.xlsx» на страничке «51 223сек gms» эти данные оптимального маршрута внесены в таблицу переменных E61:BC111 вручную для того, чтобы получить диаграмму с маршрутом. Получилось следующее изменение в маршруте.
Маршрут из 51 точки посещения, постороенный NEOS
Маршрут из 51 точки посещения. Вариант 2
Разумеется, написать макрос, вносящий данные из листинга сервера NEOS в таблицу переменных файла Excel не сложно. Но в единичном случае быстрее было сделать перенос руками.
Но универсальные алгоритмы берут свое, когда нужно решать разнообразные задачи.
В следующей части рассмотрим, как можно модифицировать алгоритм, построеный ранее, под конкретные задачи бизнеса.
Перейти на страницу
Осложнения в маршруте
✉ Если у вас появились вопросы или замечания, вы можете предложить лучшее решение, то пишите мне на электронную почту.