ट्रैफिक जाम की गणना में ट्रैक्टर पेड़ों का उपयोग 2GIS

यहां तक ​​कि एक नाविक होने के बिना, 2GIS ट्रैफ़िक जानकारी एकत्र करता है और प्रदर्शित करता है। सबसे पहले, इष्टतम मार्गों का निर्माण करना आवश्यक है, और दूसरी बात, बड़े शहरों में उपयोगकर्ताओं के लिए ऐसा डेटा बहुत आवश्यक है।

ट्रैफ़िक जाम सेवा सितंबर 2011 में 2GIS में दिखाई दी थी और आज पांच शहरों ( नोवोसिबिर्स्क , सेंट पीटर्सबर्ग , क्रास्नोयार्स्क , ऊफ़ा , कज़ान ) में चल रही है। निकट भविष्य की योजना दस लाख से अधिक लोगों के साथ सभी शहरों में ट्रैफिक जाम शुरू करने की है।

कटौती के तहत, कहानी यह है कि हमने किन समस्याओं का सामना किया और उन्हें कैसे हल किया गया।


"ट्रैफिक जैम्स" का आधार डेटा है, अर्थात् अंक। एक एकल बिंदु निम्नलिखित बुनियादी जानकारी को वहन करता है:

• परियोजना पहचानकर्ता (शहर);
• पंजीकरण का समय;
• निर्देशांक;
• तात्कालिक गति;
• पंजीकरण के समय आंदोलन की दिशा।

हमें अपने डेटा प्रदाताओं, साथ ही 2 जीआईएस मोबाइल संस्करण के उपयोगकर्ताओं से ऐसे अंक मिलते हैं। गणना में भाग लेने से पहले, डेटा MongoDB के आधार पर एक कच्चे डेटा स्टोर में समाप्त होता है।

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

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



आइए एक बिंदु (चित्रा) लें, और यह निर्धारित करने का प्रयास करें कि यह किस सड़क के किस हिस्से में पंजीकृत था।



यह स्पष्ट है कि सड़क का वांछित खंड बिंदु के पास कहीं है, इसलिए कार्य तुरंत एक निश्चित त्रिज्या (उदाहरण के लिए, 20 मीटर) में सड़क नेटवर्क के निकटतम खंड को खोजने के लिए उठता है।

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

सब कुछ ठीक हो जाएगा, लेकिन कुछ शहरों में महंगा नेटवर्क बहुत बड़ा है, सैकड़ों हजारों सेगमेंट हैं, और जिन बिंदुओं को खींचने की जरूरत है वे कुछ ही मिनटों में लाखों हैं, ताकि समस्या के समाधान की गुणवत्ता के साथ-साथ खोज गति का सवाल भी उठे।

पहले क्या था

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

चूंकि केंद्रीय डेटा वेयरहाउस PostgreSQL का उपयोग करता है, इसलिए इस समस्या को प्रारंभिक चरणों में पोस्टगिस एक्सटेंशन का उपयोग करके हल किया गया था।
सीधे शब्दों में कहें, एल्गोरिथम कुछ इस तरह था:

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

यह पूरी रसोई संग्रहीत प्रक्रियाओं पर काम करती थी, हालांकि बहुत जल्दी नहीं, लेकिन इन आंकड़ों में कोई तात्कालिकता नहीं थी, क्योंकि यह कार्य ऑफ़लाइन उत्पादों के लिए हल किया गया था।

एक औसत सर्वर पर, गति लगभग 2,000 अंक प्रति सेकंड थी।

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

यह लंबे समय से अधिक विचार को लागू करने का समय है - सी ++ में गणनाओं का कार्यान्वयन।

त्वरित समाधान के लिए खोजें

समानांतर में, हमने 2 समाधान विकसित करना शुरू किया - एक जीईओएस लाइब्रेरी पर आधारित, और दूसरा पूरी तरह से क्वाड पेड़ों पर आधारित स्क्रैच से।

GEOS के बारे में

यह समाधान पहले दिखाई दिया क्योंकि इसमें तैयार GEOS लाइब्रेरी का उपयोग किया गया था, जो कि, PostGIS द्वारा उपयोग किया जाता है।

इस लाइब्रेरी से क्वाडट्री इंडेक्स का उपयोग निकटतम सेगमेंट की खोज के लिए किया गया था।

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

चतुर्थ वृक्षों का स्वयं का कार्यान्वयन

