Исследователи разработали вычислительный метод, который почти на 80% сократил время решения крупной задачи по распределению вакцин. Полученные схемы оставались близкими к оптимальным, однако работа представляла собой моделирование на ранее собранных данных и не проверяла систему в ходе реальной кампании вакцинации.
Исследование опубликовано в журнале Sustainability Analytics and Modeling. Специалисты объединили машинное обучение с методом генерации столбцов — математическим подходом, который позволяет решать задачи оптимизации с огромным количеством возможных решений.
Разработка предназначена для ситуаций, когда необходимо одновременно учитывать стоимость доставки, расположение пунктов распределения, потребности населения и доступность ограниченного запаса вакцин.
Модель должна была учитывать 1,6 миллиарда переменных
Работа продолжает исследование 2025 года, в котором учёные создали модель для распределения вакцин между отдельными статистическими кварталами — небольшими географическими единицами, используемыми при переписи населения.
Цель модели заключалась в том, чтобы снизить совокупные затраты на распределение и одновременно направить как можно больше вакцин в районы, где они были наиболее необходимы.
Для построения набора данных исследователи использовали сведения Центров по контролю и профилактике заболеваний США (Centers for Disease Control and Prevention) и органов здравоохранения штата Пенсильвания о поставках вакцин и спросе во время пандемии COVID-19.
Однако при моделировании в масштабах штата возникло около 1,6 миллиарда потенциальных бинарных и целочисленных переменных решения. Каждая такая переменная могла, например, обозначать выбор или отказ от определённого пункта распределения либо объём направляемых туда ресурсов.
Перебор и оценка такого числа вариантов требуют слишком больших вычислительных затрат, особенно если расчёты необходимо регулярно повторять после поступления новых данных.
Как работает генерация столбцов
Генерация столбцов — метод решения крупных оптимизационных задач, при котором алгоритм не рассматривает сразу все возможные переменные.
Вместо этого исходную задачу разделяют на основную и одну или несколько вспомогательных. Алгоритм начинает с ограниченного набора решений, а затем постепенно добавляет новые варианты, способные улучшить результат.
Такой подход существенно сокращает объём вычислений. Но при особенно больших и сложных задачах даже генерация столбцов может работать слишком медленно, поскольку алгоритму приходится многократно искать новые перспективные комбинации.
Исследователи попытались ускорить именно этот этап.
Машинное обучение сузило область поиска
В новой системе машинное обучение использовало ранее решённые примеры, чтобы предсказывать наиболее перспективные значения бинарных переменных в одной из вспомогательных задач.
Алгоритм не заменял математическую оптимизацию и не создавал окончательную схему распределения самостоятельно. Его прогнозы помогали определить, каким участкам пространства решений следует уделить вычислительные ресурсы в первую очередь.
После этого результаты прогноза включали в процедуру генерации столбцов. Такой гибридный подход авторы назвали генерацией столбцов под управлением машинного обучения.
Метод включал предварительное обучение модели на известных задачах и последующее применение прогнозов при решении нового экземпляра задачи. Благодаря этому алгоритму требовалось проверять меньше заведомо малоперспективных вариантов.
Время расчётов уменьшилось на 79,1%
В численных экспериментах гибридная система сократила время работы на 79,1% по сравнению с обычной генерацией столбцов.
По данным авторов, среди протестированных подходов она обеспечила наиболее удачное соотношение между вычислительной скоростью и качеством решения.
При этом результат не всегда совпадал с математически оптимальным. Отклонение могло достигать 6% от оптимального значения целевой функции.
Такой разрыв означает, что предложенная схема распределения могла быть несколько хуже наилучшего теоретически возможного варианта. Однако исследователи считают эту потерю приемлемой с учётом значительного ускорения вычислений.
На практике допустимость отклонения будет зависеть от задачи. При распределении медицинских ресурсов необходимо оценивать не только общую эффективность, но и то, не приводит ли упрощение расчётов к недостаточному снабжению отдельных групп населения.
Модель учитывала эффективность и охват населения
Исследователи сформулировали задачу как модель максимального покрытия с размещением и распределением ресурсов.
Подобные модели помогают определить, где следует располагать пункты обслуживания и какие районы они должны обеспечивать. В данном случае алгоритм стремился расширить охват населения вакцинами и одновременно ограничить затраты на распределение.
Для решения исходной задачи авторы также применили модифицированную диаграмму Вороного. Этот математический инструмент разделяет территорию на области в зависимости от их близости к определённым объектам, например к пунктам поставки или вакцинации.
Метод был встроен в схему лагранжевой релаксации — подход, при котором часть сложных ограничений временно переносится в целевую функцию. Это позволяет упростить расчёты, а затем последовательно приблизиться к допустимому качественному решению.
Исследование не проверяло систему в реальной эпидемии
Работа представляет собой вычислительное исследование. Авторы использовали реальные исторические данные, но не сообщали о внедрении алгоритма органами здравоохранения или о проведении проспективного испытания во время кампании вакцинации.
Поэтому результаты не показывают, насколько предложенный подход изменит фактическую доступность вакцин, расходы, время доставки или охват населения.
Реальное распределение медицинских ресурсов зависит от факторов, которые трудно полностью включить в модель. К ним относятся изменения спроса, перебои поставок, сроки хранения препаратов, транспортные ограничения, доступность персонала и готовность людей пройти вакцинацию.
Кроме того, качество работы машинного обучения зависит от того, насколько новые условия похожи на данные, использованные при его подготовке. Необычная эпидемиологическая ситуация или существенное изменение инфраструктуры могут снизить точность прогнозов.
Что означает «справедливое» распределение
Лейла Хаджибабаи (Leila Hajibabai), доцент кафедры промышленной и системной инженерии имени Эдварда П. Фиттса Университета штата Северная Каролина (North Carolina State University) и автор для корреспонденции, отметила, что исходная модель должна была распределять вакцины не только эффективно, но и справедливо.
Однако математическая оптимизация не определяет справедливость сама по себе. Исследователи и органы здравоохранения должны заранее решить, какие показатели следует учитывать: численность населения, уровень заболеваемости, возраст, медицинскую уязвимость, транспортную доступность или социально-экономические условия.
Разные определения могут приводить к разным результатам. Поэтому подобные системы следует рассматривать как инструменты поддержки решений, а не как замену клинической, эпидемиологической и этической оценке.
Метод может применяться не только для вакцин
По словам соавтора исследования Али Хаджбабаи (Ali Hajbabaie), доцента кафедры гражданского строительства, строительства и экологической инженерии Университета штата Северная Каролина, предложенный подход подходит для широкого круга задач распределения ресурсов.
Сходные методы могут использоваться при планировании гуманитарной помощи и ликвидации последствий стихийных бедствий, когда необходимо быстро определить маршруты поставок и приоритетные районы.
Другими возможными областями применения являются транспортные системы, энергетическое планирование, размещение инфраструктуры и управление крупными цепочками поставок.
Но перед практическим внедрением для каждой области потребуется отдельная проверка. Данные, ограничения и цена ошибки при распределении вакцин существенно отличаются, например, от планирования энергосистемы или доставки обычных товаров.
Ускорение расчётов может сделать модели полезнее на практике
Главное преимущество нового подхода заключается не в получении более точного решения, а в возможности быстрее находить достаточно качественный вариант.
Во время чрезвычайной ситуации данные о спросе, запасах и доступных маршрутах могут быстро меняться. Если расчёт занимает слишком много времени, даже точная модель теряет практическую ценность. Ускоренный алгоритм потенциально позволяет чаще обновлять планы по мере поступления информации.
Вместе с тем результат с шестипроцентным отклонением от оптимума требует оценки в содержательных показателях: сколько дополнительных затрат он создаёт, какие территории получают меньше ресурсов и насколько меняется охват населения.
Следующим этапом должна стать проверка метода на новых наборах данных и в условиях, приближённых к реальной работе органов здравоохранения. Потребуется также сравнить гибридную систему с другими современными способами ускорения оптимизации и определить, сохраняет ли она преимущество при изменении масштаба и структуры задачи.
Литература
Li K., Niwunhella H., Hajibabai L., Hajbabaie A. Machine learning-guided column generation for a maximal covering location–allocation problem // Sustainability Analytics and Modeling. — 2026. — Article 100069. — DOI: 10.1016/j.samod.2026.100069.