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

في هذا العمل، نقوم بإعادة النظر في الأساليب التقليدية المعتمدة على خوارزمية ديكسترا لإيجاد المسارات في النقل العام مع إمكانية التبديل غير المحدود، ونظهر أن خوارزمية ديكسترا المعتمدة على الزمن (Time-Dependent Dijkstra) تتفوق على الأساليب الحالية. ومع ذلك، تعتمد التطبيقات الفعالة لهذه الخوارزمية على تصفية الروابط السائدة خلال مرحلة المعالجة المسبقة، مما يفترض أن الركاب يمكنهم دوماً الانتقال إلى رابط أسرع.

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

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

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