Учредитель журнала

Разработка глобального ограничения Block sequencing при планировании открытых горных работ

УДК 004.89

DOI 10.52815/0204-3653_2022_03187_33
EDN: RIIZMN

Олейник Юрий
Младший научный сотрудник, Институт информатики и математического моделирования – обособленное подразделение ФИЦ «Кольский научный центр Российской академии наук».
E-mail: yoleynik@iimm.ru

Зуенко Александр
Ведущий научный сотрудник, к. т. н., Институт информатики и математического моделирования – обособленное подразделение ФИЦ «Кольский научный центр Российской академии наук»
E-mail: zuenko@iimm.ru

Введение

Одной из важных задач теории расписаний является задача планирования открытых горных работ [1–4]. Суть данной задачи заключается в том, что требуется разработать карьер заданной конфигурации за определенное количество одинаковых временных промежутков (периодов) наиболее эффективным способом. Карьер моделируется в виде набора блоков с известным содержанием полезного компонента и известной ценностью блока в каждый период. Ценность блока описывает предполагаемую прибыль от его извлечения с учетом стоимости его добычи и переработки. Таким образом, часть блоков, где достаточно полезного компонента, будет иметь положительную ценность, а другие – отрицательную. Кроме того, ценность блока может меняться согласно заданным закономерностям в зависимости от периода, когда блок извлекается. Решением рассматриваемой задачи будет являться присвоение каждому блоку номера периода, в который его следует извлечь из карьера. Предполагается, что модель карьера содержит только необходимые для извлечения блоки, то есть каждому блоку модели должен быть присвоен номер одного из периодов. Критерием эффективности при решении является сумма ценностей блоков, целью оптимизации – максимизация этого критерия.
Для решения поставленной задачи широко применяются методы смешанного целочисленного линейного программирования [1–3], принципиальным недостатком которых является необходимость представления всех ограничений в явном виде с помощью линейных уравнений и неравенств. Применение подобного подхода на практике предъявляет серьезные требования к объемам оперативной памяти, необходимым для хранения модели и реализации вычислений, что особенно важно для задач планирования открытых горных работ, где количество блоков в карьере составляет десятки и сотни тысяч. Кроме того, линеаризации некоторых типов ограничений могут вызывать существенные затруднения.
В работе излагаются результаты, которые развивают исследования авторов, представленные в [5, 6], где предлагается решать задачу планирования открытых горных работ как задачу удовлетворения ограничений (CSP – constraint satisfaction problem). В рамках парадигмы программирования в ограничениях, сами ограничения (отношения), как правило, задаются не прямо, а путем указания соответствующей процедуры, которая возвращает истину, если кортеж значений удовлетворяет ограничению. Подобные процедуры называются распространителями, поскольку позволяют при не полном задании входного вектора значений переменных делать выводы о множестве допустимых значений недоопределенных компонент данного вектора. Как правило, совокупность простых ограничений эффективнее обрабатывать совместно, объединяя в одно, так называемое, глобальное ограничение. В [5, 6] описаны основные типы глобальных ограничений, которые предлагается использовать для моделирования условий рассматриваемой задачи, в частности, условия на последовательность извлечения блоков было предложено представлять и обрабатывать с помощью набора глобальных ограничений max для каждого блока в отдельности.
В настоящей статье представлено разработанное авторами глобальное ограничение Block sequencing, распространитель (обработчик) которого анализирует условия на последовательность извлечения блоков, а также некоторые дополнительные требования, за один вызов для всех блоков, находящихся в очереди распространителя, что позволяет существенно повысить эффективность вычислений.

Парадигма программирования в ограничениях

