Распределение топлива является одной из ключевых логистических задач при открытых горных работах, где крупный парк тяжёлой техники непрерывно работает на территориально удалённых участках. Любая незапланированная остановка из-за нехватки топлива ведёт к простою оборудования, росту эксплуатационных затрат и сбоям в производственном процессе. Поскольку новые технологии стимулируют рост спроса на сырьё, горнодобывающие предприятия вынуждены обеспечивать устойчивость производства и минимизировать издержки в четырёх ключевых областях: проектирование рудников, добыча, транспортировка материалов и анализ горных работ [1].

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

В предыдущих исследованиях изучались связанные с этим проблемы распределения ресурсов в условиях горных работ. Исследования по маршрутизации водовозок в карьерах [3, 4] сформулировали эту задачу как Arc Routing Problem – задачу оптимизации маршрутизации в логистике, когда услуги предоставляются не в точках (вершинах графа), а на связях (дугах или рёбрах) между ними, и показали, что частично-целочисленное линейное программирование может оптимизировать маршрутизацию операций пылеподавления и заложить методологическую основу для оптимизации маршрутизации ресурсодоставляющих транспортных средств на горных работах. Аналогичным образом оптимизация маршрутов в системе транспортировки «канатный экскаватор – самосвал» при открытых горных работах [5] показала, что алгоритмические подходы, включая генетические алгоритмы и нейронные сети, значительно превосходят эмпирическую маршрутизацию вручную, что подчеркивает практическую ценность автоматизированного принятия решений. Помимо горных работ, задача пополнения запасов топлива (FRP), изученная в работе [6], касается бензовозов, доставляющих различные виды топлива с центрального склада на распределительные станции в условиях большого и меняющегося во времени спроса. Эта структура очень похожа на рассматриваемую здесь задачу. Метаэвристический алгоритм Adaptive Large Neighborhood Search (Адаптивный поиск в больших окрестностях (ALNS)) продемонстрировал, что метаэвристические методы позволяют эффективно получать близкие к оптимальным решения для маршрутов с учетом специфики топлива в масштабе, сопоставимом с рассматриваемым в данном исследовании.

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

