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

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

Логистика в сфере лесопромышленного комплекса и биоэнергетики стала одним из важных направлений работы, проводимой в течение нескольких последних лет на лесоинженерном факультете Петрозаводского государственного университета, в частности, в рамках федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» и ряда международных проектов. Одной из ее задач является разработка компьютерной информационно-вычислительной системы для поддержки принятия решений в сфере лесопромышленной логистики (КИВС ЛПЛ) [3, 4, 5, 6, 7]. Эта система базируется на применении географических информационных систем, методов имитационного моделирования и оптимизации.

Для обеспечения функционирования КИВС ЛПЛ необходимо было в числе прочего разработать алгоритмы и подпрограммы для поиска оптимальных маршрутов вывозки древесины. Основой для работы этих алгоритмов стала ГИС-модель сети лесовозных автомобильных и железных дорог, по сути дела, представляющая собой граф.

Существует несколько подходов к определению оптимальных маршрутов на графе. Одним из самых простых и точных является алгоритм Дейкстры (Dijkstra) [8]. Алгоритм использует три массива из N чисел в каждом. N равняется числу узлов графа. Первый массив S содержит метки, принимающие два значения: 0, если узел еще не рассмотрен, и 1, если узел рассмотрен. Второй массив B содержит текущие кратчайшие расстояния от исходной точки до соответствующего узла. Третий массив C содержит номера вершин – k -ый элемент массива С ( k ) есть номер предпоследней вершины на текущем кратчайшем пути из начальной точки до узла с номером k .

Шаг 1. В цикле от i = 1 до N заполнить нулями массив S и числами i массив C .

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

Шаг 3. Присвоить значение 1 элементу массива S , соответствующему исходной точке маршрута, и значение 0 элементу массива C , соответствующему исходной точке маршрута.

Шаг 4. Определить список узлов графа, для которых элемент массива S имеет значение 0.

Шаг 5. Среди узлов из списка, найденного на шаге 4, найти тот, для которого значение элемента массива B наименьшее. Пусть номер найденного узла j .

Шаг 6. Присвоить значение 1 элементу массива 5 , соответствующему узлу, найденному на шаге 5: 5(j ') = 1.

Шаг 7. Для всех к = 1,2... N , если B ( k ) >  B(j' )+ A(j,k ), то присвоить B(к ) = B(j' )+ A (j,k ) и C(к ) = j. Здесь A(j,k ) - затраты на перевозку одного куб. м по дуге от узла j до узла к . Если такая дуга отсутствует, A (j,k ) равняется условно бесконечно большому значению.

Шаг 8. Если все элементы массива 5 равны 1, перейти к шагу 10.

Шаг 9. Перейти к шагу 4.

Шаг 10. Вставить в маршрут конечный узел.

Шаг 11. Для конечного узла определить значение массива C . Пусть это значение равно z .

Шаг 12. Вставить в маршрут узел с номером z .

Шаг 13. Если C(z ) = z , то перейти к шагу 16.

Шаг 14. z = C ( z ).

Шаг 15. Перейти к шагу 12.

Шаг 16. Прочитать маршрут в обратном порядке, от узла, вставленного последним, до узла, вставленного первым.

Маршрут, найденный на 16 шаге, и будет оптимальным.

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

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

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

Алгоритм использует четыре массива из N чисел в каждом. Как и в алгоритме Дейкстры, N равняется числу узлов графа. Массивы B и C имеют тот же смысл, что и таким же образом обозначенные массивы в алгоритме Дейкстры.

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

Реализация предложенного алгоритма состоит в выполнении следующих шагов:

Шаг 1. В цикле от i = 1 до N заполнить нулями массив 5 и числами i массив C .

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

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

Шаг 4. Присвоить значение 0 элементу массива C , соответствующему исходной точке маршрута.

Шаг 5. Сделать активным исходный узел маршрута. Шаг 6. Присвоить значение 2 элементу массива 5 , соответствующему активному узлу.

Шаг 7. Определить список узлов графа со значением массива 5 меньше 2, непосредственно связа-ных дугами с активным узлом.

Шаг 8. Для всех узлов найденного на предыдущем шаге списка присвоить 5 ( к ) = 1; если B ( к ) >  B(j' )+ A(],к ), то присвоить B ( к ) = B(j' )+ A(],к ) и C ( к ) = j . Здесь к - номер узла из рассматриваемого списка; j - номер активного узла; A (],к ) - затраты на перевозку одного куб. м по дуге от узла j до узла к .

