حل مسئلۀ پوشش تدریجی خدمات درمانی با شبیه‌سازی تبرید و روش‌های خوشه‌بندیk-means و شبکۀ عصبی

حل مسئلۀ پوشش تدریجی خدمات درمانی با شبیه‌سازی تبرید و روش‌های خوشه‌بندیk-means و شبکۀ عصبی

مهدی بشیری^1*، یونس گرمه‌ای²، محسن یحیایی³

1- دانشیار، دانشکده فنی- دانشگاه شاهد- تهران- ایران

2- دانشجوی کارشناسی‌ارشد، دانشکده فنی- دانشگاه شاهد - تهران- ایران

3- دانشجوی کارشناسی‌ارشد، دانشکده فنی- دانشگاه شاهد - تهران- ایران

چکیده

در مسائل مکان‌یابی پوشش نوین، افزایش فاصله از تسهیل ارائه‌دهنده سرویس در ناحیۀ پوشش، موجب کم‌شدن سطح پوشش­دهی می­شود و تحت عنوان پوشش تدریجی در نظر گرفته می­شود، با ازدیاد نقاط تقاضا، زمان حل در این‌گونه مسائل افزایش می­یابد. لذا روش‌های مختلف حل از جمله دقیق، فراابتکاری و ابتکاری برای مدل‌های مختلف مسئلۀ پوشش تدریجی مطرح شده است. در این مقاله مسئلۀ پوشش تدریجی با استفاده از روش‌های شبیه‌سازی تبرید، خوشه‌بندی شبکۀ عصبی و خوشه‌بندی k-means حل شده و جواب‌ها و زمان‌های بدست‌آمده از سه روش تحلیل شده است. نتایج  به‌دست‌آمده نشان‌دهندۀ کارایی روش k-means در حل مسئله است و این روش می­تواند در مدت‌زمان قابلِ‌قبول جواب‌هایی با دقت زیاد (نزدیک به جواب‌های به‌دست‌آمده از روش شبیه‌سازی تبرید) تولید کند. در ادامه کاربرد روش‌های خوشه‌بندی در مسئلۀ پوشش تدریجی برای احداث بیمارستان تخصصی در ایران ارزیابی شده است و تسهیلات به‌دست‌آمده با این روش به مکان‌هایی اختصاص داده شده­اند که بیشترین پوشش را دارا هستند.

واژه‌های کلیدی:خوشه‌بندیk-means ، شبکۀ عصبی، شبیه‌سازی تبرید، مسئلۀ مکان­یابی پوشش تدریجی.

مقدمه

مفهوم پوشش به‌عنوان زیر مجموعه­ای از مسائل مکان‌یابی کاربرد زیادی در زندگی روزمره ما دارد و مسائل زیادی همچون پوشش یک منطقه یا مناطق با ایستگاه­های آتش‌نشانی، بیمارستان­ها، مراکز تعلیم و تربیت، مراکز رفاهی و ... درخور توجه بوده است. محققان همواره به دنبال حداکثر پوشش نقاط تقاضا با استفاده از حداقل تسهیلات (حداقل هزینه) هستند. مسئلۀ پوشش خود به دو زیرمجموعه پوشش کلی و پوشش جزئی تقسیم می­شود. موضوعات عام‌المنفعه  بیشتر در پوشش کلیدرخور توجه قرار می­گیرند و به‌دنبال پوشش همۀ نقاط تقاضا هستند و هدف پیداکردن حداقل تعداد تسهیلات برای پوشش همۀ نقاط تقاضا است(بشیری و همکاران، 1387).