В данном исследовании этот пробел устраняется путем оценки и сравнения трех алгоритмических подходов: метода полного перебора (Brute Force (BF)), метода ветвей и границ (Branch and Bound с использованием сокращенной матрицы (B & B) и метода оптимизации муравьиной колонии (муравьиный алгоритм – Ant Colony Optimization (ACO)) для решения задачи маршрутизации бензовозов-топливозаправщиков при открытых горных работах. На основе данных о местоположении, виде и уровне запасов топлива, поступающих в реальном времени из рассматриваемого угольного разреза в Северной Америке, алгоритмы тестировались в двух рабочих масштабах (14 и 38 единиц техники) для оценки качества решения, вычислительной эффективности и масштабируемости. Остальная часть данной статьи организована следующим образом: в разделе 1 рассматривается соответствующая литература по задаче выбора маршрутов транспортных средств; в разделе 2 сформулирована задача и рассмотрены три метода решения; в разделе 3 представлены результаты; в разделе 4 обсуждаются результаты в контексте предшествующих исследований и практических последствий; в заключительном разделе сформулированы выводы и направления дальнейших исследований.

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

В области классического метода VRP [7] был рассмотрен маршрут доставки цемента с учетом фиксированного местоположения клиентов и известного спроса и предложен гибридный алгоритм (Hybrid Sine-Cosine Algorithm (HSCA)) – метаэвристический метод оптимизации, который объединяет сильные стороны двух алгоритмов: модифицированного синус-косинусного алгоритма (SCA) и алгоритма искусственной пчелиной колонии (ABC), включающий метаэвристический метод обучения с учетом противоположностей (OBL), который помогает улучшить работу других алгоритмов оптимизации, а также операторов мутации и скрещивания. Полученные результаты демонстрируют преимущество сочетания поиска на основе популяции с локальными стратегиями улучшения для сокращения общего пути пробега. Оптимизация маршрута вывоза мусора в стамбульском районе Умрание с высокой плотностью населения [8] дополнительно иллюстрирует практическую применимость эвристики составных маршрутов для снижения расхода топлива и повышения эффективности использования ресурсов за счет оптимальной маршрутизации в городских условиях. Эта же задача встает перед нами в условиях ограниченной пространственной планировки открытых разработок. Модели оптимизации логистики в горнодобывающей промышленности были изучены в работе [9], где использовалась надстройка Microsoft Excel Solver (Поиск решения) со встроенными картографическими инструментами для разработки оптимальных транспортных решений для горнодобывающих компаний. Хотя их подход доступен, ему не хватает алгоритмической глубины, необходимой для динамического принятия решений в реальном времени. В работе [10] представлен унифицированный точный подход к формулированию кластерного и обобщенного вариантов классической задачи маршрутизации транспорта (Clustered and Generalized VRP), который позволяет понять, как кластеризация задач может снизить вычислительную сложность – концепция, имеющая отношение к структуре приоритетных групп, использованной в данном исследовании. Алгоритм Branch-price-and-cut (BPC), объединяющий три ключевые идеи: метод ветвей и границ (branch-and-bound), генерацию столбцов (column generation) и отсечение по валидным неравенствам (cut generation) в работе [11], расширил эффективные формулировки задачи маршрутизации транспорта (VRP) для обработки параметрической неопределенности, обеспечив теоретически строгую основу для точных методов в неопределенных условиях. В контекстах маршрутизации, характерных для горнодобывающей отрасли, в работе [12] была разработана модель смешанно-целочисленного линейного программирования (MILP) для прокладки маршрутов БПЛА и планирования расположения зарядных станций в целях контроля ленточных конвейеров, что свидетельствует о растущей роли автоматизированной маршрутизации в управлении инфраструктурой горнодобывающих предприятий. В работе [13] были представлены алгоритмы с полиномиальным временем для оптимизации перевозок в металлургической промышленности, применимые к широкому спектру путей, древовидных структур и геометрических сетевых структур. В работе [14] муравьиный алгоритм (ACO) был применен к реальным задачам VRP (задачи маршрутизации транспорта) и продемонстрировал способность генерировать эффективные, близкие к оптимальным решения в значительно более короткие сроки, чем традиционные методы; этот вывод непосредственно послужил стимулом для применения ACO в настоящем исследовании.

В совокупности эти исследования подтверждают широкую применимость методов решения VRP, но обнаруживают одно и то же ограничение: они в основном предполагают статический спрос, фиксированное расположение клиентов или некритичные по времени ограничения. Ни одно из них не предполагает сочетания мониторинга уровня запасов топлива в реальном времени, динамического назначения приоритетов, а также пространственных и эксплуатационных характеристик, присущих распределению топлива на открытых разработках. Чтобы устранить эти пробелы, в данном исследовании сравнивается применение алгоритмов полного перебора (Brute Force (BF)), ветвей и границ (Branch and Bound (B & B)) и муравьиного алгоритма (Ant Colony Optimization (ACO)) для решения задачи маршрутизации бензовозов (топливозаправщиков) с учетом приоритетности на основе данных по конкретному горнодобывающему предприятию (угольному разрезу). Цель исследования – определить, какой из подходов наилучшим образом отвечает требованиям принятия оперативных решений в режиме реального времени с учетом размера парка транспортных средств. Формулировка проблемы и применение алгоритмов описаны в следующем разделе.

Задачу маршрутизации бензовозов-топливозаправщиков при открытых горных работах можно смоделировать как вариант задачи маршрутизации транспортных средств (VRP), специально адаптированный для учета динамических ограничений, зависящих от времени. Цель состоит в том, чтобы свести к минимуму общий путь пробега топливозаправщиков при одновременном обеспечении своевременной заправки техники для предотвращения эксплуатационных простоев. Задача учитывает данные в режиме реального времени о виде техники (оборудования), ее координатах и уровне запасов топлива, что отличает её от классических формулировок задачи маршрутизации транспорта (VRP), в которых, как правило, предполагаются статический спрос и фиксированные местоположения клиентов. Цель состоит в том, чтобы определить набор маршрутов, начинающихся и заканчивающихся на складе ГСМ, обеспечить дозаправку всего оборудования до исчерпания запасов топлива при минимизации общего времени пробега и с учетом ограничений по вместимости бензовоза. Три подхода к оптимизации реализовывались и оценивались с использованием набора данных по североамериканскому угольному разрезу. Алгоритмы тестировались на начальном наборе данных с 14 единицами техники для проверки алгоритмической корректности и на дополнительном наборе данных с 38 единицами техники для оценки масштабируемости методов решения. Наборы данных включают мгновенное местоположение (широта, долгота), уровень запаса топлива, вид техники (грузовики, погрузчики, экскаваторы, бульдозеры, грейдеры, самосвалы) и емкость цистерны для перевозки топлива. Техника распределяется по трем группам в порядке приоритета: первая (< 30 % топлива), вторая (30–65 %) и третья (> 65 %), а топливозаправщик начинает движение с координат (43,754; −105,266), имея емкость (максимальное количество перевозимого топлива) 50 т. Начальный набор данных представлен в табл. 1.

Таблица 1

Набор данных об оборудовании, подлежащем дозаправке с учетом приоритета

Таблица 2

Матрица расстояний между единицами техники, км

Методы решения сравнивались для условий свободного пространства, где нет дорожных ограничений, с использованием геодезических расстояний для повышения эффективности. Расстояние между всеми узлами рассчитывается по формуле расстояния по дуге большого круга, приведенной в [15]:

Δσ = cos−1 (sin ∅1 sin ∅2 + cos ∅1 cos ∅2 cos Δλ), (1)

где λ – долгота; ∅ – широта; Δσ – расстояние, м.

Расстояния между единицами техники приведены в табл. 2. Расположение единиц техники и возможные маршруты показаны на рис. 1.

Рис. 1. Местоположение единиц техники и возможные маршруты, охватывающие их

Для решения проблемы маршрутизации топливозаправщиков использовались три метода: метод полного перебора (BF), метод ветвей и границ (B & B) и муравьиный алгоритм (ACO). Каждый метод подходит к решению задачи по-своему, балансируя между вычислительной эффективностью и качеством решения, обеспечивая при этом первоочередное посещение узлов с более высоким приоритетом для предотвращения простоев. Расстояния представлены в матрице расстояний в табл. 2.

Согласно работе [16] метод грубого решения «в лоб», также известный как алгоритм полного перебора, исчерпывающе вычисляет все возможные маршруты (перемещения) и определяет самый короткий из них. Расчет и сравнение всех возможностей для асимметричной задачи маршрутизации транспорта (VRP) требуют значительного времени. Рассматривается подсеть первого приоритета, показанная на рис. 2, с матрицей расстояний, приведенной в табл. 3. Если начальной общей точкой является узел 0, то все возможные пути можно вычислить с помощью уравнения

P(n, r) = n!/(n − r)!, (2)

где n – количество узлов; r – количество единиц техники, организованных в определенном порядке.

Рис. 2. Пример сети (первая приоритетная группа + топливозаправщик; данные приведены в табл. 1)

Таблица 3

Подматрица расстояний для первой приоритетной группы

Таблица 4

Возможные маршруты и расчет пробега

Учитывая относительно небольшое количество узлов в этом сценарии, можно оценить все возможные комбинации вручную или с помощью простых вычислительных методов. Однако по мере увеличения количества узлов количество потенциальных конфигураций маршрутов растет в геометрической прогрессии, что делает ручные вычисления непрактичными и неэффективными. Все возможные маршруты и их протяженность приведены в табл. 4, а оптимальный маршрут определен как 0–1–2–3–4 с общим пробегом 12,57 км.

Алгоритм ветвей и границ (B & B) [17] исследует пространство решений, систематически разбивая его на подзадачи (ветвление) и вычисляя нижние границы для сокращения неперспективных ветвей (ограничения). Для задачи маршрутизации топливозаправщика применяется формулировка B & B со смещением по глубине с использованием сокращения матрицы для эффективного сокращения пространства поиска [18].

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

1) матрица расстояний (пробегов) определяется отдельно для каждой приоритетной группы, при этом конечный узел одной группы служит начальным узлом следующей;

