پایان نامه توسعه مدل مکانیابی پایانه های اتوبوسرانی برون شهری با استفاده از یک الگوریتم فراابتکاری

پایان نامه توسعه مدل مکانیابی پایانه های اتوبوسرانی برون شهری با استفاده از یک الگوریتم فراابتکاری

پیشگفتار:

کمینه کردن زمان اجرای هر فعالیت یکی از ارکان اصلی و در خور توجه برنامه ریزان محسوب مـی شـود.

در حل مساله مکانیابی پایانه های اتوبوسرانی ، هد ف یافتن بهترین زیر مجموعه ای از مجموعه گزینـه هـای امکان پذیر است . امکانپذیری معمولا از دیدگاه هـای نـوع کـاربری ، بودجـه و وجـود امکانـا ت مـالی بـرای پروژه های برگزیده مطرح می گردد. مساله مکانیابی پایانه های اتوبوسرانی مساله پیچیده ای است زیرا انواع ترکیبهای ممکن از نواحی دارای پتانسیل (که گزینه را می سازند) در عمل بسیار زیاد است . بـرای نمونـه اگر تنها ٢٠ ناحیه دارای پتانسیل موجود باشد و از میان آنها  تنها انتخاب ٣ ناحیه  بـرای احـدا ث پایانـه

مورد نظر باشد، نیاز به بررسی ١١٤٠=                  !٢٠   حالت ممکن از ترکیب نواحی است .  

3 !(20 −3)!

به این ترتیب برای شهرهای بزرگ ، که تعداد نواحی آنها بیش از این مقدار باشد، کار بررسی گزینـه هـای امکان پذیر با دشواری زیادی روبرو است . از این رو ابداع روشهایی که بتواند کار را در مد ت معقول و کوتاه به انجام رساند، ضروری می نماید.

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

فهرست مطالب

عنوان                                                                                                                                                        صفحه 

چکیده ................................................................................................................................................................١

مقدمه ................................................................................................................................................................٢

فصل اول : کلیـا ت ..........................................................................................................................................................................٣

١-١- پیشگفتار: ..............................................................................................................................................................................٤

١-٢- تعریف مساله ..........................................................................................................................................................................٥

١-٣- اهمیت مساله ................................................................................................................................................................................. ٦

١-٤- هد ف تحقیق .................................................................................................................................................................................. ٦

١-٥- روش کار و تحقیق ...........................................................................................................................................................................٧

١-٦- بررسی عوامل موثر در مکانیابی پایانه های برون شهری .............................................................................................................................٧

١-٦-١- موقعیت زمین ..............................................................................................................................................................................٧

١-٦-١-١- فاصله  از محل تقاضا ..................................................................................................................................................................٧

١-٦-١-٢- وسعت ..................................................................................................................................................................................٨

١-٦-١-٣- کاربری و همسایگی ..................................................................................................................................................................٨

١-٦-١-٤- اثار زیست محیطی ....................................................................................................................................................................٨

١-٦-١-٥- مالکیت ..................................................................................................................................................................................٨

١-٦-٢-  محدودیتها.................................................................................................................................................................................٨

١-٦-٢-١- موقعیت از نظر طرح شهرسازی و دستور العملهای مربوطه .............................................................................................9

١-٦-٢-٢- سیاست گذاری مدیران اجرایی شهر .....................................................................................................................................٩

١-٦-٣- امکانا ت منطقه در تامین تاسیسا ت ...................................................................................................................................................٩

١-٦-٣-١- راه های ارتباطی ........................................................................................................................................................................٩

١-٦-٣-٢-  آب ...............................................................................................................................................................................................٩

١-٦-٣-٣- برق ...............................................................................................................................................................................................٩

١-٦-٣-٤- گاز ................................................................................................................................................................................................٩

١-٦-٣-٥- مخابرا ت .................................................................................................................................................................................... ١٠

١-٦-٣-٦- تسهیلا ت انتقال و یا تصفیه فاظلاب و دفع ابهای سطحی ............................................................................................. ١٠

١-٦-٣-٧- مسائل امنیتی .......................................................................................................................................................................... ١٠

١-٦-٤- وضعیت زمین شناسی .......................................................................................................................................................................١٠

١-٦-٤-١- ایمنی ........................................................................................................................................................................................ ١٠

١-٦-٤-٢- ناهمواریها  وعوار ض طبیعی .................................................................................................................................................١٠

١-٦-٤-٣- ابهای زیرزمینی .......................................................................................................................................................................١٠

١-٦-٤-٤- مکانیک خا ک .......................................................................................................................................................................... ١١

١-٦-٥- ویژگیهای اقلیمی و جغرافیایی ........................................................................................................................................................ ١١

١-٦-٥-١-ویژگیهای اقلیمی .....................................................................................................................................................................١١