Для решения сложных задач комбинаторного поиска все чаще применяется технология программирования в ограничениях (CP – constraint programming), реализующая декларативный подход к представлению знаний [7]. Понятие “переменная”, используемое в CP, ближе к математической трактовке понятия переменной, чем той, что принята в языках программирования. Для решения любой задачи в рамках парадигмы программирования в ограничениях она должна быть представлена как задача удовлетворения ограничений. Для описания задачи CSP необходимо задать множество переменных, множество возможных значений этих переменных (домены) и множество ограничений, описывающих допустимые или недопустимые сочетания значений. Для получения решения задачи CSP необходимо каждой переменной присвоить значение из ее домена таким образом, чтобы не нарушалось ни одно из заданных ограничений (удовлетворялись все ограничения) [7]. Любой метод решения задач CSP состоит из двух основных компонент: 1) компоненты, реализующей информированный поиск с применением специализированных эвристик выбора переменной и её значения (значений); 2) компоненты, осуществляющей логических вывод путем сокращения доменов одних переменных на основе конкретизированных доменов других переменных. Для каждого типа ограничений подобный логический вывод осуществляется специализированной процедурой, которая называется пропогатором или распространителем ограничений данного типа.
Итак, для каждого типа ограничений задачи CSP должен иметься свой распространитель, согласно которому сокращаются домены участвующих в ограничении переменных. Результат работы распространителей называется распространением ограничений. Процесс распространения ограничения может завершиться с тремя исходами:

  1. Всем переменным ограничения присвоены непротиворечивые значения из их доменов – ограничение удовлетворено.
  2. Домен ­какой-либо переменной ограничения сокращен до пустого множества – получено противоречие, задача CSP не имеет решения.
  3. Не всем переменным ограничения присвоены значения и нет переменных с пустыми доменами, но распространитель не в состоянии больше исключить ни одного значения из доменов оставшихся недоопределенными переменных, то есть процесс распространения достиг неподвижной точки (fix point).

В процессе решения задачи CSP последовательно запускаются распространители всех ограничений, причем, изменение домена ­какой-либо переменной в рамках одного распространителя приведет к повторному запуску распространителей всех ограничений, где участвует эта переменная. Таким образом, распространители постоянно запускают друг друга, пока каждый из них не придет к одному из вышеописанных результатов. При этом, выявление противоречия любым из распространителей делает задачу CSP неразрешимой.
В случае, если задача CSP имеет решение, то его не всегда удается отыскать только распространением ограничений, т. к. распространители могут прекратить свою работу, достигнув неподвижной точки. Для выхода из этой ситуации применяют различные стратегии информированного поиска [7] – к имеющимся ограничениям по определенным правилам (эвристикам) добавляется одно или несколько дополнительных ограничений на области определения некоторых переменных, а некоторые из имеющихся ограничений могут быть исключены из рассмотрения. Затем снова запускаются процедуры распространения ограничений, в которых задействованы данные переменных. К стратегиям информированного поиска, используемых при решении задач удовлетворения ограничений относят, прежде всего, методы поиска в глубину с возвратами, методы локального поиска и их гибриды. По какому принципу (согласно каким эвристикам) выбираются переменные и их значения (подмножества значений), а также то, как следует действовать, когда при данном выборе решения не существует, зависит от конкретной стратегии поиска.
При решении задач CSP часто используется комбинация стратегий поиска в глубину с возвратами и методов распространения ограничений [8–10]. Данный тип поиска называется систематическим, поскольку позволяет проверить все пространство поиска. Его обобщенная схема представлена на рис. 1.

Рис. 1. Обобщенная схема систематического поиска

В работе [6] подробно изложены эвристики и другие особенности стратегии информированного поиска, предложенной авторами для реализации эффективных вычислений и организации процедуры ветвления при решении задачи планирования открытых горных работ.

Задача планирования открытых горных работ как задача удовлетворения ограничений

Для постановки задачи планирования открытых горных работ, карьер представляется в виде блочной модели, разделенный на блоки одинакового размера. Каждый блок модели обладает рядом свой­ств, зависящим от породы, содержащейся в нем, и каждому блоку в процессе решения должен быть сопоставлен номер периода разработки, в который этот блок должен быть извлечен из карьера.
Переменными задачи удовлетворения ограничений являются блоки модели, доменом переменных – множество периодов разработки карьера, а решением данной задачи будет присваивание каждой переменной определенного номера периода.
При построении решения задачи планирования открытых горных работ необходимо учитывать ряд условий, часть из которых отображают базовые ограничения на процесс разработки карьера, а некоторые описывают дополнительные требования к данному процессу.
К базовым ограничениям на процесс разработки карьера относятся ограничения технического и нормативного характера: допустимые углы уклона бортов карьера, минимальные размер площадок для расположения техники и т. д. В рамках блочной модели карьера эти ограничения обычно удается учесть путем задания шаблона извлечения блоков. Шаблон извлечение блоков применяется ко всем блокам модели и описывает, какие блоки карьера должны быть извлечены раньше или одновременно (в один период) с рассматриваемым блоком. Пример такого шаблона представлен на рис. 2, где ключевым является нижний блок.

