ساختار الگوریتم ژنتیک برای حل مسأله مکان‏یابی پایانه‏های اتوبوس‏رانی

  • ساختار الگوریتم ژنتیک برای حل مسأله مکان‏یابی پایانه‏های اتوبوس‏رانی

در الگوریتم ژنتیک ابتدا کروموزوم ایجاد می­شود وجمعیت اولیه مشخص می­شود و سپس بر روی آن عملگر آمیزش و جهش صورت می­گیرد تا کروموزم نخبه به‎دست آید و هدف مسأله ارضا شود.

 

  • کدگذاری

کدگذاری به صورت دودویی انجام می‏گیرد. در این‏صورت هر کروموزوم به صورت رشته‏ای به طول |I| از صفرها و یک‏ها در نظر گرفته می­شود. |I| برابر با تعداد گره‏های نامزد، یک به معنای انتخاب و صفر به معنای عدم انتخاب گره به عنوان پایانه است. در شکل 2-2 مثالی از یک کروموزوم را می‏توان دید. اطلاعات استخراج شده از کروموزوم شکل 2-2 نشان‏دهنده این است که گره‏های 1، 20، 25، 45 و 50 انتخاب می‏شوند.

  • جمعیت اولیه
J={1, 2, 3, . . ., 60}

I={1, 5, 15, 20, 25, 30, 35, 40, 45, 50}

k=5

1 0 0 1 1 0 0 0 1 1

 

تولید تصادفی تعدادی کروموزوم است،که طول آن‏ها برابر با تعداد گره‏های نامزد است. در هنگام تولید جمعیت اولیه باید دقت شود که مقادیر ژن‏ها با صفر یا یک پر شوند و تعداد یک‏های هر کروموزوم برابر با تعداد پایانه‏های مورد نیاز باشد.

 

 

 

 

شکل 2-2 نمونه یک کروموزوم [4]

  • انتخاب

برای انتخاب کروموزوم‏ها جهت انجام عمل آمیزش، از روش چرخ رولت استفاده خواهد شد.

  • عملگر آمیزش

مقادیری که در خانه‏های متناظر در هر دو کروموزوم برابر هستند به خانه متناظر در کروموزوم نوزاد منتقل می‏شوند. سپس برای اینکه تعداد یک‏ها در کروموزوم نوزاد حفظ شود، تعدادی از ژن‏ها که مقادیر آن‏ها صفر هستند، به صورت تصادفی یک قرار داده می‏شود.

  • عملگر جهش

کروموزومی را که برای اعمال عمل جهش انتخاب شده است، به طور تصادفی یکی از ژن‏های آن که محتوای آن صفر است با یک ژن تصادفی دیگر با محتوای یک جابه­جا خواهد شد.

  • دیگر پارامترهای ژنتیکی

دیگر پارامترهای لازم عبارتند از:

تعداد جمعیت: 10

احتمال جهش: بین 01/0 تا 2/0

احتمال آمیزش: بین 8/0 تا 99/0

  • مزایا

مسأله یافتن پایانه‏ها بر روی دو شهر تهران و تبریز با استفاده از الگوریتم ژنتیک اجرا شد. در مورد شهر مشهد زمان حل، با استفاده الگوریتم ژنتیک به ترتیب حدود 8، 485 و 1200 برابر سریعتر از روش‏های گرم و سرد کردن شبیه‏سازی شده، شمارش ضمنی و شاخه و کران اجرا شد. ابعاد شبکه شهر تهران حدود 5 برابر شهر مشهد است، لذا مکان­یابی پایانه­های اتوبوس­رانی با استفاده از روش شاخه و کران (با استفاده از نرم‏افزار GAMS) مستلزم تقسیم کردن شهر به چند زیر ناحیه است. این مسأله بدون نیاز به تقسیم‏بندی با استفاده از الگوریتم ژنتیک حل شد که زمان اجرای آن 30 برابر کمتر و میانگین دقت جواب نیز بیشتر از روش گرم و سرد کردن شبیه‏سازی شده است.

  • معایب

