Обзор программных продуктов для решения задачи построения оптимального маршрута

Задача поиска оптимального маршрута имеет достаточно обширное применение. В основном она применяется в таких областях, где есть территориальная разрозненность объектов на местности. Примерами использования на практике служат следующие задачи:

· Оптимизация маршрутов патрульной службы

· Оптимизация маршрута службы доставки

· Планирование строительства нефтегазовой магистрали

· Построение маршрутизации в сетях

· Обслуживание объектов военного назначения

Решение данных задач позволяет ускорить выполнение поставленных целей организации и приносит экономию в финансовом секторе. Таким образом, например, компьютерная сеть Национального фонда науки США внедрила муравьиные алгоритмы для построения оптимальной маршрутизации в телекоммуникационных сетях в 1994 году, что увеличило пропускную способность с 300Кбит/с до 44,736 Мбит/с и увеличило суммарный объем пакетов данных с 1 трлн до 10 трлн байт. Сеть выдерживала 4000 организаций и около 50000 сетей.

Среди известных программных средств на рынке, решающих задачу поиска оптимального маршрута, на сегодняшний день можно выделить: веб приложение построение оптимального маршрута Poncy-ru, программный комплекс «Логистика развоза» компании ООО «Программы для бизнеса», ОПТИМУС ГИС и ABMRinkaiTMS. Рассмотрим каждое программное средство более подробно.

Логистика развоза. Программный комплекс «Логистика развоза» компании – ООО «Программы для бизнеса» также использует методы для решения транспортной задачи [21]. А именно, распределяет заказы таким образом, чтобы максимально загрузить весь текущий транспорт и построить для каждой машины оптимальный маршрут проезда с учетом дорожной ситуации. Данный программный комплекс позволяет рассчитать доставку с учетом нескольких дней, расписания транспортных средств и их привязки к зонам погрузки и разгрузки.В программе есть возможность диспетчеризации водителей с использованием мобильных устройств на базе оперативной системы Android.Программный комплекс является конфигурацией для 1С и интегрирован с программой GWX и электронными картами «Ингит». В области логистики можно выделить преимущества рассматриваемой программы:

· Быстрый поиск оптимального маршрута

· Контроль отклонения фактического маршрута водителя от оптимального

· Возможность изменения построенного маршрута в случае изменившейся дорожной ситуации

По заявлениям компании программа позволяет снизить затраты на перевозку до 30%.

ОПТИМУМ ГИС. ОПТИМУМ ГИС – система GPS-мониторинга транспорта, оптимизация транспортной логистики и планирования маршрута выездного персонала [22]. Решение системы снижает расходы компании за счет уменьшения транспортных издержек, которые позволяют сократить общий километраж в среднем на 15-20% и количество используемого автотранспорта. Система так же включает в себя модули «Мониторинг и «Доставка», которые предназначены для автоматизации процессов транспортной логистики и наблюдения за перемещением авто.

«Мониторинг» позволяет контролировать в режиме реального времени на электронной карте простои транспортных средств и отклонений от маршрутов. Дает возможность снимать показания любых датчиков: расход топлива, открытие дверей, повреждения автомобиля и так далее.

Модуль «Доставка», автоматически рассчитывает наиболее оптимальную загрузку машин, на основе имеющихся заказов, длительности маршрута с учетом времени на отгрузку и возврата на склад. Формирует различные документы, накладные, кассовые и маршрутные листы.

На карте (рисунок 1.4) можно увидеть пример рассчитанный системой ОПТИМУМ ГИС, где красным цветом отмечен оптимальный маршрут, синим – маршрут пройденный водителем. На основании чего можно сделать вывод, что транспортное средство использовалось в личных целях, и представленный рейс потерпел издержки.

Рисунок 1.4. Карта оптимального и фактического маршрутов

Из плюсов представленного программного средства, можно выделить возможность в режиме реального времени отслеживать передвижение автотранспорта, оптимальное построение маршрута и возможность формирования всех необходимых документов на основе данных программы. Среди минусов это нужда в постоянной поддержке работы программного средства и в большом объеме вычислительных ресурсов.

ABMRinkaiTMS. ABMRinkaiTMS – Программа направлена на оптимизацию и построение маршрутов доставки. В своем алгоритме оптимизации учитывает факторы скорости, весогабаритные параметры и другие характеристики [27]. Основным отличием от конкурентов является интеграция карт в мобильные телефоны. Таким образом, курьер может использовать приложение как навигатор и четко следовать заданному маршруту. Помимо этого в системе предусмотрена отправка смс или почтовых уведомлений клиентам с информацией о запланированном времени прибытия. В программном средстве также предусмотрена статистика выполненных заказов и учет доставки в срок, что позволяет контролировать отклонение водителей от маршрута.

Рисунок 1.5. Статистика доставок

На рисунке1.5 представлен график статистики с всплывающим окном детальной информации по каждому заказу, где можно точно увидеть придерживался ли водитель оптимального маршрута или нет. Из недостатков программного средства можно выделить отсутствие фактического маршрута курьера, поэтому сложно сопоставить его силу отклонения от оптимального пути.

Логистика. Веб приложение позволяет находить маршрут по заданным точкам на карте. Поддерживает на выбор три варианта передвижения: на машине, на машине с учетом пробок и на воздушном транспорте. Программное средство не привязано, к какой-либо конкретной области и может использоваться как инструмент, для построения маршрута в различных целях. Интерфейс приложения имеет адаптивность под мобильные устройства. Минусами данного приложения являются отсутствие построения маршрутов для пешеходов. Среди плюсов можно выделить простоту использования, достаточно быстрое построение оптимального пути и возможность задавать маршрут GETзапросом, благодаря чему можно обрабатывать ссылки с адресами с помощью одного приложения, а для построения маршрута использовать «Логистика» как инструмент.

Задача поиска оптимального маршрута существует и в медицине. На сегодняшний день врачи-терапевты во время обхода пациентов, выстраивают свой маршрут навскидку. Но в случае большой разрозненности точек, человеческий мозг не способен сходу найти оптимальный маршрут, а на его вычисление вручную уйдет время, которое можно потратить как минимум еще на одного пациента. Программное средство позволяющее решить данную задачу и организовать работу и взаимодействие врачей и пациентов, повысит как скорость обслуживания, так и его качество. Однако сейчас на рынке нет программных средств, которые можно было бы применить конкретно к данной области. Все существующие программные средства настроены на оптимизацию автомобильных маршрутов, а пешие вовсе не берутся во внимание. Помимо этого, главное отличие большинства логистических систем заключается в жесткой привязке товаров к точкам доставки, таким образом, в них не предусмотрена оптимизация в процессе уже построенного маршрута. Исходя из выше сказанного, стоит предусмотреть в программном средстве ВКР все описанные нюансы для полноценного решения задачи.