Шаг 9. Среди узлов из списка, найденного на шаге 7, найти тот, для которого сумма значений элементов массивов B и H наименьшая. Сделать его активным.

Шаг 10. Если активным является конечный узел маршрута, перейти к шагу 12.

Шаг 11. Перейти к шагу 6.

Шаг 12. Вставить в маршрут конечный узел.

Шаг 13. Для конечного узла определить значение массива C . Пусть это значение равно z .

Шаг 14. Вставить в маршрут узел с номером z .

Шаг 15. Если C ( z ) = z , то перейти к шагу 18.

Шаг 16. z = C ( z ).

Шаг 17. Перейти к шагу 14.

Шаг 18. Прочитать маршрут в обратном порядке, от узла, вставленного последним, до узла, вставленного первым.

Благодаря тому, что в каждом цикле этого алгоритма проверяются только несколько узлов, ближайших к рассматриваемому, время его работы уже не зависит от общего числа узлов графа. Оно зависит от расстояния между исходной и конечной точками маршрута, измеряемого в дугах, а также от степени разветвленности графа. Реализация данного алгоритма в создаваемой КИВС ЛПЛ показала, что время поиска маршрута сократилось до десятков и единиц секунд.

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

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

Первые опыты эксплуатации КИВС ЛПЛ показали оправданность такого решения при составлении оперативных транспортных планов на сроки от нескольких дней до нескольких недель. Однако дальнейшее развитие разрабатываемых подходов показало также и перспективность составления планов работы на более длительные периоды (квартал, полугодие, год) [5]. В этом случае появляется возможность решения таких стратегических задач, как обоснование числа и характеристик автомобилей на вывозке древесины, обеспечение баланса производственных мощностей на заготовке и вывозке в течение года и т. п.

В данном случае значительно увеличивается число маршрутов, требующих определения, т. к. растет число делянок, участвующих в расчете. Число делянок, на которых ведутся работы в течение года, для лесопромышленного предприятия средней величины составляет около 100. Таким образом, число маршрутов может достигать 500 и более, суммарное время их определения, даже с использованием эвристического алгоритма, начинает измеряться часами.

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

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

Для подтверждения эффективности использования алгоритма Дейкстры в случае определения множества маршрутов, были выполнены измерения времени отыскания всех маршрутов, необходимых для планирования вывозки древесины на графе, включающем 5 делянок, 3 предприятия-потребителя лесоматериалов, 3 железнодорожные станции и 1 гараж. Общее число маршрутов, требующих своего определения на таком графе, равнялось 66 с учетом возможности использования железных дорог для транспортировки древесины. В первом случае использовался эвристический алгоритм на всех парах узлов, во втором – алгоритм Дейкстры.

Время нахождения всех 66 маршрутов эвристическим методом на компьютере с процессором Intel Pentium 4,3 ГГц c 2 ГБ ОЗУ составило около 39 мин, а с помощью алгоритма Дейкстры – 21 мин, т. е. на 46 % меньше. На компьютере с процессором Intel Core2 6300, 1,8 ГГц c 1 ГБ ОЗУ это время составило соответственно 8,5 и 3,5 мин, т. е. на 59 % меньше. Это полностью подтверждает правильность выбранного подхода при построении КИВС ЛПЛ.