हम Yandex.Taxi में ड्राइवरों के बीच ऑर्डर कैसे वितरित करते हैं

Yandex.Taxi के मुख्य कार्यों में से एक यह है कि यह सुनिश्चित करने के लिए कि उपयोगकर्ता के लिए एक कार जल्दी से आती है, और "निष्क्रिय रन" के लिए ड्राइवर का समय कम हो जाता है (वह समय, जब वह एक यात्री के बिना लाइन में है)। ऐसा लगता है कि सब कुछ सरल है: उपयोगकर्ता टैरिफ का चयन करता है, अतिरिक्त इच्छाओं (उदाहरण के लिए बच्चे की सीट) को इंगित करता है। यह इन मानदंडों के अनुसार ड्राइवरों को लाइन पर फ़िल्टर करने के लिए बनी हुई है, निकटतम का चयन करें और उसे ऑर्डर दें। हालाँकि, पहली नज़र में ही सब कुछ इतना सरल है।

आज मैं हबर समुदाय को बताऊंगा कि कैसे हम सबसे उपयुक्त ड्राइवर चुनते हैं और समय के साथ यह प्रक्रिया कैसे विकसित हुई है। आप समस्या को हल करने के दो तरीकों के बारे में जानेंगे।

सामान्य खोज वास्तुकला

जब उपयोगकर्ता "कॉल अ टैक्सी" बटन पर क्लिक करता है, तो बैकएंड में एक ऑर्डर ऑब्जेक्ट बनाया जाता है और इसकी प्रोसेसिंग राज्य मशीन के अनुसार शुरू होती है। आदेश में "लंबित" राज्य से "ड्राइवर को सौंपा गया है" पर जाने के लिए, आपको ड्राइवर को खोजने की आवश्यकता है, उसे एक आदेश दें और पुष्टि के लिए प्रतीक्षा करें कि आदेश स्वीकार कर लिया गया है।

लालची दृष्टिकोण

बहुत लंबे समय के लिए, एक लालची दृष्टिकोण ने यैंडेक्स.टेक्सी पर काम किया। इस दृष्टिकोण के साथ, ठेकेदार के लिए खोज करने के चरण में, ड्राइवरों के लिए जिम्मेदार ट्रैकर माइक्रो सर्विस के लिए अनुरोध किया जाता है। ट्रैकर कारों के बारे में सब कुछ जानता है: रंग और ब्रांडिंग से इसकी वर्तमान स्थिति तक । ट्रैकर के पास प्वाइंट ए से पॉइंट बी (और यहां तक ​​कि पॉइंट बी, डी, डी) के मार्गों के निर्माण के लिए ड्राइवर और कनेक्टर के लिए रूटिंग सेवाओं (राउटर) के लिए एक स्थानीय भू-सूचकांक है। इसलिए, जब ड्राइवर के लिए खोज करने के लिए अनुरोध किया जाता है, तो ट्रैकर पहले स्थानीय कारों में स्थानीय कारों को प्रत्यक्ष त्रिज्या के साथ "हार्ड" ऑर्डर प्रतिबंधों (कार वर्ग, आवश्यकताओं - बच्चे की सीट, पीली संख्या) को ध्यान में रखते हुए निर्धारित करता है। फिर, वाहन आपूर्ति मार्ग का समय और लंबाई निर्दिष्ट की जाती है और, इस जानकारी को ध्यान में रखते हुए, सबसे अच्छा विकल्प चुना जाता है।

बाद में, यह तर्क विकसित हुआ: प्रत्येक ड्राइवर के लिए वे उसके "स्कोरिंग" ऑर्डर पर गिनना शुरू कर देते थे - कार को वितरित करने का समय। और ड्राइवरों को पहले से ही स्कोरिंग मूल्य से रैंक किया गया था। फ़ंक्शन न केवल डिलीवरी के समय को, बल्कि कई अन्य कारकों को भी ध्यान में रखता है: मांग के स्तर ए और बी से ड्राइवर के "अनुभव" तक। इस लालची नियुक्ति को बोनस कहा जाता है।

बफर (बीम) दृष्टिकोण

हालांकि, एक लालची दृष्टिकोण के साथ, निकटतम चालक को वही मिलेगा जो पहले टैक्सी का आदेश देता था। हालाँकि, कुछ उपयोगकर्ताओं को कार के बिना भी छोड़ा जा सकता है।





