Компьютерные системы принятия решений в задачах маршрутизации транспорта на графах

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

В России валовая добавленная стоимость по виду экономической деятельности «Транспорт и связь» в 2015 году составила 5304,8 млрд рублей (удельный вес в экономике России – 7,3%) [8]. Грузооборот автотранспорта в России за 2014 г. равен 246 млрд тонно-километров, при этом, как показывают исследования [1], в среднем при осуществлении маршрутов 36% пути транспорт передвигается пустым, а средняя загруженность автотранспорта равна 60%, что говорит о неэффективности выбранного решения при составлении маршрутов.

Задача маршрутизации транспорта – это развитие задачи k-коммивояжеров, где каждого клиента (аналог понятия «город» в задаче коммивояжера) характеризуют числа, определяющие потребность в различных видах товаров, а каждое транспортное средство (замена понятия «коммивояжер») имеет ограничение по грузоподъемности. Оптимальное расписание маршрутов должно минимизировать расходы на удовлетворение спроса клиентов, связанные с затратами на стоимость использования машин и осуществления маршрутов. Решение задачи маршрутизации транспорта является затратным с точки зрения вычислительных ресурсов.

ГРНТИ 28.17.19

Юрий Михайлович Васильев – аспирант Санкт-Петербургского государственного экономического университета.

Статья поступила в редакцию 11.05.2017.

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

• •    минимизация некоторой комбинации времени и расстояния;

• •    сокращение затрат на обслуживание машин и выплат рабочему персоналу, связанному с транспортировкой.

Ограничения задачи часто зависят от бизнес-процесса, выстроенного в компании, для которой решается задачи маршрутизации транспорта, а также специфики области применения [4]. Новая отличительная черта задачи (бизнес-правило, практика, запрет) может в корне поменять понимание того, что такое хорошее решение, и какое решение является допустимым. В научной литературе исследовано большинство типов ограничений задачи, но часто изолированно друг от друга.

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

Получаем, что вершины маршрута в задаче маршрутизации транспорта с временными окнами будут характеризовать время прибытия в вершину и время начала обслуживания. Добавление временных окон также усложняет визуализацию решения. Как правило, для задачи маршрутизации транспорта с временными окнами получить оптимальное решение сложнее, чем для классической задачи [2].

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

Точные методы решений используются на практике только для относительно небольших по объему исходных данных (до 50 клиентов) [5]. Как следствие, на практике широкое распространение получили эвристические алгоритмы, которые зачастую дают результат, отличный от оптимального, но за приемлемое расчетное время. Однако, при изменении условий задачи, например, при добавлении нового ограничения, возникает необходимость в разработке нового алгоритма решения (который может кардинально отличаться от предыдущего варианта). Более того, учет новых ограничений может сильно увеличить продолжительность расчета.

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

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

Анализ решения задачи маршрутизация транспорта включает использование графов при визуализации. Проблема размещения графа – это задача по поиску наилучшего способа укладки графа на плоскости для улучшения восприятия информации человеком. Информация, соответствующая вершинам и ребрам, может быть передана посредством названий, подписей, различного местоположения объектов, различных цветов, толщиной линий, размером вершин, направлением ребер и т.д. Для каждого графа можно создать огромное число вариантов укладок, при этом каждая укладка может акцентировать внимание на различные свойства и связи графа и иметь различный уровень «читаемости» для человека [3].

Человек

Исходные данные

Решение

Модель

Алгоритм ЗМТ

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

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