زمان مکان­یابی پایانه‏های شهر مشهد برای تعداد پایانه‏های برابر با 1، 2 و 3، با استفاده از الگوریتم ژنتیک، بیشتر از زمان حل مسأله مذکور با استفاده از روش شمارش ضمنی است. همچنین زمان حل، برای تعداد پایانه‏های برابر با 20 با استفاده از الگوریتم ژنتیک بیشتر از زمان حل، با استفاده از دیگر روش‏ها است.

  • مکان‏یابی جایگاه‏های عرضه سوخت

نوبخت و همکارش در سال 1390 [8] به مکان‏یابی جایگاه‏های عرضه سوخت پرداخته‏اند. پروژه تعیین تعداد و محل مناسب قرار‏گیری جایگاه‏های عرضه سوخت با استفاده از مدل برنامه‏ریزی ریاضی است. در این تحقیق شهر مشهد برای مطالعه انتخاب شد. برای مکان‏یابی یک جایگاه عرضه سوخت، پارامترهای متعددی از قبیل فاصله طولی، فاصله زمانی، زمان‏های اتلاف شده، ارزش زمین و غیره را می‏توان مورد بررسی قرار داد، اما بررسی هر یک از عوامل فوق مستلزم انبوهی از آمار و اطلاعات است. از آنجاکه در خصوص محدوده مورد مطالعه محدودیت داده وجود دارد، این مطالعه به بررسی فاصله طولی (مسافت) محدود می‏شود. همچنین آمار و اطلاعات موجود بر اساس مطالعات جامع حمل و نقل شهر مشهد بوده که آن مطالعات شهر مشهد را به گونه‏ای تقریبا همگن (از نظر جمعیت، تراکم و حجم سفرها) ناحیه‏بندی كرده است.

در این مدل برای هر یک از نواحی محدوده مورد مطالعه کمیتی به نام پتانسیل تعریف می‏شود که نشان دهنده ارزش هر ناحیه بدون درنظر گرفتن نواحی اطراف برای احداث جایگاه است. همچنین برای در نظر گرفتن تاثیر نواحی مختلف بر یکدیگر، به هر زوج (i,j) از ناحیه‏ها کمیتی به نام «شاخص تقاضا» نسبت داده می‏شود که بیانگر کسری از پتانسیل موجود در ناحیه j برای خدمت گرفتن از یک پمپ بنزین در ناحیه i است. میزان خدمت‏دهی یک پمپ بنزین به نواحی پیرامون آن با افزایش فاصله نواحی از پمپ بنزین کاهش می‏یابد.

  • پتانسیل هر ناحیه

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

  • سهم عوامل ثابت

با توجه به مشخص بودن جمعیت ساکن هر یک از نواحی و همچنین داشتن سرانه مالکیت خودرو در نواحی، تعداد خودروهای هر یک از نواحی به دست می‏آید. سپس برای تعیین سهم خودروهای موجود در ناحیه i به صورت رابطه (2-1) عمل می‏شود:

(2-1) D1i=

D1i: سهم خودروهای تحت تملک ساکنین ناحیه i (سهم عوامل ثابت)

CARi: تعداد خودروهای موجود در ناحیه i

: تعداد کل خودروهای موجود در شهر

  • سهم عوامل متحرک:

سهم عوامل متحرک به صورت رابطه (2-2) محاسبه می‏شود:

(2-2) D2i=

D2i: سهم سفرهای تولید و جذب شده به ناحیه i (سهم عوامل متحرک)

ODi: مجموع تعداد سفرهای تولید شده از و جذب شده به ناحیه i

: تعداد کل سفرهای تولید و جذب شده در شهر

  • تعریف سناریوهای پتانسیل نواحی

سهم هریک از دو عامل گفته شده در بالا در پتانسیل هر ناحیه باید تعیین شود. به این منظور دو پارامتر A و B را به عنوان ارزش وزنی عوامل ثابت و عوامل متحرک تعریف کرده و در سناریوهای مختلف مقادیر متفاوتی برای آنها فرض می‏شود تا تاثیرگذاری این دو عامل در پتانسیل نواحی مورد مقایسه قرارگیرد. در این صورت رابطه برآورد پتانسیل در هر ناحیه را می‏توان به صورت رابطه (2-3) و (2-4) نوشت:

