Systems. Methods. Technologies 4 (40) 2018

Системы Методы Технологии. А.П. Мохирев и др. Оптимизация маршрутов … 2018 № 4 (40) с. 132-140 133 Введение На сегодняшний день важнейшим фактором, сдер- живающим возможности наращивания объемов заго- товки и доставки потребителю древесины, является не- решенность задачи оптимизации маршрутов транспор- тировки [1; 2]. При организации лесозаготовительного процесса неизбежно встает вопрос выбора: на каком участке, в какой период времени наиболее выгодно заготавливать древесину, какой транспортный маршрут будет опти- мален для доставки заготовленной древесины, какой технологией возможна разработка лесного участка, на каком участке наиболее эффективно расположить склад и т.д. В настоящее время задача развития транспортной инфраструктуры на территории лесосырьевой базы, ос- ваиваемой много лет, потеряла свою актуальность. За долгие годы эксплуатации построено достаточно дорог для вывозки древесины, однако в большинстве случаев для целей транспортировки создаются дороги времен- ного типа. Получается, что существует множество раз- личных маршрутов доставки древесины, но их исполь- зование носит сезонный характер. Природно- климатические, почвенно-грунтовые условия в различ- ные периоды года значительно разделяют дороги по затратам на их восстановление, обслуживание, себе- стоимости транспортировки древесины, пропускной способности. Это обуславливает актуальность разработки ком- плексной математической модели, а на ее основе — методики оптимизации маршрутов транспортировки древесины. Реализация подобной математической мо- дели должна привести к снижению затрат на транспор- тировку и хранение лесных ресурсов. Разработано большое количество алгоритмов реше- ния задач нахождения оптимальных маршрутов [3–5]. Многие из них направлены на определение кратчайше- го пути [6], многие — на преодоление маршрута за ми- нимальное время [7; 8],однако на сегодняшний день наиболее актуально нахождение минимальной стоимо- сти маршрута [9]. При этом главная задача состоит в нахождении маршрутов минимальной стоимости дос- тавки определенного количества древесины с разных лесных участков в транспортной сети в заданное коли- чество периодов времени. В данной статье приведена методика, основанная на исследованиях А.В. Боженюк [10], Е.М. Герасименко [11], К.П. Рукомойникова [12], Е.В Платоновой [13] и других исследователей. Предложенный алгоритм позволяет находить опти- мальный маршрут перевозки древесины от начального пункта к конечному в течение нескольких временных периодов, находить минимальный по стоимости мар- шрут транспортировки, а также максимальный объем древесины, который можно транспортировать по уча- сткам дороги, учитывая пропускную способность и временные периоды [14]. Таким образом, данная мето- дика позволяет найти оптимальный маршрут транспор- тировки с учетом хранения древесины на складе и ис- пользованием необходимого вида транспорта (автомо- бильного и водного) с лесных участков до потребителя. Постановка задачи исследования. Математиче- ское моделирование процесса вывозки древесины с лесного участка до пункта доставки представлено в ви- де транспортной сети —связного ориентированного графа G=(V, E) , где существует V —множество вершин х i (i=1,…,n) , Е —множество дуг ( x i ,x j ). Одна из вершин соответствует лесному участку (источник s ), другая — пункту доставки (сток t ) , остальные —промежуточным пунктам; дуги соответствуют участкам дорог, соеди- няющих указанные пункты. Каждой дуге ( x i ,x j ) графа поставлены в соответствие неотрицательное число u ij , называемое пропускной способностью дуги, и поток f ij —перевозимое по дан- ному участку количество груза. Кроме того, каждой дуге сопоставлено неотрицательно число c ij — стоимость перевозки единицы потока по дуге. Пропу- скная способность u ij дуги ( x i , x j ) транспортной сети оп- ределяет наибольшее значение потока, которое может протекать по этой дуге [2; 8]. Критерием оптимальности маршрута является ми- нимальная стоимость транспортировки древесины с лесного участка до потребителя за суммарное количе- ство периодов времени. Определяется маршрут мини- мальной стоимости от s  к t  методом Басакера– Гоуэна, в котором на этапе поиска кратчайшего пути использует- ся алгоритм Форда– Беллмана [10; 11]. В связи с тем, что в реальных условиях пропускные способности дуг, стоимости перевозки единицы потока по дуге и поток q , который требуется перевезти по сети, не могут быть точно известны и меняются в зависимо- сти от периода θ, в котором осуществляется перевозка, необходимо рассматривать нечеткие числа   θ ij u ~ ,   , ~ θ ij c   , ~ θ ij f q ~ . Так как параметры дуг являются нечеткими числа- ми, зависящими от периода прохождения потока по ду- ге, то задача сводится к нахождению минимальной стоимости транспортировки от источника заданного количества потока в нечеткой динамической транс- портной сети   EVG ~, ~  [15–17]. В рассматриваемом нами графе   EVG ~, ~  E ~ —нечеткое множество дуг, где в качестве степени принадлежности   j i E xx , ~  ду- ги ( x i , x j ) множеству E ~ применяется нечеткая пропуск- ная способность дуги [3], а время прохождения потока по дуге ( x i , x j ) не задается явно, а учитывается при опре- делении ее пропускной способности. Кроме того, задан временной горизонт Т ={1,…, р }, определяющий, что все единицы потока, отправленные из источника, должны прибыть в сток не позднее, чем в период р . Математическая модель задачи имеет вид [16; 17]:       , θ~θ~ 1 ~ , min f c ij p E xx ij j i       (1)         , ,~ θ~ θ~ 1 1 s xq f f i p ki x Г x ij xГ x i k i j                    (2)