Рис. 2. Пример шаблона добычи

К дополнительным можно отнести требования по равномерности работ, т. е. в каждый период необходимо извлекать примерно одинаковое количество блоков, а также ограничение на максимальную величину заглубления за один период выработки. Первое ограничение позволяет сформировать парк добывающей техники и равномерно его нагружать, второе – снизить сложность работ, поскольку излишнее заглубление осложнит перемещение техники по карьеру. Оба эти ограничения оптимизируют совокупные затраты на эксплуатацию добывающей техники, однако, эти затраты не учитываются в критерии эффективности решения задачи.
Важным аспектом эффективности вычислений в рамках парадигмы программирования в ограничениях является выбор способа представления задачи с помощью того или иного набора ограничений, то есть моделирование задачи в терминах ограничений.
Для описания упомянутых выше ограничений задачи планирования открытых горных работ можно использовать ограничения базовых типов, которые встроены в среду программирования. Помимо арифметических и логических выражений, программные библиотеки программирования в ограничениях предоставляют ряд так называемых глобальных ограничений, которые представляют собой совокупности более простых ограничений. Распространители глобальных ограничений за счет совместного анализа простых ограничений позволяют исключать больше “лишних” значений из доменов переменных. Так, ограничение на то, что объемы добычи должны быть одинаковы с некоторой погрешностью для всех периодов разработки карьера, можно задать как линейное ограничение на количество блоков, которым присвоен номер определенного периода. В рамках задачи ограничения подобного типа задаются как для всех блоков, что позволяет равномерно загружать добывающую технику, так и отдельно для рудных блоков, поскольку рудные блоки дальше отправляются на обогащение, а мощности обогатительных предприятий также требуется загружать равномерно. Однако распространители линейных ограничений обладают низкой эффективностью, особенно в случае большого количества слагаемых.
В работах [5, 6] авторами был осуществлен выбор готовых глобальных ограничений для моделирования задачи планирования открытых горных работ.
Так, упомянутые ограничения на объемы добычи было предложено описывать с помощью глобального ограничения bin-packing, которое легко масштабируется в зависимости от размерности задачи и эффективно обрабатывается решателем [5]. Ранее авторами условия на последовательность извлечения блоков было предложено представлять и обрабатывать с помощью набора глобальных ограничений max для каждого блока. При существенных размерностях блочной модели такое представление занимает значительные объемы памяти и недостаточно эффективно обрабатывается в связи с каскадным вызовом множества ограничений max при незначительных изменениях доменов переменных. Для более эффективного представления ограничений на порядок выработки блоков было разработано собственное ограничение.
В настоящей статье описывается разработанное авторами глобальное ограничение Block sequencing, предназначенное для эффективной совместной обработки совокупности ограничений на последовательность извлечения блоков. Кроме того, глобальное ограничение Block sequencing позволяет учитывать требование на максимальную величину заглубления за один период разработки карьера.

Процедура-­распространитель глобального ограничения Block sequencing

На листинге ниже представлен псевдокод, описывающий алгоритм работы распространителя для глобального ограничения Block sequencing.
Block sequencing (all, cubes)

  1. Q.init(all);
  2. while Q not empty
  3. k ← Q.first
  4. Q.delete(Q.first)
  5. maxlb←0
  6. foreach value i Є cubes[k].above
  7. lb←all[i].lb
  8. if lb>maxlb then maxlb←lb
  9. if all[i].ub←all[k].ub not failed
    and changes all[i] domain then
    Q.add(i)
  10. if all[k].lb← maxlb not failed and
    changes all[k] domain then Q.add(k)
  11. foreach value i Є cubes[k].below
  12. if all[i].lb←all[k].lb not failed
    and changes all[i] domain
    then Q.add(i)
  13. if all[cubes[k].bl].lb← all[k].lb+1 not
    failed and changes all[cubes[k].bl]
    domain then Q.add(cubes[k].bl)
  14. if all[cubes[k].ab].ub← all[k].ub-1 not
    failed and changes all[cubes[k].ab]
    domain then Q.add(cubes[k].ab)

