रसद। परिचय बस जटिल के बारे में

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

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

इसी तरह के मामलों की घटना सीधे संचार की कमी या पूर्व-नियोजित संयुक्त (कनेक्टिंग) मार्गों से जुड़ी होती है, या स्थानान्तरण वाले मार्गों को प्रस्तावित किया गया था जिसमें अगली उड़ान के लिए 5-6 घंटे से अधिक या पूरे दिन के लिए प्रतीक्षा समय शामिल था।

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


विश्व हवाई अड्डे का नक्शा

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

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

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

• न्यूनतम यात्रा समय;
• प्रत्यारोपण की न्यूनतम (या पर्याप्त भाषा में);
• जटिल मार्गों को चुनते समय एक उड़ान से दूसरी उड़ान में स्थानांतरण के लिए समय अंतराल।

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

लेकिन, जैसा कि सभी जानते हैं, एक परिकल्पना का परीक्षण करने के लिए, कई अन्य को उद्धृत किया जाना चाहिए। समस्या को हल करने के लिए एक अन्य विकल्प के रूप में, नॉनलाइनियर प्रोग्रामिंग के उपयोग पर विचार किया गया था।

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

समस्या को हल करने के लिए विकल्पों का विश्लेषण करने के बाद, मैं निम्नलिखित भागों के साथ अपघटन के क्लासिक संस्करण के साथ गया:

1. आगमन के बिंदु तक प्रस्थान के बिंदु से सभी "सबसे छोटे" मार्गों की अनुसूची के आधार पर खोज;
2. मानदंडों के आधार पर सबसे "इष्टतम" के "सबसे छोटे" रास्तों के बीच खोजें।

उसी समय, अपघटन के बाद, प्रश्न का तार्किक रूप से पालन किया गया, लेकिन परिवहन नेटवर्क के निर्माण के लिए किस दृष्टिकोण के आधार पर बेहतर है? और इस समस्या को हल करने के लिए उपलब्ध ग्राफ़ में से कौन सा अधिक स्वीकार्य है?

शैली के क्लासिक्स के अनुसार, कोई भी नहीं मिला था, लेकिन कई मॉडल, जिन्हें मैंने विचार करना शुरू किया था।

समय विस्तारित मॉडल

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



को दर्शाते हैं : आर्क के रूप में संकेत दिए गए हैं$$ । उदाहरण के लिए, एक चाप एक हवाई अड्डे को जोड़ता है$e_{BC,3}$$$हवाई अड्डे के साथ बी$B$$$ और से भेजा गया$$C$$$$ को$B$$$ , अल्पविराम अलग सूचकांक$C$$$ पता चलता है कि यह एकमात्र उड़ान नहीं है, बल्कि लगातार तीसरी है। इसके अलावा, प्रत्येक चाप को आसानी से भारित किया जा सकता है, उदाहरण के लिए, चाप का वजन$3$$$ रूप में गणना की जा सकती है$e_{BC,3}$$$ । प्रत्येक हवाई अड्डे के अंदर संकेतक के समय संकेतक के अनुसार एक हवाई अड्डे के अंदर आसानी से व्यवस्था की जाती है, और यह भी कि हवाई अड्डे के अंदर कनेक्टिंग समय के आधार पर, उड़ानें आर्क्स द्वारा जुड़ी होती हैं जो एक उड़ान से दूसरी उड़ान के उपलब्ध समय के अनुरूप होती हैं।$w_{BC,3} = t_{C,9}-t_{B,6}$

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

समय पर निर्भर मॉडल

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



समय-निर्भर ग्राफ़ का लाभ यह है कि यह आपको कम से कम स्थानान्तरण के साथ पथ खोजने की अनुमति देता है, नुकसान प्रत्येक चाप के डेटा पर अत्यधिक भार है।

Multigraph

मल्टीग्राफ एक निर्देशित ग्राफ़ है जिसमें समय-संवर्धित और समय-निर्भर मॉडल में निहित विशेषताओं के सेट होते हैं।



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

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

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

एक और अधिक उदाहरण के रूप में, हम एल्गोरिथ्म के संचालन को एक छोटे ग्राफ पर मानते हैं, जिसका आर्क्स दो-आयामी वैक्टर द्वारा भारित किया जाता है:



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

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



इस तरह के एक मॉडल में संशोधित डायजेस्ट्रा एल्गोरिदम का उपयोग अनुमेय है, क्योंकि यह मल्टीग्राफ पर काम कर सकता है, लेकिन एल्गोरिथ्म प्रसंस्करण की गति कोने की संख्या पर निर्भर करती है$$ , और आर्क्स की संख्या$n$$$ । विरल सरल रेखांकन और सामान्य एल्गोरिथ्म के लिए, जटिलता के क्रम का है$m$$$ । हालांकि, यह कहना मुश्किल है कि क्या परिणामी मल्टीग्राफ "विरल" होगा, क्योंकि सामान्य मामले में मल्टीग्राफ के किनारे का घनत्व पूर्ण ग्राफ़ की तुलना में बहुत अधिक हो सकता है। अगर हम इस बात को ध्यान में रखते हैं कि एक पूर्ण ग्राफ के किनारों की संख्या$O(n\log n+m\log n)$$$ उसके कोने की संख्या के माध्यम से निर्धारित किया जाता है$E$$$सूत्र द्वारा V :$V$

