В Новосибирском государственном техническом университете НЭТИ разрабатывают приложение для эффективного построения маршрутов. Потенциальные потребители продукта — компании по доставке товаров и оказывающие выездные услуги. Проект вошел в число победителей конкурса «Студенческий стартап» федерального проекта «Платформа университетского технологического предпринимательства». Команда проекта получит грантовую поддержку в размере 1 млн рублей на реализацию своего стартапа.
«На кафедре теоретической и прикладной информатики уже достаточно продолжительное время по запросам компаний ведутся исследования и разработки, касающиеся составления оптимальных маршрутов для доставки грузов или оказания услуг. Это важно, поскольку неправильно построенный маршрут приводит к увеличению времени сотрудника в пути, что влечет за собой увеличение затрат на доставку, уменьшает эффективность работы (из-за временных потерь невозможно обслужить большее количество адресов за день), вызывает недовольство клиентов, которые долго ожидают свой заказ. На данном этапе разработки приложения учитываются такие ограничения, как расстояние между адресами и временные рамки, в которые сотрудник должен приехать на каждый адрес. Перед нами стояло две задачи: разбить эти точки (адреса) на кластеры (отдельные маршруты) и составить оптимальный маршрут для каждого», — рассказали авторы проекта, студентки факультета прикладной математики и информатики НГТУ НЭТИ Анастасия Воробьева и Анастасия Богатырева.
Для решения первой задачи разработчики использовали один из алгоритмов дивизимной кластеризации. В этом алгоритме всё множество точек сначала считается одним кластером, затем оно последовательно разбивается на всё более мелкие кластеры, пока их не окажется нужное количество. А для построения маршрутов применялся алгоритм, который авторы проекта разработали на основе алгоритма ближайшего соседа. Этот алгоритм «ищет» ближайшие непосещенные точки в двух максимально противоположных направлениях, за счет чего удается снизить такой недостаток алгоритма ближайшего соседа, как неоправданно длинные участки пути между несколькими заключительными точками построенного маршрута. Кроме того, маршруты строятся по большому количеству точек (более 5000), в аналогах очень мало алгоритмов, работающих с таким объемом.
«В дальнейшем также планируется добавление в приложение других алгоритмов и методов, в том числе на основе набирающих в последнее время популярность методов машинного обучения и искусственного интеллекта», — добавили разработчики.
Проект направлен на повышение эффективности доставки для различных компаний: курьерских служб, компаний с выездным обслуживанием и крупных предприятий с собственным автопарком. Функциональность приложения будет расширяться, станет учитываться больше различных ограничений (на данном этапе учитывается только расстояние между точками и временные рамки). Приложение будет анализировать данные о пунктах доставки и ресурсах (количество заказов, временные ограничения, доступный автопарк), чтобы построить наиболее эффективный маршрут. Будут учитываться различные условия и ограничения по массе или объему товара (например, сколько груза вмещается в одно транспортное средство), возможность оперативно внести изменения в маршрут, приоритет заказов, дорожная ситуация, время обеда экипажей, продолжительность смены и другие.
На данный момент команда разработчиков успешно протестировала созданные алгоритмы. Через полгода планируется создать рабочий прототип, включающий в себя основной функционал. Постепенно его можно будет расширять, чтобы пользователь мог выбирать опции в соответствии со своими потребностями.