Table of Contents

Введение: скрытая сложность логистики отходов

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

Одной из самых мощных математических рамок для решения этих дискретных, сковывающих проблем является целочисленное программирование (IP). В отличие от методов непрерывной оптимизации, которые предполагают дробные решения (например, 0,47 грузовиков), целочисленное программирование обеспечивает принятие решений на основе целого числа, а не 2,8. Для управления отходами, где решения по своей сути дискретны (выберите маршрут A или маршрут B, открытый объект X или нет), IP обеспечивает строгий, управляемый данными путь к почти оптимальным решениям. В этой статье рассматривается, как целочисленное программирование меняет логистику отходов, от оптимизации маршрута до размещения объекта, и рассматриваются преимущества, вычислительные проблемы и новые тенденции, которые определят следующее поколение интеллектуальных систем отходов.

Понимание целочисленного программирования: основа для дискретных решений

Целое программирование — это отрасль математической оптимизации, в которой некоторые или все переменные решения ограничены целыми значениями. Это отличает его от линейного программирования (LP), где переменные могут принимать любое реальное число в пределах возможного диапазона. В то время как решатели LP могут быстро находить оптимальные решения для непрерывных задач, многие реальные логистические решения требуют целых чисел: вы не можете отправить 1,7 транспортных средств или назначить 0,3 драйвера на сдвиг. IP захватывает эту реальность, моделируя решения как целые числа & #8212; часто бинарные (0 или 1) переменные, представляющие варианты да / нет.

Типы моделей целочисленного программирования

В оптимизации управления отходами появляются три распространенных варианта:

  • Чистое программирование чисел: Все переменные решения должны быть целыми числами. Например, решение о том, сколько контейнеров для сбора данных разместить в каждом месте.
  • Миксированное целочисленное программирование (MIP): Некоторые переменные являются целыми числами, другие непрерывными. Это наиболее распространенная формулировка в логистике, где модель может выбирать двоичные маршруты для использования при постоянном распределении мощностей грузовиков по этим маршрутам.
  • Бинарное программирование целых чисел: Все переменные принимают значения 0 или 1. Это идеально подходит для проблем с местоположением объекта (открыть передаточную станцию или нет) и проблем с назначением (назначить драйвера А на маршрут B или нет).

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

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

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

Операции по сбору

Это наиболее заметная и затратоёмкая фаза, часто составляющая 60-80% от общего объема бюджетов по обращению с отходами. Сбор включает в себя отправку грузовиков в пункты пикапа (жилые, коммерческие, промышленные) в плановые дни. Ключевые решения включают:

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

Транспорт и передача

После сбора отходы перевозятся на станции или непосредственно на объекты по удалению.

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

Утилизация и обработка

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

  • Планирование мероприятий по утилизации для управления потенциалом и минимизации эксплуатационных расходов
  • Выделение видов отходов на соответствующие перерабатывающие предприятия
  • Управление запасами перерабатываемых материалов

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

Как интегральное программирование решает проблемы управления отходами

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

Оптимизация маршрута: проблема маршрутизации транспортных средств (VRP)

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

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

Целая формула программирования для базового сбора отходов VRP может включать в себя бинарные переменные x {ijk}, указывающие, перемещается ли транспортное средство k непосредственно от остановки i до остановки j, непрерывные переменные для переносимой нагрузки и ограничения, обеспечивающие сохранение потока, ограничения пропускной способности и временные окна. Решение этой модели дает набор маршрутов, которые минимизируют общее расстояние или стоимость поездки, обеспечивая обслуживание каждого клиента.

Планирование местонахождения объекта

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

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

Бинарные переменные y j указывают, открыт ли объект j, в то время как непрерывные переменные x {ij} представляют собой количество отходов, отправляемых с маршрута i на объект j. Цель сбалансирует капитальные затраты с эксплуатационными транспортными расходами на горизонте планирования.

Размер и состав флота

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

Расписание экипажа

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

Математическая формула проблемы сбора отходов

Для иллюстрации конкретной мощности целочисленного программирования рассмотрим упрощенный сценарий сбора отходов. В городе имеется 100 остановок для проживания, которые должны обслуживаться парком из 5 одинаковых грузовиков, каждый из которых имеет грузоподъемность 10 тонн. Каждая остановка генерирует от 0,05 до 0,2 тонны отходов. Цель состоит в том, чтобы свести к минимуму общее время в пути, обеспечивая при этом, чтобы ни один грузовик не превышал пропускную способность, и каждая остановка посещается ровно один раз. Это проблема маршрутизации транспортных средств с емкостью (CVRP).