در سال 2003 پوشش تدریجی توسط برمن¹ و همکاران مطرح شد. در مسئلۀ  مکان­یابی پوشش تدریجی حداقل دو شعاع پوششی مدنظر گرفته می‌شود بدین‌صورت که اگر مسافت مشتری از تسهیل، کمتر از شعاعی مانند شعاع کوچکتر باشد (d≤r)، پوشش کامل صورت خواهد گرفت؛چنانچه  فاصلۀ مشتری تا تسهیل، بین شعاع کوچک‌تر و بزرگ‌تر باشد (r<d≤u)، پوشش با تابع خاصی بر حسب میزان مسافت مشتری تا تسهیل در نظر گرفته می­شود و اگر مسافت مشتری تا تسهیل بیش از شعاع بزرگ‌تر  باشد (d>u)، هیچ‌گونه پوششی صورت نخواهد گرفت. برای حل مسئلۀ مکان­یابی پوشش تدریجی به دنبال نقاطی هستیم که بتوانیم حداکثر پوشش را با قراردادن تسهیلات در آن نقاط بدست آوریم (برمن و همکاران، 2009). در تحقیقات انجام‌شده در خصوص مسئلۀ پوشش تدریجی،مدل‌های مختلفی بررسیشده است که برخی از آنها عبارت‌اند از: پوشش تدریجی با استفاده از تابع خطی کاهنده (برمن و همکاران، 2002)؛ پوشش تدریجی با استفاده از تابع پوششی تقسیم‌بندی شده (فراهانی زنجیرانی و همکاران²، 2012)؛ پوشش تدریجی با استفاده از شعاع بیشینه  و کمینۀ یکسان برای تمامی نقاط، مدل میانه ترتیبی پوشش تدریجی (دِرِزمَن³ و همکاران، 200) و مدل پوشش تدریجی با تقاضاهای تصادفی توزیع نامعلوم (برمن و وانگ، 2011).

باید به این نکته توجه داشت که مسئلۀ مکان­یابی پوشش در سال‌های اخیر بسیار پیشرفت کرده و با سایر مباحث از جمله مسائل مختلف مکان­یابی ترکیب شده است (داوری⁴ و همکاران، 2013).  روش‌هایی برای حل مسائل پوشش مطرح شده است که می­توان به روش‌های دقیق مانند شاخه و کران، روش‌های ابتکاری مانند الگوریتم ایگنزیو و روش‌های فراابتکاری مانند شبیه‌سازی و شبکۀ‌ عصبی اشاره کرد. در مسئلۀ پوشش تدریجی، با افزایش نقاط تقاضا، زمان حل به‌شدت افزایش می­یابد و  در دنیای واقعی تعداد نقاط تقاضا زیاد است و در محققان در اکثر موارد از روش­های فراابتکاری برای حل این‌گونه مسائل استفاده می­شود (زرندی⁵ و همکاران، 2013). حال آنکه می­توان با استفاده از تکنیک‌های ریاضی مانند خوشه‌بندی تعداد نقاط را طوری کاهش داد که در اصلِ مسئله تغییر چندانی اتفاق نیفتد و با صرف زمان کمتر جواب‌های نسبتاً مناسبی به دست آورد (سرجیو⁶ و همکاران، 2007).

تکنیک‌های زیادی برای خوشه‌بندی نقاط استفاده می‌شود؛ از جمله تکنیک‌های مهم که اخیراً رواج پیدا کرده استفاده از شبکه عصبی و k-means برای حل مسائل مختلفبا تعداد نقاط زیاد تقاضا است (شرالی و دسایی⁷، 2003 و سرجیو و همکاران، 2007).

مطالعۀادبیاتتحقیقنشانمی­دهداغلبمطالعاتگذشتهازروش‌هایکلاسیکفراابتکاری نظیر الگوریتمشبیه‌سازی تبرید برای حل مسئلۀپوششتدریجیاستفادهکرده­اند. در این مقاله با بررسی و مقایسه بین روش فراابتکاری شبیه‌سازی تبرید و روش‌های خوشه‌بندی شبکۀ عصبی وk-means نقاط ضعف و قوت هر سه روش بیان شده است. همچنین تأیید کارایی استفاده از روشk-means  ازلحاظ کاربردی با خوشه‌بندی شهرهای ایران و تئوریباحلمسائلشبیه‌سازیشده اثبات گشته است. به‌عبارت‌دیگرنوآوریاینتحقیقرامی‌تواندرپیشنهاداستفادهازروش‌هایخوشه‌بندی مبتنی بر شبکۀعصبی و k-means برای حل مسئلۀپوشش تدریجی دانست. پیشنهاد طراحی شبکه خدمات درمانی ایران بر اساس مسئلۀپوششتدریجیرابه‌عنواننوآوریدیگرمی­توانبرشمرد.

