تحليل واقعي لشبكة الطرق وحل VRP في القاهرة باستخدام OSMNx وGoogle OR-Tools

في هذا التمرين، قمتُ بتجربة عملية لحل مشكلة توجيه المركبة الواحدة (Vehicle Routing Problem - VRP)، والتي تهدف إلى إيجاد أفضل مسار لمركبة واحدة تمرّ بـ10 نقاط متفرقة داخل مدينة القاهرة بأقل تكلفة وزمن ممكن. بدأت من نقطة محددة داخل المدينة، وقمت باستخلاص شبكة الطرق في نطاق دائرة نصف قطرها 25 كم باستخدام مكتبة OSMNx. بعد ذلك، أضفت بيانات السرعات وأوقات السفر لكل طريق بهدف توفير معلومات دقيقة لاختيار المسار الأمثل.

استخدمت مكتبة networkX لحساب أقصر مسار بين كل نقطتين من خلال خوارزمية Dijkstra، وهي إحدى أشهر الخوارزميات المستخدمة في تحليل الشبكات. تعتمد هذه الخوارزمية على مبدأ تقسيم المشكلة المعقدة إلى مشكلات فرعية أصغر يتم حلها بشكل تكراري، ما يسمح بتحديد المسارات تدريجيًا بدءًا من نقطة الانطلاق حتى الوصول إلى النقطة التالية الأقرب.

تُعد خاصية البحث في الرسم البياني (Graph Search) جزءًا أساسيًا من خوارزمية Dijkstra، حيث أن الخريطة يتم تمثيلها كرسم بياني يتكون من عُقد (Nodes) وروابط (Edges)، وتعمل الخوارزمية على إيجاد أقصر مسار بين هذه العقد من خلال استكشاف هذا الرسم البياني.

بعد جمع بيانات المسافات وأوقات السفر بين النقاط، أنشأت مصفوفة تخزين مؤقت للمسافات، ثم استخدمت مكتبة ORTools التابعة لشركة Google لحل المشكلة باستخدام خوارزمية أخرى تُعرف بـ PATH_CHEAPEST_ARC. ساعدتني هذه الخوارزمية في تحديد أفضل ترتيب لزيارة النقاط العشر بحيث يتم الوصول إليها بأقل وقت وتكلفة ممكنة.

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

الترتيب الذي اقترحته الخوارزمية كان كالتالي:

Route for driver: [0, 4, 1, 9, 8, 3, 2, 6, 5, 7]

المسافة الإجمالية: 3.32 كم

عدد النقاط التي تم زيارتها: 10 نقاط

في المرحلة الأخيرة، قمت برسم الشبكة على خريطة تفاعلية باستخدام مكتبة folium، لعرض المسار بشكل بصري على الخريطة. كما أنشأت توزيعًا زمنيًا للمسافات بين النقاط لتوضيح المناطق ذات الطرق الأسرع والأبطأ.

وكان الناتج النهائي تحليلًا شاملًا لشبكة الطرق مع تحديد المسار الأمثل لمركبة واحدة لتغطية 10 نقاط بأقل تكلفة وأسرع وقت ممكن.

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

ولا تنسوا الاطلاع على الكود الذي قمت برفعه للاستفادة.