پیشخوان دولت از یکدیگر بیشتر از ۱ کیلومتر باشد. در انتخاب هر مکان باید دقت شود که همه محدودیتهای سخت رعایت شوند. در صورت عدم رعایت هر یک از محدودیتهای سخت پاسخی غیر قابل قبول یا نادرست تولید میشود. محدودیتهای نرم یا به طور کلی معیارهای مکانیابی ادارههای ثبت احوال و دفاتر پیشخوان دولت شامل پراکندگی جمعیت، مخابرات، ازدحام شهری، شعاع دسترسی، نزدیکی به مترو یا ایستگاه اتوبوس، پارکینگ، نزدیکی به اداراتی چون پست، بیمارستان، بانک و قیمت اراضی است. تا حد ممکن محدودیتهای نرم باید رعایت شوند. برای مقایسه دو پاسخ یا دو مکان، پاسخ یا مکانی بهتر است که درآن محدودیتهای نرم بیشتری ارضا شده باشد.
با توجه به اینکه جمعیت شهرها همواره رو به افزایش است، نیاز بهدسترسی به ادارههای ثبت احوال و دفاتر پیشخوان دولت از اهمیت خاصی برخوردار است. بنابراین برای انتخاب مکانها جهت قرارگیری مناسب ادارههای ثبت احوال و دفاتر پیشخوان دولت، به یک برنامه مکانیابی صحیح تسهیلات نیاز است. برای انتخاب مکان تسهیلات معیارهای مختلفی وجود دارد. یکی از شرایط، حفظ فاصله دفاتر پیشخوان دولت نسبت به یکدیگر است. این شرط یکی از مهمترین شرایط لازم جهت ایجاد پراکندگی کافی مکان قرارگیری دفاتر پیشخوان دولت در سطح شهر است. منظور از این شرط حفظ فاصله مناسب بین دفاتر پیشخوان دولت است. برای مثال اگر فاصله بین دو دفتر پیشخوان دولت بیش از حد کم باشد، هزینه به کارگیری مکان و کارکنان بیهوده اتلاف میشود و اگر فاصله بین دو دفتر پیشخوان دولت بیش از حد زیاد باشد، دسترسی شهروندان به مکان دفتر پیشخوان دولت با مشکل مواجه خواهد شد. از شرایط دیگر انتخاب مکان ادارههای ثبت احوال و دفاتر پیشخوان دولت، توجه به تراکم جمعیت ناحیهها است. مناطقی از شهر که دارای جمعیت بیشتری نسبت به مناطق دیگری هستند، بیشتر مستلزم وجود ادارههای ثبت احوال و دفاتر پیشخوان دولت هستند. همچنین تا حد امکان باید سعی شود که مکان این ادارهها و دفاتر به مناطق مسکونی نزدیکتر باشد. بررسی ازدحام شهری در انتخاب مکانها نیز ضروری است. شرط دیگری که باید مدنظر باشد فاصله مکانها نسبت به دیگر ادارات دولتی است به این ترتیب که فاصله مکان نسبت به ادارات دولتی مرتبط مانند پست، بانک و بیمارستان نزدیکتر باشد. انتخاب مکانهایی که از لحاظ اقتصادی برای سازمان بهصرفه باشند از شرایط دیگر است. روشن است که مکانهای مختلف موجود در شهر از لحاظ اقتصادی با یکدیگر متفاوت هستند. بنابراین بهتر است برای قرارگیری ادارههای ثبت احوال و دفاتر پیشخوان دولت مکانهای ارزانتر شهر انتخاب شوند.
روشها و الگوریتمهای مختلفی برای حل مسأله مکانیابی تسهیلات مختلف، پیشنهاد و به کار گرفته شدهاند. از مهمترین این الگوریتمها و روشها میتوان به الگوریتم ژنتیک، تحلیل سلسله مراتبی (AHP[1]) و روشهای چند شاخصه مانند TOPSIS[2] و SAW[3] اشاره کرد. اما برای مکانیابی ادارههای ثبت احوال و دفاتر پیشخوان دولت تاکنون روش یا الگوریتمی پیشنهاد نشده است.
هدف از این پایان نامه استفاده از الگوریتم ژنتیک برای مکانیابی ادارات ثبت احوال و دفاتر پیشخوان است. فرض بر این است که در یک شهر m دفتر پیشخوان و n اداره وجود دارد. هدف این است که رویکردی ارائه شود تا با بهره گرفتن از آن بتوان تعداد ساختمانها را افزایش داد و مکان مناسبی برای قرارگیری آنها انتخاب نمود. برای ارزیابی و استفاده کاربردی از برنامه تهیه شده با بهره گرفتن از الگوریتم ژنتیک، مکانیابی ادارههای ثبت احوال و دفاتر پیشخوان دولت در شهر تبریز انتخاب شده است. نتایج این پایان نامه میتواند برای جا به جایی یا تعیین مکانهای جدید برای قرارگیری بهتر ادارههای ثبت احوال و دفاتر پیشخوان دولت در شهر تبریز مورد استفاده قرار گیرد. براساس تحقیقات صورت گرفته، شهر تبریز در حال حاضر دارای ۳ اداره ثبت احوال و ۱۰ دفتر پیشخوان دولت است. مکانهای مرتبط با قرارگیری این دفاتر و ادارهها به صورت دستی تعیین شده است. لذا مکانهای فعلی به طور کامل بهینه نیست. همچنین در آینده ممکن است نیاز به افزایش تعداد ادارههای ثبت احوال و دفاتر پیشخوان دولت باشد. بنابراین میتوان از نتایج این پایان نامه برای یافتن مکانهای بهینه برای قرارگیری این دفاتر و ادارهها استفاده نمود.
در ادامه در فصل دوم به شرح مفاهیم پایه مرتبط با مکانیابی انواع تسهیلات و کارهای مختلف انجام گرفته در زمینه مکانیابی انواع تسهیلات با بهره گرفتن از روشهای مختلف پرداخته میشود. در فصل سوم استفاده از الگوریتم ژنتیک برای مکانیابی دفاتر پیشخوان دولت و ادارههای ثبت احوال پیشنهاد میشود و مراحل مختلف الگوریتم ژنتیک برای حل مسأله بیان شده به طور کامل شرح داده میشود. همچنین در این فصل آزمایشهایی برای حصول اطمینان از پاسخهای بهدست آمده از اجرای الگوریتم و دقت پاسخها صورت میگیرد. نتیجه گیری کلی روش پیشنهادی در فصل چهارم بیان شده است و همچنین تعدادی روش برای حل مسأله مکانیابی تسهیلات پیشنهاد شده است.
فصل دوم
پیشینه
در زمینه مکانیابی تسهیلات تاکنون تلاشهای زیادی صورت گرفته است. با توجه به اینکه کار خاصی در زمینه مکان یابی ادارات ثبت احوال و دفاتر پیشخوان دولت انجام نگرفته است، در این فصل تعدادی مقاله مشابه که در مورد مکانیابیهای مختلف فعالیت نمودهاند شرح داده خواهد شد. مکانیابیهای مورد بررسی در این پایان نامه شامل مکانیابی پایانههای اتوبوسرانی، جایگاههای عرضه سوخت، دبیرستانها، آتشنشانی و مدارس هستند. این مقالهها هر کدام ممکن است بر روی شهرهای خاصی پیادهسازی شده باشند. برای تنوع موضوعات در این پایان نامه سعی شده است مقالههایی انتخاب شوند که از روشهای مختلف، در شهرهای مختلف و تسهیلات مختلف استفاده کردهاند. همچنین در طول معرفی این مقالهها روشهای مورد استفاده در این مقالهها نیز توضیح داده خواهد شد.
-
-
-
- مکانیابی پایانههای اتوبوسرانی با الگوریتم ژنتیک
-
-
سید حسینی و همکارانش در سال ۱۳۸۸ [۴] به مکانیابی پایانههای شبکه اتوبوسرانی درون شهری با بهره گرفتن از الگوریتم ژنتیک پرداختهاند. ایستگاههای اتوبوسرانی میتوانند به عنوان نقاط نامزد برای احداث پایانه انتخاب شوند. هدف انتخاب تعدادی از این ایستگاهها به عنوان پایانه است. برای آزمایش و بررسی این روش، برروی شهرهای تهران و مشهد پیادهسازی شده است. همچنین برای حل این مسأله از الگوریتم ژنتیک و نرمافزار متلب استفاده شده است.
-
- شرح الگوریتم ژنتیک
-
- مدل الگوریتم ژنتیک از تکامل داروین الهام گرفته شده است، به این ترتیب که هر کروموزومی که برتر باشد، شانس بقای بیشتری دارد. در این مدل یک جمعیت از کروموزومها در نظر گرفته میشود که حاوی اطلاعات هستند. این جمعیت یا به بیان دیگر کروموزومهای گروه، ممکن است چیدمانهای گوناگون مهرهها بر صفحه شطرنج، مقادیر مواد خام بهکار رفته در ساخت یک ترکیب شیمیایی به خصوص یا مکانهای یک نوع از تسهیلات شهری باشند. در الگوریتم ژنتیک، تبدیل و فرموله کردن عناصر یک مسأله در قالب کروموزومهای گروه یکی از کارهای مهم بهشمار میآید. با هر زاد و ولدی، عضوی به این گروه، افزوده خواهد شد و در هر لحظه یکی از افراد، بهترین ساختار ژنتیک را دارد و او پاسخ صحیح تا آن هنگام است که در اصطلاح ژنتیک نخبه نام دارد. الگوریتم ژنتیک تا آنجا ادامه مییابد که این بهترین فرد، انتظارات طراحان مسأله را برآورده سازد. در مرحله بعد تولید مثل انجام میشود. از ترکیب پدر و مادر دو فرزند حاصل میشود. فرزند اول قسمتی از مادر و قسمتی از پدر را در بر میگیرد، قسمتهای باقی مانده از پدر و مادر فرزند دوم را تشکیل میدهند. پس از تولید فرزندان شایستگی آن ها بررسی میشود و به ترتیب شایستگی در جمعیت قرار میگیرند. دو مرحله مهم و منحصر به فرد الگوریتم ژنتیک، مرحله آمیزش[۴] و جهش[۵] هستند. در مرحله آمیزش برای تولید پاسخهای جدید و متفاوت بین هر جفت از پاسخ یا کروموزوم موجود ترکیب صورت میگیرد. با ترکیب هر جفت از کروموزومها دو کروموزوم جدید حاصل میشود که این امر باعث تولید پاسخهای جدیدتر برای جستجوی فضای حالات مسأله میشود. در مرحله جهش برای دستیابی به پاسخهای دست نیافته و فرار از جستجوهای محلی، تغییراتی بر روی تعداد محدودی از کروموزومهای موجود صورت میگیرد. مراحل گردش کار موجود در شکل ۲-۱ مربوط به الگوریتم ژنتیک است [۵].
شکل ۲-۱ مراحل گردش کار مربوط به الگوریتم ژنتیک [۵]
-
- ساختار الگوریتم ژنتیک برای حل مسأله مکانیابی پایانههای اتوبوسرانی
در الگوریتم ژنتیک ابتدا کروموزوم ایجاد می شود وجمعیت اولیه مشخص می شود و سپس بر روی آن عملگر آمیزش و جهش صورت میگیرد تا کروموزم نخبه بهدست آید و هدف مسأله ارضا شود.
-
-
-
- کدگذاری
-
-
کدگذاری به صورت دودویی انجام میگیرد. در اینصورت هر کروموزوم به صورت رشتهای به طول |I| از صفرها و یکها در نظر گرفته می شود. |I| برابر با تعداد گرههای نامزد، یک به معنای انتخاب و صفر به معنای عدم انتخاب گره به عنوان پایانه است. در شکل ۲-۲ مثالی از یک کروموزوم را میتوان دید. اطلاعات استخراج شده از کروموزوم شکل ۲-۲ نشاندهنده این است که گرههای ۱، ۲۰، ۲۵، ۴۵ و ۵۰ انتخاب میشوند.
-
-
-
- جمعیت اولیه
-
-
تولید تصادفی تعدادی کروموزوم است،که طول آنها برابر با تعداد گرههای نامزد است. در هنگام تولید جمعیت اولیه باید دقت شود که مقادیر ژنها با صفر یا یک پر شوند و تعداد یکهای هر کروموزوم برابر با تعداد پایانههای مورد نیاز باشد.
J={1, 2, 3, . . ., 60}
I={1, 5, 15, 20, 25, 30, 35, 40, 45, 50}