Даны географические координаты точек маршрута. Необходимо:
- минимизировать маршрут (найти самый короткий из возможных)
- отразить маршрут на карте
Ежемесячно 25 числа сотрудники (контролёры) энергосбытовых компаний (это компании, которым мы платим за электроэнергию по квитанциям) проводят выборочный контрольный съем показаний приборов учета потребителей. Эти работы отличаются высокой трудоемкостью и минимальным КПД, но обязательностью проведения. Вследствие требуется минимизировать трудозатраты за счет оптимизации маршрута передвижения контролёра.
• 100 точек контроля (массив географических координат - задан заранее); • 2 контролёра с географическими координатами изначального местоположения.
• Построить близкий к оптимальному маршрут контролёров для обхода всех точек
• Минимальная суммарная дистанция контролёров
• Количество обращений к ГИС на километр маршрута контролёра
• Система должна быть реализована в виде серверного приложения • В качестве ГИС системы может использоваться GoogleMap или OpenStreetMap (в нашем случае я выбрал Яндекс.Карты) • Результат должен быть выдан в виде маршрута на карте, последовательности адресов, длины маршрута и количества обращений к ГИС для каждого из контролёра
- HTML/CSS
- ReactJS
- Yandex.Maps API
- ASP .NET 5 (по сути не использован, изначально предполагалось использование для сохранения маршрутов)
Изначально был реализован муравьиный алгоритм, однако он оказался не слишком эффективным во многих случаях. В результате было принятно решение использовать генетический алгоритм, который и был в итоге разработан.
На разработку ушло 2 дня, в которые и проходил сам хакатон.
- f0xeri - весь фронтенд и переписанные на Typescript алгоритмы
- Rellik-git - алгоритмы, реализованные на C++
Посмотреть и попробовать, что у нас получилось можно тут.