सुविधा स्थान की समस्या

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

न्यूनतम सुविधा स्थान

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

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

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

ग्राहकों और साइटों के बीच दूरियों के सेट पर धारणाओं के बिना (विशेष रूप से, यह माने बिना कि दूरियां त्रिकोण असमानता को संतुष्ट करती हैं), समस्या को 'गैर-मीट्रिक सुविधा स्थान' के रूप में जाना जाता है और इसे एक कारक O(log n) के भीतर अनुमानित किया जा सकता है ). सेट कवर समस्या से सन्निकटन-संरक्षण कमी के माध्यम से, यह कारक तंग (टाइट) है।

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

मिनीमैक्स सुविधा स्थान

मिनिमैक्स सुविधा स्थान समस्या एक ऐसे स्थान की तलाश करती है जो साइटों की अधिकतम दूरी को कम करती है, जहां एक बिंदु से साइटों की दूरी बिंदु से उसके निकटतम साइट की दूरी है। एक औपचारिक परिभाषा इस प्रकार है: एक बिंदु सेट P ⊂ ℝ^d दिया गया है, एक बिंदु सेट 'S' ⊂ ℝ^d ख, |'S'| = k, ताकि (अधिकतम) max_p ∈ P(min_q ∈ S(d(p, q)) ) को न्यूनतम किया गया है।

k = 1 के लिए यूक्लिडियन मीट्रिक के स्थिति में, इसे सबसे छोटी संलग्न क्षेत्र समस्या या 1-केंद्र समस्या के रूप में जाना जाता है। इसका अध्ययन कम से कम 1860 के वर्ष का है। अधिक विवरण के लिए सबसे छोटा घेरने वाला वृत्त और सीमा क्षेत्र देखें।

एनपी कठोरता (NP-hard)

यह सिद्ध हो चुका है कि वर्टेक्स के-सेंटर समस्या|के-सेंटर समस्या का सटीक समाधान एनपी कठिन है। त्रुटि छोटी होने पर समस्या का अनुमान भी एनपी कठिन पाया गया। सन्निकटन एल्गोरिथ्म में त्रुटि स्तर को सन्निकटन कारक के रूप में मापा जाता है, जिसे सन्निकटन और इष्टतम के बीच के अनुपात के रूप में परिभाषित किया जाता है। यह सिद्ध हो गया है कि जब सन्निकटन कारक 1.822 (आयाम = 2) से कम है तो के-केंद्र समस्या सन्निकटन एनपी कठिन है। या 2 (आयाम > 2).

एल्गोरिदम

सटीक सॉल्वर

इस समस्या का सटीक समाधान निकालने के लिए एल्गोरिदम उपस्थित हैं। एक सटीक सॉल्वर समय में चलता है $n^{O({\sqrt {k}})}$.

1 + ε सन्निकटन

1+ε सन्निकटन का तात्पर्य सन्निकटन कारक के साथ एक समाधान ढूंढना है जो 1+ε से अधिक न हो। यह सन्निकटन एनपी कठिन है क्योंकि ε इच्छानुकूल है। कोर सेट अवधारणा पर आधारित एक दृष्टिकोण निष्पादन जटिलता के साथ प्रस्तावित है $O(2^{O(k\log k/\varepsilon ^{2})}dn)$. विकल्प के रूप में, कोर सेट पर आधारित एक अन्य एल्गोरिदम भी उपलब्ध है। यह अंदर चलता है $O(k^{n})$. लेखक का दावा है कि चलने का समय सबसे खराब स्थिति से बहुत कम है और इस प्रकार k छोटा होने पर कुछ समस्याओं को हल करना संभव है (कहें k <5)।

'सबसे दूर बिंदु क्लस्टरिंग'