در بخش بعدی مقاله مسئلۀ مکان­یابی پوشش تدریجی و تابع خطی کاهنده تشریح شده است؛ در بخش 3 مدل عمومی خوشه‌بندی بیان شده است؛ در بخش 4 روش انجام تحقیق با استفاده از فلوچارت و یک مثال مطرح شده است؛ در بخش 5 به‌منظور اثبات صحت روش‌های حل الگوریتم شبیه­سازی تبرید به‌کار‌رفته در مقاله توضیح داده شده و با روش دقیقمقایسه شده است؛ در بخش 6پس از اثبات صحت جواب‌های به‌دست‌آمده از طریق شبیه­سازی تبرید، مقایسه­ای بین سه روش و ویژگی‌های این روش‌ها بیان شده است؛ در بخش 7 کاربرد مسئله پوشش تدریجی برای احداث بیمارستان تخصصی در کشور ایران و حل مسئله با سه روش شبکه عصبی،k-means  و شبیه‌سازی تبرید بیان شده و در بخش پایانی نتیجه‌گیریبیان شده است.

مدل مسئلۀ مکان یابی پوشش تدریجی

در مدل پوشش تدریجی هدف، تعیین محل نقاطی است که بیشترین سطح پوشش را نسبت به سایر نقاط دارا هستند (سطح پوشش با پارامتر c_ij نمایش داده می­شود).

پارامترc_ijبه صورت رابطۀ (1) تعریف می­شود:

رابطۀ (1) بیان‌کنندۀ این مهم است که اگر فاصله مشتری i از تسهیلj، کمتر از شعاع پوششی تسهیلjباشد، سطح پوشش برابر با وزن نقطه­ای است که نقطه i در آن قرار گرفته است. اگر مسافت مشتری بین شعاع کوچک‌تر و بزرگتر باشد، سطح پوشش برابر است با وزن (تقاضا) نقطه i در تابعی که به مسافت مشتری تا تسهیل بستگی دارد و اگر فاصله بیش از شعاع بزرگ‌تر باشد، سطح پوشش برابر صفر خواهد بود. مدل اصلی مسئلۀ پوشش تدریجی به‌صورت زیر است (برمن و همکاران، 2003):

هدف این مدل بیشینه کردن سطح پوشش است. محدودیت (3) بیان‌کنندۀ تعداد تسهیلاتی است که باید جایابی شوند. محدودیت (4) این اطمینان را حاصل می­کند که  نقاط می­توانند فقط با تسهیلی پوشیده شوندکه در مکان jآن تسهیل وجود دارد. محدودیت (5) بیان می­کند که هر مکان فقط به‌وسیلۀ یک تسهیل خاص پوشانده می‌شود. محدودیت (6) نشان‌دهندۀ صفرویک‌بودن متغیرهای تصمیم مسئله است. متغیرy اگر مقدار 1 بگیرد نشان‌دهنده این است که تسهیل در آن نقطه قرار میگیرد و اگر صفر باشد هیچ تسهیلی در آن نقطه قرار نمی‌گیرد. متغیرx زمانی 1 است که نقطه iتوسط تسهیلی که در نقطه jقرار دارد پوشانیده شود. مدل گفته‌شده همان مدل مسئلۀ پوشش است؛ با این تفاوت که به جای کمینه‌کردن مسافت در تابع هدف از پارامتر سطح پوشش با هدف بیشینه‌کردن آن استفاده شده است.

یکی از روش­های متداول در مسئلۀ پوشش تدریجی برای به‌دست‌آوردن سطح پوشش، استفاده از تابع کاهنده خطی است (برمن و همکاران، 2003).

در رابطۀ (7)، =max d(i,j)α است. در این مقاله از رویکرد تابع خطی کاهنده برای به‌دست‌آوردن سطح پوشش‌دهی  استفاده شده است.

مدل عمومی خوشه‌بندی

