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

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

فهرست:

عنوان                                                                                                                           صفحه

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

منبع:

[ ١] . افندی زاده ،شهریار، "مکانیابی پایانه های اتوبوسرانی جدد با هد ف کاهش زمان دسترسی مسافران "،هفتمین کنفرانس مهندسی حمل و نقل و ترافیک ایران ،اسفند ١٣٨٥.

[ ٢ ] ."روش تعیین مکان مناسب برای پایانه ها"،مجموعه مقالا ت دومین سمینار بررسی مسائل حمل و نقل کشور،١٣٦٩.

[ ٣ ] . "طرح ترمینال اتوبوسرانی بین شهری شرق تهران " ،معاونت حمل و نقل سازمان ترمینالهای شهرداری تهران ،جلد اول ،اسفند ١٣٨٠.

[ ٤ ] .اصغر پور، محمد جواد،"تصمیم گیریهای چند معیاره " ،انتشارا ت دانشگاه تهران ،تابستان ١٣٨٣.

[٢١]. افیونیان ، مجید رضا "طراحی شبکه خطو ط حمل و نقل عمومی (اتوبوسرانی ) با استفاده از تکنیک شاخه و کرانه "، نشریه امیرکبیر، بهار ١٣٨٢

[٢٢]. فصیحی لنگرودی ، فرهنگ ، " بکارگیری سیستمهای بهینه سازی به شیوه اجتماع مورچگان برای حل مسائل "، پایان نامه کارشناسی ارشد، دانشکده مهندسی صنایع ، دانشگاه علم و صنعت ، اسفند ١٣٨٠.

[٢٣]. ابولقاسمی فرهاد " کاربرد الگوریتم سیستم مورچه ها در مساله طراحی شبکه "، پایان نامه کارشناسی ارشد مهندسی سیستمهای اقتصادی - اجتماعی ، موسسه عالی پژوهش در برنامه ریزی و توسعه ، پاییز ١٣٨٠.

[٢٩]. اشراق سپیده ، " طراحی خطو ط اتوبوسرانی با استفاده از الگوریتم مورچگان "، پایان نامه کارشناسی ارشد مهندسی عمران -برنامه ریزی حمل و نقل ، دانشگاه آزاد اسلامی تهران جنوب ، شهریور ١٣٨٣.

[٣٦].کاوه ، علی .، شرفی ، پژمان ، "بهینه یابی با کلونی مورچه ها" ،انتشارا ت وزار ت مسکن و شهرسازی ، مرکز تحقیقا ت مسکن و ساختمان ، ١٣٨٦.

[٣٧]. حجازی ، بهرنگ ، "حل مساله مکانیابی پایانه های شبکه اتوبوسرانی با استفاده از روش SA"

پایان نامه کارشناسی ارشد مهندسی برنامه ریزی حمل و نقل ، دانشگاه صنعتی شریف ، ١٣٧٨.

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

[5]. Dileep R. Sule, “Logistics of Facility Location And Alocation”, Louisiana Tech

University, 2001.

[6]. Saaty, T.L , “The Analytical Hierarchy Process”. New York:Mc Graw-Hill ,1980.

[7].Witzgall C, “Optimal location of central facility”; Mathematical Model and concepts,

Gaithersberg, MD: National bureau of Standards Report, 1964.

[8].Ray ward-smith V.J & Osman I.H & Reeves C.R & Smith G.D , “Modern Heuristic

Methods”, John weily &Sons,1996.

[9].Bradley S.P & Hax A.C & Magneti T.L,“Applied Mathematicah Programing”, Addison

Wesley, 1977.

[10].Reeves.G.r,“Modern Heuristic Techniques For Combinatoral Problem” , Blackwell,

Scientific Publication, Oxford,1993.

[11].Van  Laarhoven   P.J.M   &  E.H.L.   Aarts,“Simulated  Annealing:Theory   And

Applications” , D.Reidel Publishing Company, 1987.

[12]. Yao Zhou , “Study On Genetic Algorithm Improvement And Application” , A Thesis

of the Worcester Polytechnic Institute for the Degree of M S . May 2006.

[13]Dorigo.M. ”Optimization, Learning and Natural Algorithm” . Ph.D.Thesis, Politecnico

di Milano, Italy, in Italian, 1992.