(2-3) D2i=
Potentiali= A.D1i+B.D2i

 

(2-4)
  • تعیین ضریب خدمت‏دهی نواحی ازدحامی

اگر i یک پمپ بنزین و j یک ناحیه در محدوده مطالعاتی و Cij کمترین فاصله حرکت از j به i بر روی شبکه معابر شهری بر حسب کیلومتر باشد، میزان ضریب خدمت‏دهی پمپ بنزین i به ناحیه دیگر j از رابطه (2-5) قابل محاسبه است:

(2-5) Fji = EXP (-Cji)

 

  • تعیین شاخص تقاضا نواحی ازدحامی

شاخص تقاضا بخشی از پتانسیل ناحیه j برای خدمت گرفتن از پمپ بنزین ناحیه i است. رابطه (2-6) چگونگی محاسبه تقاضا را نشان می‏دهد:

(2-6) Demandij = EXP(-Cij)×Potentialj

Demandij: شاخص تقاضای ناحیه j برای خدمت گرفتن از پمپ بنزین موجود در ناحیه i

  • مزایا

حل مسأله مکان‏یابی جایگاه‏های عرضه سوخت با استفاده از مدل برنامه‏ریزی ریاضی باعث می‏شود که دقیق­ترین پاسخ و مکان‏یابی بهینه به‎دست آید. زیرا تمامی حالت بررسی شده و با محاسبات دقیق ریاضی همراه است.

  • معایب

برای حل مسأله مکان‏یابی جایگاه‏های عرضه سوخت با استفاده از مدل برنامه‏ریزی ریاضی باید تعدادی پیشنهاد موجود باشد تا بین آنها مقایسه صورت گرفته و بهترین حالت انتخاب شود.

  • برای ارایه پیشنهاد به یک فرد خبره نیاز است.
  • اگر فردی خبره تعدادی پیشنهاد برای مقایسه بدهد، لزوما این پیشنهادها بهترین پیشنهاد‏ها نخواهند بود.
  • به علت معدود بودن و چندجمله‏ای غیرقطعی-سخت (NP-Hard[1]) بودن مسأله، در نظر گرفتن و مقایسه همه حالات تقریبا غیر ممکن و وقت گیر خواهد بود.

 

  • مکان‏یابی مدارس

در این قسمت دو مقاله در زمینه مکان‏یابی دبیرستان و مدارس ابتدایی به عنوان نمونه‏هایی از مکان‏یابی مدارس معرفی می‏شود. در این دو مقاله برای مکان‏یابی از روش AHP استفاده شده است که ابتدا این روش شرح داده می‏شود.

  • شرح روش تحلیل سلسله مراتبی

فرآیند تحلیل سلسله مراتبی یكی از روش‏های ‏تصمیم‏گیری است. معمولا مدل فرآیند سلسله مراتبی، با استفاده از نرم‏افزار انتخاب پیشرفته[2] اجرا می‏شود. این نرم‏افزار در تصمیمات و پروژه‏های برنامه‏ریزی در بیش از بیست كشور به كار گرفته شده است. روش فرآیند تحلیل سلسله مراتبی (AHP) با توجه به سادگی، انعطاف پذیری، به كارگیری معیارهای كیفی و كمی بطور همزمان و نیز قابلیت بررسی سازگاری در قضاوت‏ها می‏تواند در بررسی موضوعاتی همچون برنامه‏ریزی شهری و منطقه‏ای، بهینه‏سازی تركیب تولید محصولات در یك واحد صنعتی، بودجه‏بندی دستگاه‏های دولتی، برنامه‏ریزی حمل و نقل، برنامه‏ریزی تخصیص منابع انرژی، اولویت‏بندی در صنعت برق، اولویت‏بندی پروژه‏های تحقیقات انرژی و محیط زیست و غیره كاربرد مطلوبی داشته باشد [1].

  • روش فرآیند تحلیل سلسله مراتبی

روش فرآیند تحلیل سلسله مراتبی اولین بار به وسیله توماس ال ساعتی3 در سال 1980 ارایه شد. این روش بر پایه مقایسات زوجی استوار است. مدل‏سازی با استفاده از این روش شامل سه گام می‏باشد:

  1. ساختن یك ساختار سلسله مراتبی برای مسأله
  2. تعیین ماتریسهای زوجی و محاسبه وزن معیارها و گزینه‏ها
  3. بررسی سازگاری سیستم

