Идеальное решение для проходимости судов бы выглядело вот так:
Где каждое судно проходит оптимальный путь без ожиданий.
Сложность заключается в том что для того чтобы подобрать оптимальное расписание для всех судов, нужно учитывать множество комбинаций и вариантов проходимости судов в зависимости от ледовой обстановки.
Количество комбинаций всех решений для 42 заявок составляет число с 19 нулями так что нам пришлось испльзовать другие методы для нахождения решения задачи.
Для
- Образуем данные проходимости льда и разбиваем их по сетке координат.
- Находим две точки на графе и берем их координаты.
- Строим путь между этими точками по болшому кругу
- Разбиваем путь на n точек
- Для каждой точки на пути находим ближайшую точку данных по ледовой обстановке с помощью алгоритма K-d деревьев.
- Картинка
- Строим граф, добавляя на рёбра метаданные о проходимости на участках пути.
- Сохраняем.
Граф с данными о проходимости льда:
Для нахождения оптимального пути на графе мы использовали алгоритм Djikstra из библиотеки NetworkX, который находит кратчайший путь между двумя вершинами на графе учитывая время прохождения для выбранного судна и ледокола.
Алгоритм работает на принципе поиска кратчайшего пути на графе с помощью обновления весов рёбер в зависимости от времени прохождения. После нахождения кратчайшего пути мы можем узнать время прохождения и оптимальный путь для судна.
Изначальное расписание строится так что мы привязываем ледокол, который меньше всего ждать для нашего судна. После этого мы привязываем к следующему судну ледокол, который меньше всего ждать для него и так далее.
В итоге мы получаем расписание где близко к минимуму сумма ожиданий всех ледоколов.
Это решение является нашей отправной точкой, при котором суммарный простой всех кораблей ожидающих ледокол составляет 190 дней или 4560 часов!
-
Корабли потратили ожидая ледоколов:
4560часов <- нам нужно уменьшить время простоя кораблей в ожидании ледоколов -
Ледоколы потратили ожидая кораблей:
212часов -
Ледоколы потратили на перемещение:
4509часов -
Корабли потратили на перемещение:
2748часов
Удобство алгоритма заключается в том, что мы можем подобрать решение близкое к оптимальному, при этом регулируя, сколько времени мы готовы потратить на поиск решения.
# Настройка параметров имитации отжига
initial_temp = 1000
cooling_rate = 0.95 # Коэффициент охлаждения 0.95 значит что температура уменьшается на 5% на каждой итерации