DOI: https://doi.org/10.1109/qcnc69040.2026.00093
تاريخ النشر: 2026-04-06
المؤلف: Wei‐Hao Huang وآخرون
الموضوع الرئيسي: خوارزميات وهندسة الحوسبة الكمومية
نظرة عامة
تقدم هذه الدراسة منهجية هجينة كمومية-كلاسيكية لمعالجة مشكلة توجيه المركبات ذات السعة المحدودة (CVRP) من خلال دمج تقنية توليد الأعمدة (CG) مع نهج مشغل التناوب الكمومي (QAOAnsatz). تقوم طريقة CG بتفكيك CVRP إلى مشكلة رئيسية مختصرة، تحدد تركيبات الطرق المثلى، ومشكلات فرعية تولد طرقًا محتملة مفيدة للإدراج. تستمر هذه العملية التكرارية حتى لا يمكن إجراء تحسينات إضافية. يتم استخدام QAOAnsatz لحل هذه المشكلات الفرعية، مع هاملتونيان خلط مصمم خصيصًا يفرض قيودًا من نوع واحد للحد من مساحة البحث.
لإدارة قيود السعة بشكل فعال ضمن إطار عمل QAOAnsatz، يقوم المؤلفون بتنفيذ نهج مستوحى من لاغرانج المعزز، والذي يلغي الحاجة إلى متغيرات زائدة إضافية ويقلل من عدد الكيوبتات المطلوبة. تشير التقييمات التجريبية على حالات CVRP صغيرة النطاق (حتى 6 عملاء) إلى أن QAOAnsatz يحقق تقاربًا أسرع نحو الطرق المثلى مقارنة بخوارزمية تحسين الكم التقريبية التقليدية (QAOA). تسلط هذه النتائج الضوء على إمكانيات الإطار الهجين المقترح لحل تحديات تحسين اللوجستيات في العالم الحقيقي باستخدام موارد الحوسبة الكمومية القريبة من المدى.
مقدمة
تستعرض مقدمة هذه الورقة البحثية أهمية تحسين التوليفات، لا سيما في اللوجستيات، حيث تعتبر مشكلة توجيه المركبات ذات السعة المحدودة (CVRP) مثالًا رئيسيًا. تهدف CVRP إلى تقليل تكاليف التسليم مع الالتزام بقيود سعة المركبات، وقد تم تطوير خوارزميات مختلفة لمعالجة هذا التحدي. تسلط الورقة الضوء على إمكانيات الحوسبة الكمومية لتعزيز عمليات التحسين، خاصة من خلال خوارزمية تحسين الكم التقريبية (QAOA) وتعميمها، نهج مشغل التناوب الكمومي (QAOAnsatz). بينما تتعامل QAOA بشكل فعال مع مشكلات مثل مشكلة القطع القصوى، إلا أنها تواجه صعوبات مع القيود الموجودة في التطبيقات الواقعية، والتي تهدف QAOAnsatz إلى معالجتها.
يقترح المؤلفون نهجًا هجينيًا يجمع بين QAOAnsatz وطريقة توليد الأعمدة (CG) لحل CVRP. تقوم هذه الطريقة بتفكيك CVRP إلى مشكلة رئيسية مقيدة ومشكلات فرعية، مما يسمح بعملية حل أكثر قابلية للإدارة مع الحفاظ على الأمثلية. تقدم الدراسة أيضًا طريقة مستوحاة من لاغرانج المعزز (ALiM) للتعامل بفعالية مع قيود السعة، مما يقلل من متطلبات الكيوبتات في التطبيقات الكمومية. تم هيكلة الورقة لمناقشة أولاً المفاهيم الأساسية لـ QAOA و QAOAnsatz، تليها شرح مفصل لـ CVRP والمنهجية المقترحة، وتنتهي بنتائج تجريبية توضح فعالية النهج الهجين.
طرق
في هذا القسم، يوضح المؤلفون منهجيتهم لمعالجة مشكلة توجيه المركبات ذات السعة المحدودة (CVRP)، مع التركيز على قيودها الجوهرية والتحديات التوليفية في تحسين طرق التسليم تحت قيود السعة. يقدمون خوارزمية توليد أعمدة (CG) تقوم بتحسين المشكلة المزدوجة للمشكلة الرئيسية المقيدة (RMP) بشكل تكراري باستخدام حلول من المشكلات الفرعية (SP). كما يتم تقديم صياغة قائمة على الكم للمشكلات الفرعية، باستخدام تقنيات مثل طريقة لاغرانج المعززة و QAOAnsatz لإدارة قيود السعة واختيار الطرق ضمن إطار عمل الحوسبة الكمومية.
تشمل الإعدادات التجريبية حالات CVRP تم إنشاؤها عشوائيًا مع أربعة إلى ستة عملاء، حيث تكون سعة المركبة ثابتة عند \( W = 25 \) وطلبات العملاء \( w_i \) مأخوذة من النطاق [1، 15]. يتم إنشاء مجموعة الطرق الأولية من خلال ربط كل عميل مباشرة بالمخزن، مما يضمن الامتثال لسعة المركبة وبنية الطريق. تقارن الدراسة أداء خوارزمية تحسين الكم التقريبية القياسية (QAOA) و QAOAnsatz المقترحة، مما يكشف أن الأخيرة تتقارب بشكل أسرع بسبب تصميمها الذي يحافظ على القابلية. تشير النتائج إلى أن زيادة عدد طبقات QAOAnsatz تعزز سرعة التقارب، على الرغم من أنها تزيد أيضًا من التكاليف الحسابية. بالإضافة إلى ذلك، يتم تحليل تأثير تغيير عدد الطرق المرشحة في مجموعة المدخلات، مما يظهر أن عددًا أكبر من الطرق يمكن أن يحسن بشكل كبير من سرعة التقارب، لا سيما في الحالات التي تضم المزيد من العملاء.
نقاش
تناقش الورقة البحثية نهجًا هجينيًا كموميًا-كلاسيكيًا لحل مشكلة توجيه المركبات ذات السعة المحدودة (CVRP) من خلال دمج طريقة توليد الأعمدة (CG) مع نهج مشغل التناوب الكمومي (QAOAnsatz). يتم تقديم QAOA في البداية كخوارزمية تباينية كمومية مصممة لمعالجة مشكلة تحسين ثنائية غير المقيدة التربيعية (QUBO)، والتي تعتبر أساسية لصياغة CVRP. يوسع QAOAnsatz إطار QAOA من خلال السماح بمشغلات خلط محددة للمشكلة التي تستكشف مباشرة مساحات الحلول القابلة، مما يعزز كفاءة عملية التحسين.
تسلط الدراسة الضوء على التحديات المتعلقة بتحويل مشكلات التحسين المقيدة إلى صيغ QUBO، لا سيما عند التعامل مع المتغيرات الزائدة وطرق العقوبات. لمعالجة هذه القضايا، يقترح المؤلفون طريقة مستوحاة من لاغرانج المعززة (ALiM) التي تقلل من عدد الكيوبتات المطلوبة من خلال تضمين القيود مباشرة في دالة الهدف. تشير النتائج إلى أن QAOAnsatz يتفوق على QAOA التقليدية من حيث سرعة التقارب، لا سيما عند استخدام هاملتونيان خلط مصممة خصيصًا. تختتم الورقة بالتأكيد على الإمكانيات المستقبلية لتوسيع هذا النهج إلى حالات CVRP أكبر ومشكلات تحسين أخرى، مما يشير إلى أن دمج الخوارزميات الكمومية في سير العمل الكلاسيكي يمكن أن يعزز بشكل كبير التطبيقات العملية في التحسين.
DOI: https://doi.org/10.1109/qcnc69040.2026.00093
Publication Date: 2026-04-06
Author(s): Wei‐Hao Huang et al.
Primary Topic: Quantum Computing Algorithms and Architecture
Overview
This study introduces a hybrid quantum-classical methodology for addressing the Capacitated Vehicle Routing Problem (CVRP) by combining the Column Generation (CG) technique with the Quantum Alternating Operator Ansatz (QAOAnsatz). The CG method decomposes the CVRP into a reduced master problem, which identifies optimal route combinations, and subproblems that generate potentially beneficial routes for inclusion. This iterative process continues until no further improvements can be made. The QAOAnsatz is utilized to solve these subproblems, with a specially designed mixer Hamiltonian that enforces one-hot constraints to limit the search space.
To effectively manage capacity constraints within the QAOAnsatz framework, the authors implement an Augmented Lagrangian-inspired approach, which eliminates the need for additional slack variables and minimizes the qubit count required. Experimental evaluations on small-scale CVRP instances (up to 6 customers) indicate that the QAOAnsatz achieves faster convergence to optimal routes compared to the traditional Quantum Approximate Optimization Algorithm (QAOA). These findings highlight the potential of the proposed hybrid framework for solving real-world logistical optimization challenges using near-term quantum computing resources.
Introduction
The introduction of this research paper outlines the significance of combinatorial optimization, particularly in logistics, where the Capacitated Vehicle Routing Problem (CVRP) serves as a key example. CVRP aims to minimize delivery costs while adhering to vehicle capacity constraints, and various algorithms have been developed to address this challenge. The paper highlights the potential of quantum computing to enhance optimization processes, especially through the Quantum Approximate Optimization Algorithm (QAOA) and its generalization, the Quantum Alternating Operator Ansatz (QAOAnsatz). While QAOA effectively tackles problems like the max-cut problem, it struggles with constraints inherent in real-world applications, which QAOAnsatz aims to address.
The authors propose a hybrid approach that combines QAOAnsatz with the Column Generation (CG) method to solve CVRP. This method decomposes the CVRP into a restricted master problem and subproblems, allowing for a more manageable solution process while maintaining optimality. The study also introduces an Augmented Lagrangian-inspired Method (ALiM) to effectively handle capacity constraints, reducing the qubit requirements in quantum implementations. The paper is structured to first discuss the foundational concepts of QAOA and QAOAnsatz, followed by a detailed explanation of CVRP and the proposed methodology, culminating in experimental results that demonstrate the effectiveness of the hybrid approach.
Methods
In this section, the authors detail their methodology for addressing the Capacitated Vehicle Routing Problem (CVRP), emphasizing its inherent constraints and the combinatorial challenges in optimizing delivery routes under capacity limitations. They introduce a column generation (CG) algorithm that iteratively refines the dual problem of the restricted master problem (RMP) using solutions from subproblems (SP). A quantum-based formulation for the subproblems is also presented, utilizing techniques such as the Augmented Lagrangian-inspired Method and QAOAnsatz to manage capacity constraints and route selection within a quantum computing framework.
The experimental setup involves randomly generated CVRP instances with four to six customers, where the vehicle capacity is fixed at \( W = 25 \) and customer demands \( w_i \) are drawn from the range [1, 15]. The initial route set is established by directly connecting each customer to the depot, ensuring compliance with vehicle capacity and route structure. The study compares the performance of the standard Quantum Approximate Optimization Algorithm (QAOA) and the proposed QAOAnsatz, revealing that the latter converges more rapidly due to its feasibility-preserving design. The results indicate that increasing the number of QAOAnsatz layers enhances convergence speed, although it also raises computational costs. Additionally, the impact of varying the number of candidate routes in the input set is analyzed, demonstrating that a larger number of routes can significantly improve convergence speed, particularly in instances with more customers.
Discussion
The research paper discusses a hybrid quantum-classical approach to solving the Capacitated Vehicle Routing Problem (CVRP) by integrating the Column Generation (CG) method with the Quantum Alternating Operator Ansatz (QAOAnsatz). The QAOA is initially introduced as a quantum-classical variational algorithm designed to tackle the Quadratic Unconstrained Binary Optimization (QUBO) problem, which is foundational for formulating CVRP. The QAOAnsatz extends the QAOA framework by allowing for problem-specific mixing operators that directly explore feasible solution spaces, thereby enhancing the efficiency of the optimization process.
The study highlights the challenges of converting constrained optimization problems into QUBO formulations, particularly when dealing with slack variables and penalty methods. To address these issues, the authors propose an Augmented Lagrangian-inspired Method (ALiM) that minimizes the number of qubits required by embedding constraints directly into the objective function. The results indicate that the QAOAnsatz outperforms traditional QAOA in terms of convergence speed, particularly when tailored mixer Hamiltonians are employed. The paper concludes by emphasizing the potential for future work to expand this approach to larger CVRP instances and other optimization problems, suggesting that integrating quantum algorithms into classical workflows could significantly enhance practical applications in optimization.