Гибридный подход для решения реальных

Научные отчеты, том 13, Номер статьи: 11777 (2023) Цитировать эту статью

418 Доступов

2 Альтметрика

Подробности о метриках

Эффективная упаковка товаров в контейнеры — обычная повседневная задача. Известная как «Проблема упаковки контейнеров», она интенсивно изучалась в области искусственного интеллекта благодаря широкому интересу со стороны промышленности и логистики. На протяжении десятилетий было предложено множество вариантов, причем трехмерная задача упаковки в контейнеры оказалась наиболее близкой к реальным вариантам использования. Мы представляем гибридную квантово-классическую основу для решения реальных трехмерных задач упаковки контейнеров (Q4RealBPP), учитывая различные реалистичные характеристики, такие как: (1) размеры упаковки и контейнера, (2) ограничения по избыточному весу, (3) сходство между категории товаров и (4) предпочтения для заказа товаров. Q4RealBPP позволяет решать практические задачи с уровнем шума 3 дБПП, учитывая ограничения, которые хорошо ценятся в промышленном и логистическом секторах.

Оптимизация упаковки продукции в ограниченное количество контейнеров является важнейшей повседневной задачей в сфере производства и распределения. В зависимости от характеристик упаковок и контейнеров можно сформулировать несколько задач по упаковке, обычно известных как проблемы упаковки в контейнеры (BPP)1. В этой категории одномерный BPP (1 dBPP) считается самым простым2, цель которого — упаковать все предметы в как можно меньшее количество контейнеров. Для решения реальных ситуаций в логистике и промышленности3 было предложено множество вариантов с переменным количеством ограничений. Трехмерный BPP (3 dBPP)4, в котором каждая упаковка имеет три измерения: высоту, ширину и глубину, является самым известным и наиболее сложным вариантом. Как было отмечено в нескольких исследованиях5,6,7, уровень 3 дБПП представляет практический интерес во многих промышленных условиях. В последние годы он был разработан для разнообразных практических применений, таких как погрузка поддонов8, автомобильные перевозки9, авиаперевозки10 и т. д. Из-за своей сложности уровень 3 дБПП также периодически используется в качестве эталона для тестирования недавно разработанных методов и механизмов11,12. .

С другой стороны, квантовые вычисления все еще находятся на ранней стадии своего развития, но привлекли много внимания научного сообщества, поскольку предлагают исследователям и практикам революционную парадигму для решения различных видов практических задач оптимизации13,14,15,16. В частности, квантовые отжиги недавно были применены для решения широкого спектра задач оптимизации, связанных с промышленностью17, логистикой18 и экономикой19. Однако исследования BPP, проводимые в квантовом сообществе, по-прежнему скудны, хотя BPP широко изучается классически как задача оптимизации.

Новаторская работа по BPP в области квантовых вычислений представляет собой гибридный квантово-классический метод решения задачи 1 dBPP20, решатель которого состоит из двух модулей: (1) квантовой подпрограммы для поиска набора возможных конфигураций для заполнения одной одиночный интервал и (2) классическая вычислительная эвристика, которая строит полные решения, используя подмножества, заданные квантовой подпрограммой. Чтобы улучшить производительность разработанной квантовой подпрограммы, были проведены дальнейшие тесты на основе случайной выборки и эвристики, основанной на случайном блуждании21. Помимо этих двух статей, в дополнительном исследовании формулируется проблема, связанная с атомной энергетикой, как 1 дБПП, решаемая с использованием квантового отжигателя D-Wave22. Другие работы показывают методы квантовых эволюционных вычислений как альтернативу решению проблем, связанных с BPP23,24,25. Квантовые методы представляют собой особый класс эволюционных алгоритмов, которые используют квантовую физику для определения своих операций и предназначены для выполнения на классическом компьютере26. Таким образом, их невозможно выполнить ни на одной квантовой машине.

В отличие от 1 дБПП, решение проблемы 3 дБПП в квантовой области является гораздо более сложной задачей по двум взаимосвязанным причинам: (1) его сложность, которая возрастает по мере того, как принимаются во внимание ограничения реального мира, и (2) начальное состояние развитие нынешних коммерческих квантовых компьютеров, возможности которых все еще ограничены декогеренцией и ошибками, что может стать препятствием для решения сильно ограниченных задач. В этой статье мы представляем гибридную квантово-классическую вычислительную структуру для ориентированной на реальный мир задачи 3 дБПП, которая называется «Квантовая задача для реальной упаковки контейнеров» (Q4RealBPP). Предлагаемая структура использует гибридный решатель квадратичной модели с ограничениями Leap (CQM) (LeapCQMHybrid27) компании D-Wave. При этом Q4RealBPP построен на существующем коде28. Этот справочный код является отличной отправной точкой, которая проложила путь к двум основным разработкам, разработанным в этой работе: