اقترح العلماء خوارزمية تتنبأ بحركة المرور أسرع بعشرات المرات قبل سنوات.

بالنسبة لتنبؤات حركة المرور قصيرة المدى – من ثوانٍ إلى عدة ساعات – يتم استخدام أساليب التعلم الآلي. ومع ذلك، بالنسبة للتخطيط طويل المدى (من أيام إلى عقود)، يستخدم المهندسون نماذج رياضية تعتمد على التوزيع المتوازن للتدفقات: من المفترض أن يختار كل سائق أسرع طريق، ويعتمد وقت السفر على الازدحام المروري. تتطلب الخوارزميات الكلاسيكية لحل مثل هذه المشكلات، ولا سيما طريقة Frank-Wolf، في كل خطوة البحث عن أقصر المسارات من جميع مناطق المصدر. للقيام بذلك، نستخدم خوارزمية ديكسترا، وهي طريقة قياسية للعثور على أقصر الطرق في الرسم البياني للطريق. يقوم خطوة بخطوة بالعثور على الحد الأدنى من وقت السفر من مصدر واحد إلى جميع التقاطعات، وفي كل تكرار، يتم اختيار العقدة التي لم تتم معالجتها بعد الأقرب إلى المصدر والتحقق مما إذا كان من الممكن تقليل الوقت الحالي المعروف إلى العقد المجاورة من خلاله. في الشبكات الكبيرة، يستغرق تشغيل Dijkstra من مصدر واحد ثوانٍ، ولكن مع آلاف المصادر، يمكن أن يستغرق تكرار الطريقة ساعات. وفي شبكات الطرق الكبيرة (على سبيل المثال، البيانات الحقيقية لشيكاغو وفيلادلفيا وبرمنغهام) يؤدي هذا إلى تكاليف حسابية ضخمة. اقترح فريق من المؤلفين من مختبر MIPT للتوافقيات المتقدمة وتطبيقات الشبكات استخدام نهج مستخدم في التعلم الآلي: لا يتم أخذ كمية البيانات بأكملها للحساب، ولكن جزء عشوائي فقط. في كل تكرار للخوارزمية، اختاروا عشوائيًا جزءًا صغيرًا (على سبيل المثال، 10%) من جميع الأصول، وشكلوا أزواجًا من الأصل والوجهة، وحسبوا أقصر المسارات لهم فقط. وفي الوقت نفسه، تم تقليل وقت الحساب بشكل كبير (بمقدار 10 مرات لعينة 10٪)، وكان الفرق في التوزيع النهائي للتدفقات صغيرًا. تُسمى الطريقة الجديدة بالنسخة العشوائية من طريقة فرانك-وولف (Stochastic Origin Frank-Wolfe (SOFW)). تم نشر العمل، بدعم من منحة من مؤسسة العلوم الروسية (المشروع رقم 21-71-30005-P)، في مجلة العلوم الرياضية. ثمن التسارع هو زيادة الحمل على ذاكرة الوصول العشوائي. الآن لا تقوم الخوارزمية بتخزين إجمالي تدفق حركة المرور على كل طريق فحسب، بل تقوم أيضًا بتخزين التدفق المنفصل لأزواج الوجهة الأصلية. يتيح لك ذلك تغيير تدفق السيارات في الخطوة التالية، مع مراعاة أقصر المسارات الجديدة، للأزواج المحددة فقط. نتيجة لذلك، إذا قمنا بحساب 10٪ من الأزواج، فيجب زيادة مقدار ذاكرة الوصول العشوائي 10 مرات، ولكن في الوقت نفسه سنحصل على ربح عشرة أضعاف في الوقت المناسب. في أنظمة الحوسبة الحديثة، هذا الحل الوسط له ما يبرره. واقترح الباحثون أيضًا نسخة مرجحة من الخوارزمية (SOFW-w). في ذلك، يتم اختيار المناطق التي تغادر منها المزيد من السيارات في كثير من الأحيان. يؤدي هذا إلى تسريع التقارب الأولي: في التكرارات الأولى، ينخفض ​​الخطأ بشكل أسرع من SOFW التقليدي. تم التنافس بين الخوارزميات الكلاسيكية والعشوائية على شبكات الطرق الحقيقية المتوفرة في مستودع شبكات النقل المفتوح. تحقق الطريقة الجديدة الدقة المحددة بشكل أسرع عدة مرات، وهو أمر ليس بالغ الأهمية بالنسبة للرسوم البيانية الصغيرة (سيوكس فولز، 24 منطقة؛ أنهايم، 38 منطقة)، ولكنه ملحوظ جدًا في المناطق الكبيرة – فيلادلفيا (1525 منطقة، 40 ألف طريق) وشيكاغو والمناطق المحيطة بها (1790 منطقة، 39 ألف طريق). إن التسارع بمقدار عشرة أضعاف على شبكة صغيرة يحول ألف عملية إلى 100 عملية، ويكون التوفير غير محسوس. على شبكة كبيرة، نفس 10 مرات تحول 100 مليون عملية إلى 10 ملايين، وهذا أمر أساسي بالفعل. وبالتالي، يوفر SOFW مقايضة عملية بين جودة الحل والتكلفة الحسابية. © AI Generation ChatGPT “في رأيي، من المهم إدراك هذا العمل ليس فقط كخوارزمية لتحسين تدفقات حركة المرور، ولكن أيضًا كمثال لفكرة أكثر عمومية: يمكن تسريع الخوارزميات في مشاكل التحسين التي تستخدم أوراكل التقليل الخطي (أي روتين فرعي يجد في كل خطوة أقصر المسارات لجميع الأزواج من إلى إلى إلى) بشكل كبير، خاصة في المسائل عالية الأبعاد، حيث يكون مثل هذا أوراكل بمثابة عنق الزجاجة”. إجناشين، موظف في مختبر التوافقيات المتقدمة وتطبيقات الشبكات، MIPT. يؤكد المؤلفون على أن الطرق العشوائية (المبنية على اختيار عشوائي لجزء من البيانات) توفر ميزة واضحة عند نمذجة أنظمة النقل الكبيرة. ومع ذلك، فإنهم يعتبرون الاتجاه الرئيسي للبحث المستقبلي ليس فقط استخدام الخوارزمية الخاصة بهم، ولكن أيضًا نشر الفكرة نفسها – إدخال اختيار عشوائي لأجزاء البيانات في طرق التحسين الكلاسيكية الأخرى. وعلى وجه الخصوص، من المخطط تطبيق هذا النهج على الإصدارات المتسارعة من طريقة فرانك وولف وعلى المخططات الهجينة الأخرى. وهذا سيجعل من الممكن إنشاء خوارزميات أكثر كفاءة ومرونة لحساب حركة المرور المتوازنة، بالإضافة إلى المشكلات ذات الصلة حيث يكون من الضروري البحث بشكل متكرر عن أقصر المسارات على الرسوم البيانية الكبيرة.