Методы оптимизации маршрутов перевозок грузов

Общие принципы оптимизации маршрутов перевозки грузов

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

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

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

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

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

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

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

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

Оптимизация маршрутов перевозок грузов методом «метлы»

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

В соответствии с данным методом все вершины транспортной сети разбиваются на три множества:

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

Сначала выбирается начальная вершина сети, расстояние от которой до остальных вершин необходимо определить. Этой вершине присваивают расстояние, равное 0. Остальным вершинам присваивают расстояние, равное М (очень большое число).

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

Оптимизация маршрутов перевозок грузов методом потенциалов (распределительным методом)

Первый точный метод решения транспортной задачи был предложен в 1949 году Л. В. Канторовичем и М. К. Гавуриным. Он получил название распределительный метод или метод потенциалов. По сути этот метод представляет собой детализацию метода последовательного улучшения плана применительно к транспортной задаче. Метод потенциалов позволяет, отправляясь от некоторого опорного плана перевозок, построить решение транспортной задачи за конечное число итераций (шагов).

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

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

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