درمدل عمومی خوشه‌بندی، هدف تعیینpخوشه برای تخصیص تمام نقاط به این pخوشه است و هر نقطۀ a_iÎ (x_i,y_i)با توجه به خصوصیت‌های مشترکی که با سایر نقاط دارد در یک خوشۀ منحصربه‌فرد قرار می­گیرد. تابع هدف این مدل، فاصلۀ هر یک از نقاط را تا مراکز خوشه­ها حداقل می­کند. در مدل زیر مراکز خوشه­ها با ζ_k در فضای دوبعدی مشخص شده است و x_ik زمانی برابر با 1 است که نقطه i به خوشۀ kتخصیص داده شود (شرالی و دسایی، 2003).

محدودیت (9) و (10) این اطمینان را حاصل می­سازد که هر نقطه، فقط به یک خوشه اختصاص داده می­شود.

روش انجام تحقیق

در این مقاله مسئلۀ پوشش تدریجی با استفاده از سه رویکرد شبیه‌سازی تبرید، خوشه‌بندی شبکۀ عصبی و خوشه‌بندی k-means حل شده است. در روش‌های  شبکۀ عصبی و k-means خوشه‌بندی براساس فاصله نقاط از یکدیگر انجام گرفته و نقطه­ای که بیشترین سطح پوشش تدریجی را در هر خوشه داراست، به‌عنوان محل قرارگیری تسهیل مدنظر قرار گرفته است. گفتنی است که در هر خوشه، یک مسئلۀ پوشش تدریجی از یک طرف با درنظرگرفتن یک تسهیل برای احداث با استفاده از روابط 2 تا 6 حل شده است و در طرف دیگر مسئلۀ پوشش تدریجی با استفاده از شبیه‌‌سازی تبرید با درنظرگرفتن تعداد خوشه­ها به‌عنوان تعداد تسهیلاتی که می­توانیم احداث کنیم، حل شده است. در شکل (1) نحوۀ انجام آن به‌صورت فلوچارت نمایش داده شده است.

شکل (1) فلوچارت حل مسئله پوشش تدریجی با شبیه سازی تبرید و روش‌های خوش‌بندی

برای بیان بهتر روش حل و مقایسه بین جواب‌های گرفته‌شده از روش‌های حل ارائه‌شده در مقاله و حل دقیق، مثال زیر بر اساس اطلاعات مندرج در شبکه نقاط شکل (2) بررسی می‌شود. گفتنی است حل دقیق مسئله با استفاده از نرم‌افزارGAMS و حل‌کنندهCPLEX انجام گرفته است.

شکل (2) شبکه مسافت بین نقاط تقاضا در مثال بررسی‌شده

فرض کنید شعاع پوششی کوچک‌تر برابر 5، شعاع پوششی بزرگ‌تر برابر 7 و وزن نقاط تقاضا یکسان است. در جدول (1) سطح پوشش‌دهی بین نقاط مشخص شده است.

جدول(1) سطح پوشش‌دهی با استفاده از تابع خطی کاهنده در مثال بررسی‌شده

اگر تعداد تسهیل که احداث خواهد شد (تعداد خوشه­ها)، برابر با 2 باشد، همان‌طور که با توجه به فواصل نیز مشخص است، خوشه‌بندی با روش‌های k-means و  شبکۀ عصبی بدین‌صورت است که نقاط 1، 2 و 4 در یک خوشه و نقاط 3 و5 در خوشۀ دیگر قرار می‌گیرند و درنتیجۀ حل جداگانه در خوشه­ها نقطه 1 در خوشۀ اول و نقاط 5 و 3 در خوشۀ دوم هر دو مناسب قرارگیری تسهیل هستند و درنتیجۀ این جواب تمامی نقاط پوشش داده می‌شوند. به‌وسیلۀ حل این مسئله با روش دقیق و شبیه­سازی تبرید که در بخش بعد در مورد آن توضیح داده می­شود، جواب قرارگیری تسهیلات، نقاط 1 و 3 است که در این حالت نیز تمامی نقاط به‌وسیلۀ دو تسهیل پوشش داده می‌شوند؛ بنابراین در تمامی روش‌ها جواب مثال یکسان است.

الگوریتم شیبه‌سازی تبرید و مقایسه آن با جواب به‌دست‌آمده از حل دقیق

