УДК 656.022.4:519.168:519.852.23

Определение оптимального маршрута перевозки грузов

,

Омский государственный университет путей сообщения,

Омский государственный технический университет

Омск, Россия

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

Ключевые слова – транспорт, логистика, оптимальный маршрут, граф, критерий оптимальности, алгоритм, структурная схема.

I. ВВЕДЕНИЕ

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

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

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

НЕ нашли? Не то? Что вы ищете?

Поэтому для любого занимающегося грузоперевозками предприятия, работа которого строится на принципах транспортной логистики, актуальной является за­дача оптимизации процесса перевозки [1].

II. ПОСТАНОВКА ЗАДАЧИ

Предлагается недорогой способ реализации многовариантного решения частного случая практической логистической транспортной задачи о нахождении оптимального маршрута перевозки груза при условии наличия множества альтернативных маршрутов в соответствии с заданным критерием оптимальности, не основанный на переборе всех возможных маршрутов. В качестве критериев оптимальности маршрута предлагаются: минимальная длина маршрута, минимальное время и минимальная стоимость перевозки груза. Полученные варианты маршрутов должны включать в себя оптимальный с точки зрения заданного критерия маршрут (вариант № 1), и еще Х-1 вариантов маршрута наиболее близких к оптимальному варианту маршрута (варианты № 2, № 3, …, № Х). Способ гарантирует нахождение маршрутов с вероятностью 100% (если они существуют). Многовариантность решения задачи предусматривается, исходя из практических соображений, для того, чтобы лицо, принимающее решение (ЛПР), имело возможность окончательного выбора одного или сразу нескольких маршрутов с учетом дополнительных (иногда неформализуемых) факторов. В этом заключается одно из основных преимуществ предлагаемого метода по сравнению с другими, имеющимися способами определения оптимальных маршрутов.

«Если территория, на которой осуществ­ляется деятельность предприятия, называемая рабочим полигоном предприятия или просто полигоном, имеет достаточно большую, сложную и разветвлен­ную сеть потенциальных (возможных) путей доставки грузов, то одним из пу­тей частичного решения указанной задачи является выбор такого маршрута пе­ревозки груза от отправителя к получателю, который бы являлся оптимальным с точки зрения некоторого заданного критерия» [1, c. 7].

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

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

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

III. ТЕОРИЯ

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

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

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

Основными характеристиками перевозимого груза считаются вес груза и максимальное время, которое груз может находиться в пути (этот пара­метр актуален для скоропортящихся грузов).

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

На процесс пере­возки груза накладываются следующие ограничения:

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

- движение по любому из потенциальных маршрутов от пункта отправле­ния до пункта прибытия происходит непрерывно, без остановок и за­держек;

- движение транспортного средства по перегону происходит с допусти­мой на этом перегоне скоростью.

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

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

«Существует множество алгоритмов, которые могут быть применены при определении оптимального маршрута. Самым простым является метод пря­мого перебора всех возможных путей и сравнения их между собой с точки зре­ния выполнения критерия оптимальности (переборный метод). Этот метод эф­фективен для небольшого количества стопов и перегонов (вершин и ребер в графе полигона) – не более 10 – 15 стопов. Для определения оптимального пути на полигонах, содержащих большее количество стопов и перегонов, может быть применен один из методов при­кладной математики, позволяющих гарантированно находить оптимальный (кратчайший) маршрут от одной вершины графа до другой (или до других) за конечное количество итераций» [6, c. 15].

Это известные и хорошо зарекомендовавшие себя методы, основанные на использовании алгоритмов Дейкстры (Dijkstra’s algorithm), Дейкстры – Грибова (улучшенный алго­ритм Дейкстры), Флойда – Уоршелла (Floyd – Uorshell), Джонсона (Johnson), Беллмана – Форда (Bellman – Ford), Левита (Levit) и т. п. [7], многие из которых имеют практическое применение. Так, например, прото­кол OSPF (Open shortest path first), основанный на алгоритме Дейкстры [2], опре­деляет в процессе маршрутизации оптимальный маршрут передачи данных в средних по размеру (до 100 маршрутизаторов) распределенных цифровых IP-сетях. Еще одним алгоритмом, применяемым в протоколах маршрутизации IP-сетей, является алгоритм Беллмана – Форда, используемый в алгоритме длины вектора (Distance vector algorithm), который в свою очередь используется в RIP-протоколе маршрутизации [2]. Недостатком указанных алгоритмов является увеличение времени на определение оптимального маршрута с ростом количества вершин и ребер графа полигона. Достоинствами этих алгоритмов по отношению ко всем другим являются: гарантированное определение оптимального маршрута (если он существует), простота, невысокие требования к аппаратным ресурсам и, как следствие минимальные затраты на реализацию, надежность, подтвержденная долговременным практическим использованием в протоколах маршрутизации цифровых IP-сетей.