2) к подзадаче каждой группы добавляется фиктивный узел с непомерно большим расстоянием (100 000 км) до склада ГСМ, что не позволяет алгоритму рассчитывать преждевременное возвращение на склад между посещениями приоритетных групп. Это фиктивное расстояние вычитается из окончательного решения, чтобы восстановить истинную длину маршрута (пробег).

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

Таблица 5

Расширенная подматрица расстояний для первой приоритетной группы

При сокращении строк вычитаются минимальные значения в строках {10,53; 3,98; 0,47; 0,47; 1,35; 0} км, что дает γстроки = 16,8 км. При сокращении столбцов вычитаются минимальные значения в столбцах {0, 0, 0, 0, 0,88, 99 989,47} км, что даёт γстолбца = 99 990,35 км.

Исходная нижняя граница: 16,8 + 99 990,35 = 100 007,15 км. Вклад в 100 000 км полностью указан в столбце «Фиктивный» и вычитается для восстановления реальной длины (пробега) маршрута. Таким образом, эффективная нижняя граница маршрутизации составляет 7,15 км. Сокращенная версия матрицы расстояний приведена в табл. 6.

Таблица 6

Сокращенная матрица после сокращения строк и столбцов (γисх = 100007,15 км)

Таблица 7

Расстояния по ветвям от склада ГСМ (узел 0)

Для каждого следующего узла-кандидата j длина ветви рассчитывается по следующей формуле:

c = c(0 , n) + γ + Δγ, (3)

где c(0, n) – сокращенное расстояние до клиентов на ребрах сети; γ = 7,15 км – текущая нижняя граница, а Δγ – дополнительное сокращение, необходимое после того, как строка 0, столбец j и обратное ребро j → 0 приведены к бесконечности (чтобы предотвратить преждевременное повторное посещение склада ГСМ). Расчетные расстояния по ветвям приведены в табл. 7.

В качестве первой точки посещения выбран узел 1 (экскаватор 3), имеющий минимальную длину ветви – 13,71 км. Алгоритм работает итеративно по той же схеме: обновляет сокращенную матрицу, вычисляет длины ветвей для всех оставшихся кандидатов и всегда выбирает узел с наименьшей длиной ветви, пока не будут посещены все узлы из группы первого приоритета. Оптимальный подмаршрут для этой группы проложен, и последний посещённый узел становится отправной точкой для группы второго приоритета, в отношении которой проводится идентичный процесс сокращения матрицы и ветвления. Это продолжается в группе третьего приоритета, после чего расстояние до фиктивного узла вычитается для получения истинной общей длины маршрута.

Муравьиный алгоритм (ACO) – это вдохновленный природой метаэвристический метод, основанный на поведении муравьев, связанном с поиском и добыванием корма, представленный в работе [19]. С тех пор он широко применяется для решения задач комбинаторной оптимизации, включая задачу коммивояжера, маршрутизацию транспортных средств и планирование. Реализация, использованная в данном исследовании, применяет ACO независимо к каждой группе приоритетов последовательно, что соответствует формулировкам B & B и Brute Force, при этом последний узел оптимального подмаршрута каждой группы становится начальным узлом для следующей группы. Это обеспечивает строгое соблюдение приоритетных ограничений: все оборудование первого приоритета (запас топлива < 30 %) посещается раньше любого оборудования второго приоритета и так далее.

Стационарный склад ГСМ (узел 0, координаты 43,721° северной широты, –105,278° западной долготы) служит обязательной отправной точкой для группы первого приоритета. В каждой группе муравьи строят маршруты, вероятностно выбирая узлы в соответствии с уравнением

где τij – уровень феромона на ребре (i, j); ηij = 1/dij – эвристическое значение (обратное расстояние); α контролирует влияние феромонов; β контролирует влияние эвристики. Узлы, не входящие в текущую приоритетную группу, исключаются из набора непосещенных узлов, что гарантирует, что алгоритм не может пересекать границы групп при построении маршрута.

Параметры ACO определялись путем систематического поиска по сетке по начальному набору данных. Поиск охватывал: итерации ∈ {50, 100}, количество муравьев m ∈ {5, 10, 15}, скорость испарения ρ ∈ {0,2, …, 0,9}, α ∈ {0,1, …, 1,0} и β ∈ {0,1, …, 1,0}. Комбинация параметров, которая дала представляемый результат, показана в табл. 8. Количество отложений феромонов Q установлено на уровне 1/solution_distance (расстояние_решения), так что муравьи, находящие более короткие маршруты, откладывают пропорционально больше феромонов, усиливая лучшие решения в процессе итераций.

Относительно низкое значение α (0,2) и высокое значение β (0,8) отражают то, что в этой задаче близость является более сильным ориентиром (на который следует полагаться), чем исторический уровень феромонов. Это разумный выбор, учитывая, что изменение местоположения оборудования в зависимости от выбора маршрута и история уровня феромонов из предыдущего запуска может не отражать текущую пространственную конфигурацию. Скорость испарения ρ = 0,2 позволяет феромоновым дорожкам сохраняться на протяжении итераций, обеспечивая достаточную память и предотвращая преждевременную сходимость к субоптимальным маршрутам.

Таблица 8

Значения параметров ACO,использованные в эксперименте

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

Первоначально оптимизация маршрутов была выполнена на начальном наборе, включающем 14 единиц техники, для оценки эффективности трех алгоритмов с точки зрения оптимальности решения. Результаты представлены в табл. 9.

Таблица 9

Окончательный маршрут, полученный каждым алгоритмом

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

Рис. 3. Разница в маршрутах между алгоритмами BF, B & B и ACO

Отличающийся маршрут получен для группы второго приоритета, где метод ветвей и границ предлагает посещение Бульдозера 3 (Узел 8) раньше Экскаватора 1 (Узел 7), в то время как метод полного перебора предлагает обратный порядок как в целом оптимальный. Общая разница в длине пробега между этими двумя маршрутами (порядками посещения) составляет 0,621 км. Причиной этого расхождения является структурное свойство сокращения матрицы со смещением по глубине, лежащее в основе реализации метода ветвей и границ. На этапе разветвления во второй приоритетной группе узлы 7 и 8 географически близки друг к другу: расстояние между узлами составляет 7,94 км, а расстояние до склада ГСМ – 1,70 км и 6,32 км соответственно. Когда алгоритм оценивает ветви-кандидаты от их общего узла-предшественника, дополнительный член сокращения Δγ, связанный с выбором Узла 8 первым, немного меньше, чем при выборе Узла 7 первым. Эта разница возникает из-за того, что сокращение матрицы поглощает почти равные попарные расстояния между этими двумя узлами и оставшимися непосещенными кандидатами в несколько разных пропорциях в зависимости от того, какой столбец скрыт. Алгоритм выбирает Узел 8 на этом шаге ветвления, потому что вычисленная нижняя граница расстояния ниже, без какого-либо предвосхищения оценки того, приведет ли этот выбор к худшему результату в дальнейшем.

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

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

При крупномасштабных открытых горных работах большое количество единиц техники, необходимых для удовлетворения производственных потребностей, серьезно усложняет масштабируемость алгоритмов оптимизации. В этом разделе оценивается вычислительная производительность алгоритмов метода прямого перебора, метода ветвей и границ и муравьиного алгоритма с акцентом на их эффективность с точки зрения времени вычислений и длины маршрута по мере увеличения количества единиц техники. Анализ масштабируемости состоит из двух частей. В первой части рассматривается производительность всех трех алгоритмов для количества единиц техники от 15 до 20, что представлено на рис. 4. Во второй части анализ распространяется на 38 единиц техники, причем сравниваются только метод ветвей и границ и муравьиный алгоритм, поскольку метод полного перебора становится вычислительно неэффективным для количества узлов более 17. Результаты анализа представлены на рис. 5.

Рис. 4. Анализ масштабируемости результатов оптимизации методом полного перебора, методом ветвей и границ и муравьиным алгоритмом для количества единиц техники до 20

Рис. 5. Анализ масштабируемости результатов оптимизации методом полного перебора и муравьиным алгоритмом для количества единиц техники до 38

Рис. 5 показывает явное расхождение в трендах времени выполнения по мере увеличения количества единиц техники. Время выполнения алгоритма полного перебора растет факториально, превышая 100 с при 17 узлах и достигая более 400 с при 17 узлах с неравномерным распределением приоритетных групп. Такие темпы роста делают развертывание в реальном времени совершенно невозможным при превышении этого порогового значения. Метод ветвей и границ демонстрирует значительно лучшие характеристики масштабирования в диапазоне от 10 до 20 единиц техники: время работы остается менее 15 с, хотя тенденция роста уже заметно сверхлинейна. Время выполнения муравьиного алгоритма во всем диапазоне стабильно составляет менее секунды, а на 20 единиц техники оно составляет менее 0,5 с. Что касается качества решения, метод полного перебора и муравьиный алгоритм обеспечивают сопоставимые длины маршрутов в протестированном диапазоне, в то время как метод ветвей и границ иногда предлагает несколько более длинные маршруты, что отражает расстояния, получаемые в результате его детерминированных решений с сокращением матрицы в сценариях с почти равными расстояниями.

На рис. 6 показано расхождение между результатами оптимизации методом полного перебора и муравьиным алгоритмом на больших операционных масштабах (количествах единиц техники). Время выполнения алгоритма ветвей и границ резко возрастает при превышении количества 28 единиц техники, превышая 100 с при 29 единицах и далее делая метод практически нецелесообразным для использования в реальном времени. Эта модель роста, обусловленная комбинаторной разветвленной структурой алгоритма, делает метод ветвей и границ непригодным для рудников с большим активным парком техники. Муравьиный алгоритм, напротив, масштабируется с почти линейным ростом времени выполнения, которое остается на уровне менее 1 с при максимальном протестированном масштабе в 38 единиц техники. Этот результат напрямую мотивирует использование метаэвристических методов в крупномасштабных задачах маршрутизации распределения топлива: сочетание близкого к оптимальному качества решения и управляемого времени вычислений делает муравьиный алгоритм единственным кандидатом из трех оцененных методов, который может реально способствовать оптимизации принятия оперативных решений в реальном времени в масштабе рудника.

