نوع مقاله : مقاله پژوهشی
نویسندگان
1 دانشکده فنی- دانشگاه شاهد- تهران- ایران
2 دانشکده فنی- دانشگاه شاهد - تهران- ایران
چکیده
کلیدواژهها
عنوان مقاله [English]
نویسندگان [English]
In the recent covering studies it is assumed that the coverage is dependent to the distance from the service point and the coverage will be decreased by increasing the distance. Also in the large scaled problems the solution time will be growth exponentially by exact solution methods. In this paper three solution methods based on the simulated annealing, K-means clustering and clustering by artificial neural network are presented for the gradual covering location problem. Moreover the results by mentioned three solution methods were compared and analyzed. The results showed that the K-means clustering in gradual covering problem has reasonable results and computational time. The proposed method was analyzed more in a case study of Iran technical hospitals covering problem.
کلیدواژهها [English]
حل مسئلۀ پوشش تدریجی خدمات درمانی با شبیهسازی تبرید و روشهای خوشهبندیk-means و شبکۀ عصبی
مهدی بشیری1*، یونس گرمهای2، محسن یحیایی3
1- دانشیار، دانشکده فنی- دانشگاه شاهد- تهران- ایران
2- دانشجوی کارشناسیارشد، دانشکده فنی- دانشگاه شاهد - تهران- ایران
3- دانشجوی کارشناسیارشد، دانشکده فنی- دانشگاه شاهد - تهران- ایران
چکیده
در مسائل مکانیابی پوشش نوین، افزایش فاصله از تسهیل ارائهدهنده سرویس در ناحیۀ پوشش، موجب کمشدن سطح پوششدهی میشود و تحت عنوان پوشش تدریجی در نظر گرفته میشود، با ازدیاد نقاط تقاضا، زمان حل در اینگونه مسائل افزایش مییابد. لذا روشهای مختلف حل از جمله دقیق، فراابتکاری و ابتکاری برای مدلهای مختلف مسئلۀ پوشش تدریجی مطرح شده است. در این مقاله مسئلۀ پوشش تدریجی با استفاده از روشهای شبیهسازی تبرید، خوشهبندی شبکۀ عصبی و خوشهبندی k-means حل شده و جوابها و زمانهای بدستآمده از سه روش تحلیل شده است. نتایج بهدستآمده نشاندهندۀ کارایی روش k-means در حل مسئله است و این روش میتواند در مدتزمان قابلِقبول جوابهایی با دقت زیاد (نزدیک به جوابهای بهدستآمده از روش شبیهسازی تبرید) تولید کند. در ادامه کاربرد روشهای خوشهبندی در مسئلۀ پوشش تدریجی برای احداث بیمارستان تخصصی در ایران ارزیابی شده است و تسهیلات بهدستآمده با این روش به مکانهایی اختصاص داده شدهاند که بیشترین پوشش را دارا هستند.
واژههای کلیدی:خوشهبندیk-means ، شبکۀ عصبی، شبیهسازی تبرید، مسئلۀ مکانیابی پوشش تدریجی.
مقدمه
مفهوم پوشش بهعنوان زیر مجموعهای از مسائل مکانیابی کاربرد زیادی در زندگی روزمره ما دارد و مسائل زیادی همچون پوشش یک منطقه یا مناطق با ایستگاههای آتشنشانی، بیمارستانها، مراکز تعلیم و تربیت، مراکز رفاهی و ... درخور توجه بوده است. محققان همواره به دنبال حداکثر پوشش نقاط تقاضا با استفاده از حداقل تسهیلات (حداقل هزینه) هستند. مسئلۀ پوشش خود به دو زیرمجموعه پوشش کلی و پوشش جزئی تقسیم میشود. موضوعات عامالمنفعه بیشتر در پوشش کلیدرخور توجه قرار میگیرند و بهدنبال پوشش همۀ نقاط تقاضا هستند و هدف پیداکردن حداقل تعداد تسهیلات برای پوشش همۀ نقاط تقاضا است(بشیری و همکاران، 1387).
در سال 2003 پوشش تدریجی توسط برمن1 و همکاران مطرح شد. در مسئلۀ مکانیابی پوشش تدریجی حداقل دو شعاع پوششی مدنظر گرفته میشود بدینصورت که اگر مسافت مشتری از تسهیل، کمتر از شعاعی مانند شعاع کوچکتر باشد (d≤r)، پوشش کامل صورت خواهد گرفت؛چنانچه فاصلۀ مشتری تا تسهیل، بین شعاع کوچکتر و بزرگتر باشد (r<d≤u)، پوشش با تابع خاصی بر حسب میزان مسافت مشتری تا تسهیل در نظر گرفته میشود و اگر مسافت مشتری تا تسهیل بیش از شعاع بزرگتر باشد (d>u)، هیچگونه پوششی صورت نخواهد گرفت. برای حل مسئلۀ مکانیابی پوشش تدریجی به دنبال نقاطی هستیم که بتوانیم حداکثر پوشش را با قراردادن تسهیلات در آن نقاط بدست آوریم (برمن و همکاران، 2009). در تحقیقات انجامشده در خصوص مسئلۀ پوشش تدریجی،مدلهای مختلفی بررسیشده است که برخی از آنها عبارتاند از: پوشش تدریجی با استفاده از تابع خطی کاهنده (برمن و همکاران، 2002)؛ پوشش تدریجی با استفاده از تابع پوششی تقسیمبندی شده (فراهانی زنجیرانی و همکاران2، 2012)؛ پوشش تدریجی با استفاده از شعاع بیشینه و کمینۀ یکسان برای تمامی نقاط، مدل میانه ترتیبی پوشش تدریجی (دِرِزمَن3 و همکاران، 200) و مدل پوشش تدریجی با تقاضاهای تصادفی توزیع نامعلوم (برمن و وانگ، 2011).
باید به این نکته توجه داشت که مسئلۀ مکانیابی پوشش در سالهای اخیر بسیار پیشرفت کرده و با سایر مباحث از جمله مسائل مختلف مکانیابی ترکیب شده است (داوری4 و همکاران، 2013). روشهایی برای حل مسائل پوشش مطرح شده است که میتوان به روشهای دقیق مانند شاخه و کران، روشهای ابتکاری مانند الگوریتم ایگنزیو و روشهای فراابتکاری مانند شبیهسازی و شبکۀ عصبی اشاره کرد. در مسئلۀ پوشش تدریجی، با افزایش نقاط تقاضا، زمان حل بهشدت افزایش مییابد و در دنیای واقعی تعداد نقاط تقاضا زیاد است و در محققان در اکثر موارد از روشهای فراابتکاری برای حل اینگونه مسائل استفاده میشود (زرندی5 و همکاران، 2013). حال آنکه میتوان با استفاده از تکنیکهای ریاضی مانند خوشهبندی تعداد نقاط را طوری کاهش داد که در اصلِ مسئله تغییر چندانی اتفاق نیفتد و با صرف زمان کمتر جوابهای نسبتاً مناسبی به دست آورد (سرجیو6 و همکاران، 2007).
تکنیکهای زیادی برای خوشهبندی نقاط استفاده میشود؛ از جمله تکنیکهای مهم که اخیراً رواج پیدا کرده استفاده از شبکه عصبی و k-means برای حل مسائل مختلفبا تعداد نقاط زیاد تقاضا است (شرالی و دسایی7، 2003 و سرجیو و همکاران، 2007).
مطالعۀادبیاتتحقیقنشانمیدهداغلبمطالعاتگذشتهازروشهایکلاسیکفراابتکاری نظیر الگوریتمشبیهسازی تبرید برای حل مسئلۀپوششتدریجیاستفادهکردهاند. در این مقاله با بررسی و مقایسه بین روش فراابتکاری شبیهسازی تبرید و روشهای خوشهبندی شبکۀ عصبی وk-means نقاط ضعف و قوت هر سه روش بیان شده است. همچنین تأیید کارایی استفاده از روشk-means ازلحاظ کاربردی با خوشهبندی شهرهای ایران و تئوریباحلمسائلشبیهسازیشده اثبات گشته است. بهعبارتدیگرنوآوریاینتحقیقرامیتواندرپیشنهاداستفادهازروشهایخوشهبندی مبتنی بر شبکۀعصبی و k-means برای حل مسئلۀپوشش تدریجی دانست. پیشنهاد طراحی شبکه خدمات درمانی ایران بر اساس مسئلۀپوششتدریجیرابهعنواننوآوریدیگرمیتوانبرشمرد.
در بخش بعدی مقاله مسئلۀ مکانیابی پوشش تدریجی و تابع خطی کاهنده تشریح شده است؛ در بخش 3 مدل عمومی خوشهبندی بیان شده است؛ در بخش 4 روش انجام تحقیق با استفاده از فلوچارت و یک مثال مطرح شده است؛ در بخش 5 بهمنظور اثبات صحت روشهای حل الگوریتم شبیهسازی تبرید بهکاررفته در مقاله توضیح داده شده و با روش دقیقمقایسه شده است؛ در بخش 6پس از اثبات صحت جوابهای بهدستآمده از طریق شبیهسازی تبرید، مقایسهای بین سه روش و ویژگیهای این روشها بیان شده است؛ در بخش 7 کاربرد مسئله پوشش تدریجی برای احداث بیمارستان تخصصی در کشور ایران و حل مسئله با سه روش شبکه عصبی،k-means و شبیهسازی تبرید بیان شده و در بخش پایانی نتیجهگیریبیان شده است.
مدل مسئلۀ مکان یابی پوشش تدریجی
در مدل پوشش تدریجی هدف، تعیین محل نقاطی است که بیشترین سطح پوشش را نسبت به سایر نقاط دارا هستند (سطح پوشش با پارامتر cij نمایش داده میشود).
پارامترcijبه صورت رابطۀ (1) تعریف میشود:
|
|
if dij< li |
wi |
|
|
(1) |
if li<dij ≤ui |
wi fi (dij) |
Cij= |
|
|
if dij>ui |
0 |
|
رابطۀ (1) بیانکنندۀ این مهم است که اگر فاصله مشتری i از تسهیلj، کمتر از شعاع پوششی تسهیلjباشد، سطح پوشش برابر با وزن نقطهای است که نقطه i در آن قرار گرفته است. اگر مسافت مشتری بین شعاع کوچکتر و بزرگتر باشد، سطح پوشش برابر است با وزن (تقاضا) نقطه i در تابعی که به مسافت مشتری تا تسهیل بستگی دارد و اگر فاصله بیش از شعاع بزرگتر باشد، سطح پوشش برابر صفر خواهد بود. مدل اصلی مسئلۀ پوشش تدریجی بهصورت زیر است (برمن و همکاران، 2003):
|
(2) |
|
|
|
|
|
(3) |
|
|
(4) |
xij≤yj |
|
(5) |
|
|
(6) |
yj,xij{0,1} i,j = 1,…,n |
هدف این مدل بیشینه کردن سطح پوشش است. محدودیت (3) بیانکنندۀ تعداد تسهیلاتی است که باید جایابی شوند. محدودیت (4) این اطمینان را حاصل میکند که نقاط میتوانند فقط با تسهیلی پوشیده شوندکه در مکان jآن تسهیل وجود دارد. محدودیت (5) بیان میکند که هر مکان فقط بهوسیلۀ یک تسهیل خاص پوشانده میشود. محدودیت (6) نشاندهندۀ صفرویکبودن متغیرهای تصمیم مسئله است. متغیرy اگر مقدار 1 بگیرد نشاندهنده این است که تسهیل در آن نقطه قرار میگیرد و اگر صفر باشد هیچ تسهیلی در آن نقطه قرار نمیگیرد. متغیرx زمانی 1 است که نقطه iتوسط تسهیلی که در نقطه jقرار دارد پوشانیده شود. مدل گفتهشده همان مدل مسئلۀ پوشش است؛ با این تفاوت که به جای کمینهکردن مسافت در تابع هدف از پارامتر سطح پوشش با هدف بیشینهکردن آن استفاده شده است.
یکی از روشهای متداول در مسئلۀ پوشش تدریجی برای بهدستآوردن سطح پوشش، استفاده از تابع کاهنده خطی است (برمن و همکاران، 2003).
|
(7) |
در رابطۀ (7)، =max d(i,j)α است. در این مقاله از رویکرد تابع خطی کاهنده برای بهدستآوردن سطح پوششدهی استفاده شده است.
مدل عمومی خوشهبندی
درمدل عمومی خوشهبندی، هدف تعیینpخوشه برای تخصیص تمام نقاط به این pخوشه است و هر نقطۀ aiÎ (xi,yi)با توجه به خصوصیتهای مشترکی که با سایر نقاط دارد در یک خوشۀ منحصربهفرد قرار میگیرد. تابع هدف این مدل، فاصلۀ هر یک از نقاط را تا مراکز خوشهها حداقل میکند. در مدل زیر مراکز خوشهها با ζk در فضای دوبعدی مشخص شده است و xik زمانی برابر با 1 است که نقطه i به خوشۀ kتخصیص داده شود (شرالی و دسایی، 2003).
|
(8) |
|
|
|
St: |
|
(9) |
|
|
(10) |
|
|
(11) |
محدودیت (9) و (10) این اطمینان را حاصل میسازد که هر نقطه، فقط به یک خوشه اختصاص داده میشود.
روش انجام تحقیق
در این مقاله مسئلۀ پوشش تدریجی با استفاده از سه رویکرد شبیهسازی تبرید، خوشهبندی شبکۀ عصبی و خوشهبندی k-means حل شده است. در روشهای شبکۀ عصبی و k-means خوشهبندی براساس فاصله نقاط از یکدیگر انجام گرفته و نقطهای که بیشترین سطح پوشش تدریجی را در هر خوشه داراست، بهعنوان محل قرارگیری تسهیل مدنظر قرار گرفته است. گفتنی است که در هر خوشه، یک مسئلۀ پوشش تدریجی از یک طرف با درنظرگرفتن یک تسهیل برای احداث با استفاده از روابط 2 تا 6 حل شده است و در طرف دیگر مسئلۀ پوشش تدریجی با استفاده از شبیهسازی تبرید با درنظرگرفتن تعداد خوشهها بهعنوان تعداد تسهیلاتی که میتوانیم احداث کنیم، حل شده است. در شکل (1) نحوۀ انجام آن بهصورت فلوچارت نمایش داده شده است.
شکل (1) فلوچارت حل مسئله پوشش تدریجی با شبیه سازی تبرید و روشهای خوشبندی
برای بیان بهتر روش حل و مقایسه بین جوابهای گرفتهشده از روشهای حل ارائهشده در مقاله و حل دقیق، مثال زیر بر اساس اطلاعات مندرج در شبکه نقاط شکل (2) بررسی میشود. گفتنی است حل دقیق مسئله با استفاده از نرمافزارGAMS و حلکنندهCPLEX انجام گرفته است.
شکل (2) شبکه مسافت بین نقاط تقاضا در مثال بررسیشده
فرض کنید شعاع پوششی کوچکتر برابر 5، شعاع پوششی بزرگتر برابر 7 و وزن نقاط تقاضا یکسان است. در جدول (1) سطح پوششدهی بین نقاط مشخص شده است.
جدول(1) سطح پوششدهی با استفاده از تابع خطی کاهنده در مثال بررسیشده
|
C(i,j) |
1 |
2 |
3 |
4 |
5 |
|
1 |
1 |
1 |
0 |
1 |
0 |
|
2 |
1 |
1 |
978/0 |
0 |
981/0 |
|
3 |
0 |
97/0 |
1 |
0 |
1 |
|
4 |
1 |
0 |
0 |
1 |
0 |
|
5 |
0 |
98/0 |
1 |
0 |
1 |
اگر تعداد تسهیل که احداث خواهد شد (تعداد خوشهها)، برابر با 2 باشد، همانطور که با توجه به فواصل نیز مشخص است، خوشهبندی با روشهای k-means و شبکۀ عصبی بدینصورت است که نقاط 1، 2 و 4 در یک خوشه و نقاط 3 و5 در خوشۀ دیگر قرار میگیرند و درنتیجۀ حل جداگانه در خوشهها نقطه 1 در خوشۀ اول و نقاط 5 و 3 در خوشۀ دوم هر دو مناسب قرارگیری تسهیل هستند و درنتیجۀ این جواب تمامی نقاط پوشش داده میشوند. بهوسیلۀ حل این مسئله با روش دقیق و شبیهسازی تبرید که در بخش بعد در مورد آن توضیح داده میشود، جواب قرارگیری تسهیلات، نقاط 1 و 3 است که در این حالت نیز تمامی نقاط بهوسیلۀ دو تسهیل پوشش داده میشوند؛ بنابراین در تمامی روشها جواب مثال یکسان است.
الگوریتم شیبهسازی تبرید و مقایسه آن با جواب بهدستآمده از حل دقیق
در مدل پیشنهادی برای تولید جواب اولیه (y) ابتدا پارامترها و مکان قرارگیری تسهیلات به صورت تصادفی مشخص میشود. سپس با توجه به فواصل نقاط از یکدیگر و شعاع پوششی تسهیلات در دورههای زمانی مختلف، سطح پوشش با استفاده از تابع خطی کاهنده محاسبه میشود. در ادامه تابع هدف مدل (z)، یعنی پوشش تدریجی مشتریان برای تسهیلات، با توجه به مکان قرارگیری محاسبه میشود.
شکل (3) الگوریتمشبیهسازی تبرید برای مسئلۀپوشش تدریجی
فلوچارت الگوریتم شبیهسازی تبرید بهکاررفته در مقاله در شکل (3) نمایش داده شده است. با توجه به اینکه آزمایشها به بهترین ترکیب وضعیت پارامترها برای بهدستآوردن جواب طراحی شده است، پارامترهای استفادهشده در این کد در مناسبترین زمان حل به کار گرفته میشود. بدینمنظور از آزمایش تاگوچیL16(4**5)و با استفاده از نرمافزار minitab پنج پارامتر دخیل در الگوریتم شبیهسازی تبرید در چهار سطح و شانزده تکرار استفاده شده است. در جدول (2) پارامترها و سطوح مختلف آزمایش نشان داده شده است.
جدول (2) سطوح و پارامترهای استفادهشده شبیهسازی تبرید در آزمایش تاگوچی
|
پارامترها |
سطوح |
||||
|
nlimit |
nover |
tf |
f |
t0 |
|
|
60 |
15 |
100 |
95/0 |
05/0 |
1 |
|
40 |
10 |
80 |
85/0 |
1/0 |
2 |
|
50 |
5 |
120 |
75/0 |
01/0 |
3 |
|
30 |
20 |
70 |
65/0 |
5/0 |
4 |
در جدول(3) جوابهای بهدستآمده در این شانزده تکرار، چه در حوزۀ زمان و چه در حوزۀ جواب مدل نمایش داده شده است.
جدول (3) جوابهای تاگوچی در تکرارهای شبیهسازی تبرید
|
زمان (Time) |
تابع هدف (z) |
پارامترها |
تکرار |
||||
|
nlimit |
nover |
tf |
f |
t0 |
|||
|
06/714 |
6167/72 |
2 |
4 |
1 |
1 |
1 |
1 |
|
13/428 |
2821/72 |
3 |
2 |
2 |
2 |
1 |
2 |
|
46/368 |
8284/72 |
4 |
1 |
3 |
3 |
1 |
3 |
|
88/288 |
1169/71 |
3 |
4 |
4 |
4 |
1 |
4 |
|
19/2098 |
4473/74 |
4 |
3 |
4 |
1 |
2 |
5 |
|
207/51 |
3602/71 |
1 |
3 |
3 |
2 |
2 |
6 |
|
98/429 |
7356/71 |
2 |
4 |
2 |
3 |
2 |
7 |
|
15/231 |
0362/72 |
4 |
1 |
1 |
4 |
2 |
8 |
|
63/2381 |
4473/74 |
3 |
2 |
2 |
1 |
3 |
9 |
|
76/1089 |
9672/72 |
2 |
4 |
1 |
2 |
3 |
10 |
|
63/138 |
7466/70 |
1 |
3 |
4 |
3 |
3 |
11 |
|
77/207 |
7051/72 |
2 |
2 |
3 |
4 |
3 |
12 |
|
81/2024 |
9079/73 |
1 |
1 |
3 |
1 |
4 |
13 |
|
44/418 |
7103/71 |
4 |
4 |
4 |
2 |
4 |
14 |
|
47/169 |
5696/71 |
3 |
2 |
1 |
3 |
4 |
15 |
|
16/54 |
7429/70 |
2 |
1 |
2 |
4 |
4 |
16 |
در شکل (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) پارامترهای شبیهسازی تبرید استفاده شده در تحقیق
|
nlimit |
Nover |
Tf |
f |
t0 |
|
50 |
5 |
100 |
95/0 |
05/0 |
برای تایید صحت الگوریتم شبیهسازی تبرید در جدول (5) بین مسئله پوشش تدریجی حل شده با روش دقیقو حل مسئله پوشش تدریجی با استفاده از شبیهسازی تبریدمقایسهای در رابطه با تابع هدف انجام شده است. در جدول (5) شماره مثالها (no)، تعداد نقاط (n)، تعداد تسهیلات (P)، مکان قرارگیری تسهیلات (y) و تابع هدف (z) نمایش داده شده است. تابع هدف برای هر دو روش یکسان است که این امر حاکی از مناسب بودن الگوریتم شبیهسازی تبرید است.
جدول (5) مقایسه بین جوابهای بهدستآمده از دو روش حل دقیق و الگوریتم شبیهسازی تبرید
|
|
|
حل مسئلۀ پوشش تدریجیبا شبیهسازی تبرید |
حل مسئلۀ پوشش تدریجیبا حل دقیق |
|||
|
No |
N |
P |
Y |
Z |
Y |
Z |
|
1 |
10 |
1 |
10 |
04/6 |
10 |
04/6 |
|
2 |
2 |
1،10 |
54/8 |
1،10 |
54/8 |
|
|
3 |
3 |
1،2،10 |
32/9 |
1،2،10 |
32/9 |
|
|
4 |
20 |
1 |
20 |
77/12 |
20 |
77/12 |
|
5 |
2 |
16،17 |
68/17 |
16،17 |
68/17 |
|
|
6 |
3 |
18،19،20 |
70/19 |
18،19،20 |
70/19 |
|
|
7 |
5 |
1،5،17،18،20 |
20 |
1،5،17،18،20 |
20 |
|
|
8 |
30 |
1 |
29 |
67/10 |
29 |
67/10 |
|
9 |
2 |
1،24 |
45/17 |
1،24 |
45/17 |
|
|
10 |
3 |
1،13،24 |
25/23 |
1،13،24 |
25/23 |
|
|
11 |
5 |
2،10،12،13،28 |
25 |
2،10،12،13،28 |
25 |
|
مقایسۀ نتایج سه الگوریتم پیشنهادی برای مسئلۀ پوشش تدریجی
پس از اثبات صحت الگوریتم شبیهسازی تبرید، مقایسه بین شبیهسازی تبرید، k-means و شبکۀ عصبی انجام میگیرد. دادههای این مقاله با اعداد تصادفی در گروههای 10، 50، 100 و 500تایی در بازۀ (0 و 200) تولید شدهاند. با استفاده از روشهای k-means و شبکۀ عصبی این دادهها در خوشههای 2، 4 و 9تایی (تعداد تسهیلات) تقسیم شدهاند. در درون هر خوشه فاصلۀ بین نقاط بهصورت اقلیدسی محاسبه شده است. آنگاه با درنظرگرفتن شعاع کوچکتر 50 و شعاع بزرگتر 150برای هر تسهیل مسئلۀ پوشش تدریجی با استفاده از تابع خطی کاهنده در هر خوشه حل شده و بهترین نقطه برای احداث تسهیل مشخص شده است. حل مسئلۀ پوشش تدریجی نتایج حاصل از جوابهای بهدستآمده از سه روش k-means، شبکۀ عصبی و شبیهسازی تبرید در جدول (6) نمایش داده شده است. ستون اول نشاندهندۀ تعداد نقاط بررسیشده است؛ در ستون دوم تعداد تسهیلات مشخص شده و در ستونهای بعدی تابع هدف بهدستآمده از هر خوشه و همچنین تابع هدف پوشش کل که از طریق نقاط بهدستآمده، محاسبه شدهاند، نمایش داده شده است.
جدول (6) مقایسۀ زمان و جواب تابع هدف بین سه روش شبیهسازی تبرید، شبکۀ عصبی و k-means در مسئلۀ پوشش تدریجی
|
شبیهسازی تبرید |
شبکۀ عصبی |
k-means |
|
||||||||
|
Z |
Y |
Z کل |
Z |
Y |
تعداد نقاط |
Z کل |
Z |
y |
تعداد نقاط |
Pp |
تعداد نقاط |
|
5493/8 |
1 |
5493/8 |
2 |
1 |
3 |
5493/8 |
2 |
1 |
3 |
22 |
10 |
|
10 |
7846/4 |
10 |
7 |
7846/4 |
10 |
7 |
|||||
|
9359/41 |
19 |
3456/34 |
604/22 |
48 |
30 |
8652/41 |
129/19 |
19 |
27 |
22 |
50 |
|
40 |
016/15 |
15 |
20 |
927/15 |
49 |
23 |
|||||
|
8017/79 |
70 |
029/71 |
402/35 |
77 |
62 |
3479/72 |
028/35 |
47 |
67 |
22 |
100 |
|
96 |
299/31 |
15 |
38 |
358/30 |
38 |
43 |
|||||
|
5566/93 |
13 |
4250/88 |
605/21 |
100 |
31 |
9070/89 |
126/19 |
38 |
27 |
44 |
|
|
49 |
700/20 |
38 |
27 |
536/18 |
7 |
27 |
|||||
|
67 |
303/17 |
67 |
25 |
198/21 |
14 |
31 |
|||||
|
95 |
596/11 |
98 |
17 |
991/11 |
54 |
15 |
|||||
|
9868/366 |
214 |
073/354 |
894/132 |
411 |
229 |
8835/370 |
444/149 |
167 |
256 |
22 |
500 |
|
458 |
017/159 |
281 |
271 |
941/143 |
467 |
244 |
|||||
|
4025/447 |
6 |
3348/434 |
821/89 |
48 |
144 |
9748/383 |
326/79 |
167 |
126 |
44 |
|
|
85 |
804/77 |
221 |
122 |
715/68 |
31 |
112 |
|||||
|
170 |
191/78 |
453 |
126 |
805/77 |
14 |
127 |
|||||
|
393 |
959/62 |
124 |
104 |
681/84 |
385 |
136 |
|||||
|
8150/494 |
3 |
3498/481 |
523/41 |
382 |
65 |
4933/485 |
473/34 |
371 |
57 |
94 |
|
|
122 |
081/22 |
43 |
32 |
120/38 |
358 |
58 |
|||||
|
169 |
432/45 |
410 |
88 |
772/39 |
36 |
63 |
|||||
|
179 |
787/15 |
184 |
23 |
277/39 |
418 |
56 |
|||||
|
184 |
945/39 |
377 |
59 |
435/40 |
399 |
60 |
|||||
|
312 |
676/43 |
412 |
77 |
222/34 |
72 |
54 |
|||||
|
324 |
051/12 |
189 |
16 |
961/33 |
333 |
50 |
|||||
|
400 |
237/16 |
355 |
24 |
528/38 |
305 |
60 |
|||||
|
453 |
354/68 |
174 |
116 |
154/29 |
339 |
42 |
|||||
زمانهای حل مسئلۀ پوشش تدریجی با استفاده از سه روش شبکۀ عصبی، شبیهسازی تبرید و 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 تسهیل با استفاده از خوشهبندی شبکۀ عصبی
|
تابع هدف کل |
زمان (ثانیه) |
تابع هدف هر خوشه |
مختصات نقاط بهدستآمده برای احداث بیمارستان تخصصی در هر خوشه |
تعداد نقاط در هر خوشه |
نام هر خوشه |
تعداد خوشه |
|
757/205 |
420/2 |
440/22 |
رودبار |
28 |
A |
9 |
|
555/1 |
384/3 |
جیرفت |
11 |
B |
||
|
552/4 |
361/20 |
باغملک |
38 |
C |
||
|
614/2 |
181/22 |
کرمانشاه |
31 |
D |
||
|
510/2 |
831/12 |
فیروزآباد |
31 |
E |
||
|
007/3 |
397/21 |
قم |
32 |
F |
||
|
566/2 |
829/24 |
مراغه |
36 |
G |
||
|
626/2 |
924/14 |
تربت حیدریه |
29 |
H |
||
|
147/2 |
233/20 |
گلوگاه |
26 |
K |
در شکل (10) خوشهبندی شهرهای ایران با استفاده از k-means برای احداث 9 بیمارستان تخصصی انجام شده است.
در جدول (8) جوابهای بهدستآمده از روش k-means، به تعداد 9 خوشه نمایش داده شده است. نتایج بهدستآمده از این جدول نشان میدهد که پوششبهدستآمده از روشk-meansجواب بهتری نسبت به شبکۀ عصبی در حل مسئلۀ پوشش تدریجی ارائه میکند.
شکل (10) خوشهبندی 9تایی شهرهای ایران با استفاده از k-means
جدول (8) حل مسئلۀ پوشش تدریجیِ مسئلۀ مکانیابی بیمارستان تخصصی با 9 تسهیل با استفاده از خوشهبندی k-means
|
تابع هدف کل |
زمان (ثانیه) |
تابع هدف هر خوشه |
مختصات نقاط بهدستآمده برای احداث بیمارستان تخصصی در هر خوشه |
تعداد نقاط در هر خوشه |
نام هر خوشه |
تعداد خوشه |
|
600/207 |
619/3 |
158/19 |
رشت |
24 |
A |
9 |
|
341/2 |
427/14 |
مرودشت |
30 |
B |
||
|
723/2 |
934/23 |
ابهر |
42 |
C |
||
|
358/2 |
456/22 |
کرمانشاه |
29 |
D |
||
|
328/2 |
795/19 |
گلوگاه |
25 |
E |
||
|
432/2 |
259/8 |
راور |
19 |
F |
||
|
416/2 |
862/23 |
شیراز |
34 |
G |
||
|
364/2 |
413/22 |
جلفا |
30 |
H |
||
|
488/2 |
878/14 |
تربت حیدریه |
29 |
K |
جدول (9) حل مسئلۀ پوشش تدریجیِ مسئلۀ مکانیابی بیمارستان تخصصی با 9 تسهیل با استفاده از شبیهسازی تبرید
|
زمان (ثانیه) |
تابع هدف |
مختصات نقاط بهدستآمده برای احداث بیمارستان تخصصی در هر خوشه |
تعداد نقاط |
تعداد تسهیلات |
|
597/21 |
304/213 |
مراغه |
262 |
9 |
|
تربت حیدریه |
||||
|
اراک |
||||
|
اصفهان |
||||
|
قم |
||||
|
راور |
||||
|
کرمانشاه |
||||
|
آستانۀ اشرفیه |
||||
|
گلوگاه |
مسئلۀ دوم با فرض تعداد بیمارستان تخصصی برابر با 4 در نظر گرفته شده است و مابقی فرضها همچنان به قوت خود باقی هستند. نتایج بهدستآمده در این مسئله از سه روش، نسبت به مسئلۀ اول اختلاف بیشتری دارند و این موضوع بیانگر این مهم است که با کاهش بیمارستانهای تخصصی (تعداد تسهیلات) دقت جوابهای بهدستآمده از روشهای خوشهبندی کاهش مییابد.
جدول (10) حل مسئلۀ پوشش تدریجیِ مسئلۀ مکانیابی بیمارستان تخصصی با 4 تسهیل با استفاده از خوشهبندی شبکۀ عصبی
|
تابع هدف کل |
زمان (ثانیه) |
تابع هدف هر خوشه |
مختصات نقاط بهدستآمده برای احداث بیمارستان تخصصی در هر خوشه |
تعداد نقاط در هر خوشه |
نام هر خوشه |
تعداد خوشه |
|
334/118 |
042/2 |
932/17 |
تربت حیدریه |
40 |
A |
4 |
|
601/12 |
489/31 |
نوشهر |
64 |
B |
||
|
642/18 |
335/22 |
باغملک |
68 |
C |
||
|
311/29 |
455/27 |
مراغه |
84 |
D |
جدول (11) حل مسئلۀ پوشش تدریجیِ مسئلۀ مکانیابی بیمارستان تخصصی با 4 تسهیل با استفاده از خوشهبندی k-means
|
تابع هدف کل |
زمان (ثانیه) |
تابع هدف هر خوشه |
مختصات نقاط بهدستآمده برای احداث بیمارستان تخصصی در هر خوشه |
تعداد نقاط در هر خوشه |
نام هر خوشه |
تعداد خوشه |
|
146/119 |
753/7 |
932/17 |
تربت حیدریه |
48 |
A |
4 |
|
202/15 |
612/24 |
باغملک |
64 |
B |
||
|
560/26 |
455/27 |
مراغه |
79 |
C |
||
|
581/19 |
250/37 |
تهران |
71 |
D |
جدول (12) حل مسئلۀ پوشش تدریجیِ مسئلۀ مکانیابی بیمارستان تخصصی با 4 تسهیل با استفاده از شبیهسازی تبرید
|
تابع هدف |
زمان (ثانیه) |
مختصات نقاط بهدستآمده برای احداث بیمارستان تخصصی در هر خوشه |
تعداد نقاط |
تعدادتسهیلات |
|
783/134 |
04/12 |
مراغه |
262 |
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.
پینوشت
1 Berman
2 Farahani-Zanjirani
3 Drezner
4 Davari
5 Zarandi
6 Sérgio
7 Sherali & Desai
)