در مدل پیشنهادی برای تولید جواب اولیه (y) ابتدا پارامترها و مکان قرارگیری تسهیلات به صورت تصادفی مشخص می­شود. سپس با توجه به فواصل نقاط از یکدیگر و شعاع پوششی تسهیلات در دوره­های زمانی مختلف، سطح پوشش با استفاده از تابع خطی کاهنده محاسبه می‌شود. در ادامه تابع هدف مدل (z)، یعنی پوشش تدریجی مشتریان برای تسهیلات، با توجه به مکان قرارگیری محاسبه می­شود.

شکل (3) الگوریتمشبیه‌سازی تبرید برای مسئلۀپوشش تدریجی

فلوچارت الگوریتم شبیه‌سازی تبرید به‌کاررفته در مقاله در شکل (3) نمایش داده شده است. با توجه به اینکه آزمایش‌ها به بهترین ترکیب وضعیت پارامترها برای به‌دست‌آوردن جواب طراحی شده است، پارامترهای استفاده‌شده در این کد در مناسب‌ترین زمان حل به کار گرفته می­شود. بدین‌منظور از آزمایش تاگوچیL16(4**5)و با استفاده از نرم‌افزار minitab پنج پارامتر دخیل در الگوریتم شبیه‌سازی تبرید در چهار سطح و شانزده تکرار استفاده شده است. در جدول (2) پارامترها و سطوح مختلف آزمایش نشان داده شده است.

جدول (2) سطوح و پارامترهای استفاده‌شده شبیه‌سازی تبرید در آزمایش تاگوچی

در جدول(3) جواب­های به‌دست‌آمده در این شانزده تکرار، چه در حوزۀ زمان و چه در حوزۀ جواب مدل نمایش داده شده است.

جدول (3) جواب‌های تاگوچی در تکرارهای شبیه‌سازی تبرید

در شکل (4) میانگین و در شکل (5) SN ratios به‌دست‌آمده از آزمایش تاگوچی در زمینۀ تابع هدف نمایش داده می­شود و طبق این شکل­ها t0 در سطح سوم، f در سطح اول، tf در سطح سوم، nlimit در سطح سوم و nover در سطح دوم قرار دارند.

شکل (4) نمودار میانگین پارامترها در سطوح مختلف برای تابع هدف شبیه‌سازی تبرید

شکل (5) نمودار SN ratios پارامترها در سطوح مختلف برای تابع هدف شبیه‌سازی تبرید

در شکل (6) میانگین و در شکل (7) SN ratios به‌دست‌آمده از آزمایش تاگوچی در زمینۀ زمان محاسبات نمایش داده می­شود و طبق این شکل­ها t0 در سطح اول با توجه به میانگین و در سطح چهارم با توجه به SN ratios، fدر سطح چهارم، tf در سطح اول، nlimit در سطح اول با توجه به میانگین و سطح چهارم با توجه به SN ratios و nover در سطح اول قرار دارد.

شکل (6) نمودار میانگین پارامترها در سطوح مختلف زمان محاسبات شبیه‌سازی تبرید

شکل (7) نمودار SN ratios پارامترها در سطوح مختلف برای زمان محاسبات شبیه‌سازی تبرید

با توجه به آزمایشات تاگوچی به زمان و تابع هدف، وزن‌های 3/0 و 7/0 را می‌دهیم؛ پارامترها برای حل مدل این تحقیق به‌صورت جدول (4) است.

جدول (4) پارامترهای شبیه‌سازی تبرید استفاده شده در تحقیق

برای تایید صحت الگوریتم شبیه‌سازی تبرید در جدول (5) بین مسئله پوشش تدریجی حل شده با روش دقیقو حل مسئله پوشش تدریجی با استفاده از شبیه‌سازی تبریدمقایسه­ای در رابطه با تابع هدف انجام شده است. در جدول (5) شماره مثال­ها (no)، تعداد نقاط (n)، تعداد تسهیلات (P)، مکان قرارگیری تسهیلات (y) و تابع هدف (z) نمایش داده شده است. تابع هدف برای هر دو روش یکسان است که این امر حاکی از مناسب بودن الگوریتم شبیه‌سازی تبرید است.

