बस सार्वजनिक परिवहन एल्गोरिदम

Question

मैं ऑफ़लाइन सी # एप्लिकेशन पर काम कर रहा हूं जो बस मार्ग ढूंढ सकता है। मैं समय सारिणी/बस/मार्ग डेटा निकाल सकता हूं। मैं सबसे सरल समाधान खोज रहा हूं जो मूल डेटा के साथ काम करेगा।

बस स्टॉप "ए" से बस स्टॉप "बी" से रूट खोजने के लिए क्या एल्गोरिदम का उपयोग किया जा सकता है? क्या सी #/जावा के लिए एक ओपन-सोर्स समाधान तैयार है? क्या एक आसान समाधान के लिए डेटाबेस के लिए Google जीटीएफएस प्रारूप अच्छा है? http://code.google.com/transit/spec/transit_feed_specification.html

किसी भी मदद के लिए धन्यवाद। मैं इसके साथ अटक गया हूँ। मुझे नहीं पता कि कहां से शुरू करना है - डेटा कैसे स्टोर करें और मार्ग कैसे खोजें। मुझे डिजस्ट्रा/ए * के बारे में पता है, लेकिन मैंने उन्हें केवल उन ग्राफों पर उपयोग किया है जो समय पर निर्भर नहीं थे ...

Answer 1

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

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

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

Answer 2

यदि आप समय की जानकारी में रूचि रखते हैं, तो ग्राफ़ किनारों पर दूरी के मूल्यों को एक दूसरे से भौतिक दूरी की बजाय समय की जानकारी का उपयोग क्यों नहीं करें। इस तरह आप सबसे कम मार्ग की बजाय सबसे तेज़ मार्ग की खोज करेंगे। फिर आप अपने परिणाम की गणना करने के लिए डिजस्ट्रा/ए * का उपयोग कर सकते हैं।

मैं समय पर निर्भर होने पर आपका मतलब थोड़ा अस्पष्ट हूं। यदि आपका मतलब है कि आपको 'एक्स से पहले 10 से पहले' फॉर्म के प्रश्नों का उत्तर देने की आवश्यकता है तो आप गणना कर सकते हैं कि कौन से बस मार्ग 10am से पहले पहुंचते हैं, डेटा पर एक साधारण फ़िल्टर की तरह लगता है। फिर डेटा में डिजस्ट्रा/ए * लागू करें।

Answer 3

जिस समस्या पर आप काम कर रहे हैं वह एक छोटा काम नहीं है। इतना तो, इसका नाम है: मिश्रित पूर्णांक nonlinear प्रोग्रामिंग समस्या (MINLP)। एक लेखक के शब्दों (देब 1998) में:

"जब गणितीय तैयार की, समय शेड्यूलिंग समस्या एक मिश्रित पूर्णांक nonlinear प्रोग्रामिंग समस्या (MINLP) संसाधन और सेवा-की एक बड़ी संख्या होने हो जाता है संबंधित बाधाएं।हालांकि प्रयास एक सरलीकृत मॉडल के इष्टतम अनुसूची खोजने के लिए शास्त्रीय अनुकूलन तकनीक (बुकबाइंडर & DCsilets, 1992; किकुची & परमेश्वरन, 1993) का उपयोग कर अतीत में किए गए हैं, यह देखा गया है कि यह एक अत्यंत है छोटे ट्रांजिट नेटवर्क के लिए भी मुश्किल कार्य। कठिनाई मुख्य रूप से चर और बाधाओं, चर के असतत प्रकृति, और nonlinearities उद्देश्य समारोह में शामिल और की कमी की बड़ी संख्या की वजह से पैदा होती है। "

देब के पत्र में वह एक आनुवंशिक का प्रस्ताव एल्गोरिदम

आपका दूसरा विकल्प सिमुलेशन का उपयोग करना होगा। बस कुछ बाहर फेंकने के लिए आप तुरंत कोशिश कर सकते हैं - हजारों यादृच्छिक मार्गों को चुनें जो आपकी उत्पत्ति से शुरू होते हैं, और उन लोगों को मछली पकड़ते हैं जो उचित रूप से अच्छी तरह से काम करते हैं गंतव्य के लिए

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

Answer 4

इसे अपने डेटा मॉडल के रूप में आजमाएं।

