Система по построению маршрутов транспорта

Система по построению маршрутов транспорта (VRPPD) представляет собой решение транспортной задачи по минимизации затрат при перевозке грузов с использованием временных окон.За основу взято решение на Java и реализован полный алгоритм Разрушения и Воссоздания по Шримфу.Данный подход позволяет получить точные и быстрые результаты для классических оптимизационных задач. Данный метод используется для решения задач Коммивояжера, транспортной задачи с временными окнами, и для оптимизации сети. Он является универсальным, эвристическим, т.е. это означает, что правильность которого во всех возможных случаях не доказана, однако в большинстве случаев метод дает хорошие результаты.В качестве основного провайдера для получения расстояний между всеми точками заказов используется OSRM. OSRM позволяет строить маршруты между точками и рассчитать время и расстояние поездки. Большим плюсом в отличие от сервисов Google, является отсутствие лимитов на количество запросов. При некорректной работе основного провайдера, используется аналогичные сервисы от Google (Distance Matrix).Для полноценного использования функционала, написан простой веб-интерфейс на Ruby on Rails. Информация о заказах загружается в cvs-файле. Далее происходит обработка и построение маршрута.Так как обработка и построение маршрута занимают значительное время, потребовался асинхронный обработчик задач. В данном случае был использован gem Sidekiq.Данная система по построение маршрутов была специально разработана для сайта Aptdeco.com. Этот сайт представляет собой площадку для продажи мебели в Нью-Йорке, США. Когда пользователь добавляет свою мебель в каталог, он также указывает наилучшее время для ее приобретения. Все заказы загружаются в системы в виде csv файла и система автоматически подсчитывает наилучший маршрут для доставки. Файл с результатами также предоставлен в формате csv.