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

با توجه به اینکه جمعیت شهرها همواره رو به افزایش است، نیاز به‎دسترسی به اداره‏های ثبت احوال و دفاتر پیشخوان دولت از اهمیت خاصی برخوردار است. بنابراین برای انتخاب مکان‏ها جهت قرار‏گیری مناسب اداره‏های ثبت احوال و دفاتر پیشخوان دولت، به یک برنامه مکان‏یابی صحیح تسهیلات نیاز است. برای انتخاب مکان تسهیلات معیارهای مختلفی وجود دارد. یکی از شرایط، حفظ فاصله دفاتر پیشخوان دولت نسبت به یکدیگر است. این شرط یکی از مهمترین شرایط لازم جهت ایجاد پراکندگی کافی مکان قرارگیری دفاتر پیشخوان دولت در سطح شهر است. منظور از این شرط حفظ فاصله مناسب بین دفاتر پیشخوان دولت است. برای مثال اگر فاصله بین دو دفتر پیشخوان دولت بیش از حد کم باشد، هزینه به کارگیری مکان و کارکنان بیهوده اتلاف می‏شود و اگر فاصله بین دو دفتر پیشخوان دولت بیش از حد زیاد باشد، دسترسی شهروندان به مکان دفتر پیشخوان دولت با مشکل مواجه خواهد شد. از شرایط دیگر انتخاب مکان اداره‏های ثبت احوال و دفاتر پیشخوان دولت، توجه به تراکم جمعیت ناحیه‏ها است. مناطقی از شهر که دارای جمعیت بیشتری نسبت به مناطق دیگری هستند، بیشتر مستلزم وجود اداره‏های ثبت احوال و دفاتر پیشخوان دولت هستند. همچنین تا حد امکان باید سعی شود که مکان این اداره‏ها و دفاتر به مناطق مسکونی نزدیکتر باشد. بررسی ازدحام شهری در انتخاب مکان‏ها نیز ضروری است. شرط دیگری که باید مدنظر باشد فاصله مکان‏ها نسبت به دیگر ادارات دولتی است به این ترتیب که فاصله مکان نسبت به ادارات دولتی مرتبط مانند پست، بانک و بیمارستان نزدیکتر باشد. انتخاب مکان‏هایی که از لحاظ اقتصادی برای سازمان به‏صرفه باشند از شرایط دیگر است. روشن است که مکان‏های مختلف موجود در شهر از لحاظ اقتصادی با یکدیگر متفاوت هستند. بنابراین بهتر است برای قرارگیری اداره‏های ثبت احوال و دفاتر پیشخوان دولت مکان‏های ارزانتر شهر انتخاب شوند.
روش‏ها و الگوریتم‏های مختلفی برای حل مسأله مکان‏یابی تسهیلات مختلف، پیشنهاد و به کار گرفته شده‏اند. از مهمترین این الگوریتم‏ها و روش‏ها می‏توان به الگوریتم ژنتیک، تحلیل سلسله مراتبی (AHP^[1]) و روش‏های چند شاخصه مانند TOPSIS^[2] و SAW^[3] اشاره کرد. اما برای مکان‏یابی اداره‏های ثبت احوال و دفاتر پیشخوان دولت تاکنون روش یا الگوریتمی پیشنهاد نشده است.
هدف از این پایان‏ نامه استفاده از الگوریتم ژنتیک برای مکان‏یابی ادارات ثبت احوال و دفاتر پیشخوان است. فرض بر این است که در یک شهر m دفتر پیشخوان و n اداره وجود دارد. هدف این است که رویکردی ارائه شود تا با بهره گرفتن از آن بتوان تعداد ساختمان­ها را افزایش داد و مکان مناسبی برای قرارگیری آنها انتخاب نمود. برای ارزیابی و استفاده کاربردی از برنامه تهیه شده با بهره گرفتن از الگوریتم ژنتیک، مکان‏یابی اداره‏های ثبت احوال و دفاتر پیشخوان دولت در شهر تبریز انتخاب شده است. نتایج این پایان‏ نامه می‏تواند برای جا به ­جایی یا تعیین مکان‏های جدید برای قرارگیری بهتر اداره‏های ثبت احوال و دفاتر پیشخوان دولت در شهر تبریز مورد استفاده قرار گیرد. براساس تحقیقات صورت گرفته، شهر تبریز در حال حاضر دارای ۳ اداره ثبت احوال و ۱۰ دفتر پیشخوان دولت است. مکان‏های مرتبط با قرارگیری این دفاتر و اداره‏ها به صورت دستی تعیین شده است. لذا مکان‏های فعلی به طور کامل بهینه نیست. همچنین در آینده ممکن است نیاز به افزایش تعداد اداره‏های ثبت احوال و دفاتر پیشخوان دولت باشد. بنابراین می‏توان از نتایج این پایان نامه برای یافتن مکان‏های بهینه برای قرارگیری این دفاتر و اداره‏ها استفاده نمود.
در ادامه در فصل دوم به شرح مفاهیم پایه مرتبط با مکان‏یابی انواع تسهیلات و کارهای مختلف انجام گرفته در زمینه مکان‏یابی انواع تسهیلات با بهره گرفتن از روش‏های مختلف پرداخته می‏شود. در فصل سوم استفاده از الگوریتم ژنتیک برای مکان‏یابی دفاتر پیشخوان دولت و اداره‏های ثبت احوال پیشنهاد می‏شود و مراحل مختلف الگوریتم ژنتیک برای حل مسأله بیان شده به طور کامل شرح داده می‏شود. همچنین در این فصل آزمایش‏هایی برای حصول اطمینان از پاسخ‏های به‎دست آمده از اجرای الگوریتم و دقت پاسخ‏ها صورت می‏گیرد. نتیجه ­گیری کلی روش پیشنهادی در فصل چهارم بیان شده است و همچنین تعدادی روش برای حل مسأله مکان‏یابی تسهیلات پیشنهاد شده است.
فصل دوم
پیشینه
در زمینه مکان‏یابی تسهیلات تاکنون تلاش‏های زیادی صورت گرفته است. با توجه به اینکه کار خاصی در زمینه مکان­ یابی ادارات ثبت احوال و دفاتر پیشخوان دولت انجام نگرفته است، در این فصل تعدادی مقاله مشابه که در مورد مکان‏یابی‏های مختلف فعالیت نموده‏اند شرح داده خواهد شد. مکان‏یابی‏های مورد بررسی در این پایان‏ نامه شامل مکان‏یابی پایانه‏های اتوبوس‏رانی، جایگاه‏های عرضه سوخت، دبیرستان‏ها، آتش‏نشانی و مدارس هستند. این مقاله‏ها هر کدام ممکن است بر روی شهرهای خاصی پیاده‏سازی شده باشند. برای تنوع موضوعات در این پایان‏ نامه سعی شده است مقاله‏هایی انتخاب شوند که از روش‏های مختلف، در شهرهای مختلف و تسهیلات مختلف استفاده کرده‏اند. همچنین در طول معرفی این مقاله‏ها روش‏های مورد استفاده در این مقاله‏ها نیز توضیح داده خواهد شد.

