سال 1405، دوره 13، شماره 51، صفحات 36-51
مسیریاب چند مقصدی: روشی برای محاسبه کوتاهترین مسیر برای گذر یکباره از چندین نقطه بدون بازگشت به مبدا
KNO-1301-5103
نویسندگان:محمدرضا سلمانی،علیرضا محمودی فرد
کلمات کلیدی:
مسیریاب چندمقصدی، الگوریتم MDR ،OpenStreetMap ، مسئله فروشنده دورهگرد (TSP)، سرویسهای تحویل هوشمند
چکیده:یافتن کوتاهترین مسیر ممکن برای گذر از چندین نقطه بهشکلی که تنها یکبار از هر نقطه عبور کند، چالشی کلیدی در سیستمهای حملونقل هوشمند و لجستیک شهری است که میتواند کاربردهای زیادی در حوزههای مختلف از زندگی روزمره گرفته تا سرویسهای تحویل آنلاین کالا داشته باشد. روشهای موجود مانند مسئله فروشنده دورهگرد (TSP) با وجود کارایی نظری، بهدلیل الزام بازگشت به مبدا و عدم پشتیبانی از دادههای پویا، کارایی محدودی در کاربردهای واقعی دارند. این مقاله الگوریتم مسیریاب چند مقصدی (MDR) را ارائه میکند که با استفاده از دادههای زنده OpenStreetMap و ترکیب آن با بهینهسازی مبتنی بر گرافها، این مسئله را به صورت کاربردی و با دقت صددرصدی حل کرده است. آزمایشهای انجامشده روی دادههای واقعی در کلانشهر تهران نشاندهنده کاهش ۱۶ درصدی مسافت و ۷ درصدی زمان محاسبات نسبت به روشهای پایه است. این الگوریتم، بهویژه در زمینه سرویسهای تحویل مدرن و برنامهریزی شهری، گزینهای عملی و کارآمد به شمار میآید.