🔢 mathematics

Hybrid Quantum-Classical Branch-and-Price for Intra-Day Electric Vehicle Charging Scheduling via Partition Coloring

تقترح هذه الورقة خوارزمية هجينة من نوع (branch-and-price) تجمع بين الحوسبة الكمية والتقليدية، تدمج حلولاً مستوحاة من التلدين الكمي لمسألة التسعير لمعالجة جدولة شحن المركبات الكهربائية واسعة النطاق خلال اليوم والمصممة كمسألة تلوين التقسيم بكفاءة، مما يظهر أداءً فائقاً على النماذج المرجعية التقليدية في الحالات الصعبة.

المؤلفون الأصليون: Peng Sun, Liang Zhong, Qing-Guo Zeng, Li Wang

نُشر 2026-03-24

📖 4 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Peng Sun, Liang Zhong, Qing-Guo Zeng, Li Wang

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أنك مدير لمحطة شحن مركبات كهربائية (EV) مزدحمة. لديك أسطول من السيارات التي تصل وتغادر طوال اليوم، ولكن لديك عدد محدود من مقابس الشحن (لنفترض أنها 10 مقابس). كل سيارة تحتاج إلى الشحن لمدة زمنية محددة، لكن لا يمكنهم جميعاً التوصيل في وقت واحد لعدم وجود مقابس كافية.

هدفك بسيط: شحن كل سيارة وجعلها جاهزة للانطلاق في أسرع وقت ممكن دون أن يتشاجر أي شخص على نفس المقبس.

يبدو هذا سهلاً، لكنه في الواقع لغز رياضي هائل. إذا كان لديك 100 سيارة وكل سيارة لديها 10 أوقات مختلفة يمكنها فيها الشحن، فإن عدد الطرق التي يمكنك بها ترتيب الجدول الزمني هو عدد فلكي. محاولة إيجاد الجدول المثالي باستخدام كمبيوتر عادي يشبه محاولة العثور على إبرة معينة في كومة قش تكبر باستمرار في كل ثانية.

إليك كيف حل مؤلفو هذه الورقة البحثية ذلك اللغز، مشروحاً بأسلوب مبسط.

1. المشكلة: "ازدحام مروري" في الوقت

فكر في كل سيارة كشخص يحاول دخول حفلة، ولكن للحفلة قاعدة صارمة: يمكن لشخص واحد فقط من كل عائلة الدخول في كل مرة.

العائلات: هي السيارات.
أوقات الدخول: لكل سيارة قائمة بأوقات الوصول المحتملة (على سبيل المثال: 9:00 صباحاً، أو 10:00 صباحاً، أو 11:00 صباحاً).
التعارض: إذا وصلت السيارة (أ) في الساعة 9:00 صباحاً والسيارة (ب) في الساعة 9:00 صباحاً، فلا يمكنهما استخدام نفس المقبس. وأيضاً، لا يمكن للسيارة (أ) أن تكون في مكانين في وقت واحد (لا يمكنها الشحن في الساعة 9:00 صباحاً و الساعة 10:00 صباحاً).

وظيفة الكمبيوتر هي اختيار "وقت دخول" واحد بالضبط لكل سيارة بحيث لا يحدث أي تعارض بين السيارتين، وأن تنتهي الحفلة بأكملها في أقرب وقت ممكن.

2. الطريقة القديمة: الكمبيوتر "خارق الذكاء"

تقليدياً، استخدم الباحثون أجهزة كمبيوتر قوية (مثل جهاز Gurobi) لحل هذه المسألة. كانوا يحاولون حساب كل التشكيلات الممكنة.

الحفلات الصغيرة: إذا كان هناك 10 سيارات فقط، يحلها الكمبيوتر في لمح البصر.
الحفلات الضخمة: إذا كان هناك 100 سيارة، يصاب الكمبيوتر بالارتباك. يبدأ في الحساب، والحساب، والحساب، ولكن بعد مرور ساعة (المهلة الزمنية)، لم يجد بعد الإجابة المثالية. إنه يستسلم مع إجابة "جيدة بما يكفي" قد تترك بعض السيارات تنتظر لفترة طويلة جداً.

3. الفكرة الجديدة: "الفريق الهجين"

أدرك المؤلفون أنه بدلاً من مطالبة الكمبيوتر بالقيام بـ كل شيء، يجب عليهم تقسيم العمل. لقد أنشأوا فريقاً هجيناً من الحوسبة الكمومية والكلاسيكية.

فكر في الأمر كأنه موقع بناء:

