مقایسه سرعت همگرایی بین الگوریتمهای تخصیص ترافیک جهات مزدوج | ||
| نشریه مهندسی عمران امیرکبیر | ||
| مقاله 9، دوره 54، شماره 6، شهریور 1401، صفحه 2219-2236 اصل مقاله (2 M) | ||
| نوع مقاله: مقاله پژوهشی | ||
| شناسه دیجیتال (DOI): 10.22060/ceej.2021.19708.7244 | ||
| نویسندگان | ||
| وحید کریمی؛ عباس بابازاده* | ||
| دانشکده مهندسی عمران، دانشگاه تهران، تهران، ایران | ||
| چکیده | ||
| مسئله تخصیص ترافیک در شبکه های حمل و نقلی تحت فروضی ساده کننده به صورت یک مسئله بهینه سازی محدب فرمولبندی میشود. برای حل این مسئله الگوریتمهای بر پایه کمان، بر پایه مسیر و بر پایه مبدا ارائه شدهاند. در این بین، الگوریتمهای بر پایه کمان به دلیل حافظه مصرفی کمتر، کاربرد بیشتری یافتهاند. الگوریتم بر پایه کمان فرانک - ولف به دلیل سادگی و نیز سرعت همگرایی زیاد آن در تکرارهای اولیه هنوز جزو محبوبترین الگوریتمهای تخصیص ترافیک محسوب میشود. ولی، این الگوریتم در نزدیکی جواب بهینه دارای همگرایی ضعیفی است، و به همین علت تاکنون پژوهشهای متعددی با هدف اصلاح جهت جستوجوی فرانک - ولف انجام شده است. الگوریتمهای جهات مزدوج مؤثرترین نوع این الگوریتمها بوده و در ضمن پیادهسازی آنها بسیار سادهتر است. این الگوریتمها شامل پارتان، فرانک - ولف مزدوج، فرانک - ولف دو مزدوج میباشند. در این مقاله مقایسههایی مستقیم از نظر زمان حل و تعداد تکرار تا رسیدن به دقتهای مختلف جواب بین این چهار الگوریتم روی شبکه بزرگ مقیاس شیکاگو و شبکه کوچک مقیاس سوفالز انجام میشود. نتایج نشان میدهند که سه الگوریتم فرانک - ولف دو مزدوج، فرانک - ولف مزدوج و پارتان، در مقایسه با الگوریتم فرانک - ولف، سرعت همگرایی به جوابی با خطای 5-10 (جواب پایدار) را برای شبکه شیکاگو به ترتیب در حدود 89، 72 و 63 درصد افزایش میدهند. در ضمن، فقط الگوریتم فرانک - ولف دو مزدوج توانایی رسیدن به خطای 6-10 را دارد. مقایسه نتایج شبکه سوفالز با نتایج شبکه شیکاگو نشان میدهد که کارایی الگوریتمهای جهات مزدوج با کاهش اندازه شبکه افزایش مییابد. | ||
| کلیدواژهها | ||
| تخصیص ترافیک؛ الگوریتمهای بر پایه کمان؛ الگوریتم فرانک - ولف؛ الگوریتم پارتان؛ الگوریتمهای فرانک - ولف مزدوج | ||
| مراجع | ||
|
| ||
|
آمار تعداد مشاهده مقاله: 1,007 تعداد دریافت فایل اصل مقاله: 1,095 |
||
| تعداد نشریات | 9 |
| تعداد شمارهها | 455 |
| تعداد مقالات | 5,771 |
| تعداد مشاهده مقاله | 8,374,537 |
| تعداد دریافت فایل اصل مقاله | 6,932,631 |