Optimal facility location
सुविधा स्थान समस्याओं (एफएलपी) का अध्ययन, जिसे स्थान विश्लेषण के रूप में भी जाना जाता है, संचालन अनुसंधान और कम्प्यूटेशनल ज्यामिति की एक शाखा है जो आवास और प्रतियोगियों की सुविधाओं के पास खतरनाक सामग्री रखने से बचने जैसे कारकों पर विचार करते हुए परिवहन लागत को कम करने के लिए सुविधाओं के इष्टतम स्थान से संबंधित है। तकनीक समूह विश्लेषण पर भी लागू होती है। न्यूनतम सुविधा स्थान एक सरल सुविधा स्थान समस्या वेबर समस्या है, जिसमें एक ही सुविधा रखी जानी है, जिसमें एकमात्र अनुकूलन मानदंड बिंदु स्थलों के दिए गए सेट से दूरी के भारित योग का न्यूनतम होना है। इस विषय में विचार की जाने वाली अधिक जटिल समस्याओं में कई सुविधाओं का नियोजन, सुविधाओं के स्थानों पर बाधाएं और अधिक जटिल अनुकूलन मानदंड शामिल हैं। एक बुनियादी सूत्रीकरण में, सुविधा स्थान समस्या में संभावित सुविधा स्थलों एल का एक सेट होता है जहां एक सुविधा खोली जा सकती है, और मांग बिंदुओं डी का एक सेट होता है जिसे सेवा प्रदान की जानी चाहिए। प्रत्येक मांग बिंदु से इसकी निकटतम सुविधा तक की दूरी के योग को कम करने के साथ-साथ सुविधाओं की उद्घाटन लागत के योग को कम करने के लिए, खोलने के लिए सुविधाओं का एक उपसमुच्चय एफ चुनना लक्ष्य है। सामान्य ग्राफ पर सुविधा स्थान समस्या एन. पी.-सेट कवर समस्या (उदाहरण के लिए) से कम करके, इष्टतम रूप से हल करने के लिए कठिन है। सुविधा स्थान समस्या और इसके कई रूपों के लिए कई सन्निकटन एल्गोरिदम विकसित किए गए हैं। ग्राहकों और स्थलों के बीच दूरी के सेट पर धारणाओं के बिना (विशेष रूप से, यह माने बिना कि दूरी त्रिभुज असमानता को संतुष्ट करती है), समस्या को गैर-मीट्रिक सुविधा स्थान के रूप में जाना जाता है और एक कारक ओ (लॉग एन) के भीतर अनुमानित किया जा सकता है। सेट कवर समस्या से अनुमानित-संरक्षण कमी के माध्यम से यह कारक तंग है। यदि हम मानते हैं कि ग्राहकों और साइटों के बीच की दूरी दिशाहीन है और त्रिभुज असमानता को संतुष्ट करती है, तो हम एक मीट्रिक सुविधा स्थान (एम. एफ. एल.) समस्या के बारे में बात कर रहे हैं। एम. एफ. एल. अभी भी एन. पी.-कठोर है और 1.463 से बेहतर कारक के भीतर अनुमानित करना कठिन है। वर्तमान में सबसे प्रसिद्ध सन्निकटन एल्गोरिथ्म 1.488 के सन्निकटन अनुपात को प्राप्त करता है। मिनीमैक्स सुविधा स्थान समस्या एक ऐसे स्थान की तलाश करती है जो साइटों के लिए अधिकतम दूरी को कम करता है, जहां एक बिंदु से साइटों तक की दूरी बिंदु से उसके निकटतम स्थल तक की दूरी है। एक औपचारिक परिभाषा इस प्रकार हैः एक बिंदु समुच्चय पी आर डी को देखते हुए, एक बिंदु समुच्चय एस आर डी, |S। = के ज्ञात करें, ताकि अधिकतम पी (मिनक एस (डी (पी, क्यू))) को न्यूनतम किया जा सके। के = 1 के लिए यूक्लिडियन मीट्रिक के मामले में, इसे सबसे छोटी घेरने वाली गोल समस्या या 1-केंद्र समस्या के रूप में जाना जाता है। इसके अध्ययन का पता कम से कम 1860 के वर्ष में लगाया गया है. अधिक जानकारी के लिए सबसे छोटा घेरने वाला वृत्त और सीमा क्षेत्र देखें। एन. पी. कठोरता यह सिद्ध हो चुका है कि के-सेंटर समस्या का सटीक समाधान एन. पी. हार्ड है। त्रुटि कम होने पर समस्या का सन्निकटन भी एन. पी. कठिन पाया गया। सन्निकटन एल्गोरिथ्म में त्रुटि स्तर को एक सन्निकटन कारक के रूप में मापा जाता है, जिसे सन्निकटन और इष्टतम के बीच के अनुपात के रूप में परिभाषित किया जाता है। यह साबित हो गया है कि के-केंद्र समस्या सन्निकटन एन. पी. कठिन है जब सन्निकटन कारक 1.822 (आयाम = 2) या 2 (आयाम> 2) से कम होता है। एल्गोरिदम सटीक समाधानकर्ता इस समस्या के सटीक समाधान का उत्पादन करने के लिए एल्गोरिदम मौजूद हैं। एक सटीक समाधानकर्ता समय पर चलता है। 1 + ε सन्निकटन 1 + ε सन्निकटन 1 + ε से अधिक सन्निकटन कारक के साथ एक समाधान खोजना है। यह सन्निकटन एन. पी. कठिन है क्योंकि ε मनमाना है। कोरसेट अवधारणा पर आधारित एक दृष्टिकोण को निष्पादन जटिलता के साथ प्रस्तावित किया गया है। एक विकल्प के रूप में, कोर सेट पर आधारित एक और एल्गोरिथ्म भी उपलब्ध है। वह अंदर घुस जाता है। लेखक का दावा है कि चलने का समय सबसे खराब स्थिति की तुलना में बहुत कम है और इस प्रकार कुछ समस्याओं को हल करना संभव है जब के छोटा हो (जैसे के <5)। समस्या की कठोरता के लिए, एक सटीक समाधान या सटीक अनुमान प्राप्त करना अव्यावहारिक है। इसके बजाय, कारक = 2 के साथ एक सन्निकटन का व्यापक रूप से बड़े k मामलों के लिए उपयोग किया जाता है। सन्निकटन को सबसे दूर-बिंदु क्लस्टरिंग (एफ. पी. सी.) एल्गोरिथ्म, या सबसे दूर-प्रथम पारगमन के रूप में संदर्भित किया जाता है। एल्गोरिथ्म काफी सरल हैः सेट से किसी भी बिंदु को एक केंद्र के रूप में चुनें; दूसरे केंद्र के रूप में शेष सेट से सबसे दूर के बिंदु की खोज करें; प्रक्रिया को तब तक दोहराएं जब तक कि के केंद्र नहीं मिल जाते। यह देखना आसान है कि यह एल्गोरिथ्म रैखिक समय में चलता है। चूंकि 2 से कम कारक के साथ सन्निकटन एन. पी. हार्ड साबित होता है, इसलिए एफ. पी. सी. को सबसे अच्छा सन्निकटन माना जाता था। निष्पादन के प्रदर्शन के अनुसार, समय जटिलता को बाद में बॉक्स अपघटन तकनीक के साथ ओ (एन लॉग के) में सुधार किया जाता है। अधिकतम सुविधा स्थान अधिकतम सुविधा स्थान या अप्रिय सुविधा स्थान समस्या एक ऐसे स्थान की तलाश करती है जो साइटों के लिए न्यूनतम दूरी को अधिकतम करता है। यूक्लिडियन मीट्रिक के मामले में, इसे सबसे बड़ी खाली गोले की समस्या के रूप में जाना जाता है। समतलीय मामले (सबसे बड़ी खाली वृत्त समस्या) को इष्टतम समय में हल किया जा सकता है (एन लॉग एन)। पूर्णांक प्रोग्रामिंग सूत्रीकरण सुविधा स्थान समस्याओं को अक्सर पूर्णांक कार्यक्रमों के रूप में हल किया जाता है। इस संदर्भ में, सुविधा स्थान की समस्याओं को अक्सर निम्नानुसार प्रस्तुत किया जाता हैः मान लीजिए कि सुविधाएं और ग्राहक हैं। हम न्यूनतम लागत पर कुछ निश्चित मांग को पूरा करने के लिए (1) किन सुविधाओं को खोलना है और (2) ग्राहकों को आपूर्ति करने के लिए किन (खुली) सुविधाओं का उपयोग करना है, यह चुनना चाहते हैं। हम निम्नलिखित संकेतन प्रस्तुत करते हैंः के लिए, खोलने की सुविधा की (निश्चित) लागत को दर्शाते हैं। आइए किसी उत्पाद को सुविधा से ग्राहक को और के लिए भेजने की लागत को दर्शाते हैं। ग्राहक की मांग को दर्शाते हैं। इसके अलावा मान लीजिए कि प्रत्येक सुविधा का अधिकतम उत्पादन होता है। आइए उत्पाद की अधिकतम मात्रा को दर्शाते हैं जिसे सुविधा द्वारा उत्पादित किया जा सकता है, यानी सुविधा की क्षमता को दर्शाते हैं। इस खंड का शेष भाग कैपेसिटेड सुविधा स्थान का अनुसरण करता है हमारे प्रारंभिक सूत्रीकरण में, एक द्विआधारी चर का परिचय दें, जहां सुविधा खुली है, और अन्यथा। इसके अलावा और के लिए चर का परिचय दें जो सुविधा द्वारा भरी गई मांग के अंश का प्रतिनिधित्व करता है। तथाकथित कैपेसिटेड सुविधा स्थान समस्या तब नोट द्वारा दी जाती है कि बाधाओं का दूसरा सेट यह सुनिश्चित करता है कि यदि, यानी, सुविधा खुली नहीं है, तो सभी के लिए, यानी किसी भी ग्राहक की कोई मांग सुविधा से पूरी नहीं की जा सकती है। ऊपर दिए गए कैपेसिटेड सुविधा स्थान समस्या का एक सामान्य मामला सभी के लिए होता है। इस मामले में, निकटतम खुली सुविधा से ग्राहक की सभी मांगों को पूरा करना हमेशा इष्टतम होता है। इस वजह से, हम ऊपर से निरंतर चर को द्विआधारी चर के साथ बदल सकते हैं, जहां यदि ग्राहक को सुविधा द्वारा आपूर्ति की जाती है, और अन्यथा। असंबद्ध सुविधा स्थान समस्या तब दी जाती है जहाँ एक स्थिरांक उपयुक्त रूप से बड़ा होने के लिए चुना जाता है। का चयन गणना परिणामों को प्रभावित कर सकता है-इस उदाहरण में सबसे अच्छा विकल्प स्पष्ट हैः लें। फिर, यदि, का कोई भी विकल्प बाधाओं के दूसरे समूह को संतुष्ट करेगा। असंबद्ध सुविधा स्थान समस्या के लिए एक और सूत्रीकरण संभावना क्षमता बाधाओं (बड़ी-बाधाओं) को अलग करना है। अर्थात्, बाधाओं को बाधाओं के साथ बदलें व्यवहार में, यह नया सूत्रीकरण काफी बेहतर प्रदर्शन करता है, इस अर्थ में कि इसमें पहले सूत्रीकरण की तुलना में एक सख्त रैखिक प्रोग्रामिंग छूट है। ध्यान दें कि नई बाधाओं को एक साथ जोड़कर मूल बड़ी बाधाएं उत्पन्न होती हैं। कैपेसिटेटेड मामले में, ये फॉर्मूलेशन समतुल्य नहीं हैं। असंबद्ध सुविधा स्थान समस्या के बारे में अधिक जानकारी "असतत स्थान सिद्धांत" के अध्याय 3 में पाई जा सकती है। अनुप्रयोग स्वास्थ्य सेवा स्वास्थ्य सेवा में, गलत सुविधा स्थान निर्णयों का सरल लागत और सेवा मेट्रिक्स से परे समुदाय पर गंभीर प्रभाव पड़ता है; उदाहरण के लिए, स्वास्थ्य सुविधाओं तक पहुंच मुश्किल होने से रुग्णता और मृत्यु दर में वृद्धि होने की संभावना है। इस दृष्टिकोण से, स्वास्थ्य सेवा के लिए सुविधा स्थान मॉडलिंग अन्य क्षेत्रों के लिए समान मॉडलिंग की तुलना में अधिक महत्वपूर्ण है। बढ़ते अपशिष्ट उत्पादन और अपशिष्ट प्रबंधन से जुड़ी उच्च लागतों के कारण शहरी ठोस अपशिष्ट प्रबंधन अभी भी विकासशील देशों के लिए एक चुनौती बना हुआ है। एक सुविधा स्थान समस्या के निर्माण और सटीक समाधान के माध्यम से अपशिष्ट निपटान के लिए लैंडफिल के स्थान को अनुकूलित करना संभव है। समूह विश्लेषण समस्याओं के एक विशेष उपसमुच्चय को सुविधा स्थान समस्याओं के रूप में देखा जा सकता है। एक केंद्रक-आधारित क्लस्टरिंग समस्या में, उद्देश्य डेटा बिंदुओं (एक सामान्य मीट्रिक स्थान के तत्वों) को समतुल्य वर्गों में विभाजित करना है-जिन्हें अक्सर रंग कहा जाता है-जैसे कि एक ही रंग के बिंदु एक दूसरे के करीब हों (समान रूप से, जैसे कि विभिन्न रंगों के बिंदु एक दूसरे से दूर हों)। यह देखने के लिए कि कोई केंद्रक-आधारित क्लस्टरिंग समस्या को (मीट्रिक) सुविधा स्थान समस्या के रूप में कैसे देख सकता है ("परिवर्तन" या "कम" पढ़ें), प्रत्येक डेटा बिंदु को पूर्व में बाद वाले में एक मांग बिंदु के रूप में देखें। मान लीजिए कि क्लस्टर किए जाने वाले डेटा एक मीट्रिक स्थान के तत्व हैं (जैसे। कुछ निश्चित के लिए-आयामी यूक्लिडियन स्थान होने दें)। जिस सुविधा स्थान समस्या का हम निर्माण कर रहे हैं, हम इस मीट्रिक स्थान के भीतर किसी भी बिंदु पर सुविधाओं को रखने की अनुमति देते हैं; यह अनुमत सुविधा स्थानों के समूह को परिभाषित करता है। हम लागत को स्थान-मांग बिंदु जोड़े के बीच जोड़ीदार दूरी के रूप में परिभाषित करते हैं (उदाहरण के लिए, मीट्रिक के-केंद्र देखें)। एक केंद्रक-आधारित क्लस्टरिंग समस्या में, एक डेटा को समतुल्य वर्गों में विभाजित करता है (अर्थात। रंग) जिनमें से प्रत्येक में एक केंद्रक होता है। आइए देखें कि हमारी निर्मित सुविधा स्थान समस्या का समाधान भी इस तरह के विभाजन को कैसे प्राप्त करता है। एक व्यवहार्य समाधान स्थानों का एक गैर-खाली उपसमुच्चय है। हमारी सुविधा स्थान समस्या में इन स्थानों में हमारी केंद्रक-आधारित क्लस्टरिंग समस्या में केंद्रक का एक समूह शामिल है। अब, प्रत्येक मांग बिंदु को उस स्थान पर निर्धारित करें जो इसकी सर्विसिंग-लागत को कम करता है; यानी, डेटा बिंदु को केंद्रक को निर्दिष्ट करें (मनमाने ढंग से संबंध तोड़ें)। यह विभाजन को प्राप्त करता है बशर्ते कि सुविधा स्थान समस्या की लागतों को इस तरह से परिभाषित किया गया हो कि वे केंद्रक-आधारित क्लस्टरिंग समस्या के दूरी कार्य की छवियां हों। लोकप्रिय एल्गोरिदम पाठ्यपुस्तक एल्गोरिदम डिजाइन एक संबंधित समस्या-विवरण और एक सन्निकटन एल्गोरिदम प्रदान करता है। लेखक मीट्रिक सुविधा स्थान समस्या का उल्लेख करते हैं (अर्थात। केंद्र-आधारित क्लस्टरिंग समस्या या मीट्रिक-केंद्र समस्या) केंद्र चयन समस्या के रूप में, जिससे पर्यायवाची शब्दों की सूची बढ़ती है। इसके अलावा, देखें कि सुविधा स्थान समस्या की हमारी उपरोक्त परिभाषा में कि वस्तुनिष्ठ कार्य सामान्य है। विशिष्ट विकल्प सुविधा स्थान समस्या के विभिन्न रूपों की उपज देते हैं, और इसलिए केंद्रक-आधारित क्लस्टरिंग समस्या के विभिन्न रूप। उदाहरण के लिए, कोई व्यक्ति प्रत्येक स्थान से उसके प्रत्येक निर्धारित मांग बिंदु तक की दूरी के योग को कम करने का विकल्प चुन सकता है (ए ला वेबर समस्या), या कोई व्यक्ति ऐसी सभी दूरी के अधिकतम को कम करने का विकल्प चुन सकता है (ए ला 1-केंद्र समस्या)। ग्राफ सेंटर क्वाड्रैटिक असाइनमेंट प्रॉब्लम लोकेशन-एलोकेशन डिज्क्स्ट्रा के एल्गोरिदम लिस्ट ऑफ स्पेसियल एनालिसिस सॉफ्टवेयर कॉम्पिटिटिव फैसिलिटी लोकेशन गेम वर्टेक्स के-सेंटर प्रॉब्लम ज्यामितीय माध्यिका संदर्भ बाहरी लिंक EWGLA EURO वर्किंग ग्रुप ऑन लोकेशनल एनालिसिस को भी देखें। स्थान विश्लेषण पर सूचना अनुभाग, सुविधा स्थान से संबंधित एक पेशेवर समाज। ट्रेवर हेल द्वारा एकत्र की गई सुविधा स्थान पर ग्रंथ सूची, जिसमें 3400 से अधिक लेख हैं। स्थान एल्गोरिदम का पुस्तकालय वेब-आधारित सुविधा स्थान उपयोगिता (एकल सुविधा) सुविधा स्थान ऑप्टिमाइज़र, सुविधा स्थान समस्याओं को हल करने के लिए एक MATLAB-आधारित उपकरण। ग्राफ सिद्धांत में व्यावसायिक कम्प्यूटेशनल समस्याओं में गणितीय अनुकूलन सुविधा स्थान