[14] Dorigo.M. & Di Caro, G. “ The Ant Colony Optimization Meta-Heuristic”.In

D.Corne,M.Dorigo and F. Glover(Eds.),UK.Chapter 2, pp.11-32. 1999.

[15] Dorigo.M. & Stutzle,T. ”The Ant Colony Optimization Metahuristic”: Algorithms,

Application, and Advances. In F. Glover and G. A.Kochenberger, ”Handbook of

Metahuristics”, Kluwer Academic Press,. 2003.

[16]. Ahmadi ,S. & Osman,I.H., “Density Based Problem Space Search for the Capacitated

Clustering Problem”. Annals for Operational Research, 2004.

[17].Blum, C., Roli, A & Dorigo, M. HCACO: “The hyper-cube framework for Ant colony

Optimization”. In Proceedings of MIC’2001 –Meta-huristics International Conference, v.

2, Porto, Portugal, pp. 399-403, 2001.

[18]. Blum, c. & Dorigo, M., “The Hyper-Cube Framework for Ant Colony Optimization”.

IEEE Transportation  on Systems, Man and Cybernetics, Part B, 34(2): 1161-1172. 2004.

[19]. Fabrício Olivetti de França & Fernando J. Von Zuben, “Max Min Ant System and

Capacitated p-Medians: Extensions and Improved Solutions” State University of Campinas

(U

[20]. Kochetov, Y. & Alekseeva, V.& Levanova, T. & Loresh, M. “Large Neighborhood

Local   Search   for   The   P-Median   Problem”Sobolev   Institute   of   Mathematics,

RussiaPresented at XXX Yugoslav Simposium on Operations Research , 2005.

[24]. Dorigo, M. & Stützle, T. “Ant Colony Optimization” MIT Press, Cambridge,

Massachusetts London, England, 2004.

[25]. Glover, F., “Tabu search-part I” ORSA Journal on Computing, vol. 1, no. 3, pp.

190–206, 1989.

[26]. Ritchie. G, “Static Multi-processor Scheduling with Ant Colony Optimisation &

Local Search”, A Thesis of the Artificial Intelligence School of Informatics University of

Edinburgh for the Degree of M S, 2003.

[27]. Gambardella, L. M., “ Solving Symmetric and Asymmetric TSPS by Ant colonies” ,

0-7803-2902-3.96, IEEE, 1996.

[28]. Colorni. A & Dorigo . M, Maniezzo. V.,“Distributed Optimization by Ant Colonies”.

Dipartimento di Elettronica, Politecnico di Milano, Milano, Italy.

[30]. Bischoff.M & D¨achert.v.,” Allocation Search Methods for a Generalized Class of

Location-Allocation Problems”.Institute of Applied Mathematics, University of Erlangen-

Nuremberg, Germany,March 18, 2007.

[31]. Levanova, T.V.,”The Ant Colony Optimization Algorithm For Some Discrete

Location Problems”.Omsk State University, Mathematical Department,Mira st., 55-a,

Omsk, 644077, Russia

[32] . De Franca, F.O. & Von Zuben, F.J.& De Castro, L.N. “Definition of Capacited p-

Medians by a Modified Max Min Ant System with Local Search”.In: ICONIP - 2004 11th

International Conference on Neural Information Processing - Special Session on Ant

Colony and Multi-Agent Systems, 2004, Calcutta. Lecture Notes in Computer Science. v.

3316. pp. 1094 – 1100, 2004.

[33]. Stutzle, T. & Hoos, H.H.  “The Max-Min Ant System and Local Search for the

Traveling Salesman Problem”. In T. Bäck, Z. Michalewicz, and X. Yao, Editors,

Proceedings  of  the  IEEE  International  Conference  on  Evolutionary  Computation

(ICEC'97), IEEE Press, Piscataway, NJ, USA, pp. 309-314, 1997.

[34] . Resende, G.C.M.  & Werneck, F. R.  “On the implementation of a swap-based local

search procedure for the p-median problem”. Proceedings of the Fifth Workshop on

Algorithm Engineering and Experiments (ALENEX'03), Richard E. Ladner (Ed.), SIAM,

Philadelphia, pp. 119-127, 2003.

[35] . Teitz, M. B. & BART, P. “Heuristic Methods for Estimating the Generalized Vertex