جدول (5) مقایسه بین جواب‌های به‌دست‌آمده از دو روش حل دقیق و الگوریتم شبیه‌سازی تبرید

مقایسۀ نتایج سه الگوریتم پیشنهادی برای مسئلۀ پوشش تدریجی

پس از اثبات صحت الگوریتم شبیه‌سازی تبرید، مقایسه بین شبیه‌سازی تبرید، k-means و شبکۀ عصبی انجام می‌گیرد. داده­های این مقاله با اعداد تصادفی در گروه­های 10، 50، 100 و 500تایی در بازۀ (0 و 200) تولید شده‌اند. با استفاده از روش‌های k-means و شبکۀ عصبی این داده‌ها در خوشه­های 2، 4 و 9تایی (تعداد تسهیلات) تقسیم شده‌اند. در درون هر خوشه فاصلۀ بین نقاط به‌صورت اقلیدسی محاسبه شده است. آن‌گاه با درنظرگرفتن شعاع کوچک‌تر 50 و شعاع بزرگ‌تر 150برای هر تسهیل مسئلۀ پوشش تدریجی با استفاده از تابع خطی کاهنده در هر خوشه حل شده و بهترین نقطه برای احداث تسهیل مشخص شده است. حل مسئلۀ پوشش تدریجی نتایج حاصل از جواب‌های به‌دست‌آمده از سه روش k-means، شبکۀ عصبی و شبیه‌سازی تبرید در جدول (6) نمایش داده شده است. ستون اول نشان‌دهندۀ تعداد نقاط بررسی‌شده است؛ در ستون دوم تعداد تسهیلات مشخص شده و در ستون‌های بعدی تابع هدف به‌دست‌آمده از هر خوشه و همچنین تابع هدف پوشش کل که از طریق نقاط به‌دست‌آمده، محاسبه شده­اند، نمایش داده شده است.

جدول (6) مقایسۀ زمان و جواب تابع هدف بین سه روش شبیه‌سازی تبرید، شبکۀ عصبی و k-means در مسئلۀ پوشش تدریجی

زمان‌های حل مسئلۀ پوشش تدریجی با استفاده از سه روش شبکۀ عصبی، شبیه‌سازی تبرید و k-means در شکل (8) به‌صورت نمودار نمایش داده شده است. همان‌طور که مشاهده می­شودزمان‌ها به‌صورت چشمگیری از مثال 4 به 5 افزایش پیدا کرده­اند؛ اینموضوع به این علت استکهنقاطاز 100 به 500 افزایشپیداکردهاندوباافزایشایننقاط از 500 به بالا  زمان حل مسئله نیز با افزایشهمراهاست. در بین روش‌های حل مسئلۀپوششتدریجی،خوشه‌بندیk-means با زمان کمتری جواب نسبتاًمناسبی ارائه می­کند و این نکته به این علت است که در خوشه‌بندی نقاطی که به یکدیگر نزدیک هستند در یک خوشه قرار می­گیرند و سپس در خوشه بهترین مکان شناساییمی­شود. علت کاهش زمان در شبیه‌سازی تبرید طی مثال‌های 5 تا 7، افزودن تسهیلات از 2 به 9 است، بدین معنا که با ثابت‌بودن تعداد نقاط، شعاع‌های پوشش و با افزایش تعداد تسهیلات زمان حل شبیه‌سازی تبرید کاهش می‌یابند. علت جهش زمان بین مثال 4 و 5، افزایش نقاط تقاضا از تعداد 100 به 500 است و بیانگر حساسیت زیاد مسئلۀ پوشش تدریجی به تعداد نقاط تقاضاست.

با مقایسۀ توابع هدف سه روش مشاهده می­شود که الگوریتم شبیه‌سازی تبرید جواب بهتری نسبت به روش‌های خوشه‌بندی ارائه می­کند.  

شکل (8) مقایسۀ زمان‌های حل مسئلۀ پوشش در سه روش حل پیشنهادی

کاربرد مسئلۀ مکان‌یابی پوشش تدریجی در شناسایی بهترین مکان برای احداث بیمارستان تخصصی در ایران

