بخشی از مقاله
به کارگیري الگوریتم تبرید تدریجی در مکانیابی مراکز فوریتهاي
پزشکی
چکیده
امروزه کاهش تلفات جادهاي به عنوان یک هدف استراتژیک در برنامه ریزيهاي کلان بسیاري از کشورها شناخته مـیشـود. محـل استقرار پایگاههاي خدمات فوریتهاي پزشکی نقش بسیار مهمی در عملکرد بهینه آمبولانسها بـه منظـور نجـات جـان بیمـاران اورژانس ایفا میکند. در مسئله مکانیابی مراکز فوریتهاي پزشکی، هدف استفاده از کمترین تعداد آمبولانس به منظور رسیدن بـه پوشش حداکثري نقاط تقاضا است. براي حل چنین مسائلی با استفاده از الگوریتمهاي متاهیوریستیک میتوان به جوابهاي بسـیار نزدیک به جواب بهینه (Local Optimum) در زمان معقولی دست یافت. در این مقاله شیوه تازهاي از به کارگیري الگـوریتم شـبیه سازي تبرید تدریجی (Simulated Annealing-SA) در حل مسائل مکانیابی مراکز فوریتهاي پزشکی ارائه میگردد. اصـولا اکثـر
الگوریتمهاي متاهیوریستیک با الگوگیري و شبیهسازي یکی از قوانین یا روابط موجود در طبیعت بنا نهاده میشوند. الگوریتم تبرید تدریجی با الهام گیري از فرآیند تبرید یا بازپخت فلزات ایجاد و در حل مسائل مختلف بهینه سازي به کارگیري شده است. آنچه در این مقاله آمده است، اعمال این روش موفق بهینه سازي براي حل یک مسئله گسسته مکانیابی است. نتایج کار با نتایج الگـوریتم ژنتیک مقایسه شده و حاکی از موفقیت روش ارائه شده در حل مسائل مکانیابی مراکز فوریتهاي پزشکی بوده است.
کلمات کلیدي
مکانیابی پایگاههاي خدمات فوریت هاي پزشکی، الگوریتم شبیه سازي تبرید تدریجی
-1 مقدمه
معمولاً در سیستمهاي پیچیده تعداد زیادي مسئله ایجاد میشـود کـه داراي طبیعت ترکیبی (Combinatorial) استمثلاً. مسیر وسایل حمل و نقل باید تعیین شود، انبارهـا، نقـاط فـروش محصـولات و یـا مراکـز خدماتی و امنیتی باید جایابی شوند، شبکههاي ارتباطی بایـد طراحـی شوند؛ همگی این مسائل پیچیده و از نوع ترکیبی هستند. ایـن مسـائل در اندازههاي کـاربردي و عملـی خـود بـه قـدري بـزرگ هسـتند کـه نمــیتــوان جــواب بهینــه آنهــا را در مــدت زمــان قابــل پــذیرش
(Polynomial Run-Time) به دست آورد. با این وجود، ایـن مسـائل باید حـل شـوند و بنـابراین چـاره اي نیسـت کـه بـه جـوابهـاي زیـر بهینه((Suboptimal و یا بهینههاي محلـی (Local Optima) بسـنده نمود به گونهاي که داراي کیفیت قابل پذیرش بـوده و در مـدت زمـان قابل پذیرش به دست آیند. ما در این مقالـه در بخـش اول بـه توضـیح مسئله مکان یابی مراکز فوریتهاي پزشـکی پرداختـه و در بخـش دوم الگوریتم شبیه سازي تبرید تدریجی را معرفی نموده و در بخـش سـوم نحوه حل مسئله مکانیابی مراکز فوریتهاي پزشکی به کمک الگوریتم شبیه سازي تبرید تدریجی را توضیح میدهیم.
-2 مسئله مکانیابی مراکز فوریتهاي پزشکی
گــزارش مشــترك ســازمان بهداشــت جهــانی و بانــک جهــانی در خصوص پیشگیري از صدمات ناشی از تصادفات جـاده اي، مصـرانه بـر این نکته تاکید دارد که تلفات ترافیکی قابل پیشگیري انـد و کشـورها باید این پیشگیريها را در برنامه ریزيهاي کلان خود اعمال کنند. هم اکنون کاهش تلفات جادهاي به عنوان یک هدف اسـتراتژیک در برنامـه ریزي هاي بسیاري از کشورها شناخته میشود. در کشورهاي مختلـف جهان براي کاستن از عوارض و مرگ و میر ناشی از بیماريها و حوادث اورژانس، سیستمی موفق و کارآمد با عنـوان " خـدمات فوریـتهـاي پزشکی یا " (Emergency Medical Service) EMS طراحی شـده است که وظیفه این سیستم، ارائـه خـدمات درمـانی بربـالین بیمـار در موارد اورژانس و درصورت نیاز انتقال به مراکز درمانی است. با توجه به رشـد جمعیـت، کمبــود امکانــات و ظرفیـت محــدود پاســخگوئی ایـن سیستم، لازم است تدابیري در این زمینه اندیشـیده شـود تـا حتـی بـا امکانات موجود نیز بتوان از عـوارض و مـرگ و میـر بیمـاران اورژانـس جلوگیري کرد. محل پایگاههاي خدمات فوریتهاي پزشکی نقش بسیار اساسی در کاهش زمان پاسخ آنها دارد که ایـن کـاهش زمـان پاسـخ عامل مهمی در نجات جان بیماران اورژانـس خواهـد بـود. بـه منظـور مکانیابی پایگاههاي فوریتهاي پزشکی و تعیین تعداد آمبولانس مورد نیاز در هر مکان، از مدلهاي مکانیابی استفاده میشود. در این مدلها معمولاً نقاط تقاضا از هم فزون سازي تقاضاي مناطق مختلف (مثلا بـر حسب تعداد تماس در هر روز) بدست میآید و مکان هایی که امکـان احداث پایگاههاي خدمات فوریتهاي پزشکی در آنهـا وجـود دارد، بـه عنوان نقاط پیشنهادي اولیه (پتانسیل) ارائه میشوند و سعی میشـود با کمترین تعداد ایستگاه (آمبـولانس) بیشـترین پوشـش نقـاط تقاضـا
صورت گیرد.
حداکثر فاصله (زمان) قابل قبول بین یک پایگاه خدمات فوریـت-هاي پزشکی و یک نقطه تقاضـا بـراي سـرویس دهـی بـه آن، پـارامتر مهمی است که در کشور هاي مختلف مقادیر متفاوتی براي آن در نظر گرفته میشود. این مقادیر در شبکههاي برون شـهري و درون شـهري نیز متفاوت است. پارامتر حـائز اهمیـت دیگـر مطـرح در ایـن زمینـه، قابلیت اطمینان مورد انتظار براي سرویسدهی به نقاط مختلف تقاضا با حداکثر فاصله ( زمان) قابل قبول مشخص است. در کشورهاي مختلف مقادیر متفاوتی براي قابلیت اطمینان مورد انتظـار سـرویس دهـی در شبکههاي درون شهري و برون شهري در حداکثر فاصله (زمـان) قابـل قبول مشخص، وجود دارد. در ایران، وزارت بهداشت، درمان و آمـوزش پزشــکی موظــف اســت ضــمن حضــور در تمــامی حــوادث راننــدگی اطلاعرسانی شده، زمان رسیدن بر بالین مصدوم را در شهرها در هشتاد درصد (%80) موارد (قابلیـت اطمینـان مـورد انتظـار) بـه کمتـر از 8 دقیقه(حداکثر زمان قابل قبول بـراي رسـیدن بـه محـل حادثـه) و در جادهها در هشتاد درصد (%80) موارد به کمتر از 15 دقیقه برساند.
به منظور مکانیابی مراکز امدادرسانی در این مقاله از مـدل ارائـه شده در پایان نامه " ارائه مدل براي مکانیابی مراکز امدادرسانی جهت تامین قابلیت اطمینان موردنظر " [1] استفاده شده است. این مـدل از نوع خطی باینري است و تابع هدف، تعـداد آمبـولانسهـاي اختصـاص یافته در پایگاهها را براي پوشش نقاط تقاضا کمینه مـیکنـد. در مـدل ضریب اشغال به این صـورت محاسـبه مـیشـود: »جمـع مـدت زمـان تخمینی ماموریتها براي یک نقطه تقاضا « تقسـیم بـر »تعـداد کـل آمبولانسهاي قابل دسترس آن نقطه .« لازم به ذکر است کـه در ایـن مدل ضریب اشغال آمبولانسها از پیش محاسبه نمـیشـود، بلکـه حـد بالایی براي آن تعیین می گردد و مدل به گونهاي طراحی شده است که این حد بالا به صورت محدودیت مسئله براي تمام آمبولانسهـایی کـه انتخاب خواهند شد، تعریف می شـود و بـه ایـن ترتیـب اگـر در سـطح قابلیت اطمینان مورد نظر ، تعداد حداقل f آمبولانس بـراي پوشـش نقاط در بازه استاندارد لحاظ شده باشد، قابلیت اطمینـان پوشـش هـر نقطه تقاضا حتماً بزرگتر یا مساوي با مقدار معین خواهد بود. تـابع
هدف و محدودیتهاي مدل مذکور به صورت زیر است:
تابع هدف: کمینه کردن تعداد آمبولانس بکار گرفته شـده بـراي تامین پوشش امدادي در زمان استاندارد و با قابلیت اطمینان بـراي همه نقاط تقاضا.
محدودیتها : (1 تضمین میکند که ضـریب اشـغال تمـام پایگـاه هاي انتخاب شده از مقدار ضریب اشغال تعیین شده کمتر خواهد بود.
(2 رابطه بین استقرار یک پایگاه و آمبولانسهاي مستقر شـده در آن را نشان میدهد.
(3 حداقل آمبولانسی که باید هـر نقطـه تقاضـا را پوشـش دهـد، تضمین میکند.
(4 صفر و یک بودن مقدار متغیر ها را تضمین میکند.
-1-2 پیشینه حل مسئله مکانیابی به کمک الگوریتم هاي متاهیوریستیک
از الگوریتمهاي متاهیوریستیک مختلـف در حـل مسـئله مکـان یـابی استفاده شده است. به عنوان مثال نمونههـاي فراوانـی از بـه کـارگیري الگوریتم ژنتیک در مسائل مختلف مکانیابی وجود دارد . بیسلی و چـو [3] در سال 1996 از الگوریتم ژنتیک بـراي حـل یـک مسـئله سـاده مکانیابی استفاده و به نتایج قابل قبولی دست پیدا کردند. آیکلین [ 4] در سال 2002 نوع خاصی از الگوریتم ژنتیک را براي حل این مسئله به کار گرفت. جیا و همکاران [5] نیز در سال 2007 الگوریتم ژنتیک را با روشهاي ابتکاري دیگر براي حـل مـدل پیشـنهادي خـود مقایسـه نمودند.
الگوریتم شبیه سازي تبرید تدریجی در مسائل مکانیابی، هـم بـه تنهایی و هم به صورت ترکیبی کاربرد فراوانی داشته اسـت. بـه عنـوان مثال موراي و چرچ [6] در سال 1996 از آن بـراي حـل یـک مسـئله ساده مکانیابی استفاده کردند. ماروین و همکاران [7] در سـال 2006
عملکرد شبیه سازي تبرید تدریجی را با الگوریتم ژنتیـک و جسـتجوي تابو در مسائل مختلف مکانیابی مقایسه نموده اند.
-3 معرفی الگوریتم شبیه سازي تبرید تدریجی
الگوریتم تبرید یا شبیه سازي حرارتی، یکی از مجموعـه الگـوریتمهـاي متاهیوریستیک (فرا اکتشافی) معروف در زمینه الگـوریتمهـاي هـوش مصنوعی است. این الگوریتم در سـال 1980 و توسـط کیرکپاتریـک و همکاران ابداع شده است.[ 8 ] اصولا اکثر الگوریتمهاي متاهیوریستیک با الگوگیري و شبیه سازي یکی از قوانین یا روابط موجود در طبیعت بنا نهاده میشوند. این الگوریتم هم بر مبنـاي فرآینـد تبریـد یـا بازپخـت فلزات بنا نهاده شده است. در فرآیند تبرید، ابتدا حـرارت فلـزات را تـا دماي بسیار بـالایی افـزایش داده و سـپس، یـک فرآینـد سردسـازي و کاهش دماي تدریجی بر روي آنها صورت می گیرد. در ایـن فرآینـد در هنگام افزایش حرارت فلز، سرعت جنبش اتمهاي آن به شدت افـزایش یافته و در مرحله بعد، کاهش تدریجی دما موجب شکلگیري الگوهـاي خاصی در جایگیري اتمهاي آن میشود. این تغییر الگوي اتمهـا باعـث بروز خواص ارزشمندي در فلز تبرید شده میگردد که از جمله میتوان به افزایش استحکام آن اشاره نمود.
روند کلی کار به این صورت است که در ابتدا یک نقطه دلخـواه از فضاي جستجو انتخاب و تابع جریمه در آن حساب میشود . سـپس بـه سیستم یک دماي اولیه (متناظر با انرژي جنبشی ) نسـبت مـیدهـیم. انتخاب مقدار دماي اولیه دلخواه است اما میتوان بسته به اینکه تابع در نقطهي شروع چه رفتاري دارد دماي اولیه را انتخاب کرد. مثلا اگر تابع داراي تغیرات کمی است دماي اولیه کمتر انتخاب میشـود تـا قابلیـت تحرك کمتر باشد و اگر تابع داراي تغییرات زیاد(شیب تند) است دماي اولیه بیشتر انتخاب می شود تا امکان حرکـت و خـارج شـدن از بهینـه هاي محلی بیشتر شود. سپس یک نقطه از فضـاي اطـراف بـراي قـدم بعدي انتخاب میشود. این نحوه ي انتخاب بستگی به مسئله دارد. براي تصمیم در مورد حرکت به سـمت نقطـه ي جدیـد ایـن صـورت عمـل میشود: اگر جواب بهتر شد حرکت کن و اگر نه با احتمال P به سـمت نقطه جدید برو. احتمال P با توجه به دمـاي سیسـتم و تغییـردر تـابع جریمه (اختلاف نقطه ي مبدا و مقصد) انتخاب میشود. بعـد از انجـام هر حرکت ، دماي سیستم مقداري کاهش داده میشود (کمی از انرژي جنبشی اش را از دست میدهد). پس از تکـرار زیـاد و از دسـت دادن کامل انرژي جنبشی میتوان انتظار داشت که سیستم بـه پـایین تـرین انرژي پتانسیل (کمترین مقـدار تـابع جریمـه) رسـیده باشـد. توزیـع احتمالی که در این توابع استفاده میشود و نیز نحوه ي کم شدن دمـا، کاملا دلخواه نیستند بلکه باید در شـرایطی صـدق کننـد تـا همگرایـی جواب به سمت بهینه مطلق تضمین شود. انتخاب نحوهي کم شدن دما و نحوهي قدم برداشتن در فضاي جستجو و تعریف تابعیت احتمال P از دما، با توجه به خصوصیات مساله نیازمند تجربه و هنرمندي است.
-4 به کار گیري الگوریتم شبیه سازي تبرید تدریجی در مکانیابی مراکز فوریتهاي پزشکی
در این بخش سعی میکنیم الگوریتم شـبیه سـازي تبریـد تـدریجی را روي مسئله مکانیابی مراکز فوریتهاي پزشکی اعمال کنیم.
در به کارگیري الگوریتم شبیه سازي تبرید تدریجی ، تعداد نقاط تقاضا را با (Demand Node) DN و تعداد نقاط پتانسیل را با PS
(Potential Station) نشان میدهیم.
-1-4 وروديهاي مسئله
-1 وروديهاي مربوط به مدل:
ماتریس پوشش: یک ماتریس (DN* PS) است که درایههاي آن از جنس صفر و یک هستند. به این صورت که اگر آمبولانس j در فاصله S (حداکثر فاصله قابل قبول براي پوشش یک نقطه تقاضـا بوسیله آمبولانس) از نقطه تقاضاي i باشـد، درایـه (i,j) مـاتریس پوشش برابر یک خواهد بود و در غیر این صورت برابر صفر خواهد بود،
ماتریس تقاضا: یک ماتریس ( (1*DN اسـت کـه هـر درایـه آن مقدار تقاضاي موجود در هر نقطه تقاضا را بیان میکند،
حداکثر ضریب اشغال هر آمبولانس؛ (ضریب اشغال: نسبت مـدت زمانی از یک شبانه روز است که آمبولانس به هر دلیـل قـادر بـه سرویس دهی نیست)،
حداقل آمبولانسی که باید هر نقطه تقاضا را پوشش دهد.
-2 وروديهاي مربوط به الگوریتم شبیه سازي تبرید تدریجی: تعداد حداکثر تکرار، دماي اولیه، دماي نهایی، تعداد تکرار در هر دما، تابع کاهش دما
-2-4 روش نمایش جوابها (رمز گذاري اطلاعات یا ( Data encoding
هر جواب X از PS عدد المان تشکیل شده است که مـیتواننـد داراي مقادیر صفر و یک باشند. اگر مقدار یک المان جـواب برابـر یـک باشـد بدان معناست که در نقطه پتانسیل معادل بـا آن، ایسـتگاه دایـر شـده است (آمبولانس استقرار داده شده است) و اگر مقدار المان جواب برابـر صفر باشد بدان معناست که در نقطه پتانسیل معـادل بـا آن، ایسـتگاه دایر نشده است.
-3-4 ایجاد جواب اولیه
براي ایجاد جواب اولیه از دو روش در حل مسائل استفاده شده است. روش تصادفی نرمال: با استفاده از تابع تولید تصادفی به المانهاي
جواب مقادیر صفر و یک تعلق می گیرددر. این روش تقریبـاً نیمـی از المانهاي جواب مقدار یک و نیمی دیگر مقدار صفر میگیرند.
