Интегрированное программирование в оптимизации сетей водопроводов

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

Понимание сетей водопроводов

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

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

Роль целочисленного программирования

Целое программирование — это подмножество линейного программирования, в котором некоторые или все переменные решения ограничены целыми значениями.Когда переменные являются двоичными (0 или 1), модель называется двоичной целочисленной программой (BIP); когда переменные могут принимать любое неотрицательное целое число, это чистая целочисленная программа; и когда появляются как непрерывные, так и целые переменные, это смешанная целочисленная программа (MIP). В оптимизации водопровода MIP-формулы стандартны, потому что они захватывают непрерывные потоки и давления вместе с двоичными проектными решениями.

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

Ключевые компоненты IP-модели

Типичная модель целочисленного программирования для оптимизации сети водопровода включает следующие элементы:

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

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

Преимущества использования целочисленного программирования

Применение целочисленного программирования к проектированию сети водопроводов дает существенные практические преимущества:

• Оптимальное распределение ресурсов: IP может снизить общие затраты на 10-30% по сравнению с традиционными эвристическими проектами, особенно в больших сетях с несколькими зонами давления. Исследование, проведенное Water Research (2015), продемонстрировало 18% экономию на реальной сети среднего размера.
• Повышение надежности: Путем явного моделирования сценариев отказа (например, разрывы труб, отказы насоса) через ограничения на основе сценариев, IP может создавать сети, которые поддерживают обслуживание в заранее определенном наборе непредвиденных обстоятельств, тем самым повышая устойчивость.
• Быстрая оценка альтернатив: Модель IP может быть повторно запущена с обновленными данными о затратах, прогнозами спроса или нормативными ограничениями, что позволяет планировщикам исследовать тысячи сценариев проектирования за считанные минуты.
• Прозрачное принятие решений: Оптимальное решение сопровождается двойными переменными (теневыми ценами), которые указывают на предельную стоимость ужесточения ограничения, помогая планировщикам расставлять приоритеты инвестиций.

Реальные приложения подтвердили эти преимущества. Город Барселона использовал смешанный подход к редизайну своей системы водоснабжения, достигнув снижения затрат на 12% при одновременном повышении надежности давления (источник: Журнал чистого производства, 2016). Аналогичным образом, многие водохозяйственные компании в Соединенных Штатах теперь используют инструменты на основе IP для генерального планирования (см. Руководящие принципы AWWA ).

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

Несмотря на свои сильные стороны, целочисленное программирование несет значительные вычислительные нагрузки. Классическая проблема размера трубы NP-твердая, что означает, что время решения может расти экспоненциально с размером сети. Для сетей с более чем несколькими сотнями труб коммерческим решателям, таким как CPLEX, Gurobi или альтернативы с открытым исходным кодом (например, COIN-OR), могут потребоваться часы или дни, чтобы найти проверенные оптимальные решения. Эта вычислительная интенсивность связана с необходимостью решать большое количество релаксаций линейного программирования в ветви-и-связанной или ветви-и-вырезанное дерево поиска.

Для управления сложностью, практикующие часто используют одну или несколько из следующих стратегий:

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

Другая проблема заключается в обработке нелинейных уравнений потери головы. Многие решатели требуют линейных ограничений; следовательно, по частям линейное приближение формул Хазена-Уильямса или Дарси-Вайсбаха является общим. Точность этих приближений должна быть тщательно сбалансирована с увеличением бинарных переменных (для каждой части приближения). Расширенные методы используют выпуклость или конусное программирование второго порядка для захвата нелинейностей без чрезмерной дискретизации (см. ]SIAM Journal on Optimization, 2017].

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

Будущие направления

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

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

Заключение

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