9.2 Методы маршрутизации и распределения грузопотоков

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

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

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

Другой точный метод, используемый для решения задачи коммивояжера – метод «ветвей и границ». Данный метод является вариацией полного перебора с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных решений . Данный метод также весьма трудоемок. В связи с этим широкое распространение получили методы приближенного решения задачи, в том числе жадный и деревянный алгоритмы, метод имитации отжига, метод Кларка-Райта. Последний основан на понятии «выгоды» от объединения двух маятниковых маршрутов в один кольцевой и позволяет найти решение близкое к оптимальному (погрешность решения не превосходит в среднем 5-10%). Алгоритм Кларка-Райта позволяет решать задачу рационализации грузопотоков в сфере распределения продукции с учетом эффективной загрузки транспортных средств.

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

Рисунок 9.2 –Пример сети распределения продукции

(0 – распределительный склад; 1, 2….12 – потребители)

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

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

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

Также широко распространены модификации транспортной задачи:

• транспортная задача с приоритетами возникает, если при обеспечении удовлетворения потребителей необходимо обеспечить обслуживание в определенной очередности (динамическая транспортная задача);

• многопродуктовые транспортные задачи;

• задача с избытком (дефицитом) отправляемой продукции (открытые транспортные задачи);

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

• транспортные задачи с запретами, в случае если поставки по некоторым каналам оказываются недопустимыми;

• задачи с ограничением пропускной способности коммуникаций.