बस 1 बंद हो जाता है के लिए ए, बी और सी बस 2 चला जाता है चला जाता है बंद हो जाता है करने के लिए बी, डी और ई

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

आपको डिजस्ट्रा के एल्गोरिदम लागू करने में सक्षम होना चाहिए।

Answer 5

इसे पढ़ें:

बहु-मोडल मार्ग योजना। मास्टर की थीसिस, यूनिवर्सिटैट कार्लज़ूए (वें), Fakultät फर Informatik, http://i11www.ira.uka.de/extra/publications/p-mmrp-09.pdf

रेलवे मार्ग पर खंड पर 2009 ऑनलाइन उपलब्ध भी बस मार्ग के लिए लागू होता है।

इसका सारांश: अंतरिक्ष और समय को एक ही ग्राफ में विस्तारित करने का निष्पक्ष दृष्टिकोण बड़े नेटवर्क के लिए काम नहीं करता है। बेहतर समाधान हैं।

Answer 6

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

मैं 4 टेबल (SQLite) का उपयोग कर समाप्त हुआ। एक टेबल बसों की सूची रखती है, दूसरा स्टेशनों की एक सूची रखता है। एक और टेबल संयोजन रखती है - एक विशिष्ट स्टेशन पर कौन सी बस रुकती है और यह इस स्टेशन से कहां जाती है और यह कितनी देर तक (मिनट) लेती है। सभी संयोजनों को संग्रहीत किया जाना है। और अंतिम तालिका एक साधारण समय सारणी है।प्रत्येक स्टेशन के लिए यह हर बस को सूचीबद्ध करता है जो उस समय और समय को रोकता है (मैंने समय को पूर्णांक मान के रूप में संग्रहीत किया - 14:34 1434 है, इसे तुलना करने के लिए तेज़ी से बनाने के लिए)।

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

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

250 स्टेशनों और 100+ बसों/रेलवे के साथ, एक छोटे से शहर पर, ये दृष्टिकोण 3 परिवर्तनों तक काम करता है (जहां आपको यात्रा पर बसें बदलनी होंगी)। गणना करने में केवल सेकंड लगते हैं। लेकिन मुझे पूरे डेटाबेस को मेमोरी (डिक्शनरी) में क्वेरी को तेज करने के लिए लोड करना पड़ा, जो बहुत अधिक समय ले रहा था।

मुझे नहीं लगता कि यह एक बड़े नेटवर्क के लिए काम करेगा हालांकि। लेकिन यह एक छोटे से मध्यम आकार के शहर के सार्वजनिक परिवहन के लिए काम करता है।

Answer 7

वहाँ प्रकाशनों की एक व्यापक सूची है (30+) सार्वजनिक परिवहन मार्ग एल्गोरिदम कि खुला स्रोत (जावा) OpenTripPlanner project यहाँ के योगदानकर्ताओं द्वारा समय के साथ संकलित किया गया है पर:

https://github.com/opentripplanner/OpenTripPlanner/wiki/RoutingBibliography

OpenTripPlanner है मल्टी-मोडल रूटिंग इंजन जिसमें बाइक और पैदल भी शामिल है - उपर्युक्त लिंक से:

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

मार्ग ग्रंथ सूची ऊपर एल्गोरिदम और संबंधित काम की निम्नलिखित श्रेणियों के लिए संदर्भ शामिल हैं:

• पथ खोजें स्पीड अप तकनीक
• बहु उद्देश्य परेटो सबसे छोटा पथ
• संसाधन विवश रूटिंग
• कंट्राक्शन और ट्रांसफर पैटर्न
• समय सारिणी-आधारित रूटिंग
• एएलटी और मीट्रिक embeddings
• अंशांकन और कार्यान्वयन विवरण
• पोस्ट-डिज्कस्ट्रा सार्वजनिक परिवहन रूटिंग

आप कुछ नया है कि सूची में नहीं है मिल जाए, विकि में जोड़ने के लिए संकोच न करें!

जहां तक ​​अन्य मुक्त स्रोत सार्वजनिक परिवहन मार्ग पुस्तकालयों के रूप में - वहाँ भी Bliksem लैब्स द्वारा RRRR परियोजना:

https://github.com/bliksemlabs/rrrr

ऊपर के लिंक से:

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

ओपनट्रिपप्लानर और आरआरआरआर दोनों जीटीएफएस डेटा का उपयोग करते हैं।