सार्वजनिक परिवहन बसें का उपयोग कर शहर

Question

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

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

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

Answer 1

एक ग्राफ एक दिशात्मक ग्राफ होना जरूरी करने जा रहा है - बस (यू शायद ही कभी माध्यिकाओं है कि जैसे देश में भी) सड़कों के विपरीत दिशा में बंद हो जाता है एक ही बंद नहीं कर रहे हैं!

Answer 2

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

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

Answer 3

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

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

एप्लिकेशन शुरू करने से पहले अगले 5 घंटों (उचित के रूप में समायोजित) में सभी पथों के लिए डेटाबेस से पूछताछ की जाएगी। इसके बाद यह डिजस्ट्रा के एल्गोरिदम के साथ टूट जाएगा।

अन्य बातों लागत में कारक, आदि मार्ग, स्थानान्तरण (और उनकी लागत) की वास्तविक पैसे लागत कोई छतों के साथ बंद हो जाता है (यदि आप खराब मौसम हो जाते हैं)

यह योजना अच्छी तरह से काम मेरे लिए। मैं 3 बस प्रणालियों वाले क्षेत्र में रहता हूं।

अंत में, यह Google Transit Feed Specification के समान तरीके से आपके डेटा को ढूढ़ने के लिए कुछ अच्छा कर सकता है, क्योंकि कई एजेंसियां ​​इस प्रकार के डेटा का उत्पादन करती हैं जिन्हें आप आयात कर सकते हैं।

Answer 4

शायद तुम TransportDublin के लिए मिला on github paddydubs काम के कुछ का उपयोग हो सकता है।

Answer 5

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

मुझे याद है मैं क्योंकि प्रत्यावर्तन कभी-कभी कुछ "बुरा" क्षेत्रों में फंस जाएगा कुछ कटऑफ की स्थिति जगह पड़ा है।

मैं भी इस पत्र को देखा:

www.citeulike.org/user/rchauhan/article/819528

मेरी रुचि है, तो आप एक अलग तरीके से इस समस्या को हल करने में कामयाब रहे।