• • 1. 1. مکان‏یابی پایانه‏های اتوبوس‏رانی با الگوریتم ژنتیک

     

     

سید حسینی و همکارانش در سال ۱۳۸۸ [۴] به مکان‏یابی پایانه‏های شبکه اتوبوس‏رانی درون شهری با بهره گرفتن از الگوریتم ژنتیک پرداخته‏اند. ایستگاه‏های اتوبوس‏رانی می‏توانند به عنوان نقاط نامزد برای احداث پایانه انتخاب شوند. هدف انتخاب تعدادی از این ایستگاه‏ها به عنوان پایانه است. برای آزمایش و بررسی این روش، برروی شهرهای تهران و مشهد پیاده‏سازی شده است. همچنین برای حل این مسأله از الگوریتم ژنتیک و نرم‏افزار متلب استفاده شده است.

• • شرح الگوریتم ژنتیک

1. 1. مدل الگوریتم ژنتیک از تکامل داروین الهام گرفته شده است، به این ترتیب که هر کروموزومی که برتر باشد، شانس بقای بیشتری دارد. در این مدل یک جمعیت از کروموزوم‌ها در نظر گرفته می‏شود که حاوی اطلاعات هستند. این جمعیت یا به بیان دیگر کروموزوم‌های گروه، ممکن است چیدمان‌های گوناگون مهره‌ها بر صفحه شطرنج، مقادیر مواد خام به‌کار رفته در ساخت یک ترکیب شیمیایی به‌ خصوص یا مکان‏های یک نوع از تسهیلات شهری باشند. در الگوریتم ژنتیک، تبدیل و فرموله کردن عناصر یک مسأله در قالب کروموزوم‌های گروه یکی از کارهای مهم به‌شمار می‌آید. با هر زاد و ولدی، عضوی به این گروه، افزوده خواهد شد و در هر لحظه یکی از افراد، بهترین ساختار ژنتیک را دارد و او پاسخ صحیح تا آن هنگام است که در اصطلاح ژنتیک نخبه نام دارد. الگوریتم ژنتیک تا آنجا ادامه می‌یابد که این بهترین فرد، انتظارات طراحان مسأله را برآورده سازد. در مرحله­ بعد تولید مثل انجام می‌شود. از ترکیب پدر و مادر دو فرزند حاصل می‌شود. فرزند اول قسمتی از مادر و قسمتی از پدر را در بر می‌گیرد، قسمت‌های باقی مانده از پدر و مادر فرزند دوم را تشکیل می‌دهند. پس از تولید فرزندان شایستگی آن‌ها بررسی می‌شود و به ترتیب شایستگی در جمعیت قرار می‌گیرند. دو مرحله مهم و منحصر به فرد الگوریتم ژنتیک، مرحله آمیزش^[۴] و جهش^[۵] هستند. در مرحله آمیزش برای تولید پاسخ‏های جدید و متفاوت بین هر جفت از پاسخ یا کروموزوم موجود ترکیب صورت می‏گیرد. با ترکیب هر جفت از کروموزوم‏ها دو کروموزوم جدید حاصل می‏شود که این امر باعث تولید پاسخ‏های جدیدتر برای جستجوی فضای حالات مسأله می‏شود. در مرحله جهش برای دستیابی به پاسخ‏های دست نیافته و فرار از جستجو‏های محلی، تغییراتی بر روی تعداد محدودی از کروموزوم‏های موجود صورت می‏گیرد. مراحل گردش کار موجود در شکل ۲-۱ مربوط به الگوریتم ژنتیک است [۵].