बढ़ी हुई मांग के साथ, जब कलाकारों के लिए प्रतिस्पर्धा शुरू होती है, तो लालची दृष्टिकोण अच्छा नहीं होता है। सबसे व्यस्त घंटों में भी यथासंभव मांग को पूरा करने के लिए, हम कई दृष्टिकोण और एल्गोरिदम का उपयोग करते हैं। उनमें से एक ऑर्डर पर ड्राइवरों का बफर (बीम) पदनाम है। यह दहनशील अनुकूलन के क्षेत्र से प्रसिद्ध कार्य पर आधारित है - असाइनमेंट समस्या । संक्षेप में, इसका सार: हमें N कार्य और M कलाकार हैं, कोई भी कर्मचारी समय p (i, j) [0 <= i <N, 0 <= j <M] के दौरान किसी भी कार्य को पूरा कर सकता है। सभी कार्यों के कुल निष्पादन समय को कम करने के लिए प्रत्येक कार्य के लिए इस तरह के एक ठेकेदार को असाइन करना आवश्यक है (इस मामले में, एक ठेकेदार केवल एक काम कर सकता है)।



ऐसी असाइनमेंट समस्या को हल करते समय, निष्पादक (टैक्सी बेड़े और ड्राइवर) द्वारा कार्य (आदेश) करने की हमारी "लागत" उस समय से स्कोरिंग फ़ंक्शन का मूल्य है जब वाहन उपयोगकर्ता को दिया गया था। कार्य को द्विदलीय रेखांकन के रूप में वर्णित किया जा सकता है: एक ओर, आदेश, दूसरी ओर, कलाकार। आदेश और कलाकारों के बीच भारित किनारों (स्कोरिंग) होते हैं। इस प्रकार, हमारा एक लक्ष्य पूर्ण आदेशों (अधिकतम मिलान) की संख्या को बढ़ाकर कुल वाहन वितरण समय को कम करना है। ऐसी समस्या को हल करने के सबसे प्रसिद्ध तरीकों में से एक हंगरी एल्गोरिथम है ।

जाहिर है, एक बफर अपॉइंटमेंट के साथ, हम एक ड्राइवर को अनुरोध पर नहीं दे सकते हैं, जैसे कि लालची दृष्टिकोण के साथ। पहले आपको आदेश को कतार में रखने की आवश्यकता है, फिर बाहर खेलने के लिए, और फिर चालक के बारे में सूचित करें। यह आदेश प्रसंस्करण की राज्य मशीन में बिल्कुल भी फिट नहीं था, और इसे थोड़ा सुधारना पड़ा। अपने सहयोगियों को प्रभावित किए बिना एक नए समाधान का परीक्षण करने और बनाने के लिए, हम तुरंत सहमत हुए कि हम एक अलग DriverDispatcher ब्रदर्स सर्विस में सब कुछ करेंगे। वह आदेश लेगा, एक कतार में खड़ा करेगा, ड्राइवरों को ढूंढेगा और रैलियों के परिणामों को बचाएगा।

सबसे पहले, हमें ट्रैकर को एक नई लोड प्रोफ़ाइल के लिए तैयार करना था। यदि एक लालची दृष्टिकोण के साथ, ड्राइवरों के लिए अनुरोध ट्रैकर बैलेंसर पर व्यक्तिगत रूप से गिर गए और लोड संतुलन के साथ इसके उदाहरणों पर पुनर्निर्देशित किया गया, तो बफर गंतव्य में सभी अनुरोध एक मशीन से थे: व्यक्तिगत अनुरोध बस कनेक्शन पूल को रोकेंगे। इसलिए, हमने ट्रैकर को ट्रैकर के अंदर एक साथ संसाधित किए गए अनुरोधों के बैचों को संसाधित करने की क्षमता को जोड़ा। रास्ते के साथ, हमें बैच प्रसंस्करण के लिए उचित संख्या में अनुरोधों की समस्या को भी हल करना था। क्लाइंट की ओर से (DriverDispatcher), हमने बड़े बैच को कई छोटे लोगों में विभाजित किया और इसे विभिन्न ट्रैकर इंस्टेंस पर भेजा।



