1

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

в 25% случаев - от менее 1 до 10 секунд,
в 30% случаев - от 10 до 50 секунд,
еще в 30% случаев - от 50 до 300 секунд,
в остальных 15% случаев время счета превышало 300 секунд или оптимизация не доводилась до конца для экономии времени. Причем проверка времени счета в одном из таких случаев «до упора» показала, что оптимизация не закончилась и за 6 часов. В других случаях расчет занимал в итоге 2-3 часа.

Скачать файл "garbage_truck_route 3.xlsx" (примерно 383 Кб)

генератор произвольного набора координат для 30 пунктов посещения
модель решения задачи из 30 точек посещения, время расчета 2 сек
модель решения задачи из 30 точек посещения, время расчета 54 сек
модели решения задачи из 30 точек посещения, время расчета 1178 сек.

Если посмотреть на наборы точек, то предугадать, сколько времени будет просчитываться маршрут по этим наборам, практически невозможно.

Полученные маршруты для набора пунктов посещения сильно различаются по времени оптимизации (в каждом случае tolerance =5%).

Всегда могут встретиться варианты, когда солвер 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 точки посещения с различным временем оптимизации

Но и в этом случае предсказать время оптимизации довольно сложно. Так время поиска решения для приведенных ниже вариантов различается в разы.

Построеные маршруты и время расчета:

Облачные решения с NEOS

Ранее я упоминал, что кроме универсальных алгоритмов, подобных описанному на странице Построй маршрут (чистая целочисленная оптимизация MILP), есть и специализированные алгоритмы, которые решают задачи коммивояжера гораздо быстрее.
Эти алгоритмы умеют решать гораздо более крупные задачи, вплоть до десятков тысяч пунктов ( TSPLIB). Так что, если оптимальное планирование действительно зависит от эффективности решения большой задачи коммивояжера, имеет смысл использовать именно специальные алгоритмы.
Несколько таких алгоритмов можно увидеть среди задач библиотеки GAMS. Довольно надежный алгоритм от незабвенного Дж. Данцига реализован в задаче №213 (tsp42, «TSP solution with subtour elimination»).
Здесь можно скачать файлик с заданием для сервера NEOS.

Скачать файл "tspvse_tsp50.gms" (примерно 19 Кб)

В нем изменены только заголовок, список пунктов посещения i и данные таблицы расстояний d(i,j).
Данные таблицы расстояний соответствуют задаче на 51 пункт посещений из файла «garbage_truck_route 5.xlsx», время расчета 35 сек.

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

Решение, которое вы получите из NEOS:

В файле «garbage_truck_route 5.xlsx» на страничке «51 223сек gms» эти данные оптимального маршрута внесены в таблицу переменных E61:BC111 вручную для того, чтобы получить диаграмму с маршрутом. Получилось следующее изменение в маршруте.

Разумеется, написать макрос, вносящий данные из листинга сервера NEOS в таблицу переменных файла Excel не сложно. Но в единичном случае быстрее было сделать перенос руками.