شکل ۲-۱ مراحل گردش کار مربوط به الگوریتم ژنتیک [۵]

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

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

• • • • کدگذاری

     

     

کدگذاری به صورت دودویی انجام می‏گیرد. در این‏صورت هر کروموزوم به صورت رشته‏ای به طول |I| از صفرها و یک‏ها در نظر گرفته می­ شود. |I| برابر با تعداد گره‏های نامزد، یک به معنای انتخاب و صفر به معنای عدم انتخاب گره به عنوان پایانه است. در شکل ۲-۲ مثالی از یک کروموزوم را می‏توان دید. اطلاعات استخراج شده از کروموزوم شکل ۲-۲ نشان‏دهنده این است که گره‏های ۱، ۲۰، ۲۵، ۴۵ و ۵۰ انتخاب می‏شوند.

• • • • جمعیت اولیه

     

     

تولید تصادفی تعدادی کروموزوم است،که طول آن‏ها برابر با تعداد گره‏های نامزد است. در هنگام تولید جمعیت اولیه باید دقت شود که مقادیر ژن‏ها با صفر یا یک پر شوند و تعداد یک‏های هر کروموزوم برابر با تعداد پایانه‏های مورد نیاز باشد.
J={1, 2, 3, . . ., 60}
I={1, 5, 15, 20, 25, 30, 35, 40, 45, 50}