عنوان پایان‌نامه
الگوریتم خطی سازی مبتنی بر مسیر برای مسایل تخصیص ترافیک بزرگ مقیاس
- رشته تحصیلی
- مهندسی عمران - راه و ترابری
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس یک فنی شماره ثبت: 1600;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 51478
- تاریخ دفاع
- ۳۰ شهریور ۱۳۹۰
- دانشجو
- بابک جوانی
- استاد راهنما
- عباس بابازاده
- چکیده
- بر اساس مطالعات انجام شده در سال‌های گذشته، الگوریتم‌های بر پایه مسیر جزو کاراترین روش‌های تکراری حل مسئله تخصیص ترافیک به حساب می‌آیند. این الگوریتمها، در هر تکرار، مسئله اصلی را روی زوج‌های مبدا- مقصد تجزیه و سپس هر زیر مسئله را در فضای جریان در مسیرها حل می‌کنند. مصرف حافظه در این نوع الگوریتمها، به دلیل لزوم ذخیره کردن اطلاعات مسیرها، نسبت به الگوریتم‌های بر پایه کمان و بر پایه مبدا بیشتر است. با این وجود، پیشرفت‌های اخیر در حافظه قابل استفاده کامپیوترها و نیز همگرایی سریع این الگوریتمها موجب شده که آنها در دو دهه اخیر مورد استقبال محققان قرار بگیرند. الگوریتم خطی‌سازی یکی از معروفترین الگوریتم‌های بر پایه مسیر می‌باشد که از فرمولبندی تکمیلی مسئله تخصیص ترافیک حاصل شده است. در این الگوریتم، حل هر زیر مسئله غیرخطی با تقریبی خطی به حل دنباله‌ای از زیرمسایل تکمیلی خطی تبدیل، و هر زیرمسئله خطی توسط روش لمکه تا دقتی مشخص حل می‌شود. در این پژوهش، با استفاده از روش تصویرگرادیان به جای روش لمکه و نیز استفاده از تعریفی جدید برای دقت حل زیرمسایل، یک الگوریتم خطی‌سازی جدید پیشنهاد می‌شود. برای نشان دادن کارایی الگوریتم پیشنهادی در مقایسه با الگوریتم اصلی، از یک شبکه متوسط و دو شبکه بزرگ مقیاس استفاده می‌شود. نتایج این دو الگوریتم در مقابل نتایج حاصل از سه الگوریتم بر پایه مسیر دیگر به منظور مقایسه کارایی آنها برای شبکه‌های اخیر ارایه خواهند شد. این الگوریتمها شامل الگوریتمی بر پایه روش تصویر گرادیان برتسکاس، الگوریتمی بر پایه روش تصویر گرادیان روزن و یک الگوریتم فرانک- ولف بهبود یافته هستند. علاوه بر این، نوعی روش فیلتر کردن مبدا- مقصد برای افزایش سرعت الگوریتم‌های بر پایه مسیر پیشنهاد، و تاثیر زیاد آن توسط نتایج عددی نشان داده می‌شود.
- Abstract
- According to the previous studies, path-based algorithms are the most efficient methods for solving the traffic assignment problem (TAP). They iteratively decompose the problem in separate sub-problems, one for each Origin-Destination (OD) pair, and solve each of the sub-problems in the space of path flows. To store the information of the paths, they need more memory than Link or Origin based algorithms. Nevertheless, in the two past decades, researchers became more interested in them because of their quick convergence rate as well as the recent advances in computer's memory. One of the well-known path-based algorithms is the Linearization Algorithm (LA) that has been derived from the complementarity formulation of TAP. In LA the solution of each sub-problem is approximated with the solution of a sequence of Linear Complementarity Problems (LCPs), each of them is solved to some given accuracy using Lemke's method. In this thesis a new version of linearization algorithm is introduced, in which the LCPs are solved using a Gradient Projection (GP) based method to a different level of accuracy. The computational experiments on one medium and two large scale networks from the literature are also presented to evaluate the new LA against the original one. Some other existing path-based algorithms for TAP are also coded and applied on the test networks, providing insights into their performance relative to LAs. Those are an algorithm based on Bertsekas`s GP method, an algorithm based on Rosen's GP method, and an accelerated Frank-Wolfe algorithm. Moreover, an OD filtering strategy is applied to accelerate the path-based algorithms. The numerical results show that this strategy is very effective.
