Optimal facility location
سہولت کے مقام کے مسائل کا مطالعہ (ایف ایل پی)، جسے مقام کا تجزیہ بھی کہا جاتا ہے، آپریشنز ریسرچ اور کمپیوٹیشنل جیومیٹری کی ایک شاخ ہے جس کا تعلق نقل و حمل کے اخراجات کو کم کرنے کے لیے سہولیات کی زیادہ سے زیادہ تعیناتی سے ہے جبکہ رہائش اور حریفوں کی سہولیات کے قریب خطرناک مواد رکھنے سے بچنے جیسے عوامل پر غور کیا جاتا ہے۔ تکنیکیں کلسٹر تجزیہ پر بھی لاگو ہوتی ہیں۔ کم سے کم سہولت کا مقام ایک سادہ سہولت کے مقام کا مسئلہ ویبر کا مسئلہ ہے، جس میں ایک ہی سہولت رکھی جانی ہے، جس میں اصلاح کا واحد معیار پوائنٹ سائٹس کے دیئے گئے سیٹ سے فاصلے کے وزن کی رقم کو کم کرنا ہے۔ اس شعبے میں زیر غور مزید پیچیدہ مسائل میں متعدد سہولیات کی تعیناتی، سہولیات کے مقامات پر رکاوٹیں، اور زیادہ پیچیدہ اصلاح کے معیار شامل ہیں۔ ایک بنیادی تشکیل میں، سہولت کے مقام کا مسئلہ ممکنہ سہولت سائٹس L کے ایک سیٹ پر مشتمل ہوتا ہے جہاں ایک سہولت کھولی جا سکتی ہے، اور ڈیمانڈ پوائنٹس D کا ایک سیٹ جس کی خدمت کی جانی چاہیے۔ مقصد یہ ہے کہ کھولنے کے لیے سہولیات کا ایک ذیلی سیٹ F منتخب کیا جائے، تاکہ ہر ڈیمانڈ پوائنٹ سے اس کی قریب ترین سہولت تک کے فاصلے کو کم سے کم کیا جا سکے، نیز سہولیات کے افتتاحی اخراجات کا مجموعہ۔ عام گرافوں پر سہولت کے مقام کا مسئلہ (مثال کے طور پر) سیٹ کور کے مسئلے کو کم کرکے، بہتر طریقے سے حل کرنے کے لیے NP-مشکل ہے۔ سہولت کے مقام کے مسئلے اور اس کی بہت سی شکلوں کے لیے متعدد تخمینہ الگورتھم تیار کیے گئے ہیں۔ کلائنٹس اور سائٹس کے درمیان فاصلے کے سیٹ پر مفروضوں کے بغیر (خاص طور پر، یہ فرض کیے بغیر کہ فاصلے مثلث کی عدم مساوات کو پورا کرتے ہیں)، اس مسئلے کو غیر میٹرک سہولت کے مقام کے طور پر جانا جاتا ہے اور اس کا تخمینہ عنصر O (لاگ n) کے اندر لگایا جا سکتا ہے۔ سیٹ کور کے مسئلے سے تخمینی تحفظ میں کمی کے ذریعے یہ عنصر سخت ہے۔ اگر ہم یہ فرض کرتے ہیں کہ کلائنٹس اور سائٹس کے درمیان فاصلے غیر ہدایت شدہ ہیں اور مثلث کی عدم مساوات کو پورا کرتے ہیں، تو ہم میٹرک فیسلٹی لوکیشن (ایم ایف ایل) کے مسئلے کے بارے میں بات کر رہے ہیں۔ ایم ایف ایل اب بھی این پی سخت ہے اور 1.463 سے بہتر عنصر کے اندر تخمینہ لگانا مشکل ہے۔ فی الحال سب سے مشہور تخمینہ الگورتھم 1.488 کا تخمینہ تناسب حاصل کرتا ہے۔ منی میکس سہولت کا مقام منی میکس سہولت کے مقام کا مسئلہ ایک ایسے مقام کی تلاش کرتا ہے جو سائٹوں تک زیادہ سے زیادہ فاصلے کو کم سے کم کرے، جہاں ایک نقطہ سے سائٹوں تک کا فاصلہ اس مقام سے اس کے قریب ترین مقام تک کا فاصلہ ہے۔ ایک رسمی تعریف مندرجہ ذیل ہے: ایک پوائنٹ سیٹ P ′Rd کو دیکھتے ہوئے، ایک پوائنٹ سیٹ S ′Rd، |S | = k تلاش کریں، تاکہ زیادہ سے زیادہ ωP (minq ωS (d (p, q))) کو کم سے کم کیا جائے۔ k = 1 کے لیے یوکلڈین میٹرک کے معاملے میں، اسے سب سے چھوٹا گھیرے ہوئے دائرے کا مسئلہ یا 1 مرکز کا مسئلہ کہا جاتا ہے۔ اس کے مطالعے کا سراغ کم از کم 1860 کے سال تک لگایا گیا ہے۔ مزید تفصیلات کے لیے سب سے چھوٹا گھیرا ہوا دائرہ اور باؤنڈنگ سپیئر دیکھیں۔ این پی کی سختی یہ ثابت ہو چکا ہے کہ کے سینٹر کے مسئلے کا صحیح حل این پی ہارڈ ہے۔ غلطی چھوٹی ہونے پر اس مسئلے کا تخمینہ بھی این پی ہارڈ پایا گیا۔ تخمینہ الگورتھم میں غلطی کی سطح کو ایک تخمینہ عنصر کے طور پر ماپا جاتا ہے، جسے تخمینہ اور زیادہ سے زیادہ کے درمیان تناسب کے طور پر بیان کیا جاتا ہے۔ یہ ثابت ہوا ہے کہ جب تخمینہ عنصر 1.822 (طول و عرض = 2) یا 2 (طول و عرض> 2) سے کم ہوتا ہے تو k-مرکز مسئلہ کا تخمینہ NP سخت ہوتا ہے۔ الگورتھم ایکزیکٹ سولور اس مسئلے کا درست حل تیار کرنے کے لیے الگورتھم موجود ہیں۔ ایک درست حل کنندہ وقت پر چلتا ہے۔ 1 + ε تخمینہ 1 + ε تخمینہ ایک ایسا حل تلاش کرنا ہے جس میں تخمینہ عنصر 1 + ε سے زیادہ نہ ہو۔ یہ تخمینہ NP سخت ہے کیونکہ ε من مانی ہے۔ کورسیٹ تصور پر مبنی ایک نقطہ نظر کے نفاذ کی پیچیدگی کے ساتھ تجویز کیا گیا ہے۔ متبادل کے طور پر، بنیادی سیٹوں پر مبنی ایک اور الگورتھم بھی دستیاب ہے۔ اندر دوڑتا ہے۔ مصنف کا دعوی ہے کہ چلانے کا وقت بدترین صورت حال سے بہت کم ہے اور اس طرح جب k چھوٹا ہو تو کچھ مسائل کو حل کرنا ممکن ہے (جیسے k <5)۔ دور ترین نقطہ کلسٹرنگ مسئلہ کی سختی کے لیے، درست حل یا درست تخمینہ حاصل کرنا ناقابل عمل ہے۔ اس کے بجائے، بڑے k معاملات کے لیے عنصر = 2 کے ساتھ ایک تخمینہ وسیع پیمانے پر استعمال ہوتا ہے۔ تخمینہ کو سب سے دور پوائنٹ کلسٹرنگ (ایف پی سی) الگورتھم، یا سب سے پہلے ٹریورسل کہا جاتا ہے۔ الگورتھم کافی آسان ہے: سیٹ سے کسی بھی نقطہ کو ایک مرکز کے طور پر منتخب کریں ؛ دوسرے مرکز کے طور پر باقی سیٹ سے سب سے دور کے نقطہ کو تلاش کریں ؛ اس عمل کو دہرائیں جب تک کہ k مراکز نہ مل جائیں۔ یہ دیکھنا آسان ہے کہ یہ الگورتھم لکیری ٹائم میں چلتا ہے۔ چونکہ 2 سے کم عنصر کے ساتھ تخمینہ این پی ہارڈ ثابت ہوتا ہے، اس لیے ایف پی سی کو بہترین تخمینہ سمجھا جاتا تھا۔ عمل کی کارکردگی کے مطابق، وقت کی پیچیدگی کو بعد میں باکس سڑنے کی تکنیک کے ساتھ O (n log k) میں بہتر بنایا جاتا ہے۔ میکسمین سہولت کا مقام میکسمین سہولت کا مقام یا ناگوار سہولت کے مقام کا مسئلہ ایک ایسے مقام کی تلاش کرتا ہے جو سائٹوں تک کم سے کم فاصلے کو زیادہ سے زیادہ کرے۔ یوکلڈین میٹرک کے معاملے میں، اسے خالی دائرے کا سب سے بڑا مسئلہ کہا جاتا ہے۔ پلانر کیس (خالی دائرے کا سب سے بڑا مسئلہ) کو زیادہ سے زیادہ وقت میں حل کیا جا سکتا ہے۔ انٹیجر پروگرامنگ فارمولیشنز سہولت کے محل وقوع کے مسائل کو اکثر انٹیجر پروگراموں کے طور پر حل کیا جاتا ہے۔ اس تناظر میں، سہولت کے مقام کے مسائل اکثر اس طرح پیش کیے جاتے ہیں: فرض کریں کہ سہولیات اور گاہک موجود ہیں۔ ہم (1) کون سی سہولیات کھولنی ہیں، اور (2) کون سی (کھلی) سہولیات صارفین کو فراہم کرنے کے لیے استعمال کرنا چاہتے ہیں، تاکہ کم از کم قیمت پر کچھ مقررہ مانگ کو پورا کیا جا سکے۔ ہم مندرجہ ذیل نوٹیشن متعارف کراتے ہیں: آئیے افتتاحی سہولت کی (مقررہ) لاگت کو ظاہر کرتے ہیں۔ آئیے کسی پروڈکٹ کو سہولت سے گاہک کو اور کے لیے بھیجنے کی لاگت کو ظاہر کریں۔ کے لیے گاہک کی مانگ کو ظاہر کرتے ہیں۔ مزید فرض کریں کہ ہر سہولت کی زیادہ سے زیادہ پیداوار ہوتی ہے۔ آئیے مصنوعات کی زیادہ سے زیادہ مقدار کو ظاہر کریں جو سہولت کے ذریعے پیدا کی جا سکتی ہے، یعنی سہولت کی صلاحیت کو ظاہر کریں۔ اس حصے کا بقیہ حصہ کیپیسیٹڈ سہولت کے مقام کی پیروی کرتا ہے۔ ہماری ابتدائی تشکیل میں، بائنری متغیر کو متعارف کروائیں، جہاں اگر سہولت کھلی ہے، اور بصورت دیگر۔ مزید متغیر کو متعارف کروائیں اور جو سہولت سے بھری ہوئی مانگ کے حصے کی نمائندگی کرتا ہے۔ اس کے بعد نام نہاد کیپسیٹیٹڈ سہولت کے مقام کا مسئلہ نوٹ کے ذریعے دیا جاتا ہے کہ رکاوٹوں کا دوسرا سیٹ اس بات کو یقینی بناتا ہے کہ اگر، یعنی، سہولت کھلی نہیں ہے، تو سب کے لیے، یعنی کسی بھی گاہک کی کوئی مانگ سہولت سے پوری نہیں کی جا سکتی۔ غیر کیپسیٹڈ سہولت کا مقام اوپر کیپیسیٹڈ سہولت کے مقام کے مسئلے کا ایک عام معاملہ ہے جب سب کے لیے ہوتا ہے۔ اس صورت میں، قریب ترین کھلی سہولت سے گاہک کی تمام مانگ کو پورا کرنا ہمیشہ بہتر ہوتا ہے۔ اس کی وجہ سے، ہم اوپر سے مسلسل متغیرات کو بائنری متغیرات سے تبدیل کر سکتے ہیں، جہاں اگر گاہک کو سہولت کے ذریعے فراہم کیا جاتا ہے، اور بصورت دیگر۔ اس کے بعد غیر متزلزل سہولت کے مقام کا مسئلہ اس کے ذریعہ دیا جاتا ہے جہاں ایک مستقل مناسب طور پر بڑا ہونے کا انتخاب کیا جاتا ہے۔ کا انتخاب کمپیوٹیشن کے نتائج کو متاثر کر سکتا ہے-اس مثال میں بہترین انتخاب واضح ہے: لے لو۔ پھر، اگر، کا کوئی بھی انتخاب رکاوٹوں کے دوسرے سیٹ کو پورا کرے گا۔ غیر فعال سہولت کے مقام کے مسئلے کے لیے تشکیل کا ایک اور امکان صلاحیت کی رکاوٹوں (بڑی رکاوٹوں) کو الگ کرنا ہے۔ یعنی رکاوٹوں کو رکاوٹوں سے تبدیل کریں۔ عملی طور پر، یہ نئی تشکیل نمایاں طور پر بہتر کارکردگی کا مظاہرہ کرتی ہے، اس معنی میں کہ اس میں پہلی تشکیل کے مقابلے میں لکیری پروگرامنگ میں سخت نرمی ہے۔ نوٹ کریں کہ نئی رکاوٹوں کو یکجا کرنے سے اصل بڑی رکاوٹیں پیدا ہوتی ہیں۔ کیپسیٹیٹڈ صورت میں، یہ فارمولیشن مساوی نہیں ہیں۔ غیر فعال سہولت کے مقام کے مسئلے کے بارے میں مزید معلومات "ڈسکریٹ لوکیشن تھیوری" کے باب 3 میں مل سکتی ہیں۔ ایپلی کیشنز صحت کی دیکھ بھال صحت کی دیکھ بھال میں، سہولت کے مقام کے غلط فیصلوں کا کمیونٹی پر سادہ لاگت اور سروس میٹرکس سے بالاتر سنگین اثر پڑتا ہے۔ مثال کے طور پر، صحت کی دیکھ بھال کی سہولیات تک رسائی مشکل سے بیماری اور اموات میں اضافے سے وابستہ ہونے کا امکان ہے۔ اس نقطہ نظر سے، صحت کی دیکھ بھال کے لیے فیسلٹی لوکیشن ماڈلنگ دوسرے شعبوں کے لیے اسی طرح کے ماڈلنگ سے زیادہ اہم ہے۔ سالڈ ویسٹ مینجمنٹ میونسپل سالڈ ویسٹ مینجمنٹ اب بھی ترقی پذیر ممالک کے لیے ایک چیلنج ہے کیونکہ فضلہ کی پیداوار میں اضافہ اور فضلہ کے انتظام سے وابستہ اعلی اخراجات ہیں۔ کسی سہولت کے مقام کے مسئلے کی تشکیل اور درست حل کے ذریعے کچرے کو ٹھکانے لگانے کے لیے لینڈ فلز کے مقام کو بہتر بنانا ممکن ہے۔ کلسٹرنگ کلسٹر تجزیہ کے مسائل کے ایک خاص ذیلی سیٹ کو سہولت کے مقام کے مسائل کے طور پر دیکھا جا سکتا ہے۔ سنٹرائڈ پر مبنی کلسٹرنگ کے مسئلے میں، مقصد ڈیٹا پوائنٹس (ایک مشترکہ میٹرک اسپیس کے عناصر) کو مساوات کی کلاسوں میں تقسیم کرنا ہے-جسے اکثر رنگ کہا جاتا ہے-جیسے کہ ایک ہی رنگ کے پوائنٹس ایک دوسرے کے قریب ہوں (مساوی طور پر، جیسے کہ مختلف رنگوں کے پوائنٹس ایک دوسرے سے دور ہوں)۔ یہ دیکھنے کے لیے کہ کوئی سنٹرائڈ پر مبنی کلسٹرنگ کے مسئلے کو (میٹرک) سہولت کے مقام کے مسئلے کے طور پر کیسے دیکھ سکتا ہے ("ٹرانسفارم" یا "کم" پڑھ سکتا ہے)، سابقہ میں ہر ڈیٹا پوائنٹ کو مؤخر الذکر میں ڈیمانڈ پوائنٹ کے طور پر دیکھیں۔ فرض کریں کہ کلسٹر کیے جانے والے ڈیٹا میٹرک اسپیس کے عناصر ہیں (مثال کے طور پر۔ کچھ مقررہ کے لیے-جہتی یوکلڈین جگہ ہونے دیں)۔ سہولت کے مقام کے مسئلے میں جو ہم تعمیر کر رہے ہیں، ہم اس میٹرک جگہ کے اندر کسی بھی مقام پر سہولیات کو رکھنے کی اجازت دیتے ہیں۔ یہ اجازت شدہ سہولت کے مقامات کے سیٹ کی وضاحت کرتا ہے۔ ہم لاگت کو لوکیشن-ڈیمانڈ پوائنٹ جوڑوں کے درمیان جوڑی کے لحاظ سے فاصلے کے طور پر بیان کرتے ہیں (مثال کے طور پر، میٹرک کے-سینٹر دیکھیں)۔ سینٹرایڈ پر مبنی کلسٹرنگ کے مسئلے میں، ڈیٹا کو مساوات کی کلاسوں میں تقسیم کیا جاتا ہے (یعنی۔ رنگ) جن میں سے ہر ایک کا مرکز ہوتا ہے۔ آئیے دیکھتے ہیں کہ ہماری تعمیر شدہ سہولت کے مقام کے مسئلے کا حل بھی اس طرح کی تقسیم کو کیسے حاصل کرتا ہے۔ ایک قابل عمل حل مقامات کا غیر خالی ذیلی مجموعہ ہے۔ ہماری سہولت کے مقام کے مسئلے میں یہ مقامات ہمارے سنٹرایڈ پر مبنی کلسٹرنگ کے مسئلے میں سنٹرایڈز کے ایک سیٹ پر مشتمل ہیں۔ اب، ہر ڈیمانڈ پوائنٹ کو اس مقام پر تفویض کریں جو اس کی خدمت کی لاگت کو کم سے کم کرے ؛ یعنی، ڈیٹا پوائنٹ کو سینٹرائڈ کو تفویض کریں (من مانی طور پر تعلقات کو توڑ دیں)۔ یہ پارٹیشننگ کو حاصل کرتا ہے بشرطیکہ سہولت کے مقام کے مسئلے کے اخراجات کی وضاحت اس طرح کی جائے کہ وہ سینٹرائڈ پر مبنی کلسٹرنگ مسئلے کے فاصلاتی فنکشن کی تصاویر ہوں۔ مقبول الگورتھم ٹیکسٹ بک الگورتھم ڈیزائن ایک متعلقہ مسئلہ کی تفصیل اور ایک تخمینہ الگورتھم فراہم کرتا ہے۔ مصنفین میٹرک سہولت کے محل وقوع کے مسئلے کا حوالہ دیتے ہیں (یعنی۔ سینٹرائڈ پر مبنی کلسٹرنگ مسئلہ یا میٹرک سینٹر مسئلہ) مرکز کے انتخاب کے مسئلے کے طور پر، اس طرح مترادفات کی فہرست میں اضافہ ہوتا ہے۔ مزید برآں، دیکھیں کہ سہولت کے مقام کے مسئلے کی ہماری مذکورہ تعریف میں کہ معروضی فعل عمومی ہے۔ سہولت کے مقام کے مسئلے کی مختلف شکلیں پیدا کرنے کے مخصوص انتخاب، اور اس وجہ سے سینٹرایڈ پر مبنی کلسٹرنگ مسئلے کی مختلف قسمیں۔ مثال کے طور پر، کوئی بھی ہر مقام سے اس کے تفویض کردہ ڈیمانڈ پوائنٹس تک کے فاصلے کے مجموعے کو کم کرنے کا انتخاب کر سکتا ہے (لا ویبر کا مسئلہ)، یا کوئی اس طرح کے تمام فاصلے کو زیادہ سے زیادہ کم کرنے کا انتخاب کر سکتا ہے (لا 1 مرکز کا مسئلہ)۔ گراف سینٹر کواڈریٹک اسائنمنٹ مسئلہ لوکیشن-الاکیشن ڈیجسٹرا کا الگورتھم لسٹ آف اسپیشیئل اینالیسس سافٹ ویئر مسابقتی سہولت لوکیشن گیم ورٹیکس کے-سینٹر مسئلہ ہندسی میڈین حوالہ جات بیرونی لنکس EWGLA EURO ورکنگ گروپ آن لوکیشنل اینالیسس دیکھیں۔ لوکیشن اینالیسس پر انفارمیشن سیکشن، ایک پیشہ ور سوسائٹی جو سہولت کے لوکیشن سے متعلق ہے۔ ٹریور ہیل کے ذریعہ جمع کردہ سہولت کے مقام پر کتابچہ، جس میں 3400 سے زیادہ مضامین ہیں۔ لوکیشن الگورتھم کی لائبریری ویب پر مبنی سہولت لوکیشن یوٹیلیٹی (واحد سہولت) سہولت لوکیشن آپٹیمائزر، سہولت لوکیشن کے مسائل کو حل کرنے کے لیے ایک میٹ لیب پر مبنی ٹول ہے۔ گراف تھیوری میں کاروباری کمپیوٹیشنل مسائل میں ریاضیاتی اصلاح سہولت محل وقوع