^^^ ЛЕСОЭКСПЛУАТАЦИЯ
УДК 634.0.3
ОПЕРАТИВНОЕ ЛОГИСТИЧЕСКОЕ УПРАВЛЕНИЕ ТРАНСПОРТНЫМ ПРОЦЕССОМ ЛЕСОЗАГОТОВИТЕЛЬНОГО ПРЕДПРИЯТИЯ
© А.П. Соколов, канд. техн. наук, доц.
Петрозаводский государственный университет, просп. Ленина, д. 33, г. Петрозаводск, Республика Карелия, Россия, 185910; e-mail: a_sokolov@psu.karelia.ru
Большое значение в оперативном управлении транспортным процессом лесозаготовительного предприятия отводится определению оптимальных маршрутов перевозки. Наиболее сложной для решения задач маршрутизации является схема «многие ко многим», которая на сегодняшний день чаще всего используется при организации транспортного процесса лесозаготовительного предприятия. В статье приводится обзор подходов, методов и инструментов, предназначенных для решения задачи синтеза транспортных планов (маршрутов доставки) на перевозке продукции лесозаготовительного предприятия. Перспективным направлением решения этой задачи следует признать гибридный подход, основанный на использовании комбинации методов линейного программирования и поиска с запретами. Этот подход позволяет в полном объеме решать задачу оперативного планирования транспортного процесса лесозаготовительного предприятия с учетом всех основных особенностей такого процесса. К отличительным характеристикам этого подхода следует в первую очередь отнести его сложность, которая, несомненно, вызвана сложностью самой задачи. Качество получаемого окончательного решения здесь сильно зависит от возможностей взаимной увязки результатов решения отдельных оптимизационных задач, решаемых на отдельных этапах этой методики. Главным недостатком подхода следует считать то, что цели двух основных решаемых задач оптимизации отличаются.
Введение
Ключевое значение в оперативном управлении транспортным процессом лесозаготовительного предприятия (ЛЗП) имеет задача определения оптимальных маршрутов перевозки. Именно в случае ЛЗП она является особо сложной по сравнению с другими отраслями производства.
Существует три схемы организации перевозочного процесса «один к одному», «один ко многим» и «многие ко многим» [6-9].
Организация перевозок по схеме «один к одному» (маятниковые маршруты) наиболее проста с точки зрения планирования, но на ЛЗП она практически не применяется.
Схема «один ко многим» применяется на ЛЗП при использования одного большого центрального нижнего склада или терминала, обычно в случае применения хлыстовой технологии заготовки древесины или технологии заготовки целыми деревьями [2, 11, 17-19, 28].
Наиболее сложной для решения задач маршрутизации является схема «многие ко многим», и именно она на сегодняшний день чаще всего используется при организации транспортного процесса ЛЗП. Эта схема имеет место во всех вариантах организации движения основного транспортного потока, в которых конечная продукция формируется или «у пня» или на погрузочной площадке (верхнем складе). В основном это варианты с использованием сор-тиментной технологии заготовки древесины. В этих вариантах готовая продукция с погрузочной площадки (верхнего склада) доставляется напрямую потребителям.
Постановка задачи
Полнее всего постановка задачи определения оптимальных маршрутов в ЛЗП изложена в работах [15, 25]. В лесосырьевой базе имеется ряд делянок, на которых ведется заготовка древесины. В процессе заготовки объем различных видов продукции на погрузочных площадках этих делянок постоянно изменяется. Причем от делянки к делянке объем и его распределение по отдельным видам продукции отличаются. По завершении работы на одной делянке комплексы лесозаготовительных машин переходят на другую, еще не разработанную делянку в соответствии с известным заранее планом заготовок. Для каждого потребителя (склада, терминала) известна месячная или недельная потребность в каждой группе видов продукции (пиловочник, балансы, дрова). В каждую такую группу может входить несколько видов продукции. Для каждой делянки и каждого потребителя могут быть заданы промежутки времени, в течение которых разрешается осуществление погрузки (разгрузки). Объемы потребления для каждого потребителя обычно задаются для недельных промежутков, маршруты движения транспортных средств должны определятся на каждый рабочий день. Маршрут может быть сборным, когда одна часть продукции забирается на одной делянке, другая - на другой, и так до достижения полной загрузки транспортного средства. Имеется заданное число транспортных средств различного назначения с разной грузоподъемностью (грузовме-стимостю). Каждое транспортное средство привязано к определенной исходной точке (гаражу, депо, складу) и имеет свой распорядок работы. Водители транспортных средств могут сменять друг друга в течение дня в определенных заданных точках. Имеется детальная информация о дорожной сети (дистанции от точки до точки, средние скорости движения по каждому участку и т. п.). Различные постановки задачи определения оптимальных маршрутов по дорожной сети описаны в работах [1, 3, 10, 13, 16, 20, 21, 30]. В подавляющем большинстве случаев они сводятся к тому, чтобы определить маршруты движения для каждого транспортного средства на каждую рабочую смену с указанием видов перевозимой продукции таким образом, чтобы общие затраты, связанные с перевозочным процессом были наименьшими.
Методы
Общая постановка классической задачи маршрутизации транспортных средств (VRP - Vehicle Routing Problem) и классификация методов ее решения приведены в работах [23, 24]. Методы решения этой задачи можно разделить на точные, эвристические и метаэвристические [24].
Точные методы основаны на полном переборе всех возможных решений и являются неэффективными при решении задач большой размерности из-за значительных временных затрат [5]. Эвристические и метаэвристические методы являются приблизительными, но позволяют найти приемлемое решение задач большой размерности за приемлемое время.
Эвристические методы подразделяются на методы конструирования маршрута (например, метод Кларка-Райта); двухфазные методы, когда клиенты сначала группируются, а потом внутри каждой группы строится маршрут методом конструирования; методы улучшения маршрута, основанные на решении задачи коммивояжера в случае единственного маршрута или на принципах локального поиска в случае с несколькими маршрутами. Применение классических эвристических методов значительно сокращает время, необходимое на поиск решения, однако получаемая при этом погрешность в среднем оценивается в 3...7 % [24].
В последние годы для решения задачи VRP широко используют так называемые метаэвристические методы: метод имитации отжига [14], метод поиска с запретами [22, 24], метод муравьиной колонии [4], метод роя частиц [27], генетические и эволюционные алгоритмы [12, 13, 29]. Преимущество данных методов перед классическими эвристическими методами, основанными на методах локального поиска, заключается в том, что метаэвристические методы в ходе решения более тщательно исследуют пространство поиска, рассматривая даже локально ухудшающие и невозможные промежуточные решения. Хотя успех применения того или иного метода во многом связан с особенностями его реализации, необходимо отметить, что метод поиска с запретами явно превосходит конкурирующие подходы и чаще всего используется сейчас для решения данной задачи [23].
Несмотря на успехи в решении VRP, эта постановка в чистом виде не подходит для решения задачи организации перевозочного процесса ЛЗП. На самом деле она пригодна только для схемы «один ко многим» в случае использования развозочных (сборных или сборно-развозочных) маршрутов, но такая схема перевозок сегодня очень редко используется на ЛЗП.
Для решения задачи УЯР в перевозочном процессе ЛЗП классическая задача должна быть существенно видоизменена и дополнена для учета ряда следующих особенностей.
Например, в работе [26] подробно описывается методика определения маршрутов автомобильного транспорта на перевозке круглых лесоматериалов, базирующаяся на методе поиска с запретами.
Существенным недостатком этой методики является то, что для ее использования заранее должно быть известно место назначения для каждой партии готовой продукции, находящейся на погрузочных площадках в лесу. В ходе решения этой оптимизационной задачи алгоритм поиска с запретами перебирает различные комбинации груженых и холостых ездок так, чтобы обеспечить наилучшее использование каждого автомобиля внутри ограниченной по времени смены, т. е. выполнить как можно больше рейсов и сократить холостой пробег.
Описанный подход решает задачу оперативного планирования только наполовину. Результаты работы этого алгоритма во многом будут зависеть от того, как будут распределены партии продукции между потребителями.
Для выполнения оперативного планирования транспортного процесса ЛЗП в полном объеме авторы работы [25] предложили гибридный метод, заключающийся в двухэтапном решении этой задачи. Сначала с использованием методов линейного программирования определяются потребители для каждой партии продукции. При этом партия может быть и сборной, затем методом поиска с запретами определяются маршруты движения отдельных автомобилей. Опишем этот подход подробнее.
На рис. 1 представлен пример дневного маршрута автомобиля на транспортировке древесины в течение рабочего дня.
Рис. 1. Дневной маршрут автомобиля на транспортировке древесины (Г - гараж; Д1...Д6 - погрузочные площадки делянок; П1...П4 - потребители; С - место пересменки; цифры над стрелками - порядок движения автомобиля)
Следует обратить внимание на то, что данный маршрут является сборным. Автомобиль может набирать полный объем лесоматериалов на нескольких делянках перед доставкой их потребителю, посещать одну и ту же делянку несколько раз в день. Также в маршрут должна быть включена точка пересменки, где заменяется водитель. Такие маршруты часто применяют на практике, поэтому методика планирования должна обеспечить возможность их оптимального синтеза.
Решение задачи состоит из двух этапов [25].
решение транспортной задачи линейного программирования; формирование ездок на основе результатов решения транспортной
задачи.
решение методом поиска с запретами; коррекция списка ездок;
переход к второму шагу, если допустимое время решения не превышено.
Ход решения может быть проиллюстрирован на простом примере для случая с одним автомобилем (рис. 2).
Рис. 2. Первый этап - генерация ездок (цифры над стрелками показывают объем лесоматериалов, транспортируемый с соответствующей делянки соответствующему
потребителю; А ... Г - ездки)
В результате решения простой транспортной задачи весь объем лесоматериалов на делянках распределяется по потребителям. Результат этого распределения показан на рис. 2 а.
На втором шаге этапа 1 с учетом грузовместимости используемых автомобилей формируются ездки, обеспечивающие наиболее полную загрузку машин. Результат этого процесса приведен на рис. 2 б. В нашем случае грузовместимость автомобиля составляет 50 м3, поэтому ездка Г получается сборной.
На этапе 2 полученные ездки оптимальным образом соединяются друг с другом, в результате чего составляются маршруты автомобилей на смену, сутки или на несколько суток. При этом минимизируется общий пробег автомобилей при условии удовлетворения всех запросов потребителей. Полученный таким образом оптимальный порядок соединения ездок показан на рис. 3 а, соответствующий ему маршрут движения автомобиля от точки к точке - на рис. 3 б.
Рис. 3. Второй этап - составление маршрута (цифры над стрелками - порядок движения автомобиля; пунктирные линии соответствуют порожнему движению,
сплошные - с грузом; А ... Г - ездки)
Этап генерации ездок. На этом этапе в ходе решения транспортной задачи определяются оптимальные с точки зрения сокращения общих транспортных издержек объемы перевозок продукции для каждой пары «точка по-грузки-точка разгрузки». Далее приступают к генерированию ездок. Для этого выполняется два шага. На первом шаге фиксируются все ездки внутри полученного оптимального транспортного плана, обеспечивающие полную загрузку автомобилей на одной точке погрузки, т. е. несборные. Оставшийся объем перевозок должен быть реализован в ходе ездок, которые формируются на втором шаге.
Эти ездки генерируются следующим образом [25].
При этом для обеспечения большей гибкости алгоритма и лучшего его соответствия реальной практике полной считается загрузка автомобиля от 85 до 100 %.
Иллюстрация второго шага процесса генерации ездок показана на рис. 4.
Б Ш "
□ Г Ш Г
Рис. 4. Формирование ездок на втором шаге: а - определение пары «точка погрузки-точка разгрузки» с наибольшим объемом перевозки (точка погрузки А); б - добавление дополнительной точки погрузки Б (объем увеличивается до 30 м3); в - добавление еще одной точки погрузки В (не входящей в оптимальный транспортный план) для обеспечения более полной загрузки автомобиля, добавление новой ездки в список ездок; г - определение следующей пары «точка погрузки - точка разгрузки» с наибольшим объемом перевозки (точка погрузки Д) и добавление этой новой ездки в список ездок, так как объем в точке Д - достаточен (цифры над стрелками объем перевозимой древесины)
Для осуществления поставленной задачи необходимо для каждой ездки определить допустимый промежуток времени, в который она может быть выполнена, а также время ее выполнения.
Для обеспечения работы алгоритма поиска с запретами, который комбинирует ездки для получения эффективного маршрута автомобиля, необходимо иметь матрицу расстояний, измеренных по имеющейся дорожной сети от последней посещаемой точки каждой сгенерированной ездки до начальных точек всех остальных ездок.
Точки пересменки и их моменты задаются включением в список ездок дополнительных специальных элементов. Точка пересменки - это ездка, в которой начальная и конечная (географические) точки совпадают, допустимый промежуток времени выполнения этой ездки определяет заданный промежуток времени пересменки, а время выполнения ездки имеет смысл времени, необходимого на осуществление самой пересменки.
Этап составления маршрутов состоит из четырех шагов: на первом шаге определяется начальное решение, на втором выполняется решение задачи с помощью алгоритма поиска с запретами, описанного в работе [24], на третьем производится ревизия списка ездок, на четвертом снова запускается алгоритм поиска с запретами для получения более точного решения.
Алгоритм поиска с запретами, предложенный в работе [22], позволяет решать задачу маршрутизации транспортных средств с учетом ограничений на допустимые периоды погрузки и разгрузки (Vehicle Routing Problem with Time Windows - VRPTW) для каждого из m имеющихся автомобилей. Маршруты определяются на графе
Узел представляет собой гараж, в котором базируются автомобили. Каждому узлу графа из множества узлов V ставятся в соответствие неотрицательные объем транспортировки q¡ (д0 = 0), время выполнения (d0 = 0 ) и
допустимый период выполнения , I. ] (где и I - неотрицательные целые
числа). Каждому ребру ставятся в соответствие неотрицательные затраты Су. Грузоподъемность и доступное время использования автомобиля к
обозначаются соответственно Qk и Тк. Решение задачи VRPTW заключается в синтезе т маршрутов на графе О так, чтобы каждый маршрут начинался и заканчивался в гараже; каждый клиент принадлежал только к одному маршруту; общая загрузка автомобиля и продолжительность выполнения транспортировки по маршруту к не превышали Qk и Тк; погрузка или разгрузка в узле 1 начиналась внутри интервала времени , I. ] и каждый автомобиль совершал свой маршрут внутри интервала времени [в0,10 ]; общие затраты на осуществление транспортного процесса были бы наименьшими.
В общем случае применения этого алгоритма каждому узлу графа соответствует определенный клиент. Клиенты объезжаются автомобилем в ходе сборного маршрута для погрузки или разгрузки. В нашем случае каждому узлу ставится в соответствие определенная ездка из списка, сгенерированного на первом этапе решения [25].
G = (V A),
V = v0, Vj,..., vn - множество узлов; A = {(v,Vj): vt,Vj e V,i ф j} - множество ребер.
В рассматриваемом случае нет необходимости обязательно включать в создаваемые маршруты все сгенерированные на первом этапе ездки, нужно только обеспечить удовлетворение всех имеющихся запросов потребителей, поэтому стандартный алгоритм решения должен быть скорректирован. Для этого в модель вводится так называемый виртуальный автомобиль. Ездки, осуществляемые виртуальным автомобилем, выполняются мгновенно, затраты, связанные с ними, равны нулю и на них не распространяются временные ограничения на посещение точек погрузки и разгрузки. Для того, чтобы обеспечить выполнение всех запросов потребителей вводятся штрафы за каждый кубометр продукции, недопоставленный до нижней границы потребности или поставленный сверх верхней границы.
Для выполнения поиска оптимального решения сначала необходимо сгенерировать начальное решение. Для этого инициализируется m пустых маршрутов, в которых время простоя автомобилей равняется разности времени окончания и начала работы автомобиля, осуществляющего этот маршрут в соответствии с графиком работы. Начальное время простоя виртуального автомобиля принимается равным нулю. Все ездки из списка, сгенерированного на первом этапе, сортируются в зависимости от того, как много разных автомобилей могут их осуществить. При этом ездки с меньшим числом потенциальных автомобилей помещаются в верхнюю часть списка, ездки с большим числом автомобилей - в нижнюю. Определяется величина c(i,к), равная минимальным затратам на осуществление ездки i автомобилем k. Если автомобиль к не может выполнить временные ограничения, связанные с ездкой i, соответствующие затраты принимаются равными 2M:
c (i, к ) = 2M,
где M - величина, превышающая наибольшие возможные затраты на осуществление проектируемого маршрута.
Если ездка i осуществляется виртуальным автомобилем kv и потребности, в удовлетворении которых участвует эта ездка, еще не удовлетворены, соответствующие затраты принимаются равными M:
c (i, К ) = M,
в противном случае c (i, kv) = 0.
Для каждой ездки i:
определяются затраты cl (i) = min {c (i, к): к e K} ;
маршруты сортируются по продолжительности простоя соответствующего автомобиля, причем маршруты с наибольшим простоем помещаются в верхнюю часть списка;
ездка i добавляется к первому маршруту из списка, для которого
c(i,к)< 1,5ci (i);
простой автомобиля в маршруте, к которому была добавлена ездка i, сокращается на величину, соответствующую времени выполнения ездки i.
После определения начального решения запускается сам алгоритм поиска с запретами. Данный метод основан на перестановке ездок между маршрутами. Перестановка может осуществляться как перемещением ездок с одного маршрута на другой, так и взаимным обменом ездок между двумя маршрутами. Метод запретов позволяет продолжать поиск после нахождения локального оптимума, тем самым расширяется пространство поиска даже в направлении анализа промежуточных недопустимых решений, в надежде найти новое допустимое решение, более близкое к оптимальному.
Решение, полученное после первого запуска алгоритма поиска с запретами, не является окончательным. Поиск повторяется после корректировки списка ездок. Это необходимо, так как в рассматриваемом подходе нет гарантии, что сгенерированное на первом этапе метода множество ездок является оптимальным. Нельзя утверждать, что именно эти ездки путем комбинирования друг с другом заведомо образуют маршруты, близкие к наилучшим. Поэтому для улучшения качества окончательного решения необходимо скорректировать состав ездок с учетом полученных в первом приближении маршрутов. Ездки, которые не были использованы в маршрутах, удаляются из списка ездок. Вместо них генерируются новые ездки, которые могут потенциально улучшить качество решения. Это возможно, так как после выполнения первого этапа имеется некоторый избыток ездок (около 5 %), которые могут быть переформированы. Новые ездки генерируются в целом так же, как было описано выше, но с учетом двух дополнительных правил.
Первое правило требует (при наличии такой возможности) создания для каждой точки разгрузки как минимум двух ездок сверх необходимых для достижения нижней границы запросов потребителя, привязанного к этой точке разгрузки. Это обеспечивает более широкий выбор вариантов ездок при формировании маршрутов.
Второе правило (рис. 5) используется для замены в списке ездок одних ездок на другие, с учетом полученных в первом приближении маршрутов.
Рис. 5. Второе правило корректировки списка ездок
На рис. 5 а показан полученный в первом приближении маршрут автомобиля. В него включены три ездки: Д1-П1, Д2-П2 и Д3-П3. Точки погрузки Д4 и Д5 не были включены в транспортный план по результатам решения транспортной задачи, но в данном случае они могут быть использованы для улучшения этого маршрута. Если сгенерировать новую ездку Д5-П2 и заменить ею в маршруте старую ездку Д2-П2, можно значительно сократить пробег автомобиля (рис. 5 б). Как раз это и выполняется в процессе корректировки списка ездок.
После корректировки алгоритм поиска с запретами запускается еще раз с получением более эффективного решения. Далее опять можно выполнить корректировку и т. д. Число корректировок и новых решений зависит от заданного пользователем допустимого времени решения. Чем больше итераций будет выполнено, тем точнее будет общее решение задачи.
Выводы
Рассмотренный подход позволяет в полном объеме решать задачу оперативного планирования транспортного процесса ЛЗП с учетом всех его основных особенностей. К основным отличительным характеристикам этого подхода следует отнести его сложность, которая, несомненно, вызвана сложностью самой задачи. Качество получаемого окончательного решения здесь сильно зависит от возможностей взаимной увязки результатов решения оптимизационных задач, решаемых на отдельных этапах этой методики. Главным недостатком подхода следует считать то, что цели двух основных решаемых задач оптимизации отличаются. При решении транспортной задачи, выполняемой на первом этапе, принимается допущение, что используются только маятниковые маршруты перевозки, на втором этапе на основе сгенерированных с учетом этого допущения ездок формируются кольцевые маршруты по схеме «многие ко многим». Поэтому нельзя утверждать, что состав ездок, полученных на первом этапе, обеспечит наилучшее решение на втором. Для снижения влияния этого недостатка используется процедура коррекции ездок с последующим повторным решением поисковой задачи. Однако качественное решение может быть получено только после многократных повторений процедур коррекции и поиска, что при большой размерности задачи значительно увеличит время решения.
Кроме того, к недостаткам подхода следует отнести предположение, что все используемые автомобили имеют одинаковую грузоподъемность (грузовместимость), а также то, что грузовая работа распределяется по всем имеющимся автомобилям равномерно, что в случае локального снижения запросов потребителей может привести к неэффективному использованию парка автомобилей (методика не позволяет управлять числом задействованных автомобилей в зависимости от реальной потребности в конкретном рассматриваемом периоде времени).
СПИСОК ЛИТЕРАТУРЫ
Поступила 30.06.14
UDC 634.0.3
Operational Logistics Management of Transport Processes in Wood Harvesting Companies
A.P. Sokolov, Candidate of Engineering, Associate Professor Petrozavodsk State University, Lenina, 33, Petrozavodsk, 185910, Russia; e-mail: a_sokolov@psu.karelia.ru
Task of optimal vehicle routing definition is important for operational logistics management of wood harvesting companies. The most difficult to solve is the scheme "Many-to-many" but that it is now widely used at wood harvesting companies. The article provides an overview of approaches, methods and tools for solving the problem of synthesis of transport plans (delivery route). A hybrid approach based on a combination of linear programming and prohibition search method is the perspective assignment to solve this problem. This approach allows to solve the problem of transport operational planning, taking into account all the main features of this process. To the main features of this approach should be primarily belong its complexity, which is caused by the complexity of the problem itself. The quality of the final decision depends heavily on the possibilities for harmonizing the results of solving individual optimization problems. The main disadvantage of the approach is that the two main objectives of optimization tasks are different.
REFERENCES
Received on June 30, 2014