$$एक रिब घनत्व के रूप में परिभाषित किया गया है:$E={\frac {V(V-1)}{2}}$



$$पूर्ण रेखांकन के लिए$D={\frac {2E}{V\,(V-1)}}$

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

$$। यह देखते हुए कि यह लेख कार्यान्वयन के तात्कालिक परिणामों को कवर नहीं करता है, मैं पहले से मान सकता हूं कि मल्टीग्राफ मॉडल पर संशोधित डायजेस्ट्रा एल्गोरिदम इष्टतम समय अंतराल को ध्यान में रखते हुए काम नहीं करेगा। इसलिए, मैं मल्टीक्रिटेरिया ऑप्टिमाइज़ेशन से संबंधित प्रश्न के समाधान के लिए, पहले उपप्रोक्लेम के तत्काल समाधान पर आगे बढ़ूंगा, जिसे मैंने सशर्त अनुकूलन की विधि द्वारा चुना था। इस विधि में यह तथ्य है कि मानदंड की असंगति के बावजूद, सर्वोच्च प्राथमिकता हमेशा मौजूद होती है, और अन्य सभी में मान्य मूल्य होते हैं। परिणामस्वरूप, पूरे कार्य का अनुकूलन सर्वोच्च प्राथमिकता पर अनुकूलन के लिए नीचे आता है।$O(n^{2})$







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



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

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

हालांकि, सवाल बना हुआ है, और कनेक्शन और स्थानांतरण के साथ कौन से "सबसे छोटे" मार्ग मार्ग सबसे "कम" हैं? अन्यथा, हमारे पास एक सरणी डेटा है जो हमें निर्णय लेने की अनुमति नहीं देगा। मापदंड का एक सेट अक्सर इस मामले में सबसे इष्टतम के लिए कम हो जाता है, अर्थात्:

• न्यूनतम यात्रा समय;
• स्थानान्तरण की न्यूनतम संख्या।

दोनों मानदंडों में अनुकूलन योग्य अंतराल या समय मान हो सकते हैं, इसलिए यह केवल अनुमेय मानों के अनुपालन के लिए मार्गों और "मक्खी पर" गठबंधन करने के लिए रहता है:



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

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

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

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

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

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

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

आराम

"आराम" की अवधारणा का अर्थ हर कोई अलग-अलग तरीके से समझता है, लेकिन निम्नलिखित स्तर एयरलाइनों द्वारा स्वीकार किए जाते हैं:

• प्रथम श्रेणी;
• बिजनेस क्लास;
• किफायती वर्ग।

मेरे दृष्टिकोण में, मैंने स्वीकार किया कि "आराम" पैरामीटर को मापा जा सकता है और 1 से 10 तक मान ले सकते हैं, और निम्न स्थिति का गठन कर सकते हैं: किसी विशेष उड़ान के लिए यह संकेतक जितना कम होगा, यह रैंकिंग प्रणाली में उतना ही कम आरामदायक होगा। इस मामले में, एक समस्या तुरंत उठती है जो इस तरह की मात्रा के गैर-व्यसनीकरण से संबंधित है, अर्थात। दो उड़ानों के आराम संकेतक का योग उनके समग्र आराम को प्रतिबिंबित नहीं करेगा। उदाहरण के लिए, दो मार्ग संयोजन हैं:

• दो खंडों के साथ पहला मार्ग, आराम 10 के साथ पहला छापा, दूसरा आराम 1 के साथ;
• दो खंडों के साथ दूसरा मार्ग, 6 आराम के साथ पहला छापा, दूसरा 5 आराम के साथ।

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

स्थानान्तरण की अवधि

दो प्रकार के मार्ग समन्वय हैं:

• स्थानान्तरण (एयरलाइंस के बीच पूर्व सहमति);
• डॉकिंग।

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

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

हवाई अड्डे की

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

स्थानान्तरण की संख्या

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

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

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

वैश्विक लक्ष्य की पदानुक्रमित संरचना

मान लीजिए कि "इष्टतमता" की परिभाषा को हमेशा और सभी के लिए सबसे अच्छा समझा जाना चाहिए, और न केवल यात्रियों के लिए, बल्कि एयरलाइंस, हवाई अड्डों और, संभवतः, अन्य यात्रा सेवा प्रदाताओं के लिए भी।

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



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

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

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

सभी पेरेटो और स्लाटर इष्टतमता समाधानों को आसानी से दो मानदंडों के साथ कम से कम समस्या के लिए ग्राफिकल रूप से प्रदर्शित किया जा सकता है:



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

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