А ДАН ДЗО, Консалтинговая компания > Статьи > В поисках «короткого пути»

В поисках «короткого пути»

скачать в pdf

Опыт оптимизации логистических потоков в нефтегазовой отрасли.

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

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

Найти путь для «коммивояжёра»

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

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

Одна из таких более сложных задач известна под названием «задача коммивояжёра». Она касается оптимизации (пусть для определённости это будет минимизация протяжённости) замкнутого (кольцевого) маршрута обхода (или объезда) нескольких заданных пунктов с возвращением в исходный (начальный) пункт. В нашем арсенале имеются запрограммированные процедуры решения задачи коммивояжёра, причём как стандартным методом ветвей и границ (так называемый алгоритм Литла), так и эвристическим методом имитации отжига*.
*(Это общий алгоритмический метод решения задач дискретной комбинаторной оптимизации, который имитирует физические процессы, происходящие при кристаллизации вещества в частности, при отжиге)

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

В частности поясним на примере задачи коммивояжёра, что означает применительно к методам решения задач – слово «эвристический». Начнём, однако, с метода ветвей и границ, который как раз не является эвристическим. Почему? Потому что это абсолютно строгий метод, применение которого приводит причём за ограниченное число шагов к отысканию наилучшего (по заданному критерию оптимизации) решения рассматриваемой задачи (в нашем случае кратчайшего маршрута движения коммивояжёра). В отличие от него метод имитации отжига не гарантирует получения наилучшего маршрута. Более того, если этот метод применять повторно, то всякий раз он будет давать, вообще говоря, другой результат (то есть другой маршрут)!

Сразу возникает вопрос: а зачем нужен такой ненадёжный метод, если имеется алгоритм, гарантированно дающий наилучший результат? Дело в том, что при большом числе пунктов, которые надлежит посетить коммивояжёру (положим, порядка 100) на поиск оптимального маршрута методом ветвей и границ даже на современных компьютерах уходит слишком много времени, что делает данный метод практически неприменимым. Вот в такой ситуации, когда, как говорят математики, «размерность задачи велика», и возникает потребность в нестрогих («эвристических») методах!

По сути, поиск оптимального маршрута коммивояжёра сводится к перебору возможных маршрутов. И вопрос лишь в том, как организовать этот перебор. Проще всего, если это возможно, перебирать вообще все маршруты. Но на самом деле в этом нет необходимости: в соответствии с алгоритмом ветвей и границ в процессе перебора удаётся отбрасывать целые «ветви» дерева перебора (заведомо не содержащие оптимального варианта). Хотя при большой размерности даже такой оптимизированный (усечённый) перебор не удаётся довести до конца за разумное время.

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

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

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

Алгоритм имитации отжига (который по сравнению с рассмотренными выше оказывается более эффективным) состоит в следующем. Случайным образом формируется начальный маршрут, который затем последовательно модифицируется путём перестановок двух случайным образом выбираемых пунктов. Причём если эта модификация улучшает маршрут (то есть его протяжённость уменьшается), то она принимается безусловно. А если ухудшает, то с определённой вероятностью, которая тем меньше, чем больше относительное ухудшение маршрута. Таким образом, в отличие от локального поиска, здесь допускается не только улучшение, но и ухудшение маршрута, что позволяет избегать, если так можно выразиться, «ловушек локальных минимумов». Кроме того, если на каком-то шаге этого процесса получается маршрут, который лучше из полученных ранее, то для его дополнительного улучшения применяется процедура локального поиска.

Естественно, алгоритм имитации отжига не гарантирует, как уже отмечалось, получения абсолютно лучшего (оптимального) решения задачи коммивояжёра. Но, как показали тесты (а это происходило более 10 лет назад, когда компьютеры были такими мощными, как сейчас), при количестве пунктов маршрута порядка 100 решения, получаемые всего за 1 секунду, оказываются хуже оптимальных не более чем на 5%.

У нас был необычный опыт практического применения алгоритмов оптимизации кольцевых маршрутов на крупном нефтегазовом месторождении. Сначала там требовалось распределить разбросанные по довольно обширной территории нефтепромысла производственные объекты (скважины) между звеньями операторов

добычи нефти и газа таким образом, чтобы минимизировать перемещения работников. Это делалось методом так называемого кластерного анализа, который мы реализовали в виде отдельной программной процедуры. Кластерный анализ позволяет разбить заданное множество объектов на требуемое число кластеров подмножеств

компактно (близко друг к другу) расположенных объектов. В нашем случае каждый из получившихся кластеров был закреплён за отдельным звеном операторов в качестве его зоны обслуживания. А затем с помощью процедуры оптимизации кольцевых маршрутов мы для каждого звена сформировали маршруты движения между обслуживаемыми объектами.

Учимся у муравьёв

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

различные процессы, происходящие в природе, а два последних в живой природе. Надо отметить, что за последние примерно 20 лет сформировалось целое научное направление под названием «Природные вычисления» (Natural Computing)*, *(Здесь, вероятно, уместно упомянуть и более общий термин «мягкие вычисления» (Soft Computing), объединяющий в общий класс всякие неточные, приближённые методы решения задач и охватывающий такие области, как нечёткая логика, нейронные сети, вероятностные рассуждения, сети доверия, эволюционные алгоритмы), разрабатывающее математические методы, в которых заложены природные механизмы принятия решений.

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

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

