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

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

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

Афоничев Николай Юрьевич

Аннотация

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

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

оптимальный маршрут перевозка транспортный

Введение

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

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

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

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

Постановка задачи

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

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

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

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

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

Теория

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

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

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

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

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

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

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

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

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

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

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

«Существует множество алгоритмов, которые могут быть применены при определении оптимального маршрута. Самым простым является метод прямого перебора всех возможных путей и сравнения их между собой с точки зрения выполнения критерия оптимальности (переборный метод). Этот метод эффективен для небольшого количества стопов и перегонов (вершин и ребер в графе полигона) - не более 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 будет определен при помощи алгоритма Дейкстры). Кроме этого алгоритм Дейкстры будет использован в качестве основного блока алгоритма Йена, вычисляющего варианты наиболее близких к оптимальному маршруту путей.

Результаты

На рис. 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/

Размещено на Allbest.ru