١-٦-٥-٢-وضعیت بادها............................................................................................................................................................................. ١١

١-٧- بررسی کلی مسائل .........................................................................................................................................................................................١١

١-٧-١- طبقه بندی مسائل : .......................................................................................................................................................................... ١١

١-٧-١-١- مسائل چند جمله ای ( P ) : .............................................................................................................................................. ١٢

١-٧-١-٢- مسائل چند جمله ای نامقید ( NP ):............................................................................................................................... ١٢

١-٧-١-٣- مسائل بهینه یابی ترکیبی ( COP ) : ............................................................................................................................. ١٣

فصل دوم : بررسی روشهای مختلف مکانیابی پایانه های اتوبوسرانی برون شهری مطابق متون گذشته ...............................................١٥

٢-١-بررسی روشهای کلی مکانیابی ..................................................................................................................................................... ١٦

٢-٢- مدلهای کیفی مکانیابی پایانه های اتوبوسرانی برون شهری .................................................................................................................. ١٨

٢-٢-١- روش تحلیل سلسله مراتبی (AHP).............................................................................................................................................. ١٨

٢-٢-١-١- ایجاد ساختار درختی پارامترها و رسم نمودار AHP .................................................................................................... ١٩

٢-٢-١-٢- مقایسه زوج به زوج پارامترها با هم .................................................................................................................................... ١٩

٢-٢-١-٣-بررسی میزان سازگاری پاسخهای کارشناسان خبره ........................................................................................................٢٠

٢-٢-١-٤- روش محاسبه وزن نسبی در فرایند تحلیل سلسله مراتبی ...........................................................................................٢١

٢-٢-١-٥- روش محاسبه وزن نهایی در فرایند تحلیل سلسله مراتبی ...........................................................................................٢٢

٢-٢-٢- مکانیابی  با استفاده از منطق فازی ................................................................................................................................................٢٢

٢-٣- مدلهای کمی مکانیابی پایانه های اتوبوسرانی برون شهری ....................................................................................................................... ٢٥

٢-٣-١- مدل مکانیابی پیوسته .......................................................................................................................................................................٢٥

٢-٣-١-١-مکانیابی با در نظر گرفتن فاصله خطی بین نواحی .......................................................................................................... ٢٦

٢-٣-١-٢-مکانیابی با در نظر گرفتن فاصله دو بعدی بین نواحی .................................................................................................... ٢٧

٢-٣-١-٣- مکانیابی در مواردی که فاصله توان مثبتی از P باشد ................................................................................................... ٢٧

٢-٣-٢-روش  پی مرکز .................................................................................................................................................................................... ٢٨

٢-٣-٢-١- فاصله چه بای چه .....................................................................................................................................................................٢٩

٢-٣-٢-٢- مکانیابی با تقاضای وزین نواحی .......................................................................................................................................... ٢٩

٢-٣-٣- مکانیابی شبکه ای .............................................................................................................................................................................. ٣٠

٢-٣-٤- مکانیابی بر اسا س ماهیت دینامیکی تقاضا................................................................................................................................... ٣١

٢-٣-٥- مدل مکانیابی پایانه های چند گانه ................................................................................................................................................٣٢

٢-٤- مقایسه روشها.................................................................................................................................................................................................. ٣٣

فصل سوم : بررسی روشهای حل مساله ........................................................................................................................................................................٣٥

٣-١- روشهای حل مسأله :...................................................................................................................................................................................... ٣٦

٣-١-١- روش شبیه سازی : ............................................................................................................................................................................ ٣٧

٣-١-٢- روش بهینه سازی :............................................................................................................................................................................ ٣٧

٣-١-٢-١- روشهای شمارشی :................................................................................................................................................................ ٣٨

٣-١-٢-٢- روشهای محاسباتی :.............................................................................................................................................................. ٣٨

٣-١-٢-٣- روشهای ابتکاری : .................................................................................................................................................................. ٣٩

٣-١-٢-٤- روشهای فرا ابتکاری : ............................................................................................................................................................٤٠

٣-٢- روش جستجوی همسایه .............................................................................................................................................................٤١

٣-٣-  الگوریتم  بهینه یابی با کلونی مورچگان ( ACO ) :............................................................................................................................... ٤٥

٣-٣-١- سیستم مورچه ها (AS) ................................................................................................................................................................ ٤٧

٣-٣-١-١-ساخت راه حل .......................................................................................................................................................................... ٤٧

٣-٣-١-٢-به روزکردن جذابیت مسیر .................................................................................................................................................... ٤٩

٣-٣-٢- سیستم مورچه های حداقل و حداکثر در مساله فروشنده دوره گرد.........................................................................................٥٠

٣-٣-٢-١- به روز کردن جذابیت مسیر .................................................................................................................................................٥٠

٣-٣-٢-٢- محدودیت جذابیت مسیر...................................................................................................................................................... ٥١

