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

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

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

-- маршрут для персонала, сопровождающего груз (водителя и экспедитора), не должен быть новым;

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

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

-- состояние криминальной обстановки по маршруту;

-- стоимость груза;

-- время доставки, на которое влияет пропускная способность дороги в различное время суток и день недели;

-- водитель или экспедитор должен иметь возможность осуществлять оперативную связь по маршруту движения.

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

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

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

Методика описания модели сети дорог с учетом различных факторов, влияющих на процесс доставки грузов

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

Популярные алгоритмы поиска кратчайшего маршрута работают на взвешенных графах [5-7]: алгоритм Дейкстры; алгоритм Беллмана-Форда; алгоритм поиска А*; алгоритм Флойда-Уоршелла; алгоритм Ли (волновой алгоритм). При этом вес ребер графа выражается через некоторый векторный показатель. Причем рассмотренные алгоритмы работают, преимущественно на основе скалярных или малоразмерных векторных значений весов ребер графа. В последнее время широкое распространение получила методика использования теории искусственных нейронных сетей и генетических алгоритмов при решении оптимизационных задач [8-10].

В данной работе рассматривается способ составления такого вектора с учетом стоимости, времени и безопасности доставки груза.

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

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

-- матричная функция времени следования , зависящая от времени нахождения транспортного средства на определенном участке;

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

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

-- матричная функция , учитывающая знакомство водителя или экспедитора с данным участком дороги;

-- матричная функция угроз при отдыхе на данном участке дороги , которая зависит от времени суток (светлое или темное).

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

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

-- период до начала утренних пробок;

-- период утренних «пробок»;

-- дневной период;

-- период вечерних пробок;

-- период после вечерних «пробок»;

-- ночной период.

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

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

где -- комплексная оценка доставки груза; -- оценка риска доставки груза; -- оценка стоимости доставки груза; -- оценка времени доставки груза; -- весовые коэффициенты соответствующих оценок.

Таким образом, многокритериальная задача сводится к задаче с одним критерием.

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

,

при ,

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