Для решения задачи коммивояжёра организуют (здесь и далее, естественно, имеется в виду моделирование) целую муравьиную колонию. Обычно в каждый пункт маршрута (город), подлежащий посещению коммивояжёром, помещают ровно по одному муравью. Затем для каждого муравья случайным образом моделируется его собственный замкнутый маршрут обхода городов. При этом каждый следующий город выбирается с вероятностью, зависящей от расстояния до него от предыдущего города и от концентрации феромона на этом участке пути*, *(Начальная концентрация феромона на всех возможных участках движения коммивояжёра (и муравьёв) предполагается одинаковой.). Чем меньше расстояние и чем выше концентрация феромона, тем выше вероятность*, *(Естественно, учитывается также и запрет на повторное
посещение ранее пройденных городов.). После того как маршрут для каждого муравья составлен, рассчитываются длины этих маршрутов. А затем корректируется концентрация феромона на всех путях между городами: частично уменьшается (феромон, как и положено, испаряется), а частично увеличивается, причём вклад в это увеличение вносит каждый из муравьёв тем больший, чем короче оказался его маршрут. Этот процесс повторяется заданное число раз (или до истечения компьютерного времени, выделенного на решение задачи). Причём на каждом шаге определяется самый короткий из муравьиных маршрутов, который сравнивается с наиболее коротким из ранее найденных для определения абсолютно лучшего (который можно ещё попытаться улучшить с помощью локального поиска).

Логистический «естественный отбор»

Остановимся совсем кратко и на принципах работы генетических алгоритмов коль скоро мы их тоже упоминали. Генетический алгоритм это эвристический алгоритм поиска решения задачи оптимизации (например, всё той же задачи коммивояжёра), имитирующий процесс эволюции живых организмов*, *(Генетические алгоритмы входят в класс так называемых эволюционных вычислений (Evolutionary Computation).

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

Мутация состоит в том, что отдельная особь подвергается какому-то случайному, относительно незначительному изменению. В задаче коммивояжёра мутация обычно сводится к перестановке двух Пунктов маршрута. Скрещивание подразумевает, что из двух родительских особей путём определённого комбинирования их составных частей (генов) порождаются (обычно также две) особи-потомки. В задаче коммивояжёра скрещивание реализуется чуть более «хитро», чем мутация, но как именно, мы, дабы не перегружать повествование излишними деталями, подробно пояснять не будем*, *(Отметим лишь, что общие звенья маршрутов родителей, если таковые, конечно, имеются, потомки наследуют в обязательном порядке, а остальные родительские звенья –по возможности в шахматном порядке.).

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

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

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

Оптимизация товаропроводящих сетей.

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

Но сначала более подробно обсудим, какие вообще типичные задачи могут возникать в подобных ситуациях. Начнём с простейшего случая. Предположим, что есть несколько поставщиков и несколько потребителей определённого продукта. При этом известно, сколько продуктов готов поставить каждый поставщик (предложение) и сколько продукта требуется каждому потребителю (спрос) за определённый период допустим, год). Известны также цены каждой операции поставки (включая цену самого продукта и стоимость его доставки). Требуется определить объёмы поставок от каждого из поставщиков каждому из потребителей, удовлетворяющие спрос с минимальными суммарными затратами. Это классическая транспортная задача, которая может решаться как специально придуманным для неё так называемым «венгерским методом», так и методами линейного программирования. Последние применимы и в более сложных ситуациях (например, когда добавляются дополнительные ограничения на объёмы поставок от конкретных поставщиков конкретным потребителям).

В вышеупомянутой задаче потребителей (АЗСи прочих) было так много, что их приходилось укрупнять (объединять в кластеры). А в роли поставщиков выступали нефтебазы, хотя они, в свою очередь, снабжались нефтепродуктами с нефтеперерабатывающих заводов (но эту часть товаропроводящей сети мы в целях упрощения оставим «за кадром»). Данная задача оказалась существенно сложнее классической транспортной. Требовалось определить в условиях имевшего место падения объёмов потребления нефтепродуктов оптимальный вариант закрытия части нефтебаз и сопутствующего перераспределения потоков нефтепродуктов. При этом необходимо было минимизировать суммарные затраты, прежде всего включая условно-постоянные издержки на содержание и эксплуатацию нефтебаз (которые при закрытии данных объектов обнуляются, благодаря чему и достигается значительная экономия). Для решения этой задачи пришлось использовать целочисленное линейное программирование, точнее сказать, смешанное. Поясним, о чём идёт речь. Поскольку в отношении каждой нефтебазы приходится решать, закрыть её или оставить работающей, то здесь и возникает целочисленная (даже бинарная) переменная, принимающая всего 2 значения (а потому и бинарная): 0 (закрыть) или 1 (оставить). В то же время объёмы поставок это обычные (вещественные) переменные.

Надо отметить, что целочисленное (и смешенное) линейное программирование по сравнению с «обычным» (когда все переменные вещественные) требует неизмеримо больших объёмов вычислений.

Между тем, и размерность рассматриваемой задачи была нешуточной: количество нефтебаз составляло около 150принескольких сотнях укрупнённых потребителей. Поэтому пришлось прибегнуть, по сути дела, к той же кластеризации: разбить территорию размещения нефтебаз и потребителей (а это была фактически вся Россия!) на несколько частей, отнести каждую нефтебазу и каждого из потребителей к одной из этих частей и для каждой из них решать исходную задачу. А потом необходимо было «сшивать» получившиеся решения (с возможностью частичного перераспределения «пограничных» потребителей и потоков).

 

|

Обсуждение закрыто.