उबेर: मुख्य प्लेटफार्म प्रबंधन एल्गोरिदम का अवलोकन

1. परिचय

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

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

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

2. मुख्य एल्गोरिदम का विवरण

पिछले एक दशक में, परिवहन समाधान उद्योग तेजी से नए वैचारिक विचारों और प्रौद्योगिकियों, जैसे कि ऑनलाइन यात्री परिवहन प्लेटफार्मों, सेल्फ ड्राइविंग कारों और इलेक्ट्रिक कारों के विकास के लिए धन्यवाद बढ़ रहा है। इन प्रौद्योगिकियों का तालमेल, जो कई कंपनियां और प्रयोगशालाएं एक ही समय में काम कर रही हैं, यात्री परिवहन की इकाई लागत को कम करने में एक बड़ी सफलता का वादा करती है, एक-दो दशकों में 10 बार से कम नहीं।

प्रौद्योगिकियों की इस सूची से सबसे विस्फोटक वृद्धि वर्तमान में ऑनलाइन यात्री परिवहन प्लेटफार्मों द्वारा प्रदर्शित की जाती है। उदाहरण के लिए, उबर ने अपने 10 वर्षों के अस्तित्व [चित्रा 1] पर 80 से अधिक देशों और दुनिया भर के 700 शहरों में 10 बिलियन से अधिक यात्राएं की हैं। ऐसे ऑनलाइन परिवहन के लिए वैश्विक बाजार 2030 तक $ 285 बिलियन के अविश्वसनीय आकार तक पहुंचने का वादा करता है। इसलिए, यह आश्चर्यजनक नहीं है कि ऐसे प्लेटफार्मों की प्रभावशीलता जो यात्रियों और ड्राइवरों के द्विपक्षीय बाजार को गतिशील रूप से नियंत्रित करती है, महान व्यावहारिक महत्व है।



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

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

आदेशों के वितरण के लिए 2.1 एल्गोरिदम (मिलान)

ड्राइवर को ऑर्डर देने के लिए सबसे सरल डिस्पैचिंग एल्गोरिथ्म तथाकथित पहला-प्रेषण प्रोटोकॉल है। इसकी सादगी और अच्छे व्यावहारिक प्रदर्शन संकेतक के बावजूद, यह दिखाना आसान है कि यह एल्गोरिथ्म अक्सर होने वाली स्थितियों की एक बड़ी संख्या में अप्रभावी है। सबसे पहले, वह ड्राइवरों के उस सबसेट से केवल एक ड्राइवर का चयन करता है जो ऑर्डर के समय मुक्त होते हैं, उन ड्राइवरों की अनदेखी करते हैं जो एक नए ऑर्डर के तत्काल आसपास के क्षेत्र में एक यात्रा को पूरा करने के करीब हो सकते हैं [चित्र 4]। दूसरे, यह सरल एल्गोरिथ्म केवल एक निश्चित समय में सिस्टम के बारे में जानकारी को ध्यान में रखता है, जबकि अधिकांश बार मंच को पर्याप्त सटीक जानकारी प्रदान की जा सकती है कि आदेशों के प्रवाह और निकट भविष्य में ड्राइवरों के स्थानिक वितरण के साथ क्या होगा। साहित्य में, व्यावहारिक व्यंजनों को देने वाले समान कार्यों के एक वर्ग को एल्गोरिथ्म की गुणवत्ता में सुधार के लिए ऐसी जानकारी का उपयोग कैसे किया जा सकता है, इसे "के-सर्वर समस्या" कहा जाता है।



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

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

2.2 गतिशील मूल्य निर्धारण एल्गोरिदम

ऑनलाइन यात्री परिवहन मंच के प्रबंधन में मुख्य परिचालन कठिनाइयों में से एक टैक्सी सेवाओं के लिए मांग और आपूर्ति की मात्रा है जो लगातार अंतरिक्ष और समय में बदल रहे हैं। नीचे दिए गए आंकड़े [चित्र 5] में यात्रियों से सैन फ्रांसिस्को के दो क्षेत्रों के लिए लाइन पर बिताए गए घंटों: वित्तीय केंद्र और शहर के बाहरी इलाके में आवासीय नींद क्षेत्र में यात्रियों से ऑनलाइन यात्रा अनुरोधों की संख्या का अनुपात दिखाया गया है। यह ग्राफ आपूर्ति और मांग (जिनमें से अनुपात कभी-कभी अत्यंत उच्च मान ले सकता है) के साथ-साथ भौगोलिक स्थिति के आधार पर इस संतुलन के व्यवहार की विविधता के बीच उच्च अस्थिरता और संतुलन की कमी को अच्छी तरह से दिखाता है।



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

गतिशील मूल्य निर्धारण मॉडलिंग के लिए लोकप्रिय तरीकों में आर्थिक मॉडल शामिल हैं जो एक स्थिर-राज्य मॉडल, गतिशील प्रोग्रामिंग मॉडल, प्रतिगमन विश्लेषण और नेटवर्क अनुकूलन का वर्णन करने वाले अनुकूलन मॉडल शामिल हैं। अर्थशास्त्रियों (कैस्टिलो, 2017) के हाल के अध्ययनों से पता चला है कि एक गतिशील टैरिफ वृद्धि भी प्लेटफॉर्म को डब्ल्यूजीसी के नकारात्मक प्रभाव के क्षेत्र में गिरने से बचने की अनुमति देती है, जिसके बारे में हमने ऊपर बात की थी।

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

2.3 कार का गतिशील प्रतीक्षा समय (डायनेमिक प्रतीक्षा)

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

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

गतिशील गंतव्य समय तंत्र का सामान्य विचार निम्नानुसार है। एक यात्रा का आदेश देने वाले यात्री के लिए, एप्लिकेशन तुरंत एक ड्राइवर की नियुक्ति नहीं करता है, लेकिन प्रतीक्षा करने की पेशकश करता है, लेकिन आगे बताए गए समय की एक निश्चित राशि से अधिक नहीं (ठेठ ऊपरी सीमाएं 2 या 5 मिनट हैं)। इसके अलावा, ड्राइवर की नियुक्ति किसी भी समय प्लेटफ़ॉर्म के लिए सुविधाजनक हो सकती है: तत्काल से निर्दिष्ट ऊपरी सीमा तक। इस मामले में, कार के लिए कुल यात्री प्रतीक्षा समय में दो (लगभग स्वतंत्र) भाग होते हैं: चालक नियुक्त होने तक का समय और आदेश की जगह पर उसकी नियुक्ति से आने का समय। एक यात्री की प्रतीक्षा की असुविधा को कम किराया द्वारा मुआवजा दिया जाता है।

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

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

3. निष्कर्ष

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

उद्धृत स्रोतों के सभी संदर्भ मूल लेख ( राइड-सेलिंग प्लेटफ़ॉर्म में गतिशील मूल्य निर्धारण और मिलान - एन। कोरोलको , डी। वुडार्ड, सी। यान, एच। झू - 2019) में पाए जा सकते हैं।