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

نوع مقاله: مقاله پژوهشی

نویسندگان

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

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

چکیده

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

کلیدواژه‌ها


عنوان مقاله [English]

Solving Gradual Govering of Healthcare Services by Simulated Annealing and K-means and Artificial Neural Network Clustering Methods

نویسندگان [English]

  • Mehdi Bashiri 1
  • Yoones Garmeyi 2
  • Mohsen Yahyayi 2
1 Faculty of Engineering, University of Shahed, Tehran, Iran
2 Faculty of Engineering, University of Shahed, Tehran, Iran
چکیده [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 Clustering
  • artificial neural network
  • Simulated Annealing
  • Gradual Covering Location Problem

حل مسئلۀ پوشش تدریجی خدمات درمانی با شبیه‌سازی تبرید و روش‌های خوشه‌بندی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

 

 

 

 

بشیری مهدی؛ حسینی‌جو. عباس؛ حسینی‌نژاد جواد. (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.