بخشی از مقاله
خلاصه
مسألهی مسیریابی شبکهی حملونقل همگانی یک مسألهی NP-hard است که به ساخت شبکهی مسیرهای حملونقل همگانی با توجه به قیدهای چندگانهی موجود برای شبکه میپردازد. موضوع چالشبرانگیز در این مسأله وجود فضای جستجوی گستردهی آن و مجموعه مسیرهایی در شبکه است که به دلیل برآورده نکردن شرایط محدودیتهای مسأله به عنوان جوابی غیرقابلقبول و ناممکن تلقی میشوند.
ذات این مسأله به گونهای است که با افزایش ابعاد آن زمان حل محاسبات بسیار افزایش مییابد از این رو الگوریتمهای فراابتکاری روش حلی مناسب محسوب میشوند. در این مطالعه با دو هدف کاهش مجموع زمان سفر مسافران و مجموع تعداد انتقالها برای کل تقاضای شبکه به پیدا کردن مسیرهای بهینه در شبکه پرداخته شد.
به منظور حل مسأله، از الگوریتم جستجوی فاخته بر روی شبکهی مندل استفاده و به پیدا کردن مجموعهی مسیرهای بهینه در شرایط مختلف پرداخته شد. نتایج به دست آمده در این مطالعه با نتایج مشابه در مطالعات پیشین با استفاده از مجموعهای از پارامترها مورد بررسی و مقایسه قرار گرفتند. نتیجهی این مقایسه حاکی از کارایی مناسب روش این الگوریتم در حل مسألهی مسیریابی شبکهی حملونقل همگانی بود.
.1 مقدمه
حمل و نقل همگانی به عنوان یکی از بخشهای اساسی حملونقل شهری همواره راهحلی مؤثر برای کاهش آلودگی هوا، کاهش مصرف انرژی، افزایش میزان جابهجایی کم کردن تراکم ترافیک و داشتن الگوهای توسعهی شهری منطقی محسوب شده است.
وسایل نقلیهی شخصی به دلیل داشتن مزایای خاص خود اولین انتخاب شهروندان برای سفرهای درونشهری هستند. شهروندان برای سفر با اتومبیل شخصی منتظر رسیدن وسیلهی نقلیه برای شروع سفر خود نمیمانند. در اکثر موارد شبکههای مربوط به وسایل نقیلهی شخصی نسبت به شبکههای حملونقل همگانی بیشتر توسعهیافتهاند در نتیجه افراد فاصلههای کمتری را تا رسیدن به مقصد پیادهروی میکنند. از طرف دیگر آنها هنگام سفر با اتومبیل شخصی احساس راحتی بیشتری را نسبت به دیگر مدهای حملونقل شهری تجربه میکنند. بنابراین تا زمانی که سیستم حملونقل همگانی کارامد، راحت و ارزان وجود نداشته باشد، نمیتوان از شهروندان انتظار داشت که به جای خودروی شخصی از حملونقل همگانی استفاده کنند.
اتوبوس شهری به دلیل انعطافپذیری و هزینهی اولیهی پایین همواره مورد توجه تصمیمگیران بخش حملونقل همگانی بوده و قسمت عمدهای از یک سیستم حملونقل همگانی را در اکثر شهرها تشکیل میدهد. مهمترین ویژگیهای نشاندهندهی کیفیت خدمتدهی یک سیستم اتوبوس شهری کم بودن زمان انتظار در ایستگاه و زمان سفر درون اتوبوس برای مسافران و پرهیز از انتقال * - عوض کردن مسیر - در طی سفر تا رسیدن به مقصد است. مجموع این عوامل موجب بهبود مطلوبیت این سیستم از نظر مسافران میشود که این موضوع تنها با طراحی مناسب مسیرها در شبکه حاصل میشود.
در مطالعات گذشته از الگوریتمهای فراابتکاری برای حل این مسأله به عنوان روش حلی مناسب استفاده شده است. یکی از ویژگیهای اصلی این روشها کاربرد آنها در مسائل مختلف بهینهسازی با قیدها و توابع متفاوت است. در این مطالعه از الگوریتم جستجوی فاخته به عنوان یکی از الگوریتمهای فراابتکاری که در سالهای اخیر ارائه شده است استفاده شد. این الگوریتم در سال 2009 توسط یانگ و دب[1] معرفی و از زندگی نوعی پرنده به نام فاخته الهام گرفته شده است. بر اساس مطالعات انجام شده برروی ادبیات موضوع میتوان گفت که الگوریتم جستجوی فاخته، به عنوان یک روش حل، در این حوزه مورد استفاده قرار نگرفته است و انگیزهی اصلی انجام این مطالعه بررسی کارامدی این الگوریتم در یافتن مسیرهای یک شبکهی حملونقل همگانی بهینه بود.
.2 پیشینهی تحقیق
برنامهریزان حوزهی حملونقل همگانی در ابتدا با تکیه بر تجربهی خود و با استفاده از برخی راهنماها و دستورالعملها به تعیین مسیرهای بهینه برای شبکه - مسألهی مسیریابی شبکهی حملونقل همگانی - - UTRP - میپرداختند .[2] اما این روش برنامهریزی و طراحی در مورد شبکههای با ابعاد بزرگ که تعداد زیادی از ناوگان را نیز در خود جای میداد کارامد نبود .
تا قبل از سال 1979 تعداد کمی از مطالعات در این حوزه انجام شده بود که میتوان به مطالعهی لمپکین و سالمان [4] و سیلمن و همکاران اشاره کرد.یکی از مطالعات مهم در این حوزه مطالعهی مندل [6] بود که در آن روشی دو مرحلهای را برای طراحی مسیرهای بهینه ارائه داد. در مرحله اول مطالعهی مندل مجموعهای از مسیرهای شدنی ساخته شد و سپس با اعمال روشی ابتکاری کیفیت مسیرهای اولیه بهبود یافت. تنها فاکتور برای برآورد کیفیت مسیرها زمان سفر داخل وسیله نقلیه بود.
مندل در مطالعهی خود شبکهای که شامل 15 شهر از کشور سوئیس بود را انتخاب کرده بود و این شبکه به طور گسترده در مطالعات محققان بعدی به عنوان یک شبکه مبنا مورد استفاده قرار گرفت. پس از آن استفاده از روشهای ابتکاری و فراابتکاری برای حل مسألهی مسیریابی حملونقل همگانی از جمله الگوریتم ژنتیک، تبرید شبیهسازی شده** فراگیر شد. در میان روشهای فراابتکاری الگوریتم ژنتیک متداولترین روش برای حل این مسأله بوده است.
پتنایک و همکاران [7]، بیلی و همکاران[8]سوزتو، و وُو [9] از الگوریتم ژنتیک یا انواع بهبود یافتهی آن استفاده کردند. چاکرابورتی و دویدی [10] مسألهای طراحی شبکهی اتوبوس شهری را به دو بخش اصلی مسیریابی بهینه در شبکه و تعیین برنامهی زمانی تقسیم کردند. آنها در مطالعهی اول خود با استفاده از روشی تکراری که شامل سه مرحله بود ابتدا به ایجاد مجموعهای از شبکههای شدنی پرداختند. سپس در مرحلهی ارزیابی برازندگی هر یک از شبکهی مسیرها تعیین و در مرحلهی سوم از الگوریتم ژنتیک به منظور بهبود شبکهی مسیرها و ایجاد شبکههای جدید استفاده شد. در مطالعهای دیگر توسط چاکرابورتی هر دو مسألهی مسیریابی و زمانبندی با اعمال بر روی شبکهی مندل مورد بررسی قرار گرفت.
باج و محمسانی [12] روشی بر پایه هوش مصنوعی ارائه دادند که از سه مؤلفه اصلی تشکیل میشد. اولین قسمت آن الگوریتم تولید مسیر بود که با توجه به تعادلی بین هزینههای مسافران و سرویسدهنده مسیرهای مختلفی را ایجاد میکرد. قسمت دوم روشی برای تحلیل مسیرهای شبکه بود که به ارزیابی مسیرهای شبکه میپرداخت. قسمت سوم شامل الگوریتم بهبود مسیر بود که مسیرهای اولیه را بهبود میبخشید و به این ترتیب مسیرهای شدنی به دست میآمدند.
الگوریتم تبرید شبیهسازی شده نیز روشی پر کاربرد در حل این مسأله محسوب میشود، که از جمله مطالعات مهم انجامشده با این روش میتوان به ژائو و ژنگ[13]، فن و مکمهل [14] و فن و مامفورد [2] اشاره کرد.
.3 بیان مسأله
در مطالعات گذشته انواع مختلفی از UTRP با توجه به معیارهای مختلف برای یک شبکهی بهینه تحت محدودیتهای مشخصی ارائه شده است. به طور کلی معیارهایی که توسط اکثر محققین برای مجموعهای از مسیرهای مطلوب پذیرفتهشدهاند به شرح زیر است:
· تمام تقاضای سفر پوشش داده شود
· درصد زیای از سفرها به صورت مستقیم و بدون انجام انتقال انجام شود
· متوسط زمان سفر برای مسافران تا حد امکان کاهش یابد
بنابراین از یک مجموعه مسیر مطلوب برای اتوبوسها انتظار میرود که زمان سفر - فاصله طی شده - و تعداد انتقالها را تا حد امکان کاهش دهد. مجموعهی مسیرهای اتوبوس استخراجشده از شبکهی اصلی را میتوان شبکهای جداگانه و مختص اتوبوس در نظر گرفت چرا که ممکن است برخی از اتصال*ها از شبکهی اصلی در شبکهی اتوبوس ایجادشده وجود نداشته باشند. بنابراین برای پیدا کردن کوتاهترین مسیر بین هر مبدأ و مقصد نیاز است که محاسبات بر اساس شبکهی جدید ساختهشده انجام شود و ماتریس همسایگی جدیدی برای هر مبدأ و مقصد تشکیل شود.
1-3 تابع هدف
تابع هدف این مطالعه مجموع وزندار از دو مؤلفهی: - 1 مجموع فاصلهی طی شده توسط تمام مسافران - 2 مجموع انتقالهای کل تقاضای سفر است که از مرجع[2] استخراج شده است.