المدير العام (الكمبيوتر الكلاسيكي/Guroi): هذا هو المدير. ينظر إلى الصورة الكبيرة، ويقرر أي السيارات مجدولة حالياً، ويتأكد من اتباع القواعد. هو بارع جداً في التنظيم ولكنه بطيء في إيجاد أفكار جديدة ومبتكرة.
المستكشف المبدع (خوارزمية مستوحاة من الكم): هذا هو المساعد الجديد. مهمته الوحيدة هي البحث عن جدول زمني أفضل لمجموعة صغيرة من السيارات. وهو يستخدم تقنيات "التلدين الكمي" (تحديداً BSB و SimCIM).

ما هو التلدين الكمي (Quantum Annealing)؟
تخيل أنك في وادي مظلم وضبابي ومعك كرة. تريد إيصال الكرة إلى أدنى نقطة في الوادي (الحل الأفضل).

الكمبيوتر العادي يدحرج الكرة ببطء، خطوة بخطوة. قد يعلق في منخفض صغير (فخ محلي) ويظن أنه وصل إلى القاع.
الخوارزمية المستوحاة من الكم تشبه إعطاء الكرة "قفزة كمومية" صغيرة. يمكنها النفاذ عبر التلال الصغيرة أو هز الأرض لمساعدة الكرة على الهروب من تلك المنخفضات الصغيرة والعثور على القاع الحقيقي بشكل أسرع بكثير.

4. كيف يعملان معاً (رقصة "التفرع والأسعار")

تصف الورقة البحثية رقصة محددة تسمى Branch-and-Price:

المدير (Guroi) يضع جدولاً زمنياً أولياً.
يتم سؤال المستكشف (الخوارزمية الكمومية): "مهلاً، هل يمكنك العثور على طريقة أفضل لجدولة هذه السيارات المحددة فقط؟"
يستخدم المستكشف "قفزاته الكمومية" للعثور بسرعة على ترتيب أفضل فات المدير.
يأخذ المدير هذه الفكرة الجديدة، ويحدث الجدول الزمني، ويتأكد من صحته.
يكررون العملية حتى يصبح الجدول الزمني مثالياً.

5. النتائج: لماذا يهم هذا؟

اختبر الباحثون هذا على سيناريوهات وهمية تتراوح من مجموعات صغيرة إلى أساطيل ضخمة مكونة من 100 سيارة.

المجموعات الصغيرة: عمل الفريق الجديد بنفس سرعة الكمبيوتر القديم. لم تكن هناك حاجة للسحر بعد.
المجموعات الكبيرة (الاختبار الحقيقي): هنا حدث السحر.
- الكمبيوتر القديم تعثر. لقد استمر في العمل لمدة ساعة، ثم استسلم وقال: "أنا متأكد بنسبة 40% أن هذا هو أفضل ما يمكنني فعله".
- الفريق الهجين وجد الحل المثالي في نصف الوقت. لم يعلقوا في "منخفضات" الوادي.

الخلاصة

تثبت هذه الورقة البحثية أننا لسنا بحاجة لانتظار أجهزة كمبيوتر كمومية مثالية ومستقبلية لحل المشكلات الصعبة. من خلال دمج القليل من "التفكير الكمي" (المحاكى على أجهزة كمبيوتر عادية) مع الرياضيات التقليدية، يمكننا حل مشكلات الجدولة الضخمة - مثل شحن مئات السيارات الكهربائية بكفاءة - والتي كانت في السابق صعبة للغاية على أجهزة الكمبيوتر القياسية.

الأمر يشبه ترقية دراجة هوائية بمحرك كهربائي صغير: أنت لا تحتاج إلى صاروخ لتصبح أسرع؛ أنت فقط بحاجة إلى دفعة ذكية في اللحظات المناسبة.

إليك ملخص تقني مفصل للورقة البحثية بعنوان: "الخوارزمية الهجينة الكمية-الكلاسيكية (Branch-and-Price) لجدولة شحن المركبات الكهربائية خلال اليوم عبر تلوين التقسيم (Partition Coloring)."

1. تعريف المشكلة

تتناول الورقة مشكلة جدولة شحن المركبات الكهربائية (EV) خلال اليوم الواحد. يتضمن هذا التحدي التشغيلي تخصيص فترات الشحن لأسطول من المركبات الكهربائية خلال يوم واحد تحت قيود صارمة:

