تتمثل إحدى المهام الرئيسية في Yandex.Taxi في كيفية التأكد من وصول السيارة بسرعة إلى المستخدم ، وتقليل وقت تشغيل "الخمول" (أي ، الوقت الذي يكون فيه على الخط بدون مسافر). يبدو أن كل شيء بسيط: يحدد المستخدم التعريفة ، ويشير إلى رغبات إضافية (مقعد الطفل ، على سبيل المثال). يبقى لتصفية برامج التشغيل على الخط وفقا لهذه المعايير ، حدد أقرب واحد وتقديم طلب له. ومع ذلك ، كل شيء بسيط للغاية فقط للوهلة الأولى.
اليوم سأخبر مجتمع هبر كيف نختار السائق الأنسب وكيف تطورت هذه العملية مع مرور الوقت. سوف تتعلم عن طريقتين لحل المشكلة.
البحث العمارة العامة
عندما ينقر المستخدم على زر "استدعاء سيارة أجرة" ، يتم إنشاء كائن الطلب في الواجهة الخلفية وتبدأ معالجته وفقًا لآلة الحالة. من أجل أن ينتقل الأمر من حالة "في انتظار المراجعة" إلى "تم تعيين برنامج التشغيل" ، فأنت بحاجة إلى العثور على برنامج التشغيل وتقديم طلب له وانتظر التأكيد على أنه تم قبول الطلب.
النهج الجشع
لفترة طويلة جدا ، عملت نهج
الجشع في Yandex.Taxi. مع هذا النهج ، في مرحلة البحث عن المقاول ، يتم تقديم طلب إلى Microservice Tracker ، وهو المسؤول عن السائقين. يعرف Tracker كل شيء عن السيارات: من الألوان والعلامات التجارية إلى موقعها
الحالي . يحتوي Tracker على فهرس جغرافي محلي للسائقين والموصلات بخدمات التوجيه (أجهزة التوجيه) لبناء الطرق من النقطة A إلى النقطة B (وحتى من خلال النقاط B و D و D). لذلك ، عند تقديم طلب للبحث عن سائق ، يقوم Tracker أولاً بتحديد أقرب السيارات في الفهرس الجغرافي المحلي على طول دائرة نصف قطرها المباشر ، مع مراعاة قيود الطلب "الصعب" (فئة السيارة ، المتطلبات - مقعد الطفل ، الأرقام الصفراء). بعد ذلك ، يتم تحديد وقت وطول مسار تزويد السيارة ، ومع مراعاة هذه المعلومات ، يتم تحديد الخيار الأفضل.
في وقت لاحق ، تطور هذا المنطق: بالنسبة لكل سائق ، بدأوا في الاعتماد على "التسجيل" حسب الطلب - وهي وظيفة من الوقت الذي تم فيه تسليم السيارة. وتم تصنيف السائقين بالفعل من خلال تسجيل قيمة. تأخذ الوظيفة في الاعتبار ليس فقط وقت التسليم نفسه ، ولكن أيضًا العديد من العوامل الأخرى: من مستوى الطلب في النقطتين أ و ب إلى "تجربة" السائق. ويسمى هذا الموعد الجشع مكافأة.
العازلة (شعاع) النهج
ومع ذلك ، مع النهج الجشع ، سيتلقى أقرب سائق الشخص الذي طلب سيارة أجرة لأول مرة. ومع ذلك ، قد يتم ترك بعض المستخدمين بدون سيارة.
مع زيادة الطلب ، عندما تبدأ المنافسة على فناني الأداء ، فإن النهج الجشع ليس جيدًا. من أجل تلبية الطلب بأكبر قدر ممكن حتى في أكثر الساعات ازدحامًا ، نستخدم العديد من الطرق والخوارزميات. واحد منهم هو تعيين (شعاع) العازلة للسائقين على أوامر. يعتمد على المهمة المعروفة من مجال التحسين التوافقي -
مشكلة التعيين . باختصار ، جوهرها: دعنا ننفّذ أعمال N و M ، يمكن لأي موظف إكمال أي مهمة خلال الوقت p (i، j) [0 <= i <N، 0 <= j <M]. من الضروري تعيين مثل هذا المقاول لكل مهمة من أجل تقليل وقت التنفيذ الكلي لجميع الأعمال (في هذه الحالة ، يمكن لمتعهد واحد شغل وظيفة واحدة فقط).
عند حل مشكلة التعيين هذه ، تكون "تكلفة" تنفيذ العمل (الطلب) من قِبل المنفذ (أسطول سيارات الأجرة والسائق) هي قيمة وظيفة التسجيل من وقت تسليم السيارة للمستخدم. يمكن وصف المهمة من حيث الرسوم البيانية ثنائية الأطراف: من ناحية ، الطلبات ، من ناحية أخرى ، فناني الأداء. بين الطلبات والأداء هناك حواف مرجحة (تسجيل). وبالتالي ، فإن أحد أهدافنا هو تقليل إجمالي وقت تسليم السيارة عن طريق زيادة عدد الطلبات المكتملة (أقصى مطابقة). واحدة من أكثر الطرق شهرة لحل هذه المشكلة هي
الخوارزمية المجرية .
من الواضح ، مع موعد عازلة ، لا يمكننا إعطاء سائق عند الطلب ، كما هو الحال مع النهج الجشع. تحتاج أولاً إلى وضع الترتيب في قائمة الانتظار ، ثم اللعب ، ثم إبلاغ السائق الذي تم العثور عليه. هذا لا يتلاءم مع آلة الدولة لمعالجة الطلبات على الإطلاق ، وكان لا بد من تحسينه قليلاً. من أجل اختبار وإنشاء حل جديد دون التأثير على زملائنا ، اتفقنا على الفور على أننا سنبذل قصارى جهدنا في خدمة Microspers منفصلة. سوف يتلقى الأوامر ، ويضع في طابور ، ويجد السائقين ويحفظ نتائج التجمعات.
بادئ ذي بدء ، كان علينا إعداد Tracker لملف تعريف تحميل جديد. في حالة اتباع نهج جشع ، سقطت طلبات برامج التشغيل بشكل فردي على موازن Tracker وتمت إعادة توجيهها إلى مثيلاتها مع موازنة التحميل ، ثم في الوجهة العازلة كانت جميع الطلبات من جهاز واحد: الطلبات الفردية من شأنها أن تسد تجمع الاتصال. لذلك ، أضفنا إلى المقتفي القدرة على معالجة دفعات الطلبات التي تمت معالجتها في وقت واحد داخل المقتفي. على طول الطريق ، كان علينا أيضًا حل مشكلة عدد معقول من طلبات معالجة الدُفعات. من جانب العميل (DriverDispatcher) ، نقوم بتقسيم الدفعة الكبيرة إلى عدة مجموعات صغيرة وإرسالها إلى مثيلات Tracker مختلفة.
لذلك ، يتم إعداد المتعقب ، ويعتبر تسجيل النقاط في كل من Tracker (موعد جشع) وفي الخدمة الجديدة (DriverDispatcher'e) ، خوارزمية حل مشكلة التعيين يتم تصحيحها وتعمل بشكل صحيح. السؤال الذي يطرح نفسه هو كيفية دمج كل هذا في آلة معالجة الطلبات. لقد أضفنا إرسال وحذف معلومات تعريف الطلب في DriverDispatcher عندما يتم نقل الطلب من ولاية إلى أخرى. وهذا عمل تقريبا. تقريبا - لأن التكرار من البحث عن المقاول لطلب لم تكن خاضعة للسيطرة من الخارج. يمكننا استبدال الرحلة إلى المتعقب بالسائق برحلة إلى خدمتنا وإعطاء السائق عند العثور عليها وقبل ذلك فقط إعطاء 404. لكن هذا أمر سيئ ، لأنك تحتاج إلى تقديم طلب للسائق بمجرد العثور على طلب ، وحتى عدة تلعب ثوان من التأخير دورًا هنا: يمكن للسائق ببساطة أن يتجه في الاتجاه الخاطئ ، وسيصبح الترتيب غير ذي صلة. للقيام بذلك ، جعلنا من الممكن استدعاء عملية البحث عن فنان دون التأثير على المهام المخططة. لذلك قمنا بحفظ منطق البحث (مع إعادة الطلبات) وقمنا بإضافة القدرة على الاتصال به خارج برنامج الجدولة.
وبالتالي ، تمكنا من الجمع بين آلة الحالة الرئيسية لمعالجة الطلب وآلة الحالة في إرسال المخزن المؤقت دون التأثير على منطق العمل ودون السباق بين الحالات. يمكنك تشغيل التجارب الأولى على المستخدمين المباشرين.
كل هذا رائع ، ولكن ماذا عن الوقت للبحث عن فنان ، أنت تسأل. إذا لم يتم البحث مباشرة بعد استلام الطلب ، فسيزيد وقت البحث ونتيجةً لذلك يتم تعويضه بتغذية أسرع؟ هذا ليس صحيحًا تمامًا: بمساعدة التقنيات المختلفة (بما في ذلك استخدام التعلم الآلي) ، تمكنا من عزل الحالات عندما يكون الانتظار منطقيًا ، وفي حالات أخرى لا يتغير وقت الانتظار.
سحب دبوس
هناك طريقة أخرى للعثور على الفنان بشكل أسرع وهي البدء في البحث عنه قبل إنشاء طلب. عندما يظهر رقم التعريف
الشخصي الجديد (أي ، يقوم المستخدم بإدخال بيانات الطلب فقط في التطبيق) ، تقوم
خوارزميات التعلم
الآلي بتقييم احتمال اتباع أمر ما ، وتقرر ما إذا كان يجب أخذه في الاعتبار عند تخزين برامج التشغيل مؤقتًا أم لا. يمكننا العثور على السيارة مقدمًا ، وعندما يقوم المستخدم بالنقر فوق زر الطلب ، قم فورًا بتقديم عرض للسائق المناسب.
الخاتمة
مطابقة الطلبات وبرامج التشغيل ليست مهمة سهلة ؛ فهي تتطلب مراعاة العديد من العوامل. واحد منهم هو سياق تحركات السائقين عند اختيار المرشحين للنظام. سنتحدث عن هذا في الوظائف التالية.
وظائف تكنولوجيا سيارات الأجرة الأخرى