كنفرانس بين المللی مهندسی صنايع و سيستم ها

صفحه اصلی / دهمین كنفرانس بين المللی مهندسی صنايع و سيستم ها

برنامه ریزی مسیر از نوع زمانی – مکانیِ درب تا درب در شبکه ی حمل‌ونقل بین‌شهری چندوجهی با استفاده از الگوریتم بهبودیافته انتشار موج در دو شهر ایران

نویسندگان :

محمد باقریان¹ بهنام باقریان² نسیم نهاوندی³ مرتضی باقری⁴

1- دانشگاه تربیت مدرس 2- دانشگاه علم و صنعت ایران 3- دانشگاه تربیت مدرس 4- دانشگاه علم و صنعت

کلمات کلیدی :

شبکه ی حمل و نقل عمومی،مسیر چندوجهی،مسیر مکانی – زمانی،الگوریتم انتشار موج بهبودیافته،الگوریتم دیکسترا،الگوریتم IRSA

چکیده :

مهمترین هدف این تحقیق حل مسئله ی پیشنهاد مسیرهای زمانی – مکانی درب تا درب در یک شبکه ی حملونقل چندوجهی بینشهری است حالتهای موجودی که در مسیریابی وجود دارد شامل راهآهن، مترو، اتوبوس، اتوبوس سریعالسیر و پیادهروی میشود. از نظر مدلسازی ریاضی، مدل بازسازی شده برنامهریزی مسیر زمانی – مکانی چندین محدودیت را مد نظر قرار میدهد. این مدل با مسیر در نظریه گراف سنتی و شبکهی جادهای تفاوت بسیار زیادی دارد. برای دستیابی به K کوتاهترین مسیر در دو حالت مختلف، الگوریتم بهبودیافتهی انتشار موج معرفی شده است )که از این پس IRSA نامیده میشود(. این الگوریتم که از پدیدهی انتشار موج ایده گرفته، میتواند تنها با یک تکرار مسیرهای بهینه ی سراسری را پیدا کند. برای تسریع فرایند محاسبه یک روش برای کاهش فضای جستجو به کار گرفته شده است . در این تحقیق، از طریق مقایسه ی مدل و الگوریتم پیشنهادی با حلکننده ی Gurobi و الگوریتم دیکسترا در شبکه ای کوچک، قابلیت اجرا و کارایی روش خود را ثابت میکنیم. نتایج آزمایش با حل مسئله ی مسیریابی درب تا درب ارزیابی شده است. نتایج حاصله نشان میدهد که روش پیشنهادی میتواند K کوتاهترین مسیر را با محدودیتهای تعیینشده در زمان محاسباتی قابل قبولی پیدا کند. نتایج نشان میدهند که روش افزایش سرعت منجر به بهبودی چشمگیر در کارایی حل مسئله میشود و در عین حال تلاش میکند تا بهینه بودن مسیر را تضمین کند. این روش میتواند زمان CPU را برای زوج مبدأ و مقصدهای مورد آزمایش بین 51 تا 92 درصد کاهش دهد.