الموارد المحدودة: يتوفر عدد ثابت من أجهزة الشحن الفيزيائية ( $C$ ).
النوافذ الزمنية: لكل مركبة وقت وصول محدد، وموعد نهائي للمغادرة، ومتطلبات طاقة.
المرونة: يمكن شحن المركبات خلال فترات زمنية مرشحة متعددة ضمن فترة بقائها، ولكن يجب اختيار فترة واحدة بالضبط لكل مركبة.
التعارضات: تنشأ التعارضات من مصدرين:
1. التداخل الزمني/الموردي: لا يمكن جدولة فترتين في وقت واحد إذا تجاوزتا سعة الشاحن.
2. حصرية المركبة: يمكن اختيار فترة زمنية واحدة فقط لكل مركبة.

قام المؤلفون بنمذجة هذه المشكلة كمتغير من مشكلة تلوين التقسيم (PCP). في هذه الصياغة الرسومية:

التقسيمات (Partitions): تمثل كل مركبة تقسيماً.
الرؤوس (Vertices): تمثل فترات الشحن المرشحة لكل مركبة رؤوساً داخل ذلك التقسيم.
الحواف (Edges): تربط الحواف بين الرؤوس التي تتعارض (إما لأنها تنتمي لنفس المركبة أو لأن نوافذهما الزمنية تتداخل).
الهدف: اختيار رأس واحد بالضبط من كل تقسيم بحيث تشكل الرؤوس المختارة "مجموعة مستقلة" (Independent Set) (أي لا توجد تعارضات) مع تقليل عدد الشواحن المستخدمة (أو وقت الإنجاز/Makespan) إلى الحد الأدنى.

2. المنهجية

يقترح المؤلفون خوارزمية Branch-and-Price (B&P) هجينة كمية-كلاسيكية. يقوم هذا الإطار بتفكيك المشكلة إلى "مسألة رئيسية" (Master Problem) و"مسألة تسعير فرعية" (Pricing Subproblem)، مع الاستفادة من الحلّال الكلاسيكية للمسألة الأولى والحلول المستوحاة من الكم للمسألة الثانية.

أ. إطار عمل Branch-and-Price

المسألة الرئيسية المقيدة (RMP):
- تمت صياغتها كاسترخاء للبرمجة الخطية (LP relaxation).
- تختار مجموعات قابلة للتنفيذ من الفترات (الأعمدة) لتقليل الهدف (مثل وقت الإنجاز).
- تُحل باستخدام الحلّال التجاري الكلاسيكي Gurobi.
- تولد متغيرات مزدوجة (Dual Variables) لتوجيه عملية البحث عن أعمدة جديدة.
مسألة التسعير الفرعية (Pricing Subproblem):
- الهدف هو العثور على عمود (مجموعة مستقلة قابلة للتنفيذ من الفترات) ذات تكلفة مختزلة سالبة لإضافتها إلى الـ RMP.
- رياضياً، هذه هي مسألة أكبر مجموعة مستقلة ذات وزن (MWIS) مع قيود التقسيم.
- النهج الكلاسيكي: تُحل مباشرة بواسطة Gurobi (كخط أساس للمقارنة).
- النهج الهجين: تتم إعادة صياغتها كنموذج تحسين ثنائي تربيعي غير مقيد (QUBO).
  - دالة الهدف تعظم وزن الرؤوس المختارة.
  - يتم ترميز القيود (اختيار التقسيم وتجنب التعارض) كحدود عقوبة تربيعية في "الهاملتوني" (Hamiltonian).
  - الحلّال (Solver): يتم حل الـ QUBO باستخدام خوارقات مستوحاة من التلدين الكمي (QAIA) مُنفذة في إطار عمل MindQuantum. وتحديداً، تم اختبار خوارزميتين:
    - التفرع المتشعب البالستي (BSB): يستخدم قيود الحدود غير المرنة لقمع الأخطاء التناظرية.
    - آلة إيسينج المتماسكة المحاكية (SimCIM): تحاكي ديناميكيات آلة إيسنج المتماسكة على متغيرات لف (Spin) مستمرة.
مخطط التفرع (Branching Scheme):
- لضمان التكامل (Integrality)، يتم تطبيق استراتيجية تفرع مخصصة عندما يكون حل الـ RMP كسرياً.
- التفرع القائم على المجموعات الفرعية: يفرض فترة زمنية معينة لمركبة ما أو يمنعها.
- التفرع الثنائي (Pairwise Branching): يفرض أن فترتين متنافستين من مركبات مختلفة إما أن يتم اختيارهما معاً (دمجهما في رأس فائق) أو فصلهما (إضافة حافة إلى رسم التعارض).

