АНАЛИЗ ПРОГРАММ ДЛЯ ПОСТРОЕНИЯ МАРШРУТОВ И ПОДРОБНОЕ ИЗУЧЕНИЕ ОНЛАЙН-СЕРВИСА ЛОГИСТ «PONCY-RU»

ANALYSIS OF PROGRAMS FOR CONSTRUCTING ROUTES AND A DETAILED STUDY OF THE ONLINE SERVICE LOGIST «PONCY-RU»

Gleb Kaznacheev

5th year student, Faculty of Transport, Orenburg State University,

Russia, Orenburg

АННОТАЦИЯ

В современном мире, полном различного транспорта и цифровых технологий, для работы логиста важном знать и уметь пользоваться логистическими программами. В данной статье рассматривается история создания и формирования логистики, различные логистические программы и подробно изучается онлайн-сервис Логист «Poncy-ru».

ABSTRACT

In a modern world full of various transport and digital technologies, it is important for a logistician to know and be able to use logistics programs. This article examines the history of the creation and formation of logistics, various logistics programs and examines in detail the online logistics service "Poncy-ru".

Ключевые слова: логистические программы, логист, коммивояжер, построение маршрутов.

Keywords: logistics programs, logistics, traveling salesperson, route planning.

Доподлинно неизвестно, когда впервые была исследована работа коммивояжера (логистика). Однако, известна книга, опубликованная в 1832 году, «Коммивояжёр — как он должен вести себя и что должен делать для того, чтобы доставлять товар и иметь успех в своих делах — советы старого курьера» (нем. «Der Handlungsreisende - wie er sein soil und was er zu tun hat, um Auftrage zu erhalten und eines glucklichen Erfolgs in seinen Geschaften gewiB zu sein - von einem alten Commis-Voyageur»), книга объясняет задачу, но для ее решения не используется математический аппарат. Однако, в ней приведены примеры маршрутов для нескольких регионов Германии и Швейцарии.

Ранней версией задачи можно считать англ. Icosian Game 19 века Уильяма Гамильтона, которая заключалась в поиске маршрута на графе с 20 узлами. Первое упоминание о задаче математической оптимизации принадлежит Карлу Менгеру, сформулированному на математическом коллоквиуме 1930 года следующим образом:

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

Вскоре появилось ставшее известным название «проблема странствующего торговца» (англ. Traveling Salesman Problem), предложенное Хасслером Уитни из Принстонского университета.

Наряду с простотой определения и сравнительной простотой поиска хорошего решения, проблема коммивояжера отличается тем, что найти действительно оптимальный путь является довольно сложной задачей. Учитывая эти особенности, начиная со второй половины 20-го века изучение задачи коммивояжера имеет не столько практическое значение, сколько теоретический, в виде модели для разработки новых алгоритмов оптимизации.

На примере задачи коммивояжера было разработано множество современных распространенных методов дискретной оптимизации, таких как отсечение, ветвей и границ и различные варианты эвристических алгоритмов.

В 1950-х и 1960-х годах проблема коммивояжера привлекла внимание ученых в Соединенных Штатах и Европе. Важный вклад в изучение этой проблемы внесли Джордж Данциг, Делберт Рэй Фалкерсон и Селмер Джонсон, которые сформулировали проблему как задачу дискретной оптимизации в Институте корпорации RAND в 1954 году и применили метод отсечения для ее решения. Используя этот метод, они построили маршрут коммивояжера для частной постановки задачи в 49 городах, обосновав его оптимальность. В 1960-х и 1970-х годах эта проблема изучалась многими учеными как теоретически, так и с точки зрения ее применения в информатике, экономике, химии и биологии.

В 1972 году Ричард Карп доказал NP-полноту задачи поиска гамильтоновых путей, из которой вытекала NP-трудность задачи коммивояжера из-за полиномиальной сводимости. Основываясь на этих характеристиках, он дал теоретическое обоснование сложности поиска решения проблемы на практике.

В конце 1970-х и 1980-х годах Мартин Грётчел, Манфред Падберг и Джованни Ринальди и другие вычислили решение для одного случая задачи о 2393 городах, используя новые методы деления плоскостью, ветвей и границ, что дало большой скачок в задаче логиста.