Переменные решения

  • x {ijk} ∈ {0,1}: 1 если грузовик k едет непосредственно от остановки i до остановки j, 0 иначе (для всех i, j в наборе остановок плюс депо, и для каждого k во флоте).
  • q {ik} ∈ R+: груз на грузовике k сразу после выхода из остановки i.

Цель

Минимизируйте Σ {k} Σ {i} Σ {j} d {ij} x {ijk}, где d {ij} — время в пути между i и j.

Ограничения

  • Каждая остановка посещается ровно один раз: Σ {k} Σ {i} x {ijk} = 1 для каждой остановки j.
  • Сохранение потока: для каждого грузовика k и остановки j, Σ {i} x {ijk} = Σ {i} x {jik} (каждый грузовик, который входит в остановку, должен покинуть ее).
  • Вместимость: q {jk} ≤ 10 для всех j, k; и нагрузка накапливается в совокупности при посещении остановок.
  • Депо старт/энд: каждый грузовик начинается и заканчивается на депо с нулевой нагрузкой.
  • Устранение субтура: предотвращение маршрутов, которые не начинаются на депо.

Это стандартная формулировка MIP. В то время как решение 100 остановок и 5 грузовиков точно может быть вычислительно интенсивным, современные решатели, такие как CPLEX, Gurobi или альтернативы с открытым исходным кодом (например, SCIP), могут обрабатывать такие проблемы за секунды или минуты с помощью алгоритмов разветвления или резки, особенно с хорошей начальной эвристикой. Для более крупных случаев (тысячи остановок) методы разложения, такие как генерация колонок или Лагранжевая релаксация используются для того, чтобы сделать проблему тягучей.

Тематический анализ: оптимизация маршрутов на практике

Рассмотрим муниципалитет среднего размера с населением 250 000 человек, эксплуатирующий парк из 40 коллекторских грузовиков, обслуживающих 12 000 остановок в шести районах. Существующие маршруты были разработаны вручную на основе исторических границ и опытных водителей’ знания, но город столкнулся с ростом расходов на топливо, жалобами водителей на неравномерные рабочие нагрузки и растущими жалобами на обслуживание из-за пропущенных пикапов в дни большого объема.

Проблема трансформации с IP

Работая с группой по исследованию операций, муниципалитет сформулировал модель смешанных чисел, которая интегрировала:

  • Окна времени (коллекция жилых помещений должна быть в период с 6:00 до 2:00 PM)
  • Разнородный парк (некоторые грузовики были задней погрузкой, другие — боковой погрузкой, с различными эксплуатационными расходами и возможностями)
  • Ограничения по часам вождения (максимум 9 часов в смену, 30-минутный обеденный перерыв)
  • Передвижные модели (время в пути менялось в зависимости от времени суток, смоделировано с помощью линейных приближений по кусочке)

Модель IP содержала около 4,5 млн переменных (в основном переменных двоичной маршрутизации) и 300 тыс. ограничений. Используя коммерческий решатель на стандартном сервере, время решения составляло около 14 часов для недельного плана маршрутизации. Затем команда разработала эвристический теплый запуск (на основе существующих ручных маршрутов), чтобы сократить время решения до менее трех часов, что сделало систему практичной для еженедельной повторной оптимизации.

Результаты и воздействие

Оптимизированные маршруты позволили добиться значительных улучшений:

  • 16% сокращение общего суточного расстояния , пройденного по всему флоту, экономя примерно $420 000 в год на топливе
  • 22% снижение затрат на сверхурочные , потому что маршруты были сбалансированы более справедливо среди водителей
  • Надежность сервиса улучшилась до 99,3% пикапов, выполненных в рамках опубликованного окна (с 91,5%)
  • Годовые выбросы CO2 сократились примерно на 180 метрических тонн, что поддерживает цели города и #8217;
  • Удовлетворенность водителя улучшилась, поскольку сбалансированные маршруты уменьшили несоответствие между самыми длинными и самыми короткими сменами.

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

Передовые приложения и интеграция

Динамическая и стохастическая оптимизация