Поясним некоторые обозначения, приведенные на листинге.
Q – множество индексов распространяемых переменных.
all – массив распространяемых переменных (индексы этого массива хранятся в Q).
all[k].lb и all[k].ub – нижняя и верхняя границы домена переменной CSP all[k].
cubes – массив блоков, блоку cubes[k] соответствует переменная CSP all[k].
cubes[k].above – список индексов блоков (и соответствующих им переменных), которые необходимо вытащить вместе или раньше блока k согласно шаблону выработки.
cubes[k].below – список индексов блоков (и соответствующих им переменных), которые необходимо вытащить вместе или после блока k согласно шаблону выработки.
cubes[k].ab – индекс блока, находящегося выше блока k на величину нормы заглубления.
cubes[k].bl – индекс блока, находящегося ниже блока k на величину нормы заглубления.
В распространителе хранится очередь индексов переменных (Q), для которых надо выполнить распространение. На первом шаге производится инициализация данной очереди (строка 1). При первоначальном распространении в очередь попадают индексы всех блоков, при последующих распространениях – только индексы переменных, чей домен изменился.
Распространение продолжается, пока очередь не опустеет (строка 2). В процессе распространения из этой очереди извлекается индекс k (строки 3–4) и производятся следующие шаги алгоритма:
Шаг 1. Для всех блоков, находящихся согласно шаблону выше блока k, то есть для блоков, которые должны быть извлечены до блока k, урезаются домены соотнесенных с ними переменных, таким образом, чтобы все значения доменов были не больше максимального значения переменной k. Также при этом вычисляется максимальное из минимальных значений (maxlb) в упомянутых доменах переменных (строки 6–9).
Шаг 2. У переменной, соответствующей блоку k, урезается домен таким образом, чтобы его значения были не меньше maxlb (строка 10).
Шаг 3. Для всех блоков, находящихся согласно шаблону ниже блока k, урезаются домены таким образом, чтобы их значения были не меньше минимального значения домена переменной блока k (строки 11–12).
Шаг 4. Для блока cubes[k].bl, находящегося ниже блока k на величину нормы заглубления, урезается домен таким образом, чтобы его значения были больше минимального значения переменной k (строка 13).
Шаг 5. Для блока cubes[k].ab, находящегося выше блока k на величину нормы заглубления, урезается домен таким образом, чтобы его значения были меньше максимального значения переменной блока k (строка 14).
При попытке изменения домена любой переменной могут возникнуть следующие ситуации:

  • домен переменной не поменялся. В этом случае никаких дополнительных действий не требуется;
  • домен переменной поменялся, но не стал пустым. В этом случае индекс переменной добавляется в очередь распространения;
  • домен переменной стал пустым. В таком случае сообщается о противоречии и распространитель завершает работу.

Если распространение завершилось без противоречий, производится проверка значений переменных. Если встречена хотя бы одна переменная с неопределенным значением (в домене осталось больше 1 значения), то считается, что ограничение достигло неподвижной точки. Если значения всех переменных определены, то ограничение считается удовлетворенным.
Далее в примере будут использованы следующие правила (эвристики) для выбора наиболее перспективной ветви дерева поиска:
Э1. Выбирается самый верхний рудный блок с еще не присвоенным значением, ему присваивается наименьшее значение из домена.
Э2. Если таких рудных блоков нет, то выбирается самый нижний вскрышной блок (блок с пустой породой), ему присваивается наибольшее значение из домена.
При наличии двух блоков на одной высоте, предпочтение будет отдано блоку с меньшим значением остальных координат.
В качестве примера рассмотрим построение плана разработки простейшего карьера. Пусть разработки ведутся в три периода. Сам карьер для наглядности будем считать двумерным, как и шаблон выработки для него (рис. 3).

Рис. 3. Двумерная блочная модель карьера и шаблон извлечения

