algorithm क्या एल्गोरिदम मानचित्र पर बिंदु ए से बिंदु बी पर दिशानिर्देशों की गणना करते हैं?




routing mapping (15)

नक्शा प्रदाता (जैसे Google या याहू! मैप्स) निर्देश कैसे सुझाते हैं?

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

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

अभ्यास में वास्तव में क्या एल्गोरिदम का उपयोग किया जाता है?

पुनश्च। यह प्रश्न ऑनलाइन मैपिंग दिशानिर्देशों में क्विर्क ढूंढकर प्रेरित था। त्रिकोण असमानता के विपरीत, कभी-कभी Google मानचित्र सोचता है कि X-Z अधिक समय लेता है और X-Y-Z में मध्यवर्ती बिंदु का उपयोग करने से कहीं अधिक है। लेकिन हो सकता है कि उनके पैदल चलने के निर्देश भी दूसरे पैरामीटर के लिए अनुकूल हों?

पी पी एस। त्रिकोण असमानता का एक और उल्लंघन है जो बताता है (मेरे लिए) कि वे किसी प्रकार के टियर किए गए दृष्टिकोण का उपयोग करते हैं: X-Z बनाम X-Y-Z । पूर्व में प्रमुख बुल्वार्ड डी सेबस्तोपोल का उपयोग करना प्रतीत होता है, भले ही यह रास्ते से थोड़ा सा हो।

संपादित करें : इनमें से कोई भी उदाहरण अब काम नहीं कर रहा है, लेकिन दोनों मूल पोस्ट के समय में थे।


किसी ऐसे व्यक्ति के रूप में बोलते हुए जिसने मैपिंग कंपनी में काम करने में 18 महीने बिताए, जिसमें रूटिंग एल्गोरिदम पर काम करना शामिल था ... हाँ, Dijkstra's कुछ कामों के साथ काम करता है:

  • स्रोत से dest तक एक बार Dijkstra's को करने के बजाय, आप प्रत्येक छोर पर शुरू होते हैं, और बीच में मिलने तक दोनों तरफ विस्तार करते हैं। यह लगभग आधे काम को समाप्त करता है (2 * पीआई * (आर / 2) ^ 2 बनाम पीआई * आर ^ 2)।
  • अपने स्रोत और गंतव्य के बीच हर शहर की बैक-एलीज़ की खोज से बचने के लिए, आपके पास मानचित्र डेटा की कई परतें हो सकती हैं: ए 'राजमार्ग' परत जिसमें केवल राजमार्ग होते हैं, एक 'द्वितीयक' परत जिसमें केवल द्वितीयक सड़कों होती है, और आगे भी। फिर, आप आवश्यकतानुसार विस्तारित, अधिक विस्तृत परतों के केवल छोटे अनुभागों का पता लगाते हैं। जाहिर है कि यह विवरण बहुत अधिक जानकारी छोड़ देता है, लेकिन आपको विचार मिलता है।

उन पंक्तियों के साथ संशोधनों के साथ, आप एक बहुत ही उचित समय सीमा में क्रॉस-कंट्री रूटिंग भी कर सकते हैं।


मैं उपयोग की जाने वाली हेरिस्टिक्स के बारे में बहुत उत्सुक था, जब थोड़ी देर पहले हमें सांता रोजा के पास एक ही प्रारंभिक स्थान से मार्ग मिल गया, जो योसामेट नेशनल पार्क में दो अलग-अलग कैम्पग्राउंड तक पहुंचा। इन अलग-अलग गंतव्यों ने इस तथ्य के बावजूद काफी अलग मार्ग (आई -580 या सीए -12 के माध्यम से) का उत्पादन किया, इस तथ्य के बावजूद कि दोनों मार्ग अंत में कुछ मील से फिर से अलग होने से पहले पिछले 100 मील (सीए -20 के साथ) के लिए एकत्र हुए। यह काफी दोहराने योग्य था। दोनों मार्ग लगभग 100 मील के लिए 50 मील तक अलग थे, लेकिन दूरी / समय एक-दूसरे के करीब थे, जैसा कि आप उम्मीद करेंगे।

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


GraphHopper का GraphHopper , जो कि OpenStreetMap पर आधारित एक तेज़ ओपन सोर्स रूट प्लानर है, मैंने थोड़ा सा साहित्य पढ़ा है और कुछ तरीकों को लागू किया है। सबसे सरल समाधान एक डिजस्ट्रा है और एक साधारण सुधार एक बिडरेक्शनल डिजस्ट्रा है जो लगभग नोड्स का आधा हिस्सा खोजता है। बिडरेक्शनल डिजस्ट्रा के साथ पूरे जर्मनी के माध्यम से एक मार्ग पहले से ही 1sec (कार मोड के लिए) लेता है, सी में यह शायद केवल 0.5 या उससे अधिक होगा;)

मैंने here बिडरेक्शनल डिजस्ट्रा के साथ वास्तविक पथ खोज का एनिमेटेड gif बनाया here । इसके अलावा डिजस्ट्रा को ए * करने की तरह तेज़ी से बनाने के लिए कुछ और विचार हैं, जो एक "लक्ष्य उन्मुख डिजस्ट्रा" है। इसके अलावा मैंने इसके लिए एक gif-animation बनाया है।

लेकिन यह कैसे करें (बहुत) तेज़?

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

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

ग्राफ़होपर के लिए मैंने कंट्राक्शन पदानुक्रमों का उपयोग करने का निर्णय लिया क्योंकि यह लागू करने के लिए सापेक्ष 'आसान' है और ग्राफ की तैयारी के लिए उम्र नहीं लेता है। यह अभी भी बहुत तेज़ प्रतिक्रिया समय में परिणाम देता है जैसे आप हमारे ऑनलाइन इंस्टेंस ग्राफ़होपर मैप्स पर परीक्षण कर सकते हैं। दक्षिण अफ्रीका से पूर्व चीन तक, जिसके परिणामस्वरूप 23000 किमी दूरी और कार के लिए लगभग 14 दिन ड्राइविंग का समय होता है और सर्वर पर केवल ~ 0.1s लिया जाता है।


मैंने कुछ वर्षों तक रूटिंग पर काम किया है, हाल ही में मेरे ग्राहकों की ज़रूरतों से प्रेरित गतिविधि के विस्फोट के साथ, और मैंने पाया है कि ए * आसानी से पर्याप्त तेज़ है; अनुकूलन या अधिक जटिल एल्गोरिदम देखने की वास्तव में कोई ज़रूरत नहीं है। एक विशाल ग्राफ पर रूटिंग एक समस्या नहीं है।

लेकिन गति पूरे रूटिंग नेटवर्क पर निर्भर करती है, जिसके द्वारा मेरा मतलब स्मृति में मार्ग खंडों और जंक्शनों का क्रमशः आर्क और नोड्स का निर्देशित ग्राफ है। मुख्य नेटवर्क ओवरहेड यह नेटवर्क बनाने के लिए लिया गया समय है। विंडोज़ चलाने वाले सामान्य लैपटॉप के आधार पर कुछ नाराज आंकड़े, और पूरे स्पेन में रूटिंग: नेटवर्क बनाने के लिए समय निकाला गया: 10-15 सेकंड; एक मार्ग की गणना करने के लिए समय लिया गया: मापने के लिए बहुत छोटा है।

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


मेरे पास इस पर कुछ और विचार थे:

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

2) सीमित कनेक्टिविटी द्वारा परिभाषित जोनों के पूरे समूह में दुनिया को विभाजित करें, जोनों के बीच सभी कनेक्टिविटी बिंदुओं को परिभाषित करें। कनेक्शन बिंदुओं के बीच बस मानचित्र के बीच जोन के लिए, आपके कनेक्शन से प्रारंभ और अंत क्षेत्र मार्ग के लिए प्रत्येक कनेक्शन बिंदु पर, आपके स्रोत और लक्ष्य में कौन से क्षेत्र हैं, खोजें। (मुझे संदेह है कि बाद में बहुत से पहले से गणना की जा चुकी है।)

ध्यान दें कि जोन मेट्रोपॉलिटन क्षेत्र से छोटे हो सकते हैं। भू-भाग वाली सुविधाओं वाला कोई भी शहर जो इसे विभाजित करता है (कहें, एक नदी) कई जोन होंगे।


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


मैंने यह कई बार कई बार किया है, वास्तव में, कई अलग-अलग तरीकों की कोशिश कर रहा है। मानचित्र के आकार (भौगोलिक) के आधार पर, आप हाइपरिन फ़ंक्शन को हेरिस्टिक के रूप में उपयोग करने पर विचार करना चाहेंगे।

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

f(n) = k*h(n) + g(n)

जहां के 0 0 से अधिक स्थिर है।


यहां दुनिया की सबसे तेज़ रूटिंग एल्गोरिदम की तुलना और शुद्धता के लिए सिद्ध किया गया है:

http://algo2.iti.uka.de/schultes/hwy/schultes_diss.pdf

इस विषय पर एक Google तकनीक बात है:

youtube.com/watch?v=-0ErpE8tQbw

यहां राजमार्गों द्वारा चर्चा की गई राजमार्ग-पदानुक्रम एल्गोरिदम का कार्यान्वयन है (वर्तमान में केवल बर्लिन में, मैं इंटरफ़ेस लिख रहा हूं और एक मोबाइल संस्करण भी विकसित किया जा रहा है):

http://tom.mapsforge.org/


