Domination Metric Dimension of Graph Classes and Its Application to Electric Logistics Network Optimization

تخيل مدينة حيث كل زاوية شارع، وكل مستودع، وكل محطة شحن هي نقطة على خريطة، متصلة بطرق تشكل شبكة واسعة ومعقدة. وللتنقل في هذه الشبكة بكفاءة، خاصة لشاحنات التوصيل الكهربائية ذات عمر البطارية المحدود، يحتاج السائقون وأجهزة الكمبيوتر إلى معرفة مكانهم بالضبط وكيفية الوصول إلى وجهتهم دون إهدار الطاقة. في عالم الرياضيات، تُسمى هذه الشبكة "رسمًا بيانيًا" (graph)، وتُسمى النقاط "رؤوسًا" (vertices). لعقود من الزمن، درس علماء الرياضيات كيفية تحديد كل نقطة في مثل هذه الشبكة باستخدام أقل عدد ممكن من نقاط المرجع. واكتشفوا أنه إذا اخترت مجموعة صغيرة من المواقع الخاصة، يمكنك قياس المسافة من أي موقع آخر في المدينة إلى تلك النقاط الخاصة. وإذا كان نمط المسافات فريدًا لكل موقع، يمكنك تحديد مكانك بدقة دون الحاجة إلى رؤية الخريطة بأكملها. يُعرف هذا المفهوم باسم "البعد المتري" (metric dimension).

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

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

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

يبسط هذا النهج المشكلة بشكل كبير. فمن خلال اختزال الشبكة إلى مجموعة من المسافات بالنسبة لمجموعة استراتيجية صغيرة من النقاط، لا يحتاج الكمبيوتر إلى معالجة الخريطة بأكملها للعثور على مسار. اختبر الباحثون هذه الفكرة باستخدام عمليات محاكاة لشبكات لوجستية تتراوح من 50 إلى 500 موقع. وفي هذه الاختبارات، قارنوا طريقتهم الجديدة بخوارزميات التوجيه القياسية مثل "ديكسترا" (Dijkstra) و"A*"، وهي المعايير الصناعية لإيجاد أقصر مسار. وأظهرت النتائج أنه بينما أنتجت الطرية الجديدة مسارات مشابهة جدًا في الطول للطرق القياسية، إلا أنها كانت أسرع بشكل ملحوظ. في اختبار محدد، قللت الطريقة الجديدة الوقت اللازم لحساب المسار من 92 مللي ثانية إلى 29 مللي ثانية فقط، وهو انخفاض بأكثر من النصف. علاوة على ذلك، استهلكت الطريقة طاقة أقل في المحاكاة، حيث انخفضت من 18.4 كيلووات ساعة إلى 16.2 كيلووات ساعة لنفس الرحلة.

كما بحثت الدراسة في كيفية توسع هذه الطريقة مع زيادة حجم الشبكة. فعندما زاد عدد المواقع من 50 إلى 500، نما عدد نقاط المرساة الاستراتيجية ببطء شديد، من 9 إلى 37. وهذا يعني أنه حتى مع توسع الشبكة اللوجستية للمدينة، فإن تعقيد نظام الملاحة لا ينفجر بشكل هائل. تظل الشبكة قابلة للإدارة لأن عدد نقاط المرجع يظل صغيرًا بالنسبة للحجم الإجمالي. وقد أثبت الباحثون أن هذا الاختزال الهيكلي يسمح باتخاذ قرارات أسرع وتحسين تجميع مناطق التوصيل، وهو أمر بالغ الأهمية للمركبات الكهربائية التي تحتاج إلى تقليل مسافة السفر للحفاظ على عمر البطارية.

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