فرض کنید با استفاده از مختصات جغرافیایی شهرهای ایران، می­خواهیم بهترین مکان‌ها برای احداث بیمارستان تخصصی را با حل مسئلۀ پوشش تدریجی مشخص کنییم. یکی از مهمترین عوامل در احداث بیمارستان‌های تخصصی علاوه‌بر هزینه، فاصله است و باید این بیمارستان‌ها در شهرهایی احداث شوند که بتوانند بیشترین سطح پوشش را برای متقاضیان با کمترین هزینه مهیا کنند ( منظور از هزینه تنها مادی نیست؛ هزینه‌های ناشی از مرگ یک انسان هیچ‌گاه جبران‌کردنی نیست)؛  با فراهم‌کردن شرایط و پیش‌بینی­های لازم برای احداث بیمارستان تخصصی در مکان مناسب می­توان گام کوچکی در این مهم برداشت. هر بیمارستان تخصصی با شعاع پوششی کوچک‌تر از 1 و شعاع پوششی بزرگ‌تر از 2 مدنظر است. در مسئلۀ اول تعداد بیمارستان تخصصی 4 و در مسئلۀ دوم تعداد بیمارستان تخصصی 9 در نظر گرفته شده است. در این مسئلۀ پوشش تدریجی، 262 شهر ایران با هر سه روش خوشه‌بندی k-means، خوشه‌بندی شبکۀ عصبی و شبیه‌سازی تبرید حل شده است. در شکل (9) و (10) تعداد خوشه­ها 9تایی است؛ هر رنگ و شکل هندسی نشان‌دهندۀ یک خوشه است و شهرهایی که در مجاورت یکدیگر هستند به‌علت نزدیکی فاصله در یک خوشه قرار گرفته‌اند. همان‌طور که ملاحظه می­شود، خوشه‌بندی با هر دو روش k-means و  شبکۀ عصبی جواب‌های نسبتاً یکسانی در خوشه‌کردن شهرهای ایران می­دهد.  در جدول (7) مسئلۀ اول پوشش با استفاده از خوشه‌بندی با شبکۀ عصبی حل شده است. در جدول (8) مسئلۀ اول با استفاده از k-means حل شده است و در جدول (9) جواب به‌دست‌آمده از شبیه‌سازی تبرید برای مسئلۀ اول نمایش داده شده است.

شکل (9) خوشه‌‌بندی 9تایی شهرهای ایران  با استفاده از شبکۀ عصبی

جدول (7) حل مسئلۀ پوشش تدریجیِ مسئلۀ مکان‌یابی بیمارستان تخصصی با 9 تسهیل با استفاده از خوشه‌بندی شبکۀ عصبی

در شکل (10) خوشه‌بندی شهرهای ایران با استفاده از k-means برای احداث 9 بیمارستان تخصصی انجام شده است.

در جدول (8) جواب‌های به‌دست‌آمده از روش k-means، به تعداد 9 خوشه نمایش داده شده است. نتایج به‌دست‌آمده از این جدول نشان می‌دهد که پوششبه‌دست‌آمده از روشk-meansجواب بهتری نسبت به شبکۀ عصبی در حل مسئلۀ پوشش تدریجی ارائه می‌کند.

شکل (10) خوشه‌‌بندی 9تایی شهرهای ایران با استفاده از k-means

جدول (8) حل مسئلۀ پوشش تدریجیِ مسئلۀ مکان‌یابی بیمارستان تخصصی با 9 تسهیل با استفاده از خوشه‌بندی k-means

جدول (9) حل مسئلۀ پوشش تدریجیِ مسئلۀ مکان‌یابی بیمارستان تخصصی با 9 تسهیل با استفاده از شبیه‌سازی تبرید

مسئلۀ دوم با فرض تعداد بیمارستان تخصصی برابر با 4 در نظر گرفته شده است و مابقی فرض‌ها همچنان به قوت خود باقی هستند. نتایج به‌دست‌آمده در این مسئله از سه روش، نسبت به مسئلۀ اول اختلاف بیشتری دارند و این موضوع بیانگر این مهم است که با کاهش بیمارستان‌های تخصصی (تعداد تسهیلات) دقت جواب‌های به‌دست‌آمده از روش‌های خوشه‌بندی کاهش می­یابد.

