ما هي أمثلة المسارات؟ الخوارزميات والقيود وواجهات API

أمثلة المسارات هي ممارسة ترتيب المحطات وإسناد المركبات بحيث يُنهي الأسطول عمله بأقل وقت أو مسافة أو تكلفة. هي الفارق بين سائق توصيل يُنهي عمله في الرابعة عصرًا وآخر يُنهيه في السابعة بنفس الشاحنة ونفس المحطات. تحت كل زر "مسار مُحسَّن" في تطبيق لوجستي يجلس حلّال انتهى للتو من معالجة ملايين الترتيبات الممكنة واختار واحدًا.

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

ما هي أمثلة المسارات فعلًا

في علوم الحاسوب، تعيش أمثلة المسارات داخل مسألتين كلاسيكيتين. مسألة البائع المتجول (TSP) تسأل: بمعطى قائمة مدن والمسافات بينها، ما أقصر مسار يزور كل مدينة مرة واحدة بالضبط ويعود إلى نقطة البداية؟ هي مسألة بمركبة واحدة. مسألة توجيه المركبات (VRP) تُعمم هذا للأسطول: بمعطى مستودع ومجموعة عملاء وعدة مركبات، كيف ينبغي تقسيم العملاء بين المركبات، وبأي ترتيب تزور كل مركبة عملاءها؟

كلتا المسألتين من فئة NP-hard. عدد الترتيبات الممكنة ينمو عاملياً مع عدد المحطات. عشرون محطة تُنتج بالفعل أكثر من 10 أس 18 مسار ممكن. لا توجد خوارزمية دقيقة تستطيع البحث في تلك المساحة في الزمن الفعلي. الأمثلة في الإنتاج إذًا ليست عن إيجاد الإجابة المثالية. هي عن إيجاد إجابة جيدة جدًا بسرعة كافية للتصرف بناءً عليها.

كيف تتعامل الحلّالات مع المسألة

لأن مساحة البحث هائلة، تمزج الحلّالات الحقيقية عدة تقنيات.

للمسائل الصغيرة (أقل من حوالي 15 محطة)، يمكن لطرق دقيقة مثل التفرع والتقييد أو البرمجة الصحيحة إعادة حل مُثبَت أنه مثالي خلال ثوانٍ. خارج هذا النطاق، تتوقف الطرق الدقيقة عن كونها عملية، وينتقل الحقل إلى الإرشادات.

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

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

أين تظهر أمثلة المسارات

أمثلة المسارات تُشغّل بهدوء قائمة طويلة من الأعمال التشغيلية.

• التوصيل في الميل الأخير: شركات الطرود وتوصيل البقالة وتنفيذ التجارة الإلكترونية كلها تُرتب من عشرات إلى مئات المحطات لكل شاحنة في اليوم
• الخدمة الميدانية: فنيو التكييف ومُركبو الاتصالات وعاملو الرعاية المنزلية يزورون العملاء عبر منطقة بنوافذ مواعيد ومتطلبات مهارات
• القوى العاملة المتنقلة: طواقم المرافق وقُرّاء العدادات والمفتشون يُغطون مناطق بأنواع مهام مختلطة
• توصيل الطعام: مُجمّعو المطاعم يجمعون عدة طلبات في رحلة واحدة للسائق حين تتناسب الجغرافيا
• جمع النفايات: شاحنات البلديات تُشغّل جولات أسبوعية ثابتة، حيث تُوفّر إعادة الترتيب الصغيرة وقودًا فعليًا
• مندوبو المبيعات: تخطيط المناطق حيث يزور المندوب 8 إلى 12 حسابًا في اليوم، وحيث الترتيب يُهم لزمن القيادة وكثافة الاجتماعات

في كل حالة يرى المستخدم قائمة بالمحطات بالترتيب الصحيح. العمل يحدث في المُحسِّن خلفه.

القيود التي تُهم

حلّال يُقلل المسافة فقط هو لعبة. التوجيه الإنتاجي تُحدده قيوده.

• سعة المركبة: لكل شاحنة حد وزن أو حجم أو منصات، يجب ألّا تتجاوزه المحطات المُسندة
• النوافذ الزمنية: العملاء يتوقعون التوصيل بين، مثلًا، 9 و11 صباحًا، والوصول في 11:05 فشل
• ورديات السائقين: الحد الأقصى لساعات العمل والاستراحات الإجبارية والبدء والانتهاء في مستودعات محددة
• مطابقة المهارات أو نوع المركبة: تركيب ثلاجة يحتاج فريقًا من شخصين، توصيل سلسلة باردة يحتاج شاحنة مُبردة
• متعدد المستودعات: الأساطيل الكبيرة تُوزع من عدة مستودعات، والحلّال يُحدد أي مستودع يتعامل مع أي محطة
• العودة إلى القاعدة: بعض المسارات مفتوحة (السائق ينتهي في المنزل)، وأخرى مغلقة (السائق يعود إلى المستودع)

كل قيد يُقلّص مجموعة المسارات الممكنة ويدفع الحلّال نحو حلول تبدو أسوأ قليلًا على الورق لكنها قابلة للتنفيذ فعلًا.

عقبات في الإنتاج

أمثلة المسارات فئة يعمل فيها العرض التوضيحي دائمًا، والإطلاق غالبًا لا يعمل.

أمثلة الدالة الهدف الخاطئة. تقليل المسافة هو الأصل، لكن لكثير من الأساطيل، الإيرادات أو الالتزام بمستوى الخدمة يُهم أكثر من الكيلومترات الموفّرة. مسار يُسقط طردًا إضافيًا واحدًا على حساب 2 كم هو عادةً فوز.

الأوقات بالتدفق الحر مقابل الواعية بحركة المرور. مصفوفة مبنية من سرعات الطرق الخام ستُخبرك أن مسارًا يستغرق 4 ساعات بينما يستغرق في حركة مرور الذروة 6. استخدم محرك توجيه يكشف أزمنة سفر واعية بحركة المرور للوقت من اليوم الذي سيُشغَّل فيه المسار.

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

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

أمثلة المسارات في MapAtlas

تحلّ MapAtlas Optimize Route API مسائل توجيه المركبات الفردية والأسطول مع القيود التي تحتاجها فرق العمليات فعلًا: السعة والنوافذ الزمنية والورديات والمهارات وإعدادات المستودعات المتعددة. تُعيد خطة مُرتبة لكل مركبة مع أوقات الوصول والمغادرة المتوقعة لكل محطة.

تتكامل بشكل طبيعي مع نقطتي طرف أُخريين في حزمة MapAtlas. Distance Matrix API تبني جدول زمن السفر الذي يستهلكه الحلّال، بأزمنة واعية بحركة المرور بحيث تصمد الخطط في ساعة الذروة. Directions API ترسم مسارات الطريق الفعلية منعطفًا منعطفًا بين المحطات المتتالية حالما يُحدَّد الترتيب، ليُظهر تطبيق السائق خطًا متعرجًا حقيقيًا بدل خط مستقيم.

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