پس از مشخص شدن ساختار سلسله مراتبی، باید ماتریس‏های مقایسه زوجی براساس نظر شخص تصمیم گیرنده تعیین شود. این عمل، برای اجزای در هر سطح به صورت جداگانه انجام می‏گیرد. به طور كلی اگر تعداد گزینه‏ها و معیا رها به ترتیب برابر n و m باشد، آنگاه ماتریسهای مقایسه زوجی گزینه‏ها به صورت m×m و ماتریس مقایسه زوجی معیار‏ها یك ماتریس n×n خواهد بود [6].

  • مکان‏یابی دبیرستان‏ها

ولی زاده در سال 1386 [2] به مکان‏یابی مراکز آموزشی دبیرستان با استفاده از اطلاعات جغرافیایی بر روی شهر تبریز پرداخته است. افزایش سریع جمعیت شهرهای ایران موجب ایجاد مشكلات فراوانی از قبیل كاهش سرانه خدمات آموزشی شده است. این مسأله در شهر‏های بزرگ از جمله تبریز بنا به دلایل متنوعی چون تراكم بالای جمعیت، كمبود زمین و همجواری كاربری‏های مختلف با یكدیگر دشواری مسأله را افزایش داده است. در تحقیق حاضر مراكز آموزشی دبیرستان شهر تبریز با بررسی متغیرهای مهمی چون جمعیت، كاربری مطلوب شهری، مكان مدارس، عامل سازگاری، فاصله از كاربری‏های دیگر مورد ارزیابی قرار گرفته است. سپس از طریق مدل AHP هر كدام از لایه‏ها ابتدا به صورت منفك وزن­دهی شده و پس از آن در تركیب با لایه‏های دیگر وزن نهایی آنها مشخص شده است.

در این تحقیق معیارهای مختلف كاربری اراضی شهری برای تعیین و مكان­یابی مدارس مورد مطالعه، بررسی شده‏اند. ابتدا لایه بلوك‏های آماری و لایه موقعیت مدارس دبیرستان رقومی شده و به همراه داده‏های توصیفی یك پایگاه اطلاعات جغرافیایی تشكیل شده است. در مرحله بعد با توجه به استانداردهای بین‏المللی و ویژگی‏های محلی حاكم بر این مناطق (شامل تراكم جمعیت، آستانه‏های مدارس و غیره) شعاع دسترسی مناسب برای هر مدرسه در سطوح محلات به‎دست آمده است. در مراحل بعدی مثل تمام كاربری‏های خدمات از ماتریس‏های برنامه‏ریزی كاربری زمین برای سنجش موقعیت مدارس استفاده شده است. این ماتریس‏ها شامل ماتریس سازگاری، مطلوبیت، ظرفیت و وابستگی می‏باشد. نرم‏افزار‏هایی كه در این تحقیق به كار گرفته شده‏اند، شامل GIS[3] و دید قوسی[4] هستند. نقشه كاربری اراضی شهر به منظور بررسی مدارس متوسطه موجود از نظر همجواری با سایر كاربری‏ها و همچنین برای مدارسی كه در آینده ساخته می‏شوند، به­کار برده می­شوند.

 

  • سازگاری موقعیت مكانی

با توجه به ویژگی‏های منحصر به فرد فضاهای آموزشی از نظر سكوت و آرامش، امنیت، دوری از انواع آلودگی‏ها و غیره، كاربری آموزشی نمی تواند در مجاورت بعضی از كاربری‏ها قرار گیرد. در این تحقیق با توجه به ویژگی هر كدام از این كاربری‏ها میزان حریم برای هر یك از كاربری‏های ناسازگار با مدارس تعیین شده است. در مورد بعضی از كاربری‏ها مانند فضاهای سبز، مراكز فرهنگی و هنری، مراكز ورزشی و غیره كه با كاربری آموزشی سازگار بوده و به نوعی مكمل این كاربری محسوب می‏شوند نیز سرانه‏ها و حریم‏های لازم پیشنهاد شده است (جداول 2-1 و 2-2).