समस्या की कठोरता के लिए, सटीक समाधान या सटीक अनुमान प्राप्त करना अव्यावहारिक है। इसके बजाय, बड़े k मामलों के लिए कारक = 2 ​​के साथ एक सन्निकटन का व्यापक रूप से उपयोग किया जाता है। सन्निकटन को सबसे दूर-बिंदु क्लस्टरिंग (फार्थेस्ट -पॉइंट) (एफपीसी) एल्गोरिदम, या सबसे दूर-पहले ट्रैवर्सल के रूप में जाना जाता है।एल्गोरिथ्म काफी सरल है: सेट से किसी भी बिंदु को एक केंद्र के रूप में चुनें; किसी अन्य केंद्र के रूप में शेष सेट से सबसे दूर बिंदु की खोज करें; प्रक्रिया को तब तक दोहराएँ जब तक कि k केंद्र न मिल जाएँ।

यह देखना आसान है कि यह एल्गोरिदम रैखिक समय में चलता है। चूंकि 2 से कम कारक के साथ सन्निकटन एनपी कठिन साबित हुआ है, एफपीसी को सबसे अच्छा सन्निकटन माना जाता था जिसे कोई भी पा सकता है।

निष्पादन के प्रदर्शन के अनुसार, समय जटिलता को बाद में बॉक्स अपघटन तकनीक के साथ ओ n log k) में सुधार किया गया है।

मैक्समिन सुविधा स्थान

मैक्समिन (अधिकतम) सुविधा स्थान या अप्रिय सुविधा स्थान समस्या एक ऐसे स्थान की तलाश करती है जो साइटों से न्यूनतम दूरी को अधिकतम कर दे। यूक्लिडियन मीट्रिक के स्थिति में, इसे सबसे बड़ी खाली क्षेत्र समस्या के रूप में जाना जाता है। समतलीय मामला (सबसे बड़ी खाली वृत्त समस्या) को समय जटिलता Θ(n log n) में हल किया जा सकता है।

पूर्णांक (इंटीजर) प्रोग्रामिंग फॉर्मूलेशन

सुविधा स्थान की समस्याओं को प्रायः इंटीजर प्रोग्रामिंग के रूप में हल किया जाता है। इस संदर्भ में, सुविधा स्थान की समस्याएं प्रायः इस प्रकार सामने आती हैं: मान लीजिए कि हैं $n$ सुविधाएं और $m$ ग्राहक. हम इनमें से (1) किसे चुनना चाहते हैं $n$ खोलने के लिए सुविधाएं, और (2) आपूर्ति के लिए कौन सी (खुली) सुविधाओं का उपयोग करना है $m$ ग्राहकों को, न्यूनतम लागत पर कुछ निश्चित मांग को पूरा करने के लिए। हम निम्नलिखित संकेतन प्रस्तुत करते हैं: मान लीजिए कि $f_{i}$ सुविधा खोलने की (निश्चित) लागत को निरूपित करें $i$, के लिए $i=1,\dots ,n$. होने देना $c_{ij}$किसी उत्पाद को सुविधा से शिप करने की लागत को दर्शाता है $i$ ग्राहक को $j$ के लिए $i=1,\dots ,n$ और $j=1,\dots ,m$. मान लीजिए कि $d_{j}$ ग्राहक की मांग को निरूपित करें $j$ के लिए $j=1,\dots ,m$. इसके अलावा मान लीजिए कि प्रत्येक सुविधा का अधिकतम आउटपुट है। मान लीजिए कि $u_{i}$ सुविधा द्वारा उत्पादित किए जा सकने वाले उत्पाद की अधिकतम मात्रा को निरूपित करें $i$, अर्थात् मान लीजिए कि $u_{i}$ सुविधा की क्षमता को निरूपित करें $i$. इस खंड का शेष भाग इस प्रकार है

क्षमतायुक्त सुविधा स्थान

हमारे प्रारंभिक सूत्रीकरण में, एक बाइनरी वैरिएबल का परिचय दें $x_{i}$ के लिए $i=1,\dots ,n$, जहाँ $x_{i}=1$ यदि सुविधा $i$ खुला है, और $x_{i}=0$ अन्यथा। आगे वेरिएबल का परिचय दें $y_{ij}$ के लिए $i=1,\dots ,n$ और $j=1,\dots ,m$ जो मांग के अंश को दर्शाता है $d_{j}$ सुविधा द्वारा भरा गया $i$. तथाकथित कैपेसिटेटेड सुविधा स्थान समस्या तब दी जाती है