К другому классу алгоритмов могут быть отнесены прежде всего извест­ные эвристические методы, изначально разработанные для решения классической «задачи коммивояжера», в соответствии с которой торговец должен побы­вать в ограниченном количестве заранее определенных городов таким образом, чтобы, начиная с города А, идти кратчайшим путем, проходящим через все ос­тальные города только один раз и приводящим обратно в А. Это алгоритмы наискорейшего спуска (градиентный метод и его модификации), оценочных (штрафных) санкций, минимакса (Моргенштерна – фон Неймана), альфа-бета процедура.

Существует множество других, более сложных алгоритмов определения оптимального пути или путей (как точных, так и приближенных) в больших и сложных системах (больших, плотных графах, насчитывающих сотни и более вершин), часть из которых использует в качестве основной составляющей один из указанных выше более простых алгоритмов (прежде всего Дейкстры и Белл­мана – Форда). Это приближенный алгоритм Джеффа, неадаптивный и адап­тивный алгоритмы маршрутизации со множеством ограничений (TAMCRA и SAMCRA), приближенный алгоритм Чена, алгоритм случайного поиска Кор­маза и Крунза, A*Prune-алгоритм Лиу и Рамакришнана и др.

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

При решении поставленной задачи для определения оптимального маршрута (вариант № 1) предлагается использовать алгоритм Дейкстры как наиболее простой и недорогой в реализации, надежный и доказавший свою эффективность в реальной работе в маршрутизаторах IP-сетей. Это итерационный алгоритм. При поиске оптимального маршрута алгоритм не перебирает все возможные маршруты, а использует оригинальную стратегию поиска оптимального пути гарантирующую нахождение оптимального маршрута за количество итераций, меньшее, чем количество потенциальных маршрутов. Количество итераций не поддается предсказанию и зависит от структуры графа полигона, степени его связности и расположения на графе начального и конечного пунктов маршрута. Для решения задачи нахождения маршрутов вариантов № 2, № 3, …, № Х предлагается использовать алгоритм Йена (Ien’s algorithm) [8], который позволяет находить k ближайших к оптимальному пути маршрутов без циклов последовательного перебора при условии, что оптимальный маршрут ранее был определен (в нашем случае маршрут варианта № 1 будет определен при помощи алгоритма Дейкстры). Кроме этого алгоритм Дейкстры будет использован в качестве основного блока алгоритма Йена, вычисляющего варианты наиболее близких к оптимальному маршруту путей.

IV. РЕЗУЛЬТАТЫ

На рис. 1 приведена структурная схема реализации задачи поиска маршрутов перевозки грузов вариантов № 1, № 2, …, и № Х с использованием алгоритмов Дейкстры и Йена. Программная реализация указанной задачи проводилась в ходе работы над курсовыми проектами в Омском государственном университете путей сообщения на таких языках программирования как С++ и Pascal в таких объектно-ориентированных средах быстрой разработки приложений как C++ Builder и Delphi.

Рис. 1 Структурная схема реализации

задачи многовариантного определения оптимального маршрута

Рис. 1, лист 2

Библиографический список

[1] , Определение оптимального маршрута перевозки грузов: Учебное пособие / . Омск.: Омский государственный университет путей сообщения, 2010. – 74 с.

[2] Технология корпоративных сетей. Энциклопедия / М. Кульгин. СПб.: Питер, 2000. – 704 с.

[3] , Модели и методы теории логистики. 2-е изд. / Под ред. . СПб.: Питер, 2008. – 448 с.

[4] , Транспортная логистика: Учебник для транспортных вузов / Под общей ред. . М.: Издательство «Экзамен», 2003. – 512 с.

[5] , Мультимодальные перевозки и транспортная логистика: Учебное пособие / . М.: ТрансЛит, 2007. – 272 с.

[6] , Афоничев оптимального маршрута перевозки грузов: Электронное учебное пособие / , , Омск.: ФГБОУ ВПО «Омский государственный университет путей сообщения», 2013. ФГУП «Информрегистр» № гос. регистрации обязат. экз. электрон. изд. – 0321300119 (№ регистр. св-ва 29417).

[7] Алгоритм Дейкстры, Флойда, Беллмана-Форда [Электронный ресурс] / Режим доступа: http://www. intuit. ru/studies/courses/12181/1174/lecture/25268?page=3

http://www. intuit. ru/studies/courses/12181/1174/lecture/25268

[8] Алгоритмы Беллмана-Форда, Йена, волновой алгоритм [Электронный ресурс] / Режим доступа: http://algolist. manual. ru/maths/graphs/shortpath/

Сведения об авторах

. Ведущий программист управления информационных технологий Омского университета путей сообщения. Научные интересы: методы поиска оптимальных решений, транспортная логистика. SPIN-код автора: 7151-3097.

. Доцент кафедры «Физика» Омского государственного технического университета. Научные интересы: методы поиска оптимальных решений. SPIN-код автора: 2777-2413.