यह क्रियान्वयन दूसरा दिखाई दिया, लेकिन (थोड़ा आगे देखकर) यह थोड़ा और सफल हुआ।

सबसे पहले, स्पष्टता को जोड़ने के लिए कुछ सामान्य परिभाषाएँ।

क्वाड ट्री एक ऐसा पेड़ है जिसमें प्रत्येक आंतरिक नोड में चार वंशज हैं।
क्वाड ट्री आपको दो आयामी स्थान को चार क्वाडंट (क्षेत्रों) में पुन: विभाजित करने की अनुमति देता है।



क्वाड ट्री विभिन्न प्रकार के डेटा के बारे में जानकारी संग्रहीत कर सकते हैं, लेकिन हम स्टोरिंग सेगमेंट (सेगमेंट) में रुचि रखते हैं, क्योंकि सड़क नेटवर्क को केवल सेगमेंट के माध्यम से दर्शाया जा सकता है।

ऐसा करने के लिए, हमने स्टोरिंग सेगमेंट के लिए अनुकूलित पीएम क्वाडट्री के संस्करण का उपयोग किया - पॉलीगोनल मैप रैंडम क्वाडट्री।

पीएमआर चतुर्थी:

• एक संभाव्य विभाजन नियम का उपयोग करता है;
• प्रत्येक नोड में खंडों की एक चर संख्या होती है;
• प्रत्येक खंड को सभी नोड्स में डाला जाता है जो इसे प्रतिच्छेद करते हैं;
• यदि नोड में उन खंडों की संख्या है जो सीमा से अधिक है, तो 4 बच्चे नोड्स में एक विभाजन (केवल एक बार) होता है;
• निकटतम सेगमेंट खोजने के कार्य के लिए अच्छी तरह से अनुकूल है।

विपक्ष:

• पेड़ का संभावित असंतुलन।

पेड़ का प्रत्येक नोड एक निश्चित क्षेत्र (उदाहरण के लिए, वर्ग) का प्रतिनिधित्व करता है और इसमें निम्नलिखित जानकारी होती है:

• गहराई;
• क्षेत्र निर्देशांक;
• चार वंशज अगर नोड आंतरिक है;
• नोड बाहरी है, तो खंड।

नोड केवल उन खंडों को संग्रहीत करता है जो इसके क्षेत्र को काटते हैं। एक नोड में खंडों की संख्या परिवर्तनशील है।

इमारत

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

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

दृश्य

वृक्ष की खोज

खोज के लिए हम प्राथमिकता कतार का उपयोग करेंगे।
हम तीन प्रकार की वस्तुओं को कतार में रखेंगे:

• आंतरिक नोड्स;
• बाहरी नोड्स;
• खंडों।

कतार की कुंजी प्रारंभिक बिंदु की दूरी है। प्रारंभ में, कतार में केवल रूट नोड होता है।

अब प्रत्येक चरण में हम कतार से न्यूनतम दूरी के साथ एक वस्तु लेंगे और उसके प्रकार पर निर्भर करते हुए उचित संचालन करेंगे:

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

इसी तरह, आप पास के कई खंडों की समस्या को एक दायरे में हल कर सकते हैं।

तुलना

GEOS और हमारे स्वयं के कार्यान्वयन की तुलना में, हम सुखद आश्चर्यचकित थे:
300,000 सेगमेंट के लिए समान हार्डवेयर पर:

	GEOS	पीएमआर क्वाडट्री
एक पेड़ का निर्माण	2 सेकंड	0.2 सेकंड
मेमोरी की खपत	200 एमबी	50 एमबी
बिंदु ड्रा	35,500 डॉट प्रति सेकंड	383,500 प्रति सेकंड

नतीजतन, हमारे स्वयं के समाधान ने नए बिंदु को आकर्षित करने वाली सेवा का आधार बनाया, और हमें एक औसत सर्वर पर पूरे रूस में सभी आपूर्तिकर्ताओं से अंक खींचने की अनुमति देता है।

निष्कर्ष

नतीजतन, पोस्टजीआईएस से सी ++ में अत्यधिक विशिष्ट समाधान के लिए आगे बढ़ते हुए, हमें 2k से 380k (190 गुना) तक त्वरण मिला।

अत्यधिक विशिष्ट बाइक लिखें!

आप देख सकते हैं कि ट्रैफ़िक जाम सेवा अभी कैसे काम करती है, या iOS या Android पर 2GIS स्थापित करके।