رویکردی جدید برای حل کوتاهترین مسیر در شبکه های شهری بر اساس الگوریتم های تکاملی
سال انتشار: 1401
نوع سند: مقاله ژورنالی
زبان: فارسی
مشاهده: 137
فایل این مقاله در 10 صفحه با فرمت PDF قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
JR_JGCE-1-1_002
تاریخ نمایه سازی: 10 مهر 1402
چکیده مقاله:
پیشینه و اهداف: امروزه، مدیریت شهری به عنوان یکی از مهم ترین مسائل تصمیم گیران و مدیران در حوزههای شهری است. مسئله ی یافتن کوتاه ترین مسیر، به عنوان یکی از مسائل مهم در حوزه ی مدیریت شهری به منظور کاهش زمان سفر بین دو نقطه ی حیاتی، همواره مورد توجه بسیاری از حوزههای تحقیقاتی از قبیل مدیریت شهری، حمل و نقل، ارتباطات و غیره بوده است. در طول دهه های گذشته، الگوریتم ژنتیک در حل مسائل پیچیده ی بهینه سازی چند هدفه، به خوبی عمل کرده است، اما بسیاری از الگوریتمهای ژنتیک، تنها برای یافتن مسیر بهینه در شبکههای محلی، مناسب هستند. در این شبکهها، در صورتی که تعداد نقاط افزایش یابد، الگوریتمهای ارائه شده کارآیی خود را نخواهند داشت. هدف از این تحقیق، یافتن مسیری در شبکه ی خیابانهای شهر تهران میباشد که کمترین زمان، مسافت و هزینه را داشته باشد. بنابراین، یک روش جدید برای حل مسئله ی مسیریابی بر مبنای الگوریتم ژنتیک، با این فرض که تمام خطوط موجود در شبکه دارای وزنهای مثبت میباشند، پیشنهاد میگردد.روش ها : ویژگی الگوریتم پیشنهادی، متغیر بودن عملگرهای الگوریتم ژنتیک می باشد که متناسب با ساختار شبکه، تعریف می گردد. بر همین اساس، عملگر جهش در الگوریتم ژنتیک بر اساس فضای مورد مطالعه و فاصله ی بین نقاط شروع و پایان، تعریف میگردد. برای حل مسئله، از کدگذاری اعداد صحیح استفاده میشود و لذا، نقاط موجود در این گراف با استفاده از اعداد صحیح، نام گذاری شده و هر فرد در جمعیت به عنوان یک جواب برای حل مسئله، در نظر گرفته میشود. اندازه ی جمعیت، بسته به تعداد گرههای موجود در گراف و طول هرکروموزوم دارد. طول رشتههای انتخاب شده، حداکثر برابر با تعداد گرههای موجود در شبکه، در نظر گرفته میشود، زیرا این احتمال وجود دارد که بهترین مسیر، مسیری باشد که از تمام گرهها عبور میکند. در پایان، این الگوریتم بر روی شبکهی مورد مطالعه که یک گراف مسطح میباشد، پیادهسازی میشود. دقت روش پیشنهادی نسبت به روش متداول، در سه جفت نقطه، مورد ارزیابی قرار گرفته است.یافته ها: با توجه به این که هدف از حل مسئله، یافتن مسیری بود که کمترین وزن را داشته باشد، در الگوریتم پیشنهادی یک عملگر ترکیب و سه عملگر جهش، ارائه گردید. این، در حالی است که در الگوریتمهای ژنتیک رایج، تنها از یک عملگر جهش و ترکیب، استفاده شده است. در این الگوریتم، نحوه ی استفاده از عملگرهای جهش، به ساختار شبکه و فاصله ی بین نقطه ی شروع و پایان، بستگی دارد. استفاده از الگوریتم ژنتیک پیشنهادی، نسبت به الگوریتم ژنتیک رایج، با ۱۶% بهبود عملکرد همراه بوده است که نشان میدهد الگوریتم ژنتیک پیشنهادی، سریع تر به جواب مسئله میرسد. همان طور که در شکل ۴ نشان داده شده است بهترین مسیر، مسیری است که مقدار تابع برازندگی آن به یک، نزدیکتر باشد. نتایج حاصل از مقایسه ی روش پیشنهادی با روش های متداول، ۱۶ درصد سرعت بالاتر را نشان میدهد.نتیجه گیری: با توجه به این که فرض اولیه ی این تحقیق، مثبت بودن وزن تمام خطوط موجود در شبکه بوده است، عملگر جهش در الگوریتم ژنتیک، بر اساس فضای مورد مطالعه و فاصله ی بین نقاط شروع و پایان، تعریف شد. نتایج نشان داد که در صورت وجود فضای جستجوی کوچک، نقاط کمتری مورد نیاز است و به منظور تولید جمعیت اولیه، گرههایی که در کنار هم قرار دارند و به هم نزدیکتر هستند، باید انتخاب شوند. بدین ترتیب، مقدار تابع برازندگی افراد موجود در جمعیت اولیه، افزایش یافته و جوابها به واقعیت، نزدیکتر میشود. برای تحقیقات آتی، پیشنهاد میگردد که به منظور تولید جمعیت اولیه، نقاط بین نقطه ی شروع و پایان انتخاب گردد و همچنین، نقاط انتخاب شده در نزدیکی خط واصل بین نقطه ی شروع و پایان باشد، زیرا هنگامی که وزن یالهای شبکه، فاصله ی بین نقاط باشد، بهترین مسیر در فضای بین نقطه ی شروع و پایان قرار دارد. همچنین، پیشنهاد میشود که عملکرد شبکه با چندین عملگر ترکیب نیز، مورد ارزیابی قرار گیرد.
کلیدواژه ها:
نویسندگان
سعید بهزادی
گروه مهندسی نقشه برداری، دانشکده ی عمران، دانشگاه تربیت دبیر شهید رجائی، تهران، ایران
مصطفی آدرسی
گروه مهندسی ژئوتکنیک و آب، دانشکدهی عمران، دانشگاه تربیت دبیر شهید رجائی، تهران، ایران
مسعود شیرازیان
گروه مهندسی نقشه برداری، دانشکده ی عمران، دانشگاه تربیت دبیر شهید رجائی، تهران، ایران
مراجع و منابع این مقاله:
لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :