Как я оптимизировал свою стратегию уборки листьев с помощью линейного программирования

От рутинной работы на выходных до увлекательного применения ценных принципов исследования операций.

Делиться

Наступила осень, и официально начался сезон уборки листьев. Занимаясь этой утомительной задачей, я понял, что по сути это одна большая задача оптимизации.

Когда я сгребала листья, я сделала четыре кучи: одну по обе стороны дерева, одну у передней части двора и одну на дальней стороне, чтобы собрать редкие листья, которые подхватил ветер.

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

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

Почему оптимизация по-прежнему важна

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

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

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

1) Разложить формулировку задачи линейного программирования (ЛП),
2) сравнить оптимальный план с интуитивно понятными стратегиями человека, и
3) Посмотрите, как те же самые рассуждения применимы к другим реальным проблемам.

Определение проблемы

При определении любой задачи оптимизации следует учитывать несколько ключевых элементов:

Целевая функция: Определение целевой функции сводится к определению цели задачи. Целевая функция всегда направлена на максимизацию или минимизацию некоторого значения. В данной задаче мы минимизируем время, затраченное на уборку и сбор листьев.

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

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

И вот так, внезапно, мы получаем основные элементы линейного программирования.

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

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

Параметры и предположения

Сначала я думал, что мне понадобится только скорость сгребания и время на сбор урожая.

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

Быстрый концептуальный эксперимент

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

Аналогично, я мог бы засечь время упаковки для куч разного размера: ¼ мешка, ½ мешка, ¾ мешка и целой кучи размером с мешок. Затем я мог бы построить функцию, показывающую, как время упаковки увеличивается с объемом листьев. Я подозреваю, что это приблизительно линейная зависимость.

Я не засекал время выполнения этих заданий. Вместо этого я делал приблизительные оценки. Цель состоит не в достижении идеальных результатов, а в демонстрации структуры и подхода линейного программирования.

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

Полная модель

1. Изображение двора

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

Наборы:

• I: набор ячеек двора (ячеек сетки), индексированных по i.
• J: множество потенциальных мест для установки свай, индексированных буквой j.

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

Таблица 1 – Параметры и их оценочные значения

Исходя из этих параметров и модели плотности листьев, получаем:

• mᵢ: масса листьев (в фунтах) в ячейке i ∈ I.
• dᵢⱼ: расстояние от центра ячейки i до предполагаемого места расположения кластера j.

Эти значения вычисляются численно (в коде) и рассматриваются как заданные константы в модели оптимизации.

2. Дополнительные параметры модели (время/мощность)

• α > 0: коэффициент масштабирования времени уборки; базовый показатель того, сколько времени требуется для уборки небольшого количества листьев на коротком расстоянии. Более высокое значение α соответствует более низкой общей скорости уборки.
• β > 0: параметр масштабирования расстояния, моделирующий, как усилие по уборке листьев увеличивается с расстоянием (т.е. уборка замедляется по мере перемещения листьев на большее расстояние).
• b₀ ≥ 0: фиксированное время подготовки на один пакет (секунды на каждый открытый пакет).
• b₁ ≥ 0: время упаковки на фунт листьев (секунды на фунт).
• C > 0: вместимость мешка (фунты на мешок).
• Kₘₐₓ ∈ ℕ₀: максимальное количество свай, которые могут быть открыты.

Мы также определяем производную массу кучи mⱼ как общую массу листьев, отнесенных к куче j:

mⱼ = ∑ᵢ mᵢ xᵢⱼ

3. Переменные принятия решения

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

Переменные присваивания

Чтобы определить, какие листья будут сгребены в какие кучи, мы составили следующую схему распределения:

xᵢⱼ ∈ {0, 1}

для всех i ∈ I, j ∈ J: xᵢⱼ = 1, если ячейка i перемещена в стопку j, иначе 0.

Переменные, открытые для обработки

Чтобы определить, куда именно следует сгребать листья, мы определяем переменную, определяющую степень готовности к уборке кучи:

yⱼ ∈ {0, 1}

для всех j ∈ J: yⱼ = 1, если стопка j открыта (использована), иначе 0.

переменные количества пакетов

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

nⱼ ∈ ℕ₀

для всех j ∈ J: целое число мешков, использованных в стопке j.

Листья каждой клетки должны быть полностью распределены ровно в одну кучу (посредством xᵢⱼ), а количество мешков nⱼ должно быть достаточным для хранения массы, выделенной для каждой открытой кучи.

4. Условия целостности

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

Запомните, i обозначает количество листьев во дворе, а j — местоположение куч.

xᵢⱼ ∈ {0, 1}, для всех i ∈ I, j ∈ J
yⱼ ∈ {0, 1}, для всех j ∈ J
nⱼ ∈ ℕ₀, для всех j ∈ J

В Python мы указываем их следующим образом:

# Переменные решения x = [[pulp.LpVariable(f»x_{i}_{j}», cat=»Binary») for j in range(m)] for i in range(n)] y = [pulp.LpVariable(f»y_{j}», cat=»Binary») for j in range(m)] B = [pulp.LpVariable(f»B_{j}», lowBound=0, cat=»Integer») for j in range(m)]

5. Целевая функция

Время уборки зависит от массы и расстояния; время упаковки в мешки зависит от массы кучи и количества мешков.
Мы сводим к минимуму общее время:

минимизировать по x, y, n:

∑ᵢاᴵ ∑ⱼاᴶ xᵢⱼ · α · mᵢ · dᵢⱼ^β + ∑ⱼاᴶ ( b₀ · nⱼ + b₁ · mⱼ )

Первый член аппроксимирует усилие по сбору мусора: масса × расстояние^β, масштабированное на α. Второй член добавляет время подготовки мешков: b₀, умноженное на количество мешков nⱼ, и время упаковки, пропорциональное массе кучи mⱼ через b₁.

В коде это реализовано следующим образом:

∑ᵢ,ⱼ xᵢⱼ (α mᵢ dᵢⱼ^β + b₁ mᵢ) + b₀ ∑ⱼ nⱼ,

что алгебраически идентично, поскольку

∑ᵢ,ⱼ xᵢⱼ b₁ mᵢ = b₁ ∑ⱼ ∑ᵢ mᵢ xᵢⱼ = b₁ ∑ⱼ mⱼ.

6. Ограничения

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

(C1) Задание

Листья каждой ячейки должны быть отнесены ровно к одной группе:

∑ⱼ∈ᴶ xᵢⱼ = 1, для всех i ∈ I.

for i in range(n): prob += pulp.lpSum(x[i][j] for j in range(m)) == 1

(C2) Связывание: используйте стопку только в том случае, если она открыта.
Листья в ячейке не могут быть назначены в местоположение, если в ней нет открытой стопки. Мы определяем это ограничение следующим образом:
xᵢⱼ ≤ yⱼ, для всех i ∈ I, j ∈ J.

for i in range(n): for j in range(m): prob += x[i][j] <= y[j]

(C3) Вместимость сумки

Общая масса, отведенная под кучу $j$, не должна превышать вместимость ее мешков:

∑ᵢ∈ᴵ mᵢ xᵢⱼ = mⱼ ≤ C nⱼ, для всех j ∈ J.

# В данном случае я использовал B[j] для обозначения n_j для j в диапазоне (m): prob += pulp.lpSum(masses[i] * x[i][j] for i in range(n)) <= bag_capacity_lb * B[j]

(C4) Максимальное количество свай

Мы ограничиваем общее количество свай, которые можно открыть:
∑ⱼاᴶ yⱼ ≤ Kₘₐₓ.

prob += pulp.lpSum(y[j] for j in range(m)) <= K_max

Полная модель

В итоге получаем:

минимизировать по x, y, n:

∑ᵢاᴵ ∑ⱼاᴶ xᵢⱼ · α · mᵢ · dijβ + ∑ⱼاᴶ ( b₀ · nⱼ + b₁ · mⱼ )

при условии:

∑ⱼ∈ᴶ xᵢⱼ = 1, для всех i ∈ I.

xᵢⱼ ≤ yⱼ, для всех i ∈ I, j ∈ J.

∑ᵢ∈ᴵ mᵢ xᵢⱼ = mⱼ ≤ C nⱼ, для всех j ∈ J.

∑ⱼاᴶ yⱼ ≤ Kₘₐₓ.

На этом описание модели завершается.

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

Проверка простых эвристических методов

Эвристический метод — это подход, основанный на «эмпирических правилах», для решения проблем. Когда большинство людей убирают за собой газон, они используют простой эвристический метод, независимо от того, знают они об этом или нет.

Чтобы проверить, какую пользу приносит оптимизация, я сравнил алгоритм целочисленного линейного программирования с тремя простыми эвристиками:

• Уборка с передней стороны двора : непрерывная уборка граблями от задней части двора к передней.
• Микрокучки : множество небольших куч вблизи мест с густой листвой.
• Задняя-Передняя-Центральная часть : несколько больших куч в центральных местах.

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

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

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

Ниже приведён пример фрагмента кода, демонстрирующий, как эвристический алгоритм «микрокучей» инициализирует и уточняет центры на основе плотности листьев:

Пример: эвристический метод для микросвай

def centers_micro(cells, masses, bag_capacity_lb, seed=42): rng = np.random.default_rng(seed) M_total = masses.sum() k = max(1, int(round(M_total / (2 * bag_capacity_lb)))) probs = masses / (M_total + 1e-12) centers = cells[ rng.choice(len(masses), size=k, replace=False, p=probs) ] # Итеративное разделение плотных кластеров for _ in range(8): … return centers

Полные реализации всех эвристических алгоритмов доступны в репозитории по адресам src/core/centers.py и src/core/front_sweep.py.

Результаты

Рисунок 1: Общее время, затраченное на уборку газона при использовании каждой стратегии.

Решение, найденное в результате оптимизации, выявляет 5 скоплений деревьев, расположенных преимущественно вокруг них. Его превосходство над простыми эвристическими методами заметно, но не кардинально.

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

Рисунок 2: Тепловая карта эвристического и оптимального алгоритмов ранжирования (изображение предоставлено автором). GIF-файл доступен на GitHub.

Заключение

Во многих ситуациях вычисление полной линейной программы слишком затратно с точки зрения вычислительных ресурсов, поэтому нам приходится использовать эвристику, которая «достаточно близка» к оптимальной. Даже для такой простой задачи, как эта, мне пришлось остановить работу решателя после того, как он достиг отметки оптимальности в 5% от нижней границы. В таких обыденных и тривиальных делах, как уборка листьев, мы постоянно используем эвристики. Возможно, мы теряем около 2,5 минут из-за неоптимальной уборки, но мы экономим часы, не составляя и не программируя линейную программу.

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

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

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

Как только вы усвоите этот процесс, вы будете замечать возможности для оптимизации повсюду.

Ссылки

[1] Код оптимизации сбора листьев и моделирование данных (2025). Репозиторий GitHub: [https://github.com/Josiah-DeValois/Optimize-Leaf-Raking].

Примечание автора

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

Источник: towardsdatascience.com