Введение

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

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

Постановка проблемы

Для эффективного планирования и реализации доставки товаров, компании должны работать с надежными телекоммуникационными системами и информационно-компьютерной поддержкой [7-9]. Такой поддержкой выступают информационные системы транспортной логистики.

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

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

Цель данной работы: повешение эффективности учета отправки и прибытия грузов транспортной компании посредством автоматизации и внедрения оптимальных алгоритмов работы с базой данных и электронной картой при планировании логистических процессов. Для достижения поставленной цели необходимо решения следующих исследовательских задач:

1) Математическое описание методов и реализации алгоритмов автоматизации работы по учету отправки и прибытия грузов транспортной компании.

2) Разработка проблемно-ориентированной программной системы маршрутизации грузоперевозок, включающей в себя: базу данных и средства работы с ней, редактор и визуализатор цифровых карт, модуль решения задач маршрутизации с визуальным интерфейсом настроек алгоритмов и выводом результатов на экран.

3) Экспериментальная оценка эффективности предлагаемых критериев и алгоритмов.

Обзор существующих алгоритмов автоматизации работы по учету отправки и прибытия грузов транспортной компании

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

Общая идея метода может быть описана на примере поиска минимума и максимума функциина множестве допустимых значений х. Функция f и х могут быть произвольной природы. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ).

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

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

В основе метода ветвей и границ лежит следующая идея (для задачи минимизации): если нижняя граница для подобласти A дерева поиска боль­ше, чем верхняя граница какой-либо ранее просмотренной подобласти B, то A может быть исключена из дальнейшего рассмотрения (правило отсева). Обычно, минимальную из полученных верхних оценок записывают в глобальную переменную m; любой узел дерева поиска, нижняя граница которого больше значения m, может быть исключен из дальнейшего рассмотрения.

Если нижняя граница для узла дерева совпадает с верхней границей, то это значение является минимумом функции и достигается на соответствующей подобласти.

Самым известным алгоритмом поиска пути на графе является алгоритм Дейкстры [2, 3]. Суть алгоритма состоит в следующем.

Каждой вершине графа сопоставим метку — минимальное известное расстояние от этой вершины до начальной. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Расширением алгоритма Дейкстры является алгоритм А* [5]. Он поэтапно рассматривает все пути, ведущие от начальной вершины в конечную до тех пор, пока не найдёт маршрут с минимальной стоимостью. Данный алгоритм является информированным алгоритмом поиска, и за счет этого, выполняет поиск в глубину.

Рассматриваемый алгоритм работает до тех пор, пока значение функции f(x) найденного маршрута, не будет меньше значения оценки любого другого маршрута в приоритетной очереди (либо пока не будет просмотрено все дерево возможных решений).

Также существуют различные модификации алгоритма А*, производящие некоторые оптимизации по тому или иному параметру.

Простейший способ сокращения потребностей в памяти для поиска А* состоит в применении идеи итеративного углубления в контексте эвристического поиска. Реализация этой идеи привела к созданию алгоритма А* с итеративным углублением (Iterative-DeepeningА* — IDA*) [6].

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

Задача маршрутизации транспорта объединяет в себе задачу о коммивояжере [6] и задачу о ранце [5]. Задача маршрутизации включает в себя возможность работы с парком автотранспортных средств с ограничениями грузоподъемности и использует ориентированный дорожный граф с нерегулярным весом ребер. Кроме того, должно выполняться условие доставки «точно в срок».

В общем математическом виде задачу транспортной логистики можно представить как функцию (Opt) от следующих параметров: длины маршрута (l), времени передвижения транспортного средства (t), текущей стоимости топлива (p), соотношения оптимальности выбранного маршрута ко всем возможным (m/n), процент брака продукции или сырья в пути (b), процент отказа и сбоев транспорта (q), планов управленцев (P), а также ожиданий клиентов (K). Результат можно представить в виде формулы (1):

              (1)

Математически пройденное расстояние при движении транспортного средства можно измерить благодаря использованию значений точек координат на плоскости (в данном случае понимается в пространстве, используя географические и картографические данные). Пройденный маршрут схематично можно представить в виде (рисунок 1).

Рис. 1. Упрощенный вид маршрута транспортного средства при выполнении поставок или предоставление других видов обслуживания

Таким образом образуется вектор AB. Очевидно, что с координатами A (x₁, y₁) и B (x₂, y₂) при условиях правила равенства квадрату длины вектора сумме квадратов его координат, можно определить расстояние между точками A и B по формуле (2):

                      (2)

В общем случае расстояние d между точками A (x1, y1) и B (x2, y2) определяется по формуле (3):

                     (3)

Полученная формула позволяет находить расстояния между любыми двумя точками плоскости, если только известны координаты этих точек. Географическая система координат обеспечивает возможность идентификации любой точки на поверхности земного шара благодаря совокупности цифр и обозначений буквами. Этими точками являются данные позиции по вертикали и по горизонтали транспортного средства на карте. Широта определяется как угол между плоскостью экватора и прямой, проходящей через исследуемую точку (в виде нормали к поверхности базового эллипсоида). Долгота точки на поверхности Земли определяется как угол в восточном или западном направлении от основного меридиана к другому, проходящей через эту точку. Системы компьютерной картографии на сегодняшнее время решают необходимости проведения сложных расчетов и позволяют с очень высокой точностью определить координаты точек на картографической плоскости самостоятельно.

