عنوان پایان‌نامه
یک الگوریتم سیمپلکس‌گونه برای حل مسئله تخصیص ترافیک
- رشته تحصیلی
- مهندسی عمران - راه و ترابری
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس یک فنی شماره ثبت: 1865;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 60688
- تاریخ دفاع
- ۳۱ شهریور ۱۳۹۲
- دانشجو
- میرفرنام تابنده
- استاد راهنما
- عباس بابازاده
- چکیده
- تعیین جریان تعادلی در یک شبکه حمل و نقل با حل مسئله تخصیص ترافیک به صورت یک مدل تکمیلی غیرخطی بر حسب جریان در مسیرها حاصل می‌شود.از جمله الگوریتمهای تخصیص ترافیک، الگوریتمهای بر پایه مسیر می‌باشند که در آنها جریان در مسیرهای بین هر زوجهای مبدأ- مقصد به طور تکراری و با حرکت به سمت جواب تعادلی بهنگام می‌شوند. برای حل مشکل ابعاد بزرگ مسئله، مسئله اصلی با استفاده از دو ایده تجزیه مسئله و تولید مسیر به زیرمسائل کوچک‌تر برای هر زوج مبدأ- مقصد تبدیل می‌شود که متغیرهای آن جریان در مسیرهای فعال بین هر زوج مبدأ- مقصد است. زیر مسئله مربوط به هر زوج مبدأ- مقصد خود یک مسئله تکمیلی غیرخطی است که به خاطر ماهیت غیرخطی آن، روش تکراری خطیسازی برای حل آن توسط آشتیانی، ارایه شد. در هر تکرار این روش، مسئله در جواب فعلی خطیسازی و به صورت یک مسئله تکمیلی خطی تبدیل می‌شود. جواب این مسئله خطی از روش‌های عمومی ریاضی محاسبه می‌شود. هدف از این پژوهش ارایه یک الگوریتم بر پایه مسیر است که در آن زیر مسایل غیرخطی به صورت تکراری و با تبدیل به دستگاه معادلات خطی حل می‌شوند. برای حل دستگاه معادلات روشی کارا با توجه به ساختار خاص مسئله تخصیص ترافیک ارایه می‌شود. در پایان، نتایج اجرای الگوریتم پیشنهادی برای یک شبکه کوچک، سایوکس فالز و شیکاگو با نتایج الگوریتمهای خطیسازی آشتیانی و تصویر گرادیان جوانی مقایسه خواهد شد.
- Abstract
- Determination of equilibrium flow in a transportation network is obtained by solving traffic assignment problem as a nonlinear complementary model based on the path flows. Path-based algorithms are one of the traffic assignment algorithms which path flows between each origin-destination pair are updated iteratively by moving toward the equilibrium solutions. To overcome the problem of model`s large dimensions, a decomposition and a path generation technique are used by dividing the main problem to smaller sub-problems.The sub-problem corresponding to each origin- destination pair is a Non-linear complementary problem (NCP). Due to the nonlinear nature of the NCPs, an iterative linearization solution algorithm was presented by Ashtiani. In each iteration of this method, the NCPs are linearized in current solution and converted to linear complementary problems (LCP). Solution of this LCPs are calculated by the general mathematical linear methods. The purpose of this paper is to present a path-based algorithm which LCPs are reformulated to a system of linear equations through some assumptions. An efficient method will be presented to solve the system of linear equations consistent with the traffic assignment problem`s special structure. Finally, the proposed algorithm is compared with a Gradient Projection and Ashtiana Linearization algorithms for a small network, Sioux Falls and Chicago networks.
