رویکردی جدید برای حل کوتاهترین مسیر در شبکه های شهری بر اساس الگوریتم های تکاملی

امروزه، مدیریت شهری به عنوان یکی از مهم ترین مسایل تصمیم گیران و مدیران در حوزه های شهری است. مسیله ی یافتن کوتاه ترین مسیر، به عنوان یکی از مسایل مهم در حوزه ی مدیریت شهری به منظور کاهش زمان سفر بین دو نقطه ی حیاتی، همواره مورد توجه بسیاری از حوزه های تحقیقاتی از قبیل مدیریت شهری، حمل و نقل، ارتباطات و غیره بوده است. در طول دهه های گذشته، الگوریتم ژنتیک در حل مسایل پیچیده ی بهینه سازی چند هدفه، به خوبی عمل کرده است، اما بسیاری از الگوریتم های ژنتیک، تنها برای یافتن مسیر بهینه در شبکه های محلی، مناسب هستند. در این شبکه ها، در صورتی که تعداد نقاط افزایش یابد، الگوریتم های ارایه شده کارآیی خود را نخواهند داشت. هدف از این تحقیق، یافتن مسیری در شبکه ی خیابان های شهر تهران می باشد که کمترین زمان، مسافت و هزینه را داشته باشد. بنابراین، یک روش جدید برای حل مسیله ی مسیریابی بر مبنای الگوریتم ژنتیک، با این فرض که تمام خطوط موجود در شبکه دارای وزن های مثبت می باشند، پیشنهاد می گردد.

ویژگی الگوریتم پیشنهادی، متغیر بودن عملگرهای الگوریتم ژنتیک می باشد که متناسب با ساختار شبکه، تعریف می گردد. بر همین اساس، عملگر جهش در الگوریتم ژنتیک بر اساس فضای مورد مطالعه و فاصله ی بین نقاط شروع و پایان، تعریف می گردد. برای حل مسیله، از کدگذاری اعداد صحیح استفاده می شود و لذا، نقاط موجود در این گراف با استفاده از اعداد صحیح، نام گذاری شده و هر فرد در جمعیت به عنوان یک جواب برای حل مسیله، در نظر گرفته می شود. اندازه ی جمعیت، بسته به تعداد گره های موجود در گراف و طول هرکروموزوم دارد. طول رشته های انتخاب شده، حداکثر برابر با تعداد گره های موجود در شبکه، در نظر گرفته می شود، زیرا این احتمال وجود دارد که بهترین مسیر، مسیری باشد که از تمام گره ها عبور می کند. در پایان، این الگوریتم بر روی شبکه‎ی مورد مطالعه که یک گراف مسطح می باشد، پیاده‎سازی می شود. دقت روش پیشنهادی نسبت به روش متداول، در سه جفت نقطه، مورد ارزیابی قرار گرفته است.

با توجه به این که هدف از حل مسیله، یافتن مسیری بود که کمترین وزن را داشته باشد، در الگوریتم پیشنهادی یک عملگر ترکیب و سه عملگر جهش، ارایه گردید. این، در حالی است که در الگوریتم های ژنتیک رایج، تنها از یک عملگر جهش و ترکیب، استفاده شده است. در این الگوریتم، نحوه ی استفاده از عملگرهای جهش، به ساختار شبکه و فاصله ی بین نقطه ی شروع و پایان، بستگی دارد. استفاده از الگوریتم ژنتیک پیشنهادی، نسبت به الگوریتم ژنتیک رایج، با 16% بهبود عملکرد همراه بوده است که نشان می دهد الگوریتم ژنتیک پیشنهادی، سریع تر به جواب مسیله می رسد. همان طور که در شکل 4 نشان داده شده است بهترین مسیر، مسیری است که مقدار تابع برازندگی آن به یک، نزدیک تر باشد. نتایج حاصل از مقایسه ی روش پیشنهادی با روش های متداول، 16 درصد سرعت بالاتر را نشان می دهد.

با توجه به این که فرض اولیه ی این تحقیق، مثبت بودن وزن تمام خطوط موجود در شبکه بوده است، عملگر جهش در الگوریتم ژنتیک، بر اساس فضای مورد مطالعه و فاصله ی بین نقاط شروع و پایان، تعریف شد. نتایج نشان داد که در صورت وجود فضای جستجوی کوچک، نقاط کمتری مورد نیاز است و به منظور تولید جمعیت اولیه، گره هایی که در کنار هم قرار دارند و به هم نزدیک تر هستند، باید انتخاب شوند. بدین ترتیب، مقدار تابع برازندگی افراد موجود در جمعیت اولیه، افزایش یافته و جواب ها به واقعیت، نزدیک تر می شود. برای تحقیقات آتی، پیشنهاد می گردد که به منظور تولید جمعیت اولیه، نقاط بین نقطه ی شروع و پایان انتخاب گردد و همچنین، نقاط انتخاب شده در نزدیکی خط واصل بین نقطه ی شروع و پایان باشد، زیرا هنگامی که وزن یال های شبکه، فاصله ی بین نقاط باشد، بهترین مسیر در فضای بین نقطه ی شروع و پایان قرار دارد. همچنین، پیشنهاد می شود که عملکرد شبکه با چندین عملگر ترکیب نیز، مورد ارزیابی قرار گیرد.