إيجاد المسار ذي أصغر مجموع أوزان بين عقدتين على رسم بياني موزون — بصِيَغ single-source single-destination، single-source all-destinations، أو all-pairs. مسألة تأسيسية في OR على الرسوم البيانية؛ الخوارزميات الكلاسيكية: Dijkstra، Bellman-Ford، Floyd-Warshall. أكثر خوارزميات OR استدعاءً في الصناعة الحديثة.
باختصار
هل يبدو مألوفاً؟
- نحن مشغّل توجيه طرود محلّي — لـ5.000-50.000 طرد يوميًا نحتاج مسارات بأقلّ زمن من المستودع المركزي إلى عناوين العملاء؛ نحتاج تحسينًا متعدّد المعايير على الزمن والمسافة والوقود.
- نشغّل خدمة ميدانية حضرية بـ10-50 مركبة (سباكة، كهرباء، إصلاح أجهزة منزلية، تكييف)؛ نحسب أزمنة الانتقال بين العملاء ونريد محرّك حساب واعيًا بالمرور.
- نحن مركز إدارة مرور بلديّ؛ نريد جسرًا بين بيانات الاختناق في الوقت الحقيقي وشبكة الخرائط الثابتة لتقديم مسار أقصر واعٍ بالمرور لخدمات الطوارئ (سيارة إسعاف، إطفاء، شرطة).
- نحن مخطّطو شبكة دورية اتصالات؛ نحسب مسار إعادة توجيه الحزم بأدنى زمن استجابة بين موزّعَين (أو POPين)؛ بروتوكولات التوجيه مثل OSPF (Open Shortest Path First) تنفّذ هذا الحساب تحت.
- نحن مخطّطو سلسلة توريد؛ في شبكة مصنع-ميناء-مستودع-عميل نحتاج تكلفة التدفّق الأرخص بين كلّ زوج من العُقد (all-pairs shortest path) — عبر خيارات نقل متعدّدة الوسائط.
- نحن مشغّل طريق سريع أو شركة نقل؛ لتوجيه المسافات الطويلة نطبّق مسارًا أقصر بثلاثة معايير (وقود + رسوم + ساعات قيادة)؛ الرسم البياني الثابت لا يكفي، نبحث عن مسار أقصر مرتبط بالزمن.
- بدأ فريقنا البرمجي بتنفيذ Dijkstra مباشر، لكن استعلامات الوقت الحقيقي على رسوم كبيرة (1M+ عقدة، شبكة طرق على مستوى دولة) بطيئة — نقيّم حلولًا قائمة على المعالجة المسبقة (contraction hierarchies).
لماذا تهم
كيف تُحل
عمق تقني
كيف تُحل
عمق تقنيفي جملة واحدة: بمعلومية عُقَد (تقاطعات) + حواف موزونة (مسافة/زمن)، استخدم Dijkstra عند كون الحواف غير سالبة (في كلّ خطوة اختر الجار الأقرب وحدّث مسافات الجيران)، وBellman-Ford عند إمكان وجود حواف سالبة، وFloyd-Warshall عند الحاجة لمصفوفة مسافات all-pairs — يضمن كلٌّ منها الأمثلية.
تُدرَس هذه المسألة في أدبيات بحوث العمليات (التخصّص الذي يستخدم الرياضيات والحاسوب لحلّ قرارات الأعمال) بوصفها Shortest Path Problem (SPP — مسألة المسار الأقصر) — المسألة التأسيسية في OR على الرسوم البيانية، بنضوج 60+ عامًا. ثلاث صِيَغ رئيسة: single-source single-destination (نقطة-إلى-نقطة)، single-source all-destinations (من مصدر إلى جميع الوجهات)، all-pairs (كلّ زوج). تعود الخوارزميات الكلاسيكية التأسيسية إلى أواخر الخمسينيات والستينيات: Dijkstra لرسوم بحوافّ غير سالبة، Bellman-Ford للحواف السالبة، Floyd-Warshall لـall-pairs؛ وcontraction hierarchies الحديثة المبنيّة على المعالجة المسبقة تحقّق زمن استعلام دون المللي ثانية على شبكات طرق بمقياس وطني. ثلاث مراحل:
1. النمذجة. بيانات الإدخال: (أ) بنية الرسم البياني — مجموعة العُقد V (التقاطعات، المواقع، الموزّعات)، مجموعة الحواف E (الطرق، الوصلات)، أوزان الحواف w(u,v) (مسافة، زمن، تكلفة، زمن استجابة)، موجَّه (شارع باتّجاه واحد) أو غير موجَّه (اتّجاهان)، أوزان غير سالبة أو ربّما سالبة، مع أو بدون دورات سالبة، (ب) نوع الاستعلام — نقطة-إلى-نقطة (مصدر s، هدف t)، single-source all-destinations (مصدر s، هدف V)، all-pairs (كلّ زوج i,j)، (ج) الديناميكية — أوزان ثابتة، مرتبطة بالزمن (مرور يتغيّر بساعة اليوم) أو بتحديثات في الوقت الحقيقي (إغلاقات بسبب حوادث، طقس)، (د) تعدّد المعايير — أحادي الهدف (الزمن فقط) أو متعدّد الأهداف (زمن + مسافة + وقود + رسوم)؛ متعدّد الأهداف بمسارات Pareto-مثلى أو مجموع موزون، (هـ) القيود — حظر حسب نوع الطريق (الشاحنة لا تدخل بعض الطرق، الإسعاف مستثنى)، نوافذ زمنية (ساعات العمل)، سعة (حمولة منقولة). متغيّرات القرار: تسلسل الحواف على الرسم (s → … → t)، متغيّر “في المسار أم لا” لكلّ حافّة. الهدف: أقلّ مجموع لأوزان الحواف.
2. القرار بقيادة الحلّال. يتوقّف اختيار الخوارزمية على الرسم ونوع الاستعلام:
(أ) Dijkstra — حواف غير سالبة، مصدر واحد. جشِع (greedy — في كلّ خطوة الاختيار الأمثل محليًا): في كلّ خطوة استخرج من قائمة الأولوية العقدة غير المزارة ذات أصغر مسافة مؤقّتة وحدِّث مسافات جيرانها. تنفيذ binary heap بـO((V+E)logV)، Fibonacci heap بـO(E + V logV). تطبيقًا: single-source single-destination / single-source all-destinations، رسوم ثابتة صغيرة-متوسّطة (1K-100K عقدة).
(ب) Bellman-Ford — يدعم الحواف السالبة. استرخاء (إعادة فحص كلّ حافّة عن “هل يوجد مسار أقصر الآن”) عبر كلّ الحواف V-1 مرّة. تعقيد O(VE). كشف الدورة السالبة: إن استمرّ التحديث في التكرار V، توجد دورة سالبة والمسار الأقصر غير معرَّف. الاستخدام: رسوم بحوافّ سالبة (مراجحة مالية، تدفّق عكسيّ في شبكات التدفّق)، بروتوكولات توجيه distance-vector.
(ج) Floyd-Warshall — all-pairs، رسم صغير. برمجة ديناميكية: O(V³) زمنًا، O(V²) ذاكرةً. تطبيقًا: V ≤ 1.000 عقدة، حين يلزم all-pairs. يدعم الحواف السالبة (دون دورات).
(د) A — نقطة-إلى-نقطة موجَّه بالاستدلال.* متغيّر موجَّه نحو الهدف من Dijkstra؛ استدلال h(v) (مثلًا مسافة إقليدية / دائرة عظمى) يقود أولويات العُقد. Hart وNilsson وRaphael (1968). تطبيقًا: single-source single-destination على شبكات طرق جغرافية، إيجاد المسار في خرائط الألعاب. أسرع في المتوسّط من Dijkstra؛ إذا كان الاستدلال مقبولًا (h ≤ المسافة الحقيقية) يُضمن الأمثل.
(هـ) البحث ثنائيّ الاتّجاه. تنفيذ Dijkstra/A* للأمام من المصدر وللخلف من الهدف؛ الوقوف عند التقاء البحثين. عادةً 2-4x أسرع من Dijkstra أحاديّ الاتّجاه.
(و) Contraction Hierarchies (Geisberger وآخرون 2008) — حديثة قائمة على المعالجة المسبقة لشبكات طرق على مستوى دولة. يُعالَج الرسم البياني مسبقًا مرّة (تُقلَّص العُقد بترتيب هرميّ، تُضاف اختصارات)؛ كلّ استعلام لاحق يُجاب عليه في زمن دون الميلّيثانية. النهج المعياري ميدانيًّا للملاحة في الوقت الحقيقي على شبكات طرق وطنية (10M+ حافّة). ALT (A*، Landmarks، Triangle inequality)، Transit Node Routing، Hub Labels طرائق حديثة أخرى قائمة على المعالجة المسبقة.
(ز) المسار الأقصر مرتبط بالزمن — واعٍ بالمرور. أوزان الحواف دوالّ في الزمن w(u,v,t)؛ زمن الانتقال يتوقّف على ساعة الانطلاق t. يُعمَّم Dijkstra الثابت؛ إذا تحقّقت خاصية FIFO (انطلاق متأخّر — لا وصول أبكر)، فالمسألة كثيرة الحدود. تطبيقًا: محرّك توجيه يتغذّى ببيانات توقّع المرور.
(ح) المسار الأقصر العشوائي. أوزان الحواف متغيّرات عشوائية (مثلًا توزيع المرور)؛ مسار أقصر بالقيمة المتوقَّعة أو مُعدَّل للمخاطر (CVaR)؛ Polychronopoulos-Tsitsiklis (1996).
3. التكامل الميداني. الإخراج بثلاث طبقات: (أ) تشغيلي — عرض المسار عنوانًا-عنوانًا في تطبيق السائق المحمول / مسار توصيل الطرود / تطبيق فنّي الخدمة الميدانية، متكامل مع الملاحة، (ب) التخطيط — تُستدعى مصفوفة المسار الأقصر روتينًا فرعيًّا تحت تحسين VRP/TSP في برامج التخطيط اليومي للمسارات، (ج) استراتيجي / تحليلي — تحليل شبكة سلسلة توريد، تقارير اختناقات شبكة الاتّصالات، مصفوفة all-pairs للمسافة / الزمن لدعم القرار. التكامل الأعلى: ERP (عناوين الطلبات)، TMS (نظام إدارة النقل)، خدمة الخرائط (geocoding + بيانات شبكة الطرق)، خدمة بيانات المرور (توقّع في الوقت الحقيقي)، بيانات GPS لتتبّع الأسطول. لجنة عمليات ربع سنوية: حجم استعلامات المسار الأقصر، متوسّط زمن الاستعلام، انحراف توقّع المرور (واقع مقابل خطّة)، معدّل تغيير المسار (مشغّلات إعادة الحساب).
البدائل
يدويّ + خدمة خرائط + خبرة السائق
مجانيخدمة الخرائط في الطبقة المجانية، صفر تكلفة تطوير
لمن مناسبة: عملية صغيرة (1-10 مركبات/يوم)، 10-50 وقفة/مركبة، مسارات ثابتة معلومة
- + صفر استثمار برمجيّ
- + معرفة السائق الميدانية تظهر
- + استجابة هاتفية لمرور الوقت الحقيقي
- − لا ضمانة أمثل، المسار الحدسيّ ينفخ المسافة 15-30%
- − لا حساب متعدّد المعايير (زمن + وقود + رسوم)
- − لا التقاط بيانات — الأداء لا يُقاس
- − فوق 10 مركبات تُستنفد طاقة المخطّط
واجهة برمجة خدمة خرائط + تكامل داخليّ
cloudتسعير لكلّ استعلام؛ 0,003-0,01 دولار/استعلام، عند 50K طرد/يوم 2K-7K دولار/شهر
لمن مناسبة: عملية متوسّطة (50-500 مركبة، 50K-500K وقفة/يوم)، استعلامات واعية بالمرور
- + بيانات مرور ناضجة مدمجة
- + geocoding للعناوين مدمج
- + API سهل الاستهلاك، زمن تطوير قصير
- − تكلفة الاستعلام مرتفعة عند الحجم الكبير
- − الخوارزمية صندوق أسود، التحكّم محدود
- − ارتباط بالمزوّد (عقد خدمة الخرائط)
- − لا يتسع لاستعلامات all-pairs / مصفوفات كبيرة
محرّك مفتوح المصدر لشبكة الطرق + خوادم خاصّة
مفتوح المصدرترخيص مجاني؛ تطوير داخلي + خوادم 6-12 أسبوعًا أو 80K-250K يورو استشارة + 15K-50K يورو/سنة بنية تحتية
لمن مناسبة: عملية بفريق تقنيّ، حجم استعلامات مرتفع (1M+/يوم)، قيود متخصّصة (حظر نوع طريق للشاحنات)
- + لا رسوم ترخيص ولا رسوم لكلّ استعلام
- + اختيار الخوارزمية تحت السيطرة (Dijkstra، A*، contraction hierarchies)
- + قيود متخصّصة (وصول شاحنات، استثناء الإسعاف) يمكن دمجها
- + سيادة البيانات داخل المؤسّسة
- + 30+ أطروحة من TR (YÖK) كتنفيذات مرجعية
- − بيانات شبكة الطرق (جودة OpenStreetMap) تتطلّب تحديثًا دوريًّا
- − بيانات المرور تتطلّب مزوّدًا منفصلًا
- − اختصاصيّ OR داخليّ + فريق بنية تحتية لا بدّ منهما
- − من النموذج الأكاديمي إلى الإنتاج: 3-6 أشهر
منصّة دولية لتوجيه الأسطول / TMS
مؤسسي300K-2M يورو ترخيص + 100K-500K يورو/سنة صيانة
لمن مناسبة: عملية كبيرة (500+ مركبة، متعدّدة المواقع، 1M+ وقفة/يوم)، تكامل TMS كامل
- + وحدة ناضجة للمسار الأقصر + VRP مدمجة
- + تعدّد المعايير (زمن + تكلفة + وقود + رسوم) معياريّ
- + متغيّرات مرتبطة بالزمن + عشوائية مدعومة
- + خدمة المرور ضمن الحزمة
- − ترخيص مرتفع + تركيب طويل (12-24 شهرًا)
- − تعيير شبكة الطرق المحلّية يطيل المشروع
- − الخوارزمية صندوق أسود — التحكّم في معاملات المعالجة المسبقة محدود
- − خطر ارتباط بمزوّد وحيد مرتفع
التوصية
اسأل في الاجتماع
- ما النهج الذي تستخدمه خوارزمية المسار الأقصر — Dijkstra (binary heap، Fibonacci heap)، A*، بحث ثنائيّ الاتجاه، contraction hierarchies، ALT؟ كم متوسّط زمن الاستعلام على شبكة طرق على مستوى دولة (10M+ حافّة)؟
- هل تُدعم الحواف السالبة (Bellman-Ford)؟ هل يتوفّر كشف الدورات السالبة؟ في أيّ سيناريوهات (مراجحة مالية، تدفّق عكسيّ) يُلجَأ إلى Bellman-Ford؟
- هل يُدعم المسار الأقصر المرتبط بالزمن (الواعي بالمرور)؟ من أيّ مصدر تأتي بيانات المرور، وبأيّ تواتر (5-دقائق، 15-دقيقة، ساعة)؟ هل خاصية FIFO مضمونة؟
- من أين تأتي بيانات شبكة الطرق (OpenStreetMap، خدمة خرائط تجارية، جرد طرق وطنيّ)؟ ما دورة التحديث؟ كيف تُنمذَج أنواع الطرق (طريق سريع، طريق مزدوج، حضريّ، وصول النقل الثقيل) كقيود؟
- هل يُدعم all-pairs shortest path (Floyd-Warshall، Johnson)، وحتى أيّ حجم (كم عقدة)؟ كيف تُنتَج مصفوفة all-pairs لتحليل شبكة سلسلة التوريد؟
- هل يُدعم التحسين متعدّد المعايير (زمن + مسافة + وقود + رسوم) — مجموع موزون أم مسارات Pareto-مثلى؟ هل يمكن للمستخدم ضبط معاملات تعدّد الأهداف؟
- في تجربة ميدانية ببيانات تشغيلية حقيقية (8-12 أسبوعًا)، أيّ تقرير ادّخار يمكن تقديمه مقارنةً بالمسار اليدويّ / النظام القائم — وقود، زمن تسليم، ساعات سائق، معدّل تغيير المسار؟
- إذا انتهى العقد، بأيّ صيغة قياسية (GeoJSON، GraphML، CSV) نستطيع تصدير بيانات شبكة الطرق، بيانات تعيير المرور، سجلّ الاستعلامات وأرشيف المسارات؟
تفاصيل تقنية
ملاحظة المحرّر
في الكلام الدارج تُسمّى هذه المسألة “أقصر مسار” أو “حساب المسار” أو “الملاحة”. في الأدبيات الأكاديمية الاسم المعياري هو Shortest Path Problem (SPP)، المسألة التأسيسية في OR على الرسوم البيانية. Edsger Dijkstra (1959) في ورقة من صفحتين في Numerische Mathematik عرّف خوارزمية كثيرة الحدود لرسوم بحوافّ غير سالبة — هذه الورقة من أكثر الأوراق استشهادًا في علوم الحاسوب. Richard Bellman (1958) في Quarterly of Applied Mathematics قدّم Bellman-Ford القادر على الحواف السالبة. Robert Floyd (1962) في Communications of the ACM خوارزمية 97 (ورقة من فقرة) طوّر all-pairs Floyd-Warshall. Ahuja وMagnanti وOrlin (1993) Network Flows الكتاب المعياري. النهج الحديث القائم على المعالجة المسبقة (Geisberger وآخرون 2008 — contraction hierarchies) يقدّم زمن استعلام دون الميلّيثانية على شبكات طرق على مستوى دولة.
الفرق عن #068 (TSP): TSP مسألة جولة على كلّ العُقد — زيارة كلّ واحدة من N عقدة مرّة واحدة فقط والعودة إلى البداية، NP-صعب، المسألة التأسيسية للتحسين التوافيقي. shortest path نقطة-إلى-نقطة أو single-source all-destinations — كثيرة الحدود (Dijkstra O((V+E)logV)، Bellman-Ford O(VE)، Floyd-Warshall O(V³)). فجوة التعقيد كبيرة: لرسم بـ1.000 عقدة ينتهي Dijkstra في ميلّيثوانٍ، ويعمل TSP ساعات-أيّامًا. TSP يستدعي shortest path كروتين فرعي: تُحسَب مصفوفة المسافات الزوجية بـshortest path، ثمّ يحلّ TSP مسألة الجولة فوقها.
الفرق عن #069 (CVRP): CVRP توجيه أسطول بسعة — مركبات متعدّدة، مقيَّدة بالسعة، العملاء يُخدَمون جماعيًّا. يستدعي CVRP shortest path كروتين فرعي: تُحسَب مسافات عميل-عميل ومستودع-عميل بـshortest path، ثمّ يحلّ CVRP مسألة تعيين مركبة-عميل + ترتيب المسار. في هذه المنظومة يلعب shortest path دور “املأ مصفوفة أوزان الرسم” ويلعب CVRP دور “التعيين + الترتيب”.
الفرق عن #002 (VRPTW): VRPTW توجيه أسطول بنوافذ زمنية — مركبات متعدّدة، قيود سعة + نوافذ زمنية. VRPTW أيضًا يستدعي shortest path كروتين فرعي. إذا دُمج المسار الأقصر المرتبط بالزمن داخل VRPTW، نتج توجيه أسطول واعٍ بالمرور.
أكثر النقاط تجاهلًا في الميدان: كشف الحواف السالبة أو الدورات السالبة. يستخدم الممارس Dijkstra في كلّ الحالات؛ لكن في حال وجود تكلفة سالبة (مثلًا خصم على وصلة، عائد رأسمالي، خصم مرتدّ بسبب تدفّق عكسيّ، حافّة لوغاريتمية سالبة في دورة مراجحة عملات) لا يكون Dijkstra أمثل — يعطي نتيجة خاطئة بصمت. يلزم Bellman-Ford. إذا وُجدت دورة سالبة، فالمسار الأقصر غير معرَّف (الدورة تُجتاز لانهائيًا، تخفّض المجموع في كلّ دورة). في كثير من سيناريوهات المراجحة المالية / تدفّق الشبكات / التدفّق العكسي يحصل هذا الخطأ بصمت. يكشف Bellman-Ford عن دورة سالبة إذا استمرّ التحديث في التكرار V.
النقطة الثانية المتجاهَلة: اختيار التعقيد الخوارزمي. يقول الممارس “Dijkstra يعمل في كلّ مكان”؛ لكن على شبكة طرق على مستوى دولة (10M+ حافّة) يستغرق استعلام Dijkstra كلاسيكيّ واحد ثوانٍ — غير مقبول للملاحة في الوقت الحقيقي. النُّهج الحديثة القائمة على المعالجة المسبقة (contraction hierarchies — Geisberger وآخرون 2008، Transit Node Routing، Hub Labels) تقدّم زمن استعلام دون الميلّيثانية؛ المعالجة المسبقة تكلفة مرّة واحدة (ساعات-أيّام) ولكن كلّ استعلام لاحق سريع. النقطة الثالثة المتجاهَلة: افتراض الرسم الثابت. المرور يتغيّر في الوقت الحقيقي؛ يُشير المسار الأقصر على رسم ثابت إلى “الأمثل للساعة 14:00” لكنّه ينهار في ساعة الذروة 17:00. المسار الأقصر المرتبط بالزمن (وزن الحافّة دالة في الزمن) أو إعادة الحساب بأفق متدحرج لا غنى عنهما.
مسار خطوة بخطوة للشركات الصغيرة والمتوسّطة
المرحلة 1 — قِس أولًا، ثمّ خطّط. 6 أشهر على الأقلّ من بيانات الاستعلامات / المسارات: حجم استعلام يوميّ (كم استعلام A-B، كم all-pairs)، متوسّط زمن الاستعلام، انحراف توقّع المرور (الزمن المخطَّط مقابل الفعليّ)، معدّل تغيير المسار (مشغّلات إعادة الحساب). جرد شبكة الطرق: المصدر (خدمة خرائط، OpenStreetMap، جرد خاصّ)، الجودة (التغطية، التحديث، نوع الوزن — مسافة / زمن / تكلفة)، نوع الطريق (طريق سريع، مزدوج، حضريّ، وصول النقل الثقيل). مصدر بيانات المرور: لا شيء / ضمن حزمة خدمة الخرائط / مزوّد منفصل / بيانات GPS لأسطول خاصّ.
المرحلة 2 — بناء مصفوفة الخوارزميات. ملف الاستعلامات: غالبًا نقطة-إلى-نقطة، single-source all-destinations، تحليل all-pairs؟ سيناريوهات حواف / دورات سالبة (مراجحة، تدفّق عكسيّ)؟ حجم الرسم: 1K، 10K، 100K، 1M، 10M+ عقدة؟ متطلّب زمن الاستعلام: دون الميلّيثانية (ملاحة في الوقت الحقيقي)، ثوانٍ (تخطيط)، دقائق (تحليل استراتيجي)؟ اختر الخوارزمية من هذه المصفوفة: Dijkstra (صغيرة-متوسّطة، غير سالبة)، Bellman-Ford (حواف سالبة)، Floyd-Warshall (all-pairs صغيرة)، A* (شبكة طرق جغرافية)، contraction hierarchies (وطنية في الوقت الحقيقي).
المرحلة 3 — التجربة الميدانية. 8-12 أسبوعًا. نفّذ محرّك المسار الأقصر الجديد على مجموعة فرعية من العملية (مثلًا أكثر المناطق ازدحامًا أو شريحة العملاء الأكثر استعلامات)؛ يبقى القرار للمخطّط / السائق، والمحرّك يوصي. معيار النجاح مكتوب مسبقًا: في المنطقة التجريبية وقود -10% حدًّا أدنى، زمن تسليم -15% حدًّا أدنى، زمن الاستعلام يلبّي متطلّب الوقت الحقيقي.
المرحلة 4 — الانتشار. 6-12 شهرًا لتمديد العملية الكاملة + تكامل مع خدمة المرور + إعادة الحساب بأفق متدحرج. لجنة عمليات ربع سنوية: حجم استعلامات المسار الأقصر، متوسّط زمن الاستعلام، انحراف توقّع المرور، معدّل تغيير المسار، تقرير اختناقات الشبكة (تحليل all-pairs).
المخاطر — ما قد يخطئ
انحراف توقّع المرور (خطر الرسم الثابت). لا يعكس المسار الأقصر على رسم ثابت ظروف المرور الواقعية؛ أخطر مخاطر. في ساعات الذروة، يستغرق المسار “الأمثل” المحسوب وقتًا أطول في الواقع. الحلّ: مسار أقصر مرتبط بالزمن (وزن دالة في الزمن) + خدمة بيانات مرور (تحديث 5-15 دقيقة) + إعادة حساب بأفق متدحرج (كلّ 15-30 دقيقة أو بحدث — حادث، إغلاق).
تأخّر التحديث في الوقت الحقيقي. إذا وصلت بيانات الإغلاق أو الحادث أو حدث المرور إلى المحرّك متأخّرة، يوصي المحرّك بطريق مُغلَق دون علم — يذهب السائق، يعود، تكلفة مزدوجة. الحلّ: إعادة حساب مدفوعة بالأحداث، إشعار حدث مرور في الوقت الحقيقي داخل تطبيق السائق، اقتراح مسار بديل.
إغلاق / حظر طريق غير معلوم. إذا لم تُحدَّث بيانات شبكة الطرق (الثابتة) دوريًّا، تُتجاهَل الإنشاءات الجديدة والإغلاقات الموسمية وحظر النقل الثقيل؛ ينتج المحرّك مسارات غير قابلة للتطبيق. الحلّ: دورة تحديث شبكة طرق كلّ 3-6 أشهر، تغذية راجعة ميدانية من السائق (تقرير “طريق مُغلَق” في التطبيق)، طبقة شبكة طرق خاصّة بالشاحنات لتوجيه الحمولة الثقيلة.
الارتباط بمزوّد وحيد لبرنامج التوجيه / خدمة الخرائط. بدون بند تعاقدي لـ"تصدير سنويّ بصيغ قياسية (GeoJSON، GraphML، CSV) لبيانات شبكة الطرق، بيانات تعيير المرور، سجلّ الاستعلامات وأرشيف المسارات"، يعني الخروج من النظام فقدان سنوات من البيانات التشغيلية وذاكرة التعيير. يجب أن يغطّي العقد صراحةً سيادة بيانات شبكة الطرق وتصدير معاملات تعيير المرور والمخرَجات بصيغ قياسية لـAPI الاستعلام.
طريقة الحلّ — رؤية تقنية
| النهج | الحجم النموذجي | زمن الحلّ | حواف سالبة؟ |
|---|---|---|---|
| Dijkstra ساذج (O(V²)) | صغير، V ≤ 1.000 | ميلّيثوانٍ | لا |
| Dijkstra binary heap (O((V+E)logV)) | متوسّط، V ≤ 100K | ms-ثوانٍ | لا |
| Dijkstra Fibonacci heap (O(E + VlogV)) | متوسّط-كبير، V ≤ 1M | ثوانٍ | لا |
| Bellman-Ford (O(VE)) | صغير-متوسّط، حواف سالبة | ثوانٍ-دقائق | نعم، يكشف الدورة السالبة |
| Floyd-Warshall (O(V³)) | all-pairs صغير، V ≤ 1.000 | ثوانٍ-دقائق | نعم (بلا دورة) |
| Johnson (O(V² logV + VE)) | all-pairs متوسّط، متناثر | دقائق | نعم |
| A* (موجَّه بالاستدلال) | شبكة طرق جغرافية، نقطة-إلى-نقطة | ms-ثوانٍ | لا |
| Dijkstra/A* ثنائيّ الاتجاه | نقطة-إلى-نقطة، رسم كبير | ms-ثوانٍ | لا |
| Contraction Hierarchies | شبكة طرق وطنية | دون الميلّيثانية (معالجة مسبقة ساعات) | لا |
| Dijkstra مرتبط بالزمن | شبكة طرق واعية بالمرور | ms-ثوانٍ | لا |
اختيار دالة الهدف:
- الهدف 1 — أقلّ زمن إجماليّ: مُركَّز على السرعة؛ نموذجيّ للملاحة، الطوارئ، توصيل الطرود.
- الهدف 2 — أقلّ مسافة إجمالية: مُركَّز على الوقود + استهلاك المركبة؛ نموذجيّ للمسافات الطويلة.
- الهدف 3 — أقلّ تكلفة إجمالية: مجموع موزون من وقود + رسوم + ساعات قيادة.
- الهدف 4 — متعدّد المعايير (Pareto-أمثل): مفاضلة بين الزمن + التكلفة + الوقود؛ يختار صانع القرار من جبهة Pareto.
تعدّد الأهداف: مجموع موزون (الأكثر شيوعًا) أو هرميّ (الزمن أوّلًا، ثمّ التكلفة، ثمّ الوقود) أو مسارات Pareto-مثلى (لدعم القرار المتقدّم).
متغيّرات المسار الأقصر — اختر حسب الميدان:
- Dijkstra الكلاسيكي (1959): حواف غير سالبة، مصدر واحد، تأسيسي.
- Bellman-Ford (1958): قادر على الحواف السالبة، يكشف الدورات السالبة، توجيه distance-vector.
- Floyd-Warshall (1962): all-pairs، رسم صغير، برمجة ديناميكية.
- A (Hart-Nilsson-Raphael 1968):* نقطة-إلى-نقطة موجَّه بالاستدلال، شبكات طرق جغرافية.
- Contraction Hierarchies: شبكة طرق وطنية، قائم على المعالجة المسبقة، في الوقت الحقيقي.
- مسار أقصر مرتبط بالزمن: واعٍ بالمرور، وزن الحافّة دالة في الزمن.
- مسار أقصر عشوائي (Polychronopoulos-Tsitsiklis 1996): أوزان غير مؤكَّدة، مُعدَّل للمخاطر.
- مسار أقصر بقيود الموارد (RCSP): قيود إضافية (وقود، نوافذ زمنية)؛ يظهر كمسألة فرعية للتسعير في VRP بطريقة column generation.
المراجع الأكاديمية
مدرَجة في frontmatter الصفحة تحت sources.
المصادر
- Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271. ورقة تأسيسية من صفحتين؛ من أكثر الأوراق استشهادًا في علوم الحاسوب.
- Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87-90. المرجع التأسيسي لـBellman-Ford على الرسوم البيانية ذات الحواف السالبة.
- Floyd, R. W. (1962). Algorithm 97: Shortest path. Communications of the ACM, 5(6), 345. المصدر المعياري ذو الفقرة الواحدة لـFloyd-Warshall all-pairs.
- Ahuja, R. K., Magnanti, T. L. وOrlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall. الكتاب المعياري لمجال تدفّقات الشبكات والمسار الأقصر.
- Cormen, T. H., Leiserson, C. E., Rivest, R. L. وStein, C. (2009). Introduction to Algorithms (الطبعة الثالثة). MIT Press. المرجع التعليمي لـDijkstra / Bellman-Ford / Floyd-Warshall.
- Geisberger, R., Sanders, P., Schultes, D. وDelling, D. (2008). Contraction hierarchies: Faster and simpler hierarchical routing in road networks. Experimental Algorithms (WEA 2008), LNCS 5038, 319-333. خوارزمية حديثة قائمة على المعالجة المسبقة لشبكات طرق على مستوى دولة.
- Hart, P. E., Nilsson, N. J. وRaphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. الورقة التأسيسية لخوارزمية A*.
- YÖK Thesis Center — كلمة مفتاحية: ’en kısa yol’ أو ‘Dijkstra’ أو ‘graf algoritması’ — 30+ أطروحة من الأكاديميا التركية. tez.yok.gov.tr
المسرد
- Shortest Path Problem
- مسألة تأسيسية في OR على الرسوم البيانية لإيجاد المسار ذي أصغر مجموع أوزان بين عقدتين على رسم بياني موزون (single-source single-destination، single-source all-destinations، أو all-pairs)؛ خوارزميات كثيرة الحدود Dijkstra (1959)، Bellman-Ford (1958)، Floyd-Warshall (1962).
- Dijkstra Algorithm
- خوارزمية كثيرة الحدود لـEdsger Dijkstra (1959) للمسارات الأقصر من مصدر واحد على رسوم بأوزان حواف غير سالبة؛ جشِعة — تستخرج العقدة غير المزارة ذات أصغر مسافة مؤقّتة من قائمة أولوية وتُرَخّي جيرانها؛ O((V+E) log V) مع binary heap.
- MIP
- نموذج تحسين تكون فيه بعض متغيرات القرار أعداداً صحيحة (مثل: عدد الشاحنات، عدد الورديات).
- VRP
- قرار أي المركبات — منطلقةً من مستودع واحد أو عدة مستودعات — تزور أي عملاء وبأي ترتيب.
مشاكل ذات صلة
أي مركبة لأي زبون، وفي أي ساعة؟
أسطول توصيل محلي من 5 إلى 30 مركبة يخطّط مساراته اليومية. لكل عميل نافذة زمنية للاستلام (متجر يقبل التسليم بين 09:00 و12:00، ومطعم لا يقبل إلا قبل 14:00). القرار: أي عميل لأي مركبة، بأي ترتيب، كي تُحترم كل النوافذ، وتبقى ساعات الوقود والسائق عند حدودها الدنيا، ولا تتجاوز أي مركبة طاقتها. المنسّق يستطيع تخطيط 30–50 نقطة ذهنياً؛ بعد هذا الحد تنخفض جودة الخطة — كيلومترات فارغة، تسليمات متأخرة، جولات ثانية، وساعات إضافية للسائقين.
أين أفتح المستودع الجديد؟
موزّع أو متجر إلكتروني أو مصنع متوسط يخطّط لافتتاح 1–5 مستودعات أو فروع أو مراكز توزيع جديدة خلال 2–5 سنوات. القرار: في أي مدينة أو منطقة، كم منشأة، بأي حجم، وأي من المستودعات الحالية ينقل أي حجم من العملاء/الطلبات إلى أي منشأة جديدة. الموقع الخاطئ يعني 5–10 سنوات من ارتفاع تكاليف النقل وتأخر التسليم وفقدان عملاء؛ والموقع الصحيح يعني توفيراً سنوياً 300 ألف – 1.5 مليون دولار خلال الفترة نفسها. حين يُؤخذ القرار حدسياً (مثلاً «إلى جانب المصنع، العمال يسكنون قرباً») نادراً ما يصيب الأمثل — لأن تكلفة النقل والإيجار والضرائب وكلفة العمالة وزمن الخدمة قيود ينبغي موازنتها معاً.
عدّة مركبات، عملاء كثيرون — أيّ مركبة في أيّ ترتيب، دون تجاوز السعة، وبأقلّ مسافة إجمالية؟
موزّع أو مورّد يسلّم يوميًا من مستودع واحد إلى 10-100 عميل (أغذية، مشروبات، مياه، قطع غيار B2B)؛ سعة المركبة ثابتة (2-5 طن، 30 م³)، وكمية طلب كلّ عميل معروفة، وموعد التسليم مرن. كلّ صباح ثلاثة أسئلة: كم مركبة تنطلق اليوم، وأيّ مركبة تزور أيّ عملاء، وبأيّ ترتيب — دون تجاوز السعة، مع تقليل المسافة الإجمالية. منسّق متمرّس يدير 15-25 عميلًا ذهنيًا؛ فوق ذلك تنخفض جودة الجولات، ويتوزّع عملاء المنطقة الواحدة على مركبتين، وتنطلق 1-2 مركبة إضافية كلّ يوم. 10-25% من المسافة الإجمالية و1-2 مركبة في اليوم تعتمد على جودة التخطيط؛ الوقود + السائق يشكّلان 30-50% من المصاريف التشغيلية.