Реальная генерация отходов неопределенна. Статическая модель IP, которая предполагает фиксированные объемы отходов на каждой остановке, неизбежно отклоняется от реальности. Расширенные подходы включают в себя стохастическое целое число программирования для обработки неопределенности: генерация отходов моделируется как случайная переменная, и оптимизация ищет политику, которая хорошо работает по многим сценариям. Альтернативно, надежная оптимизация гарантирует, что решение осуществимо для всех правдоподобных объемов отходов реализации в пределах определенного набора неопределенности. Эти методы более требовательны к вычислениям, но дают решения, которые изящно ухудшаются, когда реальность расходится с прогнозами.

Интеграция с телематикой и IoT

Современные мусоровозы оснащены GPS, считывателями RFID на контейнерах и датчиками веса, которые сообщают об уровнях заполнения в реальном времени. Эти данные могут питать систему поддержки принятия решений на основе IP, которая динамически настраивает маршруты в середине смены: если контейнер заполнен только на 30%, система может отложить его пикап до более позднего дня, в то время как неожиданно полный контейнер может вызвать срочный переадресация. Это создает цикл оптимизации замкнутого цикла, где целочисленное программирование повторно оптимизируется в почти реальном времени, реагируя на фактические условия, а не на оценки.

Местоположение объекта с экологическими ограничениями

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

Преимущества и возврат инвестиций

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

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

Возврат инвестиций на реализацию оптимизации ИС обычно превышает 10:1 за пятилетний горизонт. Начальные затраты (разработка модели, лицензирование решателей, интеграция данных) скромны по сравнению с достигнутыми операционными сбережениями. Исследование европейских операторов отходов 2019 года показало, что те, кто использует расширенную оптимизацию, сообщили о 12-18% более низких затратах на сбор по сравнению с коллегами, полагающимися на ручное планирование. Для города, тратящего 10 миллионов долларов в год на сбор, что означает постоянную экономию в 1,2-1,8 миллиона долларов.

Проблемы и вычислительные соображения

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

Вычислительная сложность

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

  • Разложение: Разбейте проблему на более мелкие подзадачи (например, маршрутизация на уровне района), которые могут быть решены самостоятельно.
  • Эвристические теплые старты: Используйте простую конструктивную эвристику (например, ближайший сосед, алгоритм экономии) для быстрого создания хорошего выполнимого решения, которое ускоряет поиск по ветвям и ссылкам.
  • Метагевристика: Для очень больших проблем алгоритмы, такие как генетические алгоритмы, смоделированный отжиг или большой поиск по соседству, могут производить почти оптимальные решения за долю времени, хотя и без гарантий оптимальности.
  • Облачные вычисления и параллельные решатели: Современные MIP-решатели могут использовать десятки ядер и распределенных вычислений для решения больших проблем в приемлемые настенные часы.

Качество данных и интеграция

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

Организационное сопротивление

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

Будущие направления: конвергенция IP, AI и систем реального времени

Следующим шагом в оптимизации логистики отходов является объединение целочисленного программирования с машинным обучением и потоками данных в реальном времени. Появляются три многообещающих направления:

Трубопроводы прогнозирования-оптимизации

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

Усиление обучения для динамической маршрутизации

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

Цифровые близнецы и анализ «что если»

Цифровой двойник— виртуальная копия системы управления отходами— может встроить IP-двигатель для имитации воздействия предлагаемых изменений: что произойдет, если мы добавим два электрогрузовика? Что, если мы закроем передаточную станцию для технического обслуживания? Что, если скорость переработки увеличится на 5%? Лица, принимающие решения, могут изучить компромиссы в безрисковой среде, прежде чем совершать капитальные или изменяющие операции. Это превращает IP из статического инструмента планирования в динамическую интерактивную систему планирования.

Вывод: от линейных программ к циркулярным экономикам

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

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

Чтобы узнать больше об основных алгоритмах и программном обеспечении, рассмотрите возможность изучения Gurobi’s праймера по программированию на смешанных числах , который охватывает основы MIP-решателей. Для более глубокого погружения в оптимизацию отходов, журнал Waste Management регулярно публикует тематические исследования по приложениям целочисленного программирования . Муниципалитеты также могут ссылаться на EPA’s инструменты поддержки принятия решений по управлению отходами для практического руководства по включению оптимизации в процессы планирования.

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