3. المساهمات الرئيسية

صياغة مبتكرة: هذه هي أول صياغة منهجية لجدولة شحن المركبات الكهربائية كـ مشكلة تلوين التقسيم (PCP). تتعامل هذه الصياغة مع قيد "فترة واحدة لكل مركبة" وتعارضات الموارد المعقدة بشكل طبيعي أكثر من نماذج البرمجة الخطية المختلطة (MILP) التقليدية المعتمدة على الفترات الزمنية.
تصميم خوارزمية هجينة: تقدم الورقة خوارزمية Branch-and-Price حيث يتم إسناد مسألة التسعير الفرعية المكلفة حاسوبياً إلى الحلّال المستوحاة من الكم (BSB و SimCIM)، بينما تظل المسألة الرئيسية على حلّال كلاسيكي.
القابلية للتوسع عبر QAIA: من خلال دمج حلّالات QAIA الخاصة بـ MindQuantum، يظهر الإطار القدرة على حل مسائل تركيبية واسعة النطلة وصعبة يصعب حلها بالطرق الكلاسيكية البحتة ضمن حدود زمنية معقولة.

4. النتائج الحسابية

أجرى المؤلفون تجارب مكثفة على نماذج اصطناعية تتراوح من عدد مركبات صغير ( $V=10$ ) إلى كبير ( $V=100$ )، مع تباين في سعات الشواحن.

النماذج الصغيرة والمتوسطة ( $V \le 40$ ):
- أدت الطرق المعززة بـ QAIA (مثل BSB و SimCIM) أداءً مقارباً لخط الأساس (Guroth) النقي.
- حققت جميع الطرق فجوة مثالية صفرية وحلت النماذج في نطاق أجزاء من الثانية إلى عشرات الثواني.
النماذج الكبيرة والصعبة ( $V \ge 80$ ):
- خط الأساس (Gurobi النقي): عانى بشكل كبير. في أكبر النماذج ( $V=100$ )، غالباً ما وصل إلى الحد الزمني الأقصى (3600 ثانية) مع وجود فجوات مثالية غير صفرية (تصل إلى 40%)، وفشل في إثبات المثالية.
- متغيرات QAIA (BSB/SimCIM): تفوقت باستمرار على خط الأساس.
  - نجحت في إغلاق الفجوات المثالية لتصل إلى 0% ضمن نفس الميزانية الزمنية.
  - حققت أوقات تشغيل إجمالية أقل بكثير (على سبيل المثال، حل نموذج $V=100$ في حوالي 900 ثانية مقابل 3600 ثانية لـ Gurobi).
  - ولدت أعمدة عالية الجودة بكفاءة أكبر، مما سمح باستكشاف شجرة Branch-and-Price بعدد أقل من العقد.
مقارنة بين QAIA: أظهر كل من BSB و SimCIM أداءً قوياً، مع تفوق BSB غالباً في السرعة في النماذج الأكبر، وإن كان كلاهما فعالاً.

5. الأهمية والخاتمة

تثبت الورقة أن دمج الخوارقات المستوحاة من التلدين الكمي (QAIA) في مخططات التفكيك الكلاسيكية هو اتجاه واعد للغاية لحل مشا-ل التحسين التركيبية واسعة النطاق.

الأثر العملي: يوفر الأسلوب المقترح حلاً قابلاً للتطبيق لإدارة أساطيل المركبات الكهربائية الواقعية واسعة النطاق حيث تكون سعة الشحن ضيقة وتعقيد الجدولة مرتفعاً.
الرؤية النظرية: تؤكد الورقة صحة صياغة PCP لجدولة المركبات الكهربائية وتثبت أن النهج الهجين (كمي-كلاسيكي) يمكن أن يتغلب على قيود القابلية للتوسع التي تواجهها الحلّالات الكلاسيكية البحتة (مثل Gurobi) في سياق توليد الأعمدة.
العمل المستقبلي: يقترح المؤلفون توسيع الإطار ليشمل قيود شبكة أكثر ثراءً، وتوليد نماذج قائمة على البيانات، ودمج خوارقات كمية متغيرة أخرى.

باختصار، نجحت الدراسة في جسر الفجوة بين التحسين المستوحى من الكم النظري والجدولة الصناعية العملية، مظهرة أن الحلّال الهجينة يمكن أن تقدم حلولاً مثالية مثبتة لمشكلات تعد حالياً مستعصية على أفضل الحلّال الكلاسيكية المتطورة.