В 1990-х годах Дэвид Эплгейт, Роберт Биксби, Вашек Хватал и Уильям Кук установили рекорды для программы Конкорд. Герхард Рейнельт создал TSPLIB - набор стандартизированных примеров задач коммивояжера различной степени сложности, чтобы сравнить результаты работ разных групп исследователей. В 2005 году проблема с 33 810 узлами была решена с помощью программы Конкорд: была рассчитана длина пути в 66 048 945 узлов и доказано, что более коротких путей не существует. В 2006 году нашли решение для экземпляра с 85 900 узлами. Метод декомпозиции позволяет рассчитать решение в случае задач с миллионами узлов, длина которых менее чем на 1% превышает оптимальную./[1]

Одним из современных исследователей проблемы оптимизации маршрутов с помощью математики и программного обеспечения является Шенмайер Владимир Владимирович. Основой всех логистических программ является программа Конкорд.

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

Для построения маршрутов доставки можно использовать специальное программное обеспечение.

Наиболее распространены такие программы, как Maxoptra, Логист (poncy- ru), Умная Логистика, КиберЛог, АвтоПеревозки, ЯКурьер, 4logist, Грузоплан, NovaTrans. Муравьиная логистика, Яндекс.Маршрутизация.

Основное назначение данных программ - облегчить работу специалиста, упростить вычисление оптимального маршрута, расчёт путевого времени, составление графиков следования, автоматизировать транспортный процесс, оптимизация в час пик и т.д.

Преимущество программ - большой набор выполняемых операций, автоматизация процессов перевозки, способность обработки большого количества информации автоматически, возможность выгрузки баз данных.

Недостатками данных программ являются: необходимость покупки лицензионной версии, короткий бета-период использования программы, возможность обсчёта маленького количества точек в тестовой версии программ.

В данной статье мы изучим онлайн-сервис «Poncy-ru». Данный сервис позволяет составлять эффективный маршрут на основе множества точек доставки, рассчитывает затраченной время и расстояние, пройденное автомобилем. Маршрут может составляться с учетом автомобильных пробок или абсолютного расстояния между пунктами для воздушного транспорта. Особенностью сервиса является интуитивно понятный интерфейс, позволяющий задать точки маршрута, помечая или передвигая их по карте. Главным преимуществом «Poncy-ru» является его полностью бесплатный метод распространения. [2]

Рисунок 1. Интерфейс программы «Poncy-ru»

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

Рисунок 2. Интерфейс программы «Poncy-ru» - построение маршрута

Вкладка «Пробки» содержит информацию о наличии пробок на дороге в определенный период времени и день недели на основе статистики. Данная информация позволяет составить более эффективный маршрут и подобрать время для доставки груза.

Рисунок 3. Интерфейс программы «Poncy-ru» - «Пробки»

Вкладка «Описание маршрута для печати» содержит в себе описание маршрута, включая повороты, дистанцию до следующего поворота или конца маршрута, общее расстояние и время маршрута, а также позволяет распечатать представленную информацию.

Рисунок 4. Интерфейс программы «Poncy-ru» - «Описание маршрута для печати»

Задачи логистики решаются посредством различных методов, выведенных в результате теоретических исследований. Все эффективные методы (сокращающие полный перебор) — методы эвристические. В большинстве эвристических методов находится не самый эффективный маршрут, а приближённое решение. Зачастую востребованы, так называемые, any-time алгоритмы, то есть постепенно улучшающие некоторое текущее приближенное решение.

Выделяют следующие группы методов решения задач логистики, которые относят к простейшим:

- полный перебор;

- случайный перебор;

- жадные алгоритмы (метод ближайшего соседа, метод включения ближайшего города, метод самого дешевого включения);

- метод минимального остовного дерева (деревянный алгоритм);

- метод имитации отжига. [3]

Рисунок 5. Методы решения задачи

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

Таким образом, в данной статье была рассмотрена история создания и формирования логистики, различные логистические программы и подробно изучен онлайн-сервис Логист (Poncy-ru). Выявлены положительные и отрицательные стороны данных программ. Установлены причины необходимости использования специальных программ для построения оптимальных маршрутов.

Список литературы:

1. Историческая справка [Электронный ресурс] – режим доступа:  https://studwood.ru/1895758/matematika_himiya_fizika/zadacha_kommivoyazhere  (дата обращения:10.06.2024).
2. Логист – построение оптимального маршрута по нескольким точкам [Электронный ресурс] – режим доступа: http://gov.swizz.ru/ (дата обращения: 10.06.2024).
3. Методы решения задач коммивояжера [Электронный ресурс] – режим доступа: https://studfile.net/preview/9535178/page:3/ (дата обращения: 10.06.2024).