В ячейках, представляющих блоки карьера, указаны домены соответствующих блокам переменных, цветом выделены рудные блоки (блоки с положительной ценностью). В качестве дополнительных ограничений укажем, что за период должно быть извлечено ровно 2 рудных блока и от 5 до 6 блоков в целом, а также что величина заглубления за период не должна превышать 2 блока. В примере будет демонстрироваться работа описанного распространителя. Детали работы стандартных распространителей (распространителей других глобальных ограничений, в частности bin-packing) будут опущены, а указаны лишь внесенные ими изменений. Также для решения будут использоваться эвристики для выбора текущей ветви дерева поиска, которые описаны выше.
Распространитель проверяет все блоки, начиная снизу. На основе анализа блоков D4, C3, D3, E3 на шаге 5 работы распространителя изменяются домены переменных для блоков D2, C1, D1, E1. На рис. 4 и далее редуцированные домены переменных выделены жирным шрифтом.

Рис. 4. Редукция доменов переменных для блоков, лежащих выше заданного более чем на норму заглубления

Далее на основе анализа блоков D2, C1, D1, E1 на шаге 4 работы распространителя изменяются домены переменных для блоков D4, C3, D3, E3 как показано на рис. 5, а сами переменные помещаются в очередь Q. Проверка оставшихся в очереди элементов ничего не дает. Процесс распространения ограничений достигает неподвижной точки.

Рис. 5. Редукция доменов переменных для блоков, лежащих ниже заданного более чем на норму заглубления

Для выхода из этой ситуации необходимо выполнить ветвление процесса поиска решений. Для этого согласно первой эвристике (Э1) блоку B2 присваивается значение 1, что влечет за собой запуск распространителя. При анализе блока B2, на шаге 1 работы распространителя изменяются домены переменных, соответствующих блокам A1, B1, C1 (рис. 6).

Рис. 6. Редукция доменов переменных для блоков, лежащих выше заданного согласно шаблону выемки

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

Рис. 7. Состояние задачи CSP к моменту запуска ограничения bin-packing

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

Рис. 8. Состояние задачи CSP после работы ограничения bin-packing

Затем снова активируется распространитель глобального ограничения Block sequencing. На основе анализа блоков E1 и D2, на шаге 4 работы распространителя домены переменных для блоков E3 и D4 сужаются до значения 3, то есть полностью конкретизируются, после чего достигается очередная неподвижная точка (рис. 9).

Рис. 9. Состояние задачи CSP после очередной итерации

Для выхода из нее переменной блока C3, согласно эвристике Э1, будет присвоено значение 2, после чего, в результате распространения ограничения на норму рудных блоков, блоку D3 присваивается значение 3 (рис. 10).

Рис. 10. Состояние задачи CSP после конкретизации значений для всех переменных, соответствующих рудным блокам

Дальнейший процесс решения заключается в ветвлении дерева поиска с применением эвристики Э2. Согласно Э2, переменным E2, F2, в соответствующей очередности, присваивается значение 3. Далее эта же эвристика применяется и к блоку F1, и переменной F1 присваивается значение 3, однако, при дальнейшем распространении с помощью глобального ограничения bin-packing выясняется, что последнее присваивание приводит к противоречию, т. к. в этом случае останется всего 4 блока со значением 2 (рис. 11).

Рис. 11. Обнаружение тупиковой вершины дерева поиска

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

Рис. 12. Решение задачи CSP

Заключение

По сравнению с ранее использованным авторами способом представления ограничений на последовательность извлечения блоков, применение глобального ограничения Block sequencing при решении рассматриваемой задачи планирования открытых горных работ позволяет существенно увеличить скорость получения решения, поскольку избавляет от затратных процедур многократного вызова небольших распространителей. За один вызов разработанный распространитель глобального ограничения Block sequencing анализирует и редуцирует домены всех переменных, которые итеративно изменяются при выполнении шагов 1–5. Глобальное ограничение Block sequencing позволяет реализовать более глубокую редукцию доменов переменных, то есть в процессе распространения (вывода) из рассмотрения исключается больше “лишних” значений, которые не входят ни в одно решение задачи CSP. Подобный эффект достигается не только благодаря совместному анализу набора ограничений на последовательность извлечения блоков, но и учету в основном цикле распространителя дополнительного ограничения на допустимый уровень заглубления за период. По сравнению с методами целочисленного линейного программирования использование парадигмы программирования в ограничениях позволяет существенно снизить требования к оперативной памяти за счет имплицитного представления ограничений, что, в конечном счете, приводит к возможности решать задачи с требуемым уровнем дискретизации модели карьера.

Работа выполнена при финансовой поддержке РФФИ, грант №20-07-00708a.