عنوان پایان‌نامه
الگوریتم خطی سازی مبتنی بر مسیر برای مسائل تخصیص ترافیک چند کلاسی
- رشته تحصیلی
- مهندسی عمران - راه و ترابری
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس یک فنی شماره ثبت: 2048;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 69157
- تاریخ دفاع
- ۲۹ آذر ۱۳۹۳
- دانشجو
- امیرحسین فانی
- استاد راهنما
- عباس بابازاده
- چکیده
- مسئله¬ی تخمین جریان ترافیک روی کمان¬های یک شبکه حمل و نقل به مسئله تخصیص ترافیک معروف است. مسئله تخصیص ترافیک در دو حالت یک کلاسی یا چندکلاسی بررسی شده است. در تخصیص ترافیک یک کلاسی، تمام استفاده¬کنندگان زمان سفرهای یکسانی را روی کمان¬های شبکه تجربه می کنند. ولی، در تخصیص ترافیک چندکلاسی، کلاس¬های مختلف استفاده¬کنندگان دارای زمان سفرهای متفاوتی روی کمانهای شبکه هستند. یک حالت خاص از تخصیص چندکلاسی زمانی رخ می¬دهد که استفاده¬کنندگان مربوط به هر کلاس فقط می‌توانند روی زیرشبکهای خاص از شبکه اصلی حرکت کنند (مانند ماشین های فاقد مجوز ورود به طرح ترافیک در شهر تهران). در این پایان¬نامه، با ایجاد تغییراتی در الگوریتم‌های استاندارد فرانک-ولف ، فرانک-ولف بر پایه مبدأ-مقصد و خطی¬سازی- تصویر گرادیان ، نسخه چند کلاسی این الگوریتمها ارایه میشود. سپس، تخصیص چندکلاسی در حالت خاص ذکر شده با استفاده از این الگوریتمها برای شبکه کوچک سوفالز و شبکه¬ بزرگ تهران حل نتایج آنها ارایه و مقایسه می‌شوند. اگرچه روش¬های استاندارد تخصیص ترافیک (در شرایط معمول) جوابی یکتا بر حسب جریان در کمان¬های شبکه می¬یابند، جواب آنها بر حسب جریان در مسیرها یکتا نیست. به علاوه، روش¬های تخصیص ترافیک چند کلاسی حتی نمی¬توانند جوابی یگانه بر حسب جریان کلاس¬ها در کمان¬های شبکه به دست آورند. برای برقراری یکتایی جریان¬ها یک شرط اضافی مورد نیاز است که شرط تناسب جریان نامیده شده است. بر اساس مراجع موجود، الگوریتم¬های بر پایه کمان و بر پایه مبدأ شرط تناسب را تا حدبه خوبی برقرار می‌کنند، ولی الگوریتم¬های بر پایه مسیر قادر به این کار نیستند. در این پایان¬نامه یک الگوریتم¬ بر پایه مسیر جدید معرفی میشود که شرط تناسب جریان را تا حد بسیار خوبی برقرار می‌سازد. این الگوریتم، که فرانک-ولف بر پایه مبدا نامیده خواهد شد، مشابه الگوریتم است، با این تفاوت که در آن مسئله اصلی به جای زوج¬های مبدا-مقصد روی مبادی تجزیه و حل میشود. همچنین، معیاری تحت عنوان معیار تناسب تعریف می¬شود و به وسیله آن موازین برقرار شدن شرط تناسب توسط این دو الگوریتم و نیز الگوریتم برای شبکه‌های سوفالز و تهران مقایسه می‌شوند. این پایان نامه، در نهایت، نحوه برقرار سازی شرط تناسب در الگوریتم‌های خطی سازی از جمله را به عنوان موضوعی باز برای مطالعات آتی معرفی می‌کند.
- Abstract
- Traffic assignment Problem (TAP) is studied in case of single-class or multi-class assignment. In the single-class equilibrium assignment, all travellers on a given link experience the same cost. The multi-class user equilibrium assignment problem arises if different categories of travelers, experience different cost functions. An interesting special case is happened when the different user classes perceive the same costs, but each can access only a class specific subnetwork. In this thesis, this special case of multi-class assignment is solved by Frank-Wolfe (FW) algorithm, origin-destination based Frank-Wolfe (ODBFW) algorithm and gradient projection based linearization (GPL) algorithm. Then, the results of proposed algorithms are presented for a small-scale and a large-scale network. Although the total flows on links of the urban road network are uniquely determined by the standard method for predicting traffic flows, the flows on paths and multi-class link flows are not. An additional assumption, the condition of proportionality, is required to determine these flows uniquely. On the basis of references, link based algorithms and origin based algorithms are tended to satisfy approximately the proportionality condition but path based algorithms are produced solutions that violate the proportionality. In this thesis, a new path based algorithm is introduced which approximately satisfy the proportionality condition. This algorithm which is named origin based Frank-Wolfe algorithm (OBFW), is similar to ODBFW algorithm with the different that the main problem is decomposed into origins instead of origin destinations. Also, a proportionality criteria is defined and with the help of this criteria, the condition of proportionality for FW algorithm, ODBFW algorithm and OBFW algorithm are evaluated and compared on Sioux falls and Tehran network.