جدول 2-1 وضعیت مدارس دبیرستان شهر تبریز نسبت به کاربری‏های ناسازگار [2]

                        نوع کاربری                                    تعداد مدارس
صنعتی 5
بزرگراه و کمربندی 5
خطوط هوایی و فرودگاه 5
ایستگاه قطار و مسیر راه‏آهن 1
بیمارستان 25
مراکز نظامی 11
کاربری تجاری 34
پایانه‏های مسافربری و ترمینال 20

جدول 2-2 وضعیت مدارس دبیرستان شهر تبریز نسبت به کاربری‏های سازگار [2]

                        نوع کاربری                                    تعداد مدارس
کاربری فرهنگی 14
کاربری فضای سبز 33
کاربری ورزشی 15
کاربری مذهبی 79

پس از اینكه لایه‏های كاربری وزن‏دهی شدند تمام لایه‏های فوق با هم تركیب شده و نقشه ماتریس سازگاری مدارس دبیرستان به‎دست می‏آید. نتیجه‏ای كه ازتركیب لایه‏های ماتریس سازگاری به‎دست می‏آید شامل 2 طیف است. ضرایب [5 ,1] به عنوان مكان‏های نامناسب و كاملا نامناسب و ضرایب [10,5] به عنوان مكان‏های مناسب و كاملا مناسب، برای استقرار واحدهای آموزشی هستند.

 

  • ناهمواری‏ها

از نظر ناهمواری شهر تبریز در اطراف كوه‏های متعددی قرار گرفته و دارای شیب تندی در برخی مناطق است، ولی وضعیت فعلی مدارس از نظر شیب و ناهمواری مناسب هستند. به همین جهت در ارزیابی مكانی فضاهای آموزشی به این نتیجه رسیده می‏شود كه اكثر مدارس دبیرستان چه از لحاظ وضع موجود و چه از لحاظ مكان­گزینی مدارس دبیرستان برای سال‏های آتی دچار مشكل جدی نخواهد شد.

  • سیل

مسیر رود و حریم آن هنگام طغیان رودخانه از جمله مواردی است كه برای مكان­یابی مدارس باید به آن توجه نمود. در شهر تبریز رودخانه تلخه رود قرار دارد كه از قسمت شرق به غرب جریان می‏یابد و این شهر را به دو قسمت تقسیم می‏كند. در بررسی موقعیت دبیرستان‏های تبریز در ارتباط با مسیر رودخانه مشخص گردید كه 7 واحد از این مدارس درحریم 150 متری رودخانه قرار دارند.

  • شعاع دسترسی مدارس

شعاع دسترسی یك واحد آموزشی با تراكم جمعیت، اندازه هر واحد آموزشی و شرایط سنی استفاده كنندگان تعیین می‏شود. برای به‎دست آوردن  شعاع دسترسی متناسب با ویژگی‏های شهر، ابتدا تعداد و تراكم جمعیت در سطح نواحی شهر به‎دست آمده و نواحی شهر با توجه به تراكم تقسیم‏بندی می‏گردد. هرچه تعداد جمعیت و یا ظرفیت واحد آموزشی تغییر یابد به همان نسبت شعاع دسترسی مفید نیز تغییر پیدا خواهد كرد. برای تعیین شعاع‏های مشخص شده برای هر کدام از مدارس و نشان دادن آن دوایری به Arc view در محیط buffering بر روی نقشه ترسیم شد. پس از این مرحله مساحت مسكونی و جمعیت تحت پوشش هر كدام از گروه‏های تقسیم‏بندی مشخص شد كه در جدول 2-3 نشان داده شده است.

جدول 2-3 مساحت مسكونی و جمعیت تحت پوشش شعاع عملكردی دبیرستان [2]

            شعاع دسترسی      مساحت مسكونی m2 جمعیت
1000-600 7347769 242460
1400-1000 10031041 252457
1800-1400 9418490 274256
2200-1800 6907581 391457
2600-2200 4387643 232455
جمع 38092524 13930805

1 Non-deter Ministic Polynominal-time Hard

2 expert choice

3 Tumas El Saati

[3] Geographic Information System

[4] Arc view