[صفحه اصلی ]   [Archive] [ English ]  
:: صفحه اصلي :: درباره نشريه :: آخرين شماره :: تمام شماره‌ها :: جستجو :: ثبت نام :: ارسال مقاله :: تماس با ما ::
:: دوره 9، شماره 3 - ( 12-1398 ) ::
دوره 9 شماره 3 صفحات 145-158 برگشت به فهرست نسخه ها
مسیریابی بهینه در شبکه ی حمل و نقل درون شهری با ادغام الگوریتم های فرا ابتکاری ژنتیک (GA) و جستجوی ممنوع (TS)
ابوذر شهمرادی، سعید بهزادی*
چکیده:   (406 مشاهده)
    با توجه به گسترش شهرها و پیچیده­تر شدن شبکه­ی راه­های درون شهری به ویژه در شهرهای بزرگ، مسئله­ی مسیریابی و در واقع یافتن کوتاه­ترین مسیر تبدیل به یکی از دغدغه­های افراد در هنگام تصمیم گیری برای انتخاب مسیر در جابجایی از مبدا حرکت به یک مقصد مشخص، شده است. روشی که در این پژوهش برای حل مسئله­ی کوتاه­ترین مسیر پیشنهاد می­شود، استفاده از ترکیب الگوریتم­های فراابتکاری ژنتیک (GA) و جستجوی ممنوع (TS) می­باشد. بدین منظور پس از اعمال یک سری پیش پردازش هندسی بر روی شبکه­ی مورد نظر برای سرعت بخشیدن به روند جستجوی الگوریتم از یک محدوده­ی جستجو حول نود مبدا و مقصد استفاده می­شود. در الگوریتم پیشنهادی، تابع هزینه به صورت یک عدد مختلط تعریف می­شود که قسمت حقیقی آن نشان­دهنده­ی مجموع وزن یال­های واقعی و قسمت موهومی آن نشان­دهنده­ی تعداد یال­های مجازی و در واقع تعداد عدم اتصالات بین نود­ها در کروموزوم­های الگوریتم ژنتیک می­باشد.  همچنین در بحث اعمال جهش بر روی کروموزوم­های الگوریتم ژنتیک، از الگوریتم جستجوی ممنوع استفاده می­گردد. علت پیشنهاد این روش، جدید بودن و نیز زمان­بر بودن روش­های قطعی مثل الگوریتم دایجسترا و نیز جواب نامناسب الگوریتم ژنتیک خالص(غیر ترکیبی) از لحاظ وزن نهایی مسیر در حل مسئله­ی مسیریابی در شبکه­های واقعی بخصوص شبکه­های بزرگ می­باشد. به منظور ارزیابی کارایی الگوریتم پیشنهادی، الگوریتم بر روی یک شبکه­ی واقعی جهت­دار شامل 739 نود و 1160 یال که بخشی از شبکه­ی راه­های شهر تهران می­باشد، پیاده­سازی شد. نتایج نشان می­دهد که در الگوریتم پیشنهادی، طول مسیر تا حد ممکن به جواب حاصل از الگوریتم قطعی دایجسترا نزدیک است. این الگوریتم طول نهایی مسیر را 5 درصد بیشتر پیش بینی می­کند. اما از لحاظ سرعت اجرا به طور متوسط 12/5 برابر نسبت به الگوریتم دایجسترا سریع­تر است. در مقایسه­ با الگوریتم ژنتیک خالص نیز الگوریتم پیشنهادی از نظر طول مسیر به طور متوسط 9 درصد کوتاه­تر می­باشد و از نظر زمان اجرا سرعت الگوریتم پیشنهادی با الگوریتم ژنتیک خالص تقریبا برابر است. همچنین به لحاظ قابلیت تکرارپذیری نیز الگوریتم پیشنهادی 36/25 درصد، تکرارپذیری را نشان می­دهد.
واژه‌های کلیدی: یافتن کوتاه‌ترین مسیر، الگوریتم ژنتیک، الگوریتم جستجوی ممنوع، پیش پردازش هندسی، محدوده‌ی جستجو
متن کامل [PDF 1766 kb]   (84 دریافت)    
نوع مطالعه: پژوهشي | موضوع مقاله: سامانه های اطلاعات مکانی
ارسال پیام به نویسنده مسئول

ارسال نظر درباره این مقاله
نام کاربری یا پست الکترونیک شما:

CAPTCHA


XML   English Abstract   Print


Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

Shahmoradi A, Behzadi S. Optimum Routing in the Urban Transportation Network by Integrating Genetic Meta-heuristic (GA) and Tabu Search (Ts) Algorithms. JGST. 2020; 9 (3) :145-158
URL: http://jgst.issge.ir/article-1-862-fa.html

شهمرادی ابوذر، بهزادی سعید. مسیریابی بهینه در شبکه ی حمل و نقل درون شهری با ادغام الگوریتم های فرا ابتکاری ژنتیک (GA) و جستجوی ممنوع (TS). نشریه علمی پژوهشی علوم و فنون نقشه برداری. 1398; 9 (3) :145-158

URL: http://jgst.issge.ir/article-1-862-fa.html



دوره 9، شماره 3 - ( 12-1398 ) برگشت به فهرست نسخه ها
نشریه علمی علوم و فنون نقشه برداری Journal of Geomatics Science and Technology