$${\begin{array}{rl}\min &\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{m}c_{ij}d_{j}y_{ij}+\sum _{i=1}^{n}f_{i}x_{i}\\{\text{s.t.}}&\displaystyle \sum _{i=1}^{n}y_{ij}=1{\text{ for all }}j=1,\dots ,m\\&\displaystyle \sum _{j=1}^{m}d_{j}y_{ij}\leqslant u_{i}x_{i}{\text{ for all }}i=1\dots ,n\\&y_{ij}\geqslant 0{\text{ for all }}i=1,\dots ,n{\text{ and }}j=1,\dots ,m\\&x_{i}\in \{0,1\}{\text{ for all }}i=1,\dots ,n\end{array}}$$

ध्यान दें कि बाधाओं का दूसरा सेट यह सुनिश्चित करता है कि यदि $x_{i}=0$, यानी सुविधा $i$ तो फिर, खुला नहीं है $y_{ij}=0$ सभी के लिए $j$यानी सुविधा से किसी भी ग्राहक की कोई डिमांड नहीं भरी जा सकेगी $i$.

अनकैपेसिटीड सुविधा स्थान की समस्या

उपरोक्त कैपेसिटेटेड सुविधा स्थान समस्या का एक सामान्य मामला तब होता है जब $u_{i}=+\infty$ सभी के लिए $i=1,\dots ,n$. इस स्थिति में, ग्राहक की सभी मांगों को पूरा करना हमेशा इष्टतम होता है $j$ निकटतम खुली सुविधा से. इस वजह से, हम सतत चरों को प्रतिस्थापित कर सकते हैं $y_{ij}$ ऊपर से बाइनरी डेटा के साथ $z_{ij}$, जहाँ $z_{ij}=1$ यदि ग्राहक $j$ सुविधा द्वारा आपूर्ति की जाती है $i$, और $z_{ij}=0$ अन्यथा। अनकैपेसिटीड सुविधा स्थान की समस्या तब दी जाती है

$${\begin{array}{rl}\min &\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{m}c_{ij}d_{j}z_{ij}+\sum _{i=1}^{n}f_{i}x_{i}\\{\text{s.t.}}&\displaystyle \sum _{i=1}^{n}z_{ij}=1{\text{ for all }}j=1,\dots ,m\\&\displaystyle \sum _{j=1}^{m}z_{ij}\leqslant Mx_{i}{\text{ for all }}i=1\dots ,n\\&z_{ij}\in \{0,1\}{\text{ for all }}i=1,\dots ,n{\text{ and }}j=1,\dots ,m\\&x_{i}\in \{0,1\}{\text{ for all }}i=1,\dots ,n\end{array}}$$

जहाँ $M$ उपयुक्त रूप से बड़े होने के लिए चुना गया एक स्थिरांक है। का चुनाव $M$ गणना परिणामों को प्रभावित कर सकता है - इस उदाहरण में सबसे अच्छा विकल्प स्पष्ट है: लेना $M=m$. तो अगर $x_{i}=1$, का कोई भी विकल्प $z_{ij}$ बाधाओं के दूसरे सेट को संतुष्ट करेगा।

अप्रतिबंधित सुविधा स्थान समस्या के लिए एक अन्य सूत्रीकरण संभावना क्षमता बाधाओ को अलग करना है (बड़ा-$M$ प्रतिबंध)। यानी बाधाओं को बदलें है

$$\sum _{j=1}^{m}z_{ij}\leqslant Mx_{i}{\text{ for all }}i=1,\dots ,n$$

बाधाओं के साथ

$$z_{ij}\leqslant x_{i}{\text{ for all }}i=1,\dots ,n{\text{ and }}j=1,\dots ,m$$

व्यवहार में, यह नया फॉर्मूलेशन काफी बेहतर प्रदर्शन करता है, इस अर्थ में कि इसमें पहले फॉर्मूलेशन की तुलना में अधिक सख्त रैखिक प्रोग्रामिंग छूट है।ध्यान दें कि नई बाधाओं को एक साथ जोड़ने पर मूल बड़ा परिणाम प्राप्त होता है-$M$ प्रतिबंध। कैपेसिटेटेड स्थिति में, ये फॉर्मूलेशन समकक्ष नहीं हैं। असंबद्ध सुविधा स्थान समस्या के बारे में अधिक जानकारी ''असतत स्थान सिद्धांत'' के अध्याय 3 में पाई जा सकती है।