Настоящая работа устанавливает конкретные и воспроизводимые эмпирические пороговые значения. Метод полного перебора становится практически нецелесообразным за пределами примерно 17 единиц техники, а метод ветвей и границ – за пределами примерно 20 единиц, в то время как муравьиный алгоритм остается вычислительно целесообразным на всём протестированном масштабе в 38 единиц с временем выполнения менее 1 с. Эти пороговые значения представляют собой непосредственно применимые рекомендации для специалистов-практиков и разработчиков систем управления автопарком. Рудник, эксплуатирующий парк менее чем из 17 единиц активного оборудования, учитываемого в цикле маршрутизации, может рассматривать метод полного перебора как вполне достаточный для получения гарантированно оптимальных маршрутов. Рудник с диапазоном от 17 до 20 эксплуатируемых единиц техники может использовать метод ветвей и границ как вычислительно осуществимый и дающий близкий к оптимальным маршрутам подход. Любой рудник, эксплуатирующий более 20 действующих единиц техники, что характерно для подавляющего большинства современных открытых разработок на уголь и металлы, должен принять муравьиный алгоритм или сопоставимую метаэвристическую стратегию в качестве основной стратегии маршрутизации. Демонстрация того, что муравьиный алгоритм последовательно и устойчиво предоставляет близкие к оптимальным маршруты в течение не более чем 2 с на всех протестированных масштабах, предоставляет эмпирическую основу для этой рекомендации, которая ранее отсутствовала в литературе по маршрутизации, специфичной для горного дела.

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

Отклонение результатов метода ветвей и границ и муравьиного алгоритма от оптимального значения метода полного перебора, составляющее 1,13 %, должно оцениваться относительно правильной отправной точки, которой является не идеал, а реалистичная альтернатива неоптимизированной маршрутизации. При добыче полезных ископаемых без систематического алгоритма маршрутизации водитель бензовоза-топливозаправщика следует ситуативной последовательности, основанной на оценке близости или личном мнении, которая фактически представляет собой случайную последовательность посещений единиц техники в каждой приоритетной группе. Чтобы количественно оценить, что это означает конкретно, все 24 возможных порядка посещений первой приоритетной группы (четыре единицы оборудования с уровнем запаса топлива ниже 30 %) были оценены относительнально начального набора данных из 14 единиц техники. Оптимальный маршрут только для этой группы составляет 16,33 км. Случайно выбранный порядок посещения дает в среднем длину маршрута 20,51 км – на 25,6 % длиннее оптимального маршрута, а в худшем случае – длину 23,57 км, на 44,4 % длиннее оптимального. Таким образом, разница в 1,13 % между муравьиным алгоритмом и методом полного перебора – это не просто приемлемое отклонение, а демонстрация того, что метаэвристическая оптимизация обеспечивает близкую к идеальной эффективность по сравнению с реальными исходными операционными показателями. Такая концепция становится особенно важной при рассмотрении масштабов реальных открытых разработок. На средних и крупных рудниках обычно используется парк из 100–150 единиц активной техники в смену, при этом уровни запасов топлива постоянно меняются в течение дня. При таких масштабах применение метода полного перебора не просто слишком медленно, но и категорически неосуществимо: количество оцениваемых перестановок растет факториально и на несколько порядков превышает любые практические вычислительные пределы. Как показали результаты исследования масштабируемости в данной работе, метод ветвей и границ становится практически нецелесообразным при использовании более 20 единиц техники. Для рудника с численностью от 100 до 150 единиц техники выбор заключается не между точным алгоритмом (например, метод полного перебора) и муравьиным алгоритмом, а между муравьиным алгоритмом и отсутствием алгоритма вообще. Принятие отклонения от теоретического оптимального значения менее чем на 2 % в обмен на решение по маршрутизации, рассчитанное менее чем за две секунды, не является ограничением метаэвристического подхода, а единственным практическим способом продвижения вперед по пути оптимизации. Данные по масштабируемости подтверждают это. Время выполнения муравьиного алгоритма при 38 единицах техники составляет 1,59 с, и его почти линейный тренд роста указывает на то, что даже при 100 единицах вычисление останется в пределах временных ограничений системы маршрутизации в реальном времени.

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

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

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

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