कार द्वारा दिशाओं की खोज करते समय ट्रैफिक जाम के बारे में सांख्यिकीय जानकारी पर विचार

बहुत पहले नहीं, हब पर 2GIS उत्पादों में एल्गोरिदम को रूट करने के बारे में एक लेख प्रकाशित किया गया था। मैं अपने सहकर्मी की कहानी जारी रखूंगा, जो समझाता है कि पीसी संस्करण में हम कार के लिए सर्वोत्तम समय मार्ग की तलाश कर रहे हैं। यहां मैं याद करना चाहूंगा कि 2 जीआईएस का पीसी संस्करण बिना इंटरनेट कनेक्शन के काम करता है।



आरंभ करने के लिए, बिंदु A से बिंदु B तक आवश्यक मार्ग की अलग-अलग आवश्यकताएं हो सकती हैं:
- मार्ग की लंबाई (सबसे छोटी);
- मार्ग के साथ आवाजाही का समय (ट्रैफिक जाम को ध्यान में रखते हुए);
- मध्यवर्ती बिंदु (मार्ग पर प्राथमिकताएं), आदि।

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

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

सांख्यिकी संग्रह

यह सब यातायात के आंकड़ों को एकत्र करने से शुरू होता है। यह शहर के रोड ग्राफ के सभी किनारों पर इकट्ठा होता है और सप्ताह के हर दिन 15 मिनट के लिए जमा होता है। आँकड़ों की तैयारी में दो मुख्य चरण होते हैं:

1. सप्ताह के दिनों तक डेटा का संचय । प्रति दिन एकत्र किए गए उपकरणों के सभी बिंदुओं को ग्राफ के किनारों और 15 मिनट के अंतराल के अनुसार वर्गीकृत किया गया है। इसके अलावा, प्रत्येक किनारे के लिए हर बार अंतराल के लिए, औसत प्रदर्शन किया जाता है। हम ऐसे आंकड़ों को प्राथमिक कहेंगे। यह पिछले 4 हफ्तों के लिए एक डेटाबेस में संग्रहीत है। 4 सप्ताह से अधिक पुराना डेटा हटा दिया जाता है।
2. संचित डेटा का एकत्रीकरण । एक नए दिन के लिए डेटा जोड़ने के बाद, हम तथाकथित को पुनर्गणना करते हैं सप्ताह के संबंधित दिन के लिए आंकड़े "आमतौर पर"।

सप्ताह के एक निश्चित दिन के लिए, ट्रैफ़िक जाम में शामिल होने वाले रोड ग्राफ़ के सभी किनारों के लिए, और प्रत्येक 15 मिनट के समय अंतराल के लिए:

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

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

डेटा विश्लेषण विधि

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

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

अस्थायी किनारे प्रोफाइल का वर्गीकरण

कारक विश्लेषण के उपयोग को तीन मुख्य चरणों में विभाजित किया जा सकता है।

1. सहसंयोजक मैट्रिक्स

विश्लेषण किनारों के लौकिक प्रोफाइल के कोवरियन के मैट्रिक्स के निर्माण से शुरू होता है, जो कारकों को उजागर करने के लिए आवश्यक है। हम वेक्टर v = (v [1], ..., v [m]) द्वारा किनारे के समय प्रोफ़ाइल को निरूपित करते हैं, जहां v [i] किनारे पर यातायात प्रवाह की गति i = 1, ..., m है। अब "आमतौर पर" आँकड़ों की समयावधि 15-मिनट के विवेक के साथ 1 सप्ताह है, जो m = 7 × 24 × 60/15 = 672 देता है।

समय प्रोफाइल के सहसंयोजक का मैट्रिक्स निम्नलिखित रूप है, जहां ई गणितीय अपेक्षा है:

2. मूल समस्या का अपघटन

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

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

3. अस्थायी प्रोफाइल की कक्षाओं का निर्माण

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

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

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

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



कुल मिलाकर, नोवोसिबिर्स्क के लिए लगभग 100 ऐसी कक्षाएं प्राप्त की जाती हैं। इन वर्गों द्वारा सभी अस्थायी किनारे प्रोफाइल का वितरण मूल प्रोफाइल के बजाय कक्षाओं के बजाय कॉम्पैक्ट सेट को स्टोर करना संभव बनाता है, एक डिस्क पर केवल ~ 65-70 Kb पर कब्जा कर लेता है। हम ऐसे वर्गों को वेग मैट्रिक्स कहते हैं।

रूटिंग एल्गोरिदम में स्पीड मैट्रिक्स

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

नोवोसिबिर्स्क में सोमवार को 18:00 स्थानीय समय पर एक सामान्य ट्रैफ़िक जाम पर विचार करें (आंकड़े "आमतौर पर"):


बिंदु ए से बिंदु बी तक दो मार्गों की तुलना करें - दूरी में सबसे कम और यात्रा समय में इष्टतम। सबसे छोटा मार्ग: लंबाई - 7,330 मीटर, यात्रा का समय ट्रैफिक की जानकारी लेने में - 1,347 सेकंड:



मार्ग जो यात्रा के समय के संदर्भ में इष्टतम है: लंबाई - 8,033 मीटर, यात्रा के समय की जानकारी ट्रैफ़िक जानकारी लेने में - 1,295 सेकंड:



इस प्रकार, वर्णित तकनीक ~ 65-70 Kb की मात्रा के साथ एक अपेक्षाकृत छोटी वस्तु में रोड ग्राफ के दसियों किनारों पर दसियों वेग पर "पैक" सांख्यिकीय जानकारी की अनुमति देता है। यह ऑफ़लाइन उत्पादों में इसका उपयोग करना संभव बनाता है। माना गया उदाहरण बताता है कि यात्रा के समय में इष्टतम मार्ग, संकेतित समय पर देखे गए ट्रैफिक जाम पैटर्न के अनुरूप है (हम सबसे छोटे मार्ग से गुजरते हैं, जहां से सबसे छोटा मार्ग गुजरता है)।