अनुप्रयोग

स्वास्थ्य देखभाल

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

ठोस अपशिष्ट प्रबंधन

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

क्लस्टरिंग

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

यह देखने के लिए कि कोई सेंट्रोइड-आधारित क्लस्टरिंग समस्या को (मीट्रिक) सुविधा स्थान समस्या के रूप में कैसे देख सकता है (परिवर्तन या कम करें पढ़ें), पूर्व में प्रत्येक डेटा बिंदु को बाद में मांग बिंदु (डिमांड पॉइंट) के रूप में देखें। मान लीजिए कि क्लस्टर किया जाने वाला डेटा मीट्रिक स्पेस के तत्व हैं $M$ (उदा. मान लीजिए कि $M$ होना $p$कुछ निश्चित के लिए -आयामी यूक्लिडियन स्थान $p$). हम जिस सुविधा स्थान की समस्या का निर्माण कर रहे हैं, उसमें हम सुविधाओं को इस मीट्रिक स्थान के भीतर किसी भी बिंदु पर रखने की अनुमति देते हैं $M$; यह अनुमत सुविधा स्थानों के सेट को परिभाषित करता है $L$. हम लागतों को परिभाषित करते हैं $c_{\ell ,d}$ स्थान-मांग बिंदु जोड़े के बीच जोड़ीवार दूरी होना (उदाहरण के लिए, मीट्रिक के-केंद्र देखें)। सेंट्रोइड-आधारित क्लस्टरिंग समस्या में, डेटा को विभाजित किया जाता है $k$ समतुल्य वर्ग (अर्थात रंग) जिनमें से प्रत्येक में एक केन्द्रक होता है। आइए देखें कि हमारी निर्मित सुविधा स्थान समस्या का समाधान भी इस तरह के विभाजन को कैसे प्राप्त करता है। एक व्यवहार्य समाधान एक गैर-रिक्त उपसमुच्चय है $L'\subseteq L$ का $k$ स्थान. हमारी सुविधा स्थान समस्या में इन स्थानों का एक सेट सम्मिलित है $k$ हमारी सेंट्रोइड-आधारित क्लस्टरिंग समस्या में सेंट्रोइड्स। अब, प्रत्येक मांग बिंदु निर्दिष्ट करें $d$ स्थान के लिए $\ell ^{*}$ जो इसकी सर्विसिंग-लागत को कम करता है; अर्थात्, डेटा बिंदु निर्दिष्ट करें $d$ केन्द्रक को $\ell ^{*}:=\mathrm {arg\,min} _{\ell \in L}\{c_{\ell ,d}\}$ (मनमाने ढंग से संबंध तोड़ें)। यह विभाजन को प्राप्त करता है बशर्ते कि सुविधा स्थान की समस्या की लागत हो $c_{\ell ,d}$ परिभाषित किया गया है कि वे सेंट्रोइड-आधारित क्लस्टरिंग समस्या के दूरी फ़ंक्शन की छवियां हैं।

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

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

यह भी देखें

• ग्राफ़ केंद्र
• द्विघात असाइनमेंट समस्या
• स्थान-आवंटन
• डिज्क्स्ट्रा का एल्गोरिदम
• स्थानिक विश्लेषण सॉफ़्टवेयर की सूची
• प्रतिस्पर्धी सुविधा स्थान खेल
• वर्टेक्स के-सेंटर समस्या
• ज्यामितीय माध्यिका

बाहरी संबंध

• EWGLA EURO Working Group on Locational Analysis.
• INFORMS section on location analysis, a professional society concerned with facility location.
• Bibliography on facility location collected by Trevor Hale, containing over 3400 articles.
• Library of location algorithms
• Web-based facility location utility (single facility)
• Facility Location Optimizer, a MATLAB-based tool for solving facility location problems.