स्थैतिक सड़क नेटवर्क के लिए पूछताछ के समय कला की वर्तमान स्थिति अब्राहम एट अल द्वारा प्रस्तावित हब लेबलिंग एल्गोरिदम है। http://link.springer.com/chapter/10.1007/978-3-642-20662-7_20 । क्षेत्र के माध्यम से और उत्कृष्ट रूप से लिखित सर्वेक्षण को हाल ही में एक Microsoft तकनीकी रिपोर्ट http://research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf रूप में प्रकाशित किया गया था।

लघु संस्करण है ...

हब लेबलिंग एल्गोरिदम स्थिर सड़क नेटवर्क के लिए सबसे तेज़ प्रश्न प्रदान करता है लेकिन रैम चलाने के लिए बड़ी मात्रा में रैम की आवश्यकता होती है (18 जीबीबी)।

ट्रांजिट नोड रूटिंग थोड़ा धीमा है, हालांकि, इसे केवल 2 जीबी मेमोरी की आवश्यकता होती है और इसमें एक तेज प्रीप्रोकैसिंग समय होता है।

कंट्राक्शन पदानुक्रम त्वरित प्रीप्रोकैसिंग समय, कम स्पेस आवश्यकताएं (0.4 जीबीबी) और तेज क्वेरी समय के बीच एक अच्छा व्यापार प्रदान करते हैं।

कोई भी एल्गोरिदम पूरी तरह से हावी नहीं है ...

पीटर सैंडर्स द्वारा यह Google तकनीक की बात ब्याज की हो सकती है

https://www.youtube.com/watch?v=-0ErpE8tQbw

एंड्रयू गोल्डबर्ग द्वारा भी यह बात

https://www.youtube.com/watch?v=WPrkc78XLhw

संकुचन पदानुक्रमों का एक खुला स्रोत कार्यान्वयन किट में पीटर सैंडर्स अनुसंधान समूह वेबसाइट से उपलब्ध है। http://algo2.iti.kit.edu/english/routeplanning.php

माइक्रोसॉफ्ट द्वारा सीआरपी एल्गोरिदम के उपयोग पर भी आसानी से सुलभ ब्लॉग पोस्ट ... http://blogs.bing.com/maps/2012/01/05/bing-maps-new-routing-engine/


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

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

लेख इंजीनियरिंग फास्ट रूट योजना एल्गोरिदम उस क्षेत्र में अनुसंधान की प्रगति का एक सिंहावलोकन देता है। अधिक जानकारी के लिए उस पेपर के संदर्भ देखें।

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

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

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


डिजस्ट्रा के एल्गोरिदम जैसे ग्राफ़ एल्गोरिदम काम नहीं करेंगे क्योंकि ग्राफ बहुत बड़ा है।

यह तर्क जरूरी नहीं है क्योंकि डिजस्ट्रा आमतौर पर पूरे ग्राफ को नहीं देखेगा बल्कि बल्कि एक बहुत ही छोटा सबसेट (बेहतर ग्राफ से जुड़ा हुआ होगा, यह सबसेट छोटा होगा)।

डिजस्ट्रा वास्तव में अच्छी तरह से व्यवहार किए गए ग्राफ के लिए अच्छा प्रदर्शन कर सकता है। दूसरी तरफ, सावधान parametrization ए * हमेशा अच्छा, या बेहतर प्रदर्शन करेंगे। क्या आपने पहले ही कोशिश की है कि यह आपके डेटा पर कैसा प्रदर्शन करेगा?

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


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


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

यह देखते हुए कि यह एक Google ऐप है, यह भी मानना ​​उचित है कि व्यापक कैशिंग के माध्यम से बहुत सारे जादू किए जाते हैं। :) यदि मैं एक साधारण लुक-अप द्वारा उत्तर देने के अनुरोधों के बड़े हिस्से (20%? 50%?) के लिए अनुमति देने वाले शीर्ष 5% सबसे आम Google मानचित्र मार्ग अनुरोधों को कैशिंग कर रहा हूं तो मुझे आश्चर्य नहीं होगा।


मैं देखता हूं कि ओपी में नक्शे के साथ क्या चल रहा है:

निर्दिष्ट मध्यवर्ती बिंदु के साथ मार्ग देखें: उस सड़क के कारण मार्ग सीधे पीछे की तरफ जाता है जो सीधे नहीं है।

अगर उनके एल्गोरिदम बैकट्रैक नहीं करेंगे तो यह छोटा रास्ता नहीं देखेगा।


मैंने पहले Google या माइक्रोसॉफ्ट या याहू मैप्स पर काम नहीं किया है, इसलिए मैं आपको नहीं बता सकता कि वे कैसे काम करते हैं।

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

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

आप इस तकनीक पर और अधिक जानने के लिए एसीओ या टीएसपी गूगल कर सकते हैं। मैंने इसके लिए किसी भी ओपन-सोर्स एआई टूल्स का उपयोग नहीं किया है, इसलिए एक सुझाव नहीं दे सकता (हालांकि मैंने सुना है कि SWARM बहुत व्यापक था)।





mapping