Однако движение транспортного средства трудно представить в виде прямой линии или отрезке. Система его мониторинга будет работать по принципу постоянного обновления данных относительно координат местонахождения объекта. Каждые десять секунд будет происходить синхронизация данных с сервером от клиентской части с новыми текущими координатами. Таким образом пройденное расстояние автотранспортом может быть представлена ​​(и она действительно так будет выглядеть на карте во время мониторинга) как совокупность пройденных точек.

Доставка товаров осуществляется парком автотранспортных средств в соответствии со списком заявок на доставку. Каждое транспортное средство имеет определенную грузоподъемность, что накладывает ограничения на суммарный вес перевозимых товаров. Товары также характеризуются определенным весом.

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

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

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

Таким образом, для начала необходимо формализовать задачу таким образом, чтобы её решение можно было закодировано в виде вектора («генотипа») генов, где каждый ген может быть битом, числом или неким другим объектом. В классических реализациях ГА предполагается, что генотип имеет фиксированную длину. Однако существуют вариации ГА, свободные от этого ограничения.

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

На этапе селекции отбирается оптимальная популяция для дальнейшего размножения. Обычно берут определённое число лучших по приспособленности. Имеет смысл также отбрасывать “клонов”, т.е. особей с одинаковым набором генов.

Программная реализация алгоритма автоматизации работы по учету отправки и прибытия грузов транспортной компании на основе многоальтернативной маршрутизации грузоперевозок

Для реализации поставленной задачи мониторинга транспортных средств предприятия будет использована навигационная система дистанционного спутниковой связи. Она функционирует по следующим принципам: на транспортное средство устанавливается специальный пользовательский терминал, который автоматически связывается со спутниковой системой глобального позиционирования GPS (GlobalPositioningSystem) и определяет географические координаты местоположения объекта [6].

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

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

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

API определяет функциональность, которую предоставляет разработанная программа (модуль, библиотека), при этом API позволяет абстрагироваться от того, как именно эта функциональность реализована.

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

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

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

Модуль MapComp – модуль компонента карты. Он отвечает за визуальное представление карты и предоставляет методы работы с картой, такие как масштабирование, скроллинг и выделение объектов.

Планирования доставки/приема груза вынесено в отдельный модуль MapEdit (рис. 1). Данный модуль отвечает за редактирование данных о грузе, добавление и удаление объектов на карте.

Вид окна планирования доставки/приема груза представлен на рис. 1. Вверху окна располагается панель инструментов, на которой расположены кнопки автоматизирования и оптимизирования рейсов по отправке грузов. Слева располагается панель свойств выделенного объекта. Редактирование свойств объекта производится непосредственно в панели свойств.

Рис.1. Окно планирования доставки/приема груза

Для расчета оптимальной скорости движения по той или иной дороге в течения дня применяется соответствующее диалоговое окно (рис. 1), которое вызывается нажатием кнопку с номером груза, к примеру, «3011»в панели свойств объекта.

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

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

Разработана структура специального проблемно-ориентированного программного обеспечения в соответствии с архитектурой МVС.

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

Проанализированы входные и выходные данные системы маршрутизации. На основе анализа разработана структура базы данных программного средства.

Разработана геоинформационная составляющая в составе системы маршрутизации. Реализован интерфейс взаимодействия с электронными картами в открытом польском формате.

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

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

Заключение

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

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

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

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

1. Подвальный Е.С. Плотников O.A. Решение задачи поиска оптимального пути между двумя точками на графе с нерегулярным весом ребер // Вестник ВГТУ. — №8., Выпуск 6. — 2012. — с. 22-27
2. Подвальный, С.Л. Многоальтернативные системы: обзор и классификация / Подвальный С.Л.  // Системы управления и информационные технологии. – 2012. – № 48 (ч. 2). – С. 4-13.
3. Тимшина, Д.В. Алгоритмы сортировки для автоматизации решения задачи информационной логистики / Д.В. Тимшина, А.О. Максюта // Вестник академии знаний. – 2014. – № 3 (ч. 10). – С. 29-38.
4. Шмаков, Н.В. Автоматизация работы на малых предприятиях / Н.В. Шмаков, Ю.Г. Некрасов // Механики XXI Веку. – 2016. – № 15. – С. 95-99.
5. Abdenebaoui, L. Modeling of decentralized processes in dynamic logistic networks by means of graph-transformational swarms / AbdenebaouiL., KreowskiH.J. // LogistRes. – 2016. -Vol. 16, No. 20. -P. 1-13.
6. Yue, Y. Micro-simulation model of two-lane freeway vehicles for obtaining traffic flow characteristics including safety condition / Yue Y., Luo S., Luo T. // J. Mod. Transport. – 2016. – Vol. 24, No. 3. – P. 187-195.
7. Васильев С.Н., Рыбанов А.А. Исследование программных средств оптимальной укладки грузов в транспортное средство//NovaInfo.Ru. 2015. Т. 2. № 32. С. 14-18.
8. Лебединский А.И., Рыбанов А.А. Автоматизация мониторинга топлива в резервуарах азс на базе измерительного комплекса “Струна” с целью повышения эффективности принимаемых решений специалистом отдела логистики//Молодой ученый. 2014. № 7. С. 35-40.
9. Рыбанов А.А., Усмонов М.С.О., Попов Ф.А., Ануфриева Н.Ю., Бубарева О.А. Информационные системы и технологии//ЦЕНТР НАУЧНОЙ МЫСЛИ (г. Таганрог); Научный редактор И. А. Рудакова; Редакционная коллегия: Рудакова И.А., Гребенщиков Г.Ф., Акутина С.П., Краснолуцкий В.П. Москва, 2013. Том Часть 4 Информационные системы и технологии.

Все статьи автора «Шкондин Антон Юрьевич»