٣-٣-٢-٣- شروع و بازسازی جذابیت مسیر .......................................................................................................................................... ٥٢

٣-٣-٣- سیستم مورچه های حداقل و حداکثر در مساله پی - میانه با ظرفیت محدود.......................................................................٥٢

٣-٣-٣-١-پتانسیل اولیه  هر ناحیه جهت عرضه سرویس ( η ):.....................................................................................................٥٣

٣-٣-٣-٢- میزان جذابیت هر ناحیه ( τ) : ......................................................................................................................................... ٥٣

٣-٣-٣-٣-کنترل رکود ................................................................................................................................................................. ٥٤

٣-٤- ACO بعلاوه جستجوی محلی ............................................................................................................................................... ٥٥

٣-٤-١- چگونگی افزودن جستجوی محلی به الگوریتم های ACO.......................................................................................................55

٣-٤-٢- به روز کردن جذابیت مسیر لامارک و داروین : ............................................................................................................................٥٧

فصل چهارم : روش تحقیق ....................................................................................................................................................................... ٥٨

٤-١- پروسه حل مساله ...........................................................................................................................................................................٥٩

٤-٢- مدل پیشنهادی توسعه یافته مکانیابی پایانه های اتوبوسرانی برون شهری ............................................................................................ ٦١

٤-٣-ایجاد تغییرا ت در الگوریتم تلفیقی پیشنهادی و متناسب نمودن آن با مساله ...................................................................................... ٦٣

٤-٣-١-پتانسیل اولیه هر مرکز جهت پایانه شدن ( η ):.......................................................................................................................... ٦٤

٤-٣-٢- میزان جذابیت مرکز هر ناحیه ( τ ) : .......................................................................................................................................... ٦٤

٤-٤- پروسه بهینه سازی مدل ...........................................................................................................................................................٦٦

فصل  پنجم : مطالعه موردی و پیاده سازی روش تحقیق روی شبکه شهر اصفهان .........................................................................................٧١

٥-١- مقدمه .............................................................................................................................................................................٧٢

٥-٢- تعیین محدوده مورد مطالعه ................................................................................................................................................... ٧٢

٥-٣- وضعیت پایانه های موجود در شهر اصفهان .................................................................................................................................٧٤

٥-٣-١- پایانه کاوه ....................................................................................................................................................................... ٧٤

٥-٣-٢- پایانه صفه ........................................................................................................................................................................٧٥

٥-٣-٣- پایانه زاینده رود ..................................................................................................................................................................٧٧

٥-٣-٤- پایانه جی .................................................................................................................................................................... ٧٨

٥-٤- بررسی اطلاعا ت موجود ......................................................................................................................................................٧٩

٥-٥- ساخت مدل پیشنهادی .......................................................................................................................................................٨١

٥-٦- ارزیابی مدل .....................................................................................................................................................................٨٧

٥-٧- ارزیابی پایانه های شهر اصفهان در وضعیت کنونی .............................................................................................................. ٩٠

٥-٨- تعیین مکان بهینه پایانه ها............................................................................................................................................ ٩٠

٥-٩- تحلیل حساسیت پارامترهای مدل .................................................................................................................................. ٩٢

٥-٩-١- تحلیل حساسیت مدل نسبت به پارامتر" تعداد تکرار برنامه " .................................................................................................. ٩٣

٥-٩-٢- تحلیل حساسیت مدل نسبت به پارامتر" تعداد انتخابگر".........................................................................................................٩٣

٥-٩-٣- تحلیل حساسیت مدل نسبت به پارامتر" نرخ کاهش جذابیت "................................................................................................ ٩٤

٥-٩-٤- تحلیل حساسیت مدل نسبت به پارامتر کنترل کننده میزان تاثیر جذابیت ( α) و پارامتر کنترل کننده میزان تاثیر

پتانسیل اولیه (β)............................................................................................................................................................................. ٩٦

٥-١٠- تعیین تعداد پایانه مورد نیاز بر اسا س رشد تقاضا در افق ١٣٩٠............................................................................................................. ٩٧

فصل ششم : نتیجه گیری و پیشنهادا ت ............................................................................................................................................... ١٠٠

٦-١- نتیجه گیری ............................................................................................................................................................................ ١٠١

٦-٢- ارائه پیشنهادا ت برای آینده ........................................................................................................................................................ ١٠٢

پیوست ١: نمونه پرسشنامه نظرسنجی از کارشناسان خبره ....................................................................................................................... ١٠٤

پیوست ٢: متن برنامه نوشته شده در محیط نرم افزار MATLAB .................................................................................................................... ١٠٧

منابع و ماخذ ................................................................................................................................................................................ ١١٦

فهرست منابع فارسی .................................................................................................................................................................... ١١٦

فهرست منابع لاتین ....................................................................................................................................................................... ١١٧