جدول (10) حل مسئلۀ پوشش تدریجیِ مسئلۀ مکان‌یابی بیمارستان تخصصی با 4 تسهیل با استفاده از خوشه‌بندی شبکۀ عصبی

جدول (11) حل مسئلۀ پوشش تدریجیِ مسئلۀ مکان‌یابی بیمارستان تخصصی با 4 تسهیل با استفاده از خوشه‌بندی k-means

جدول (12) حل مسئلۀ پوشش تدریجیِ مسئلۀ مکان‌یابی بیمارستان تخصصی با 4 تسهیل با استفاده از شبیه‌سازی تبرید

نتیجه‌گیری

در مقالۀ ارائه‌شده مدل عمومی خوشه‌بندی، مدل مسئلۀ پوشش تدریجی و رابطۀ آن با تابع خط کاهنده ذکر شد. هدف اصلی این مقاله، معرفی روش  مؤثر و سریع برای حل مسائل مکان­یابی پوشش تدریجی است. بدین‌منظور، 25 مثال عددی شبیه‌سازی شده با فواصل تصادفی برای مقایسۀ سه روش حل مسئلۀ پوشش تدریجی k-means، شبکۀ عصبی و شبیه‌سازی تبرید تولیدشد و جواب­های به‌دست‌آمده از هر سه روش تحلیل شد. زمان حل کمتر روشk-means نسبت به دو روش خوشه‌بندی شبکۀ عصبی و شبیه‌سازی تبرید با جواب‌های قابل قبول نسبت به خوشه‌بندی شبکۀ عصبی اثبات شد. الگوریتم شبیه‌سازی تبرید نسبت به روش‌های خوشه‌بندی جواب بهتری ارائه می­کند.در راستای این مقاله مثال کاربردی از کشورمان نیز تحلیلشد و نتایج به‌دست‌آمده از این مثال کاربردی کارایی روش خوشه‌بندی k-meansرا تأیید می‌کند.

برای مطالعات آتی، بررسی روش‌های خوشه‌بندی برای مسئلۀ پوشش تدریجی اشتراکی پیشنهاد می‌شود.

منابع

بشیری مهدی؛ حسینی‌جو. عباس؛ حسینی‌نژاد جواد. (1387). طراحیسیستم­های صنعتی، دانشگاه شاهد تهران..

Berman, O, Drezner, Z., & Dmitry, K. (2003).The gradualcovering decay location problem on a network.European Journal of Operational Research, 151,474-480.

Berman, O., Jörg, K., Dmitry, K., & Nickel S. (2009)."The Ordered Gradual Covering Location Problem on a Network", Discrete Applied Mathematics, 157, 3689-3707.

Berman, O., & Dmitry, K. (2002)."The generalized maximal covering location problem".Computers & Operations Research, 29, 563-581.

Farahani-Zanjirani, R., Asgari, N., Heidare. N., Hosseininia, M., & Goh, Mark.. (2012). "Covering problems in facility location: A review".Computers & Industrial Engineering, 62 (1) 368-407.

Drezner Z., Wesolowsky G., & Drezner T. (2004)."The gradual covering problem". Naval Research Logistics, 51, 841–855.

Berman O.,& Wang J. (2011).  "The minmax regret gradual covering location problem on a network withincomplete information of demand weight". European Journal of Operational Research Society, 208, 233–238.

Davari, S., M. H. Fazel Zarandi&Turksen., I. B. (2013). "The incomplete hub-covering location problem considering imprecise location of demands.".Scientia Iranica, 20.3 983-991.

Zarandi, M., Fazel, H.,Davari, S., & Haddad Sisakht. A. (2013)."The large-scale dynamic maximal covering location problem" Mathematical and Computer Modelling, 57.3, 710-719.

Sérgio B., Carlos F., José P., & Beatriz S., (2007)."Using clustering analysis in a capacitated location-routing problem". European Journal of Operational Research, 179, 968–977.

Sherali, H.D., & Desai, J. (2003)."A global optimization RLT-based approach for solving the hard clustering problem". Journal of Global Optimization. 32, 281–306.