पथ प्रतिबंध (रूटिंग, यात्रा योजना, ...) समय प्रतिबंधों के साथ ग्राफ पर एल्गोरिदम

Question

मेरे पास बस/ट्रेन/डेटाबेस का प्रत्येक डेटाबेस है ... प्रत्येक तारीख पर आगमन और प्रस्थान/प्रस्थान का समय। मैं दो स्थानों के बीच सबसे तेज़ (सबसे कम/सस्ती/कम से कम संक्रमण) यात्रा की खोज करने का एक तरीका ढूंढ रहा हूं। मैं भविष्य में मनमाने ढंग से स्थानों को देखना चाहता हूं, स्टॉप और स्टॉप से ​​स्टार्ट/स्टॉप के बीच चलने के लिए OpenStreetMap डेटा का उपयोग करके, हालांकि समय के लिए मैं डेटाबेस में दो स्टॉप के बीच पथ ढूंढना चाहता हूं।

समस्या यह है कि मुझे इस विषय के बारे में अधिक जानकारी नहीं मिल रही है, उदाहरण के लिए this Wikipedia page में इसमें कोई उपयोगी जानकारी नहीं है।

जो मुझे मिला है वह GTFS प्रारूप है, जो Google Transit में उपयोग किया गया है। जबकि मेरा शहर सार्वजनिक डेटा फीड (यहां तक ​​कि एक निजी भी नहीं) प्रदान नहीं करता है, मेरे पास पहले से ही सभी महत्वपूर्ण जानकारी है कि जीटीएफएस में बदलाव और परिवर्तन करना तुच्छ होगा।

वहाँ

OpenTripPlanner वह भी पैदल यात्री/कार/बाइक OpenStreetMap का उपयोग कर मार्ग से कर सकते हैं की तरह की तरह, कुछ GTFS आधारित सॉफ्टवेयर है।

हालांकि, रूटिंग कोड अच्छी तरह से प्रलेखित नहीं है (कम से कम मुझे मिला है) और मुझे पूरी चीज़ की आवश्यकता नहीं है।

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

तो, प्रश्न है, स्टॉप, मार्ग और आगमन/प्रस्थान/यात्रा के समय की एक सूची दी गई है, मैं आसानी से रोकने के लिए स्टॉप ए से सबसे तेज़ पथ कैसे ढूंढ सकता हूं?

Answer 1

1. graph के रूप में अपनी समस्या का मॉडल करें। प्रत्येक स्टेशन वर्टेक्स होगा, और प्रत्येक बस/ट्रेन एक एज होगी।
2. एक फ़ंक्शन w:Edges->R बनाएं, जो प्रत्येक किनारे के लिए समय/धन/... इंगित करता है।
3. अब, आपके पास एक सामान्य न्यूनतम पथ समस्या है, जिसे Dijkstra algorithm द्वारा हल किया जा सकता है, जो किसी दिए गए स्रोत से सभी शीर्षकों के लिए न्यूनतम पथ पाता है।

(*) 'कम से कम बदलाव' के लिए, अपने वजन प्रत्येक बढ़त के लिए वास्तव में 1 है, तो आप भी, डिज्कस्ट्रा के बजाय एक BFS या यहाँ तक कि bi-directional BFS चलाकर इस अनुकूलन कर सकते हैं के रूप में मैं इस post में विस्तार से बताया [यह सामाजिक दूरी के लिए समझाया गया है, लेकिन यह वास्तव में वही एल्गोरिदम है]।

---

संपादित
[समय के लिए] ग्राफ आप टिप्पणी [मूल्य और संक्रमण की संख्या के लिए पर उल्लेख किया है, क्या मैं अभी भी लागू होता है जैसा कि ऊपर उल्लेख किया है की गैर स्थिर प्रकृति के एक संपादन के रूप में, इन के बाद से ग्राफ स्थिर हैं], आप distance vector routing algorithm का उपयोग कर सकते हैं, जो वास्तव में गतिशील ग्राफ के लिए काम करने के लिए है, और Bellman Ford algorithm का एक वितरित विविधता है।
एल्गोरिथ्म विचार:

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