तो, ट्रैकर तैयार किया जाता है, स्कोरिंग को ट्रैकर (लालची नियुक्ति) और नई सेवा (DriverDispatcher'e) दोनों में माना जाता है, असाइनमेंट समस्या को हल करने के लिए एल्गोरिथ्म को डीबग किया जाता है और सही तरीके से काम करता है। सवाल यह है कि ऑर्डर प्रोसेसिंग की राज्य मशीन में यह सब कैसे एकीकृत किया जाए। हमने आदेश को राज्य से राज्य में स्थानांतरित किए जाने पर DriverDispatcher में ऑर्डर मेटा-जानकारी भेजना और हटाना शामिल किया। और वह लगभग काम कर गया। लगभग - क्योंकि ऑर्डर करने के लिए एक ठेकेदार की खोज के पुनरावृत्तियों को बाहरी रूप से नियंत्रित नहीं किया गया था। हम अपनी सेवा में यात्रा के साथ ड्राइवर के साथ ट्रैकर की यात्रा को बदल सकते हैं और जब यह पाया जाता है तब ड्राइवर को दे सकते हैं, और इससे पहले बस 404 दें। लेकिन यह बुरा है, क्योंकि आपको हमारे ऑर्डर मिलते ही ड्राइवर को ऑर्डर देने की आवश्यकता है, और यहां तक ​​कि कई देरी के सेकंड यहां एक भूमिका निभाते हैं: ड्राइवर बस गलत दिशा में मोड़ सकता है, और आदेश अप्रासंगिक हो जाएगा। ऐसा करने के लिए, हमने योजनाबद्ध कार्यों को प्रभावित किए बिना एक कलाकार के लिए खोज प्रक्रिया को कॉल करना संभव बना दिया। इसलिए हमने खोज तर्क (फिर से अनुरोध के साथ) को बचाया और इसे शेड्यूलर के बाहर कॉल करने की क्षमता जोड़ी।

इस प्रकार, हम कार्यशील तर्क को प्रभावित किए बिना और राज्यों की दौड़ के बिना बफर डिस्पैच में राज्य मशीन के साथ प्रसंस्करण के लिए मुख्य राज्य मशीन को संयोजित करने में सक्षम थे। आप लाइव उपयोगकर्ताओं पर पहला प्रयोग कर सकते हैं।

यह सब बहुत अच्छा है, लेकिन एक कलाकार की खोज करने के समय के बारे में आप क्या पूछते हैं। यदि आदेश प्राप्त होने के तुरंत बाद खोज नहीं होती है, तो खोज का समय बढ़ता है और परिणामस्वरूप तेज़ फ़ीड द्वारा मुआवजा दिया जाता है? यह पूरी तरह से सच नहीं है: विभिन्न तकनीकों (मशीन सीखने का उपयोग करने सहित) की मदद से, हम मामलों को अलग करने में सक्षम थे जब प्रतीक्षा समझ में आती है, अन्य मामलों में प्रतीक्षा समय नहीं बदलता है।

पिन ड्रा

एक कलाकार को तेजी से खोजने का दूसरा तरीका यह है कि एक आदेश बनाने से पहले उसकी तलाश शुरू कर दी जाए। जब एक नया पिन प्रकट होता है (अर्थात, उपयोगकर्ता केवल एप्लिकेशन में ऑर्डर डेटा दर्ज करता है), मशीन लर्निंग एल्गोरिदम इस संभावना का मूल्यांकन करते हैं कि एक आदेश का पालन होगा, और यह तय करें कि ड्राइवरों को बफर करते समय इसे ध्यान में रखना चाहिए या नहीं। हम पहले से कार पा सकते हैं, और जब उपयोगकर्ता ऑर्डर बटन पर क्लिक करता है, तो तुरंत एक उपयुक्त ड्राइवर को एक प्रस्ताव दें।

निष्कर्ष

मैचिंग ऑर्डर और ड्राइवर एक आसान काम नहीं है, इसके लिए कई कारकों को ध्यान में रखना पड़ता है। उनमें से एक ड्राइवर के आंदोलनों का संदर्भ है जब आदेश के लिए उम्मीदवार चुनते हैं। हम इस बारे में निम्नलिखित पोस्ट में बात करेंगे।

अन्य टैक्सी टेक्नोलॉजी पोस्ट

• गतिशील मूल्य निर्धारण, या कैसे Yandex.Taxi उच्च मांग की भविष्यवाणी करता है
• कार की स्थिति का आकलन करने के लिए कंप्यूटर विजन का उपयोग कैसे करें। अनुभव यैंडेक्स। टेक्सी
• कैसे Yandex.Taxi मशीन सीखने का उपयोग करते हुए कार डिलीवरी समय की भविष्यवाणी करता है