عنوان پایان‌نامه
الگوریتم هیبرید مبتنی بر پی اس او برای مسائل طراحی شبکه حمل و نقل با ابعاد بزرگ
- رشته تحصیلی
- مهندسی عمران - راه و ترابری
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس یک فنی شماره ثبت: 1774;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 57990
- تاریخ دفاع
- ۰۱ بهمن ۱۳۹۱
- دانشجو
- کاوه بخش کلارستاقی
- استاد راهنما
- عباس بابازاده
- چکیده
- مساله طراحی شبکه حمل و نقل (NDP)، مساله تصمیم گیری در مورد ساخت یا توسعه شبکه معابر موجود در شرایط منابع محدود برای سرمایه گذاری است. در حالت گسسته، NDP همان انتخاب زیر مجموعه ای امکان پذیر از مجموعه پروژه های نامزد برای افزودن به یک شبکه است به گونه ای که تابع هدف مشخصی بهینه شود. از میان الگوریتمهای ارایه شده برای NDP، الگوریتمهای فراابتکاری امروزه بیشتر مورد توجه می‌باشند. این الگوریتمها فضای جواب مسایل را با استفاده از رویکردهایی برگرفته شده از طبیعت و تصادفی جستجو می‌کنند. استفاده از رویکردهای تصادفی قابلیت اکتشافی این الگوریتمها را افزایش داده و از گیر افتادن آنها در جوابهای بهینه محلی جلوگیری می‌کند. در برخی کاربردها الگوریتمهای فراابتکاری در یافتن جوابهای بهینه موفق نبوده‌اند و بدین لحاظ برخی از آنها با سایر الگوریتمها هیبرید شده‌اند. چندین سال قبل یک الگوریتم هیبرید بهینه سازی کلونی مورچه (HACO) برای حل مسئله طراحی شبکه گسسته (DNDP) ارایه و کارایی بسیار مناسب آن نشان داده شد. اخیرا نیز الگوریتمی مبتنی بر روش فراابتکاری بهینه‌سازی گروه ذرات (PSO) که در فضای پیوسته کار می‌کند برای حل DNDP ارایه و نتایج آن نشان داد که در اغلب اوقات به جواب بهینه می‌رسد. در این مقاله یک الگوریتم هیبرید PSO گسسته (HDPSO) که در فضای گسسته کار می‌کند برای حل DNDP پیشنهاد می‌شود. مقایسه نتایج این الگوریتم برای شبکه سایوکس فالز با نتایج الگوریتمهای HACO و PSO نشان می‌دهد که الگوریتم HDPSO نسبت به آن دو الگوریتم برتری داشته و نیز کمتر در بهینه‌های محلی گیر می‌افتد. در انتها، قابلیت به کارگیری الگوریتم پیشنهادی برای شبکه‌های بزرگ با اجرای آن روی شبکه کلان‌شهر تهران نشان داده می‌شود.
- Abstract
- Network design problem (NDP) is the decision making problem of constructing or improving the available network in the situation of limited resources for investment. In the discrete case, NDP is the problem of choosing a subset of alternative projects, to add to a network, which minimizes an objective function. Among the Algorithms that have been developed to solve the NDP, the meta-heuristic algorithms have drawn a lot of attention recently. These algorithms search the feasible solution space of an objective function by using nature-inspired and random procedures. By applying randomness, they are able to increase the difference of the solutions in order to prevent being trapped in local optimums. Still, the meta-heuristic algorithms may never find the optimal solution so some of them are hybridized. A particle swarm optimization (PSO) algorithm has been devised lately that works in continuous solution space and can reach the optimal solution most of the time. In this thesis, four hybrid meta-heuristic PSO (HDPSO) algorithms that works in discrete solution space is proposed and results of them are compared with the PSO, ant colony optimization (ACO) and hybridized ant colony optimization (HACO). For comparison, the algorithms are implemented on the network of Sioux-falls and the results show that the new algorithm is superior to the other three algorithms and is trapped rarely in local optimums. An application of the proposed algorithm on large-scale networks has been demonstrated by carrying out the algorithm on